Re: [boost] Proposed templated integer_sort

Subject: Re: [boost] Proposed templated integer_sort
From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2009-01-08 21:29:52

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...