AMDG Steven Ross wrote:
I've finished optimizing and testing Spreadsort (integer_sort/float_sort/string_sort), a hybrid radix-based/comparison-based algorithm. It is now available from: http://sourceforge.net/projects/spreadsort I have tested it using an (included) automated test script on Mac OSX and Cygwin with a range of different distributions of random data on 20MB data sets. It is roughly twice as fast as std::sort on average across all three data types and many distributions, with the main exception of a 28X average performance improvement for float_sort on Cygwin. Average runtime seems to be proportional to roughly theta(n*square_root(log(n))); worst-case is more complicated but better than O(nlog(n)), due to the radix-based portion. Test it and see for yourself how it performs on your system. At this point I'm looking for suggestions on formatting it to submit as a Boost.Algorithm.Sorting namespace. I would appreciate comments that aid that process. I am also interested in knowing whether people would like a parallel_sort integrated in Boost.Algorithm.Sorting with Spreadsort
Well, the normal directory structure for boost would be boost/ algorithm sorting/ spreadsort.hpp libs/ algorithm/ sorting/ test/ Jamfile.v2 ... doc/ ... index.html BTW, the code doesn't compile with msvc 9.0 or gcc 4.3.0. error logs attached. In Christ, Steven Watanabe ...found 64 targets... ...updating 22 targets... gcc.compile.c++ bin\gcc-4.3.0\release\sample.o samples\sample.cpp: In function 'int main(int, const char**)': samples\sample.cpp:19: error: 'strcmp' was not declared in this scope "g++-4.3.0" -ftemplate-depth-128 -O3 -finline-functions -Wno-inline -Wall -DNDEBUG -I"." -c -o "bin\gcc-4.3.0\release\sample.o" "samples\sample.cpp" ...failed gcc.compile.c++ bin\gcc-4.3.0\release\sample.o... ...skipped <pbin\gcc-4.3.0\release>spreadsort.exe for lack of <pbin\gcc-4.3.0\release>sample.o... gcc.compile.c++ bin\gcc-4.3.0\release\rightshiftsample.o samples\rightshiftsample.cpp: In function 'int main(int, const char**)': samples\rightshiftsample.cpp:22: error: 'strcmp' was not declared in this scope "g++-4.3.0" -ftemplate-depth-128 -O3 -finline-functions -Wno-inline -Wall -DNDEBUG -I"." -c -o "bin\gcc-4.3.0\release\rightshiftsample.o" "samples\rightshiftsample.cpp" ...failed gcc.compile.c++ bin\gcc-4.3.0\release\rightshiftsample.o... ...skipped <pbin\gcc-4.3.0\release>rightshift.exe for lack of <pbin\gcc-4.3.0\release>rightshiftsample.o... gcc.compile.c++ bin\gcc-4.3.0\release\floatsample.o samples\floatsample.cpp: In function 'int main(int, const char**)': samples\floatsample.cpp:21: error: 'strcmp' was not declared in this scope samples\/../spreadsort.hpp: In function 'cast_type CastFloatIter(const RandomAccessIter&) [with cast_type = int, RandomAccessIter = __gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >]': samples\/../spreadsort.hpp:705: instantiated from 'void FloatSortRec(RandomAccessIter, RandomAccessIter, std::vector<RandomAccessIter, std::allocator<_Tp1> >&, unsigned int, std::vector<unsigned int, std::allocator<unsigned int> >&) [with RandomAccessIter = __gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >, div_type = int, data_type = float]' samples\/../spreadsort.hpp:945: instantiated from 'void FloatSort(RandomAccessIter, RandomAccessIter, cast_type, data_type) [with RandomAccessIter = __gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >, cast_type = int, data_type = float]' samples\/../spreadsort.hpp:974: instantiated from 'void float_sort_cast(RandomAccessIter, RandomAccessIter, cast_type) [with RandomAccessIter = __gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >, cast_type = int]' samples\/../spreadsort.hpp:983: instantiated from 'void float_sort_cast_to_int(RandomAccessIter, RandomAccessIter) [with RandomAccessIter = __gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >]' samples\floatsample.cpp:62: instantiated from here samples\/../spreadsort.hpp:424: error: 'memcpy' was not declared in this scope "g++-4.3.0" -ftemplate-depth-128 -O3 -finline-functions -Wno-inline -Wall -DNDEBUG -I"." -c -o "bin\gcc-4.3.0\release\floatsample.o" "samples\floatsample.cpp" ...failed gcc.compile.c++ bin\gcc-4.3.0\release\floatsample.o... ...skipped <pbin\gcc-4.3.0\release>floatsort.exe for lack of <pbin\gcc-4.3.0\release>floatsample.o... gcc.compile.c++ bin\gcc-4.3.0\release\shiftfloatsample.o samples\shiftfloatsample.cpp: In function 'int main(int, const char**)': samples\shiftfloatsample.cpp:30: error: 'strcmp' was not declared in this scope samples\/../spreadsort.hpp: In function 'cast_type MemCast(const DATA_TYPE&) [with DATA_TYPE = float, cast_type = int]': samples\shiftfloatsample.cpp:17: instantiated from here samples\/../spreadsort.hpp:434: error: 'memcpy' was not declared in this scope "g++-4.3.0" -ftemplate-depth-128 -O3 -finline-functions -Wno-inline -Wall -DNDEBUG -I"." -c -o "bin\gcc-4.3.0\release\shiftfloatsample.o" "samples\shiftfloatsample.cpp" ...failed gcc.compile.c++ bin\gcc-4.3.0\release\shiftfloatsample.o... ...skipped <pbin\gcc-4.3.0\release>shiftfloatsort.exe for lack of <pbin\gcc-4.3.0\release>shiftfloatsample.o... gcc.compile.c++ bin\gcc-4.3.0\release\floatfunctorsample.o samples\floatfunctorsample.cpp: In function 'int main(int, const char**)': samples\floatfunctorsample.cpp:30: error: 'strcmp' was not declared in this scope samples\/../spreadsort.hpp: In function 'cast_type MemCast(const DATA_TYPE&) [with DATA_TYPE = float, cast_type = int]': samples\floatfunctorsample.cpp:17: instantiated from here samples\/../spreadsort.hpp:434: error: 'memcpy' was not declared in this scope "g++-4.3.0" -ftemplate-depth-128 -O3 -finline-functions -Wno-inline -Wall -DNDEBUG -I"." -c -o "bin\gcc-4.3.0\release\floatfunctorsample.o" "samples\floatfunctorsample.cpp" ...failed gcc.compile.c++ bin\gcc-4.3.0\release\floatfunctorsample.o... ...skipped <pbin\gcc-4.3.0\release>floatfunctorsort.exe for lack of <pbin\gcc-4.3.0\release>floatfunctorsample.o... gcc.compile.c++ bin\gcc-4.3.0\release\stringsample.o samples\stringsample.cpp: In function 'int main(int, const char**)': samples\stringsample.cpp:21: error: 'strcmp' was not declared in this scope "g++-4.3.0" -ftemplate-depth-128 -O3 -finline-functions -Wno-inline -Wall -DNDEBUG -I"." -c -o "bin\gcc-4.3.0\release\stringsample.o" "samples\stringsample.cpp" ...failed gcc.compile.c++ bin\gcc-4.3.0\release\stringsample.o... ...skipped <pbin\gcc-4.3.0\release>stringsort.exe for lack of <pbin\gcc-4.3.0\release>stringsample.o... gcc.compile.c++ bin\gcc-4.3.0\release\reversestringsample.o samples\reversestringsample.cpp: In function 'int main(int, const char**)': samples\reversestringsample.cpp:23: error: 'strcmp' was not declared in this scope "g++-4.3.0" -ftemplate-depth-128 -O3 -finline-functions -Wno-inline -Wall -DNDEBUG -I"." -c -o "bin\gcc-4.3.0\release\reversestringsample.o" "samples\reversestringsample.cpp" ...failed gcc.compile.c++ bin\gcc-4.3.0\release\reversestringsample.o... ...skipped <pbin\gcc-4.3.0\release>reversestringsort.exe for lack of <pbin\gcc-4.3.0\release>reversestringsample.o... gcc.compile.c++ bin\gcc-4.3.0\release\charstringsample.o samples\charstringsample.cpp: In function 'int main(int, const char**)': samples\charstringsample.cpp:35: error: 'strcmp' was not declared in this scope "g++-4.3.0" -ftemplate-depth-128 -O3 -finline-functions -Wno-inline -Wall -DNDEBUG -I"." -c -o "bin\gcc-4.3.0\release\charstringsample.o" "samples\charstringsample.cpp" ...failed gcc.compile.c++ bin\gcc-4.3.0\release\charstringsample.o... ...skipped <pbin\gcc-4.3.0\release>charstringsort.exe for lack of <pbin\gcc-4.3.0\release>charstringsample.o... gcc.compile.c++ bin\gcc-4.3.0\release\stringfunctorsample.o samples\stringfunctorsample.cpp: In function 'int main(int, const char**)': samples\stringfunctorsample.cpp:34: error: 'strcmp' was not declared in this scope "g++-4.3.0" -ftemplate-depth-128 -O3 -finline-functions -Wno-inline -Wall -DNDEBUG -I"." -c -o "bin\gcc-4.3.0\release\stringfunctorsample.o" "samples\stringfunctorsample.cpp" ...failed gcc.compile.c++ bin\gcc-4.3.0\release\stringfunctorsample.o... ...skipped <pbin\gcc-4.3.0\release>stringfunctorsort.exe for lack of <pbin\gcc-4.3.0\release>stringfunctorsample.o... gcc.compile.c++ bin\gcc-4.3.0\release\reversestringfunctorsample.o samples\reversestringfunctorsample.cpp: In function 'int main(int, const char**)': samples\reversestringfunctorsample.cpp:34: error: 'strcmp' was not declared in this scope "g++-4.3.0" -ftemplate-depth-128 -O3 -finline-functions -Wno-inline -Wall -DNDEBUG -I"." -c -o "bin\gcc-4.3.0\release\reversestringfunctorsample.o" "samples\reversestringfunctorsample.cpp" ...failed gcc.compile.c++ bin\gcc-4.3.0\release\reversestringfunctorsample.o... ...skipped <pbin\gcc-4.3.0\release>reversestringfunctorsort.exe for lack of <pbin\gcc-4.3.0\release>reversestringfunctorsample.o... gcc.compile.c++ bin\gcc-4.3.0\release\keyplusdatasample.o samples\keyplusdatasample.cpp: In function 'int main(int, const char**)': samples\keyplusdatasample.cpp:30: error: 'strcmp' was not declared in this scope "g++-4.3.0" -ftemplate-depth-128 -O3 -finline-functions -Wno-inline -Wall -DNDEBUG -I"." -c -o "bin\gcc-4.3.0\release\keyplusdatasample.o" "samples\keyplusdatasample.cpp" ...failed gcc.compile.c++ bin\gcc-4.3.0\release\keyplusdatasample.o... ...skipped <pbin\gcc-4.3.0\release>keyplusdata.exe for lack of <pbin\gcc-4.3.0\release>keyplusdatasample.o... ...failed updating 11 targets... ...skipped 11 targets... ...found 65 targets... ...updating 8 targets... compile-c-c++ bin\msvc-9.0express\release\threading-multi\floatsample.obj floatsample.cpp samples\floatsample.cpp(26) : warning C4996: 'fopen': This function or variable may be unsafe. Consider using fopen_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details. C:\Program Files\Microsoft Visual Studio 9.0\VC\INCLUDE\stdio.h(237) : see declaration of 'fopen' samples\floatsample.cpp(43) : error C3861: 'fpclassify': identifier not found samples\floatsample.cpp(43) : error C2050: switch expression not integral samples\floatsample.cpp(44) : error C2065: 'FP_NAN' : undeclared identifier samples\floatsample.cpp(44) : error C2051: case expression not constant samples\floatsample.cpp(45) : error C2065: 'FP_ZERO' : undeclared identifier samples\floatsample.cpp(45) : error C2051: case expression not constant samples\floatsample.cpp(51) : warning C4065: switch statement contains 'default' but no 'case' labels call "C:\Program Files\Microsoft Visual Studio 9.0\VC\vcvarsall.bat" x86 >nul cl /Zm800 -nologo @"bin\msvc-9.0express\release\threading-multi\floatsample.obj.rsp" ...failed compile-c-c++ bin\msvc-9.0express\release\threading-multi\floatsample.obj... ...skipped <pbin\msvc-9.0express\release\threading-multi>floatsort.exe for lack of <pbin\msvc-9.0express\release\threading-multi>floatsample.obj... compile-c-c++ bin\msvc-9.0express\release\threading-multi\shiftfloatsample.obj shiftfloatsample.cpp samples\shiftfloatsample.cpp(35) : warning C4996: 'fopen': This function or variable may be unsafe. Consider using fopen_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details. C:\Program Files\Microsoft Visual Studio 9.0\VC\INCLUDE\stdio.h(237) : see declaration of 'fopen' samples\shiftfloatsample.cpp(52) : error C3861: 'fpclassify': identifier not found samples\shiftfloatsample.cpp(52) : error C2050: switch expression not integral samples\shiftfloatsample.cpp(53) : error C2065: 'FP_NAN' : undeclared identifier samples\shiftfloatsample.cpp(53) : error C2051: case expression not constant samples\shiftfloatsample.cpp(54) : error C2065: 'FP_ZERO' : undeclared identifier samples\shiftfloatsample.cpp(54) : error C2051: case expression not constant samples\shiftfloatsample.cpp(60) : warning C4065: switch statement contains 'default' but no 'case' labels call "C:\Program Files\Microsoft Visual Studio 9.0\VC\vcvarsall.bat" x86 >nul cl /Zm800 -nologo @"bin\msvc-9.0express\release\threading-multi\shiftfloatsample.obj.rsp" ...failed compile-c-c++ bin\msvc-9.0express\release\threading-multi\shiftfloatsample.obj... ...skipped <pbin\msvc-9.0express\release\threading-multi>shiftfloatsort.exe for lack of <pbin\msvc-9.0express\release\threading-multi>shiftfloatsample.obj... compile-c-c++ bin\msvc-9.0express\release\threading-multi\floatfunctorsample.obj floatfunctorsample.cpp samples\floatfunctorsample.cpp(35) : warning C4996: 'fopen': This function or variable may be unsafe. Consider using fopen_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details. C:\Program Files\Microsoft Visual Studio 9.0\VC\INCLUDE\stdio.h(237) : see declaration of 'fopen' samples\floatfunctorsample.cpp(52) : error C3861: 'fpclassify': identifier not found samples\floatfunctorsample.cpp(52) : error C2050: switch expression not integral samples\floatfunctorsample.cpp(53) : error C2065: 'FP_NAN' : undeclared identifier samples\floatfunctorsample.cpp(53) : error C2051: case expression not constant samples\floatfunctorsample.cpp(54) : error C2065: 'FP_ZERO' : undeclared identifier samples\floatfunctorsample.cpp(54) : error C2051: case expression not constant samples\floatfunctorsample.cpp(60) : warning C4065: switch statement contains 'default' but no 'case' labels call "C:\Program Files\Microsoft Visual Studio 9.0\VC\vcvarsall.bat" x86 >nul cl /Zm800 -nologo @"bin\msvc-9.0express\release\threading-multi\floatfunctorsample.obj.rsp" ...failed compile-c-c++ bin\msvc-9.0express\release\threading-multi\floatfunctorsample.obj... ...skipped <pbin\msvc-9.0express\release\threading-multi>floatfunctorsort.exe for lack of <pbin\msvc-9.0express\release\threading-multi>floatfunctorsample.obj... compile-c-c++ bin\msvc-9.0express\release\threading-multi\randomGen.obj randomGen.cpp samples\randomGen.cpp(24) : warning C4996: 'fopen': This function or variable may be unsafe. Consider using fopen_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details. C:\Program Files\Microsoft Visual Studio 9.0\VC\INCLUDE\stdio.h(237) : see declaration of 'fopen' samples\randomGen.cpp(40) : error C3861: 'isnan': identifier not found samples\randomGen.cpp(43) : error C3861: 'isnan': identifier not found call "C:\Program Files\Microsoft Visual Studio 9.0\VC\vcvarsall.bat" x86 >nul cl /Zm800 -nologo @"bin\msvc-9.0express\release\threading-multi\randomGen.obj.rsp" ...failed compile-c-c++ bin\msvc-9.0express\release\threading-multi\randomGen.obj... ...skipped <pbin\msvc-9.0express\release\threading-multi>randomgen.exe for lack of <pbin\msvc-9.0express\release\threading-multi>randomGen.obj... ...failed updating 4 targets... ...skipped 4 targets...