Re: [boost] sorting floats by casting to integer

Subject: Re: [boost] sorting floats by casting to integer
From: Vladimir Prus (vladimir_at_[hidden])
Date: 2009-07-05 04:01:44

Steven Ross wrote:

>> I am using  MSVC 2005 standard edition with bjam's default release settings
> for it.  I have not tried other compiler settings, besides 64-bit
> compilation, which has comparable performance.
> This is on a Core 2 Duo purchased earlier this year for Boost development.
> I saw the same behavior and the same magnitude of speedup for float_sort vs.
> std::sort on floats on a 6 year old refurbished Dell Windows system using
> gcc in Cygwin.
> With two different compilers on processors manufactured at least 6 years
> apart, I suspect it's an issue with the architecture.
> There may be Intel processors that are faster for this purpose, but they
> certainly aren't the two mass-market Intel processors I've tried, with
> default optimizations.
> 
> If anybody would like to look at my testcase, it is in the boost vault,
> inside algorithm_sorting.zip.  Inside there, it is in
> libs/algorithm/sorting/samples/float_as_integer.cpp.  

This version fails to compile for me, because it includes boost/static_warning.hpp,
and it does not seem to be present in my SVN HEAD tree. I've changed include to
boost/serialization/static_warning.hpp, but this can't be right. Am I missing
something?

> Even without using 
> integer_sort, and just using std::sort on integers with the code I posted
> initially, the speedup is on the same order (80X).  I tested using randomgen
> 7 16 1000000 (randomgen is compiled from my randomgen.cpp).  7 is the bit
> range among the "high" 16 bits, the second number (16) is the bit range
> among the "low" 16 bits, and 1000000 is the size of the vector to sort.  23
> bits are used to exclude NaNs, which I assume to be uncommon in real data,
> and which are sorted arbitrarily, meaning that two correct sorted results
> containing NaNs will often not be identical.  With mostly NaNs the speedup
> with this approach is about 2X.
>>From the libs/algorithm/sorting directory (once copied into the boost tree),
> you can test this way:
> bjam --tune randomgen
> randomgen 7 16 1000000
> bjam --tune float_as_integer
> float_as_integer (uses the approach I described)
> float_as_integer -std (uses std::sort on floats)
> (I see a huge difference in runtime on x86, but not on PowerPC)

To bet bigger times that are less prone to noise, I have changed loopCount
in your test to 10. Then, then time reported without -std is 1 second,
with very small difference between each run. The time with -std is 
43 seconds, again with negligible variation.

If I add:

    cxxflags="-march=nocona -mfpmath=sse"

then -std runs in 16 seconds, while the time for your algorithm is the same 1
second. Of course, this is still significant speedup, but smaller than number
you have reported, so probably a deeper look is reasonable.

Incidentally, does your library allow to sort only a collection of integers/floats,
or it also allows to sort an arbitrary collection where each item has integer/float
key? If so, can you point me at example?

- Volodya