Re: [boost] Proposed templated integer_sort

Subject: Re: [boost] Proposed templated integer_sort
From: Steven Ross (spreadsort_at_[hidden])
Date: 2009-01-11 20:45:24

Thanks for testing it Steve.
I was unable to reproduce the errors you encountered, but I eliminated all
references to nans and strcmp.  I also changed the code to use std::memcpy
and include <cstring>.  I believe this should resolve the problems you
encountered.
I've added html documentation.
The new version is at: http://sourceforge.net/projects/spreadsort
I'd appreciate feedback on any issues.  I believe that the only thing this
is missing now is test integration with Boost, which I'll try to do with a
Jamfile.
When I submit a proposed library, should I include the multi-level directory
structure for it as it would appear in the boost hierarchy?

Regards,

Steve Ross

On Thu, Jan 8, 2009 at 6:29 PM, Steven Watanabe <watanabesj_at_[hidden]>wrote:

> 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...
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>