Re: [boost] sorting floats by casting to integer

Subject: Re: [boost] sorting floats by casting to integer
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2009-07-04 12:49:09

Steven Ross wrote:
> I've been investigating why float_sort is so much faster than std::sort on
> x86 processors, and why sorting integers is so much faster than float_sort,
> and came to the conclusion that floating-point comparisons are extremely
> slow on x86.  Based upon that, I've written a different sorting approach
> that copies the input array of floats, casting them to integers, and sorts
> them as integers, dealing with the negative floats sorting in reverse order
> issue, completely eliminating floating-point comparisons.  It takes O(n)
> additional memory, and is somewhat less general, as a different approach is
> required for key plus data sorting (as non-float data can't be safely cast
> this way), but it obtains integer-sorting speeds.  On some problems it is as
> much as 120X as fast as std::sort.  I doubt average results will be quite
> that good, but they could easily be well over 10X as fast.

Hi Steven,

120X seems so enormous that it makes me think there must be something 
else going on.  I would suggest looking at the assembler that is 
generated, but I think that sort is sufficiently complicated that the 
assembler will be hard to read (unless you're used to it).  So, I 
suggest instead looking at a simpler problem involving comparisons e.g. 
is_sorted(range) or minmax(range).  Assuming that you see a similar 
difference between floating point and integer for that, you should be 
able to check the assembler for "smoking guns".

Possibilities that occur to me include:
- Unnecessary transfers between integer and floating point registers.
- Memory alignment issues.
- Lack of optimisation.
- Something related to NaNs, de-normals etc (do you have these in your 
test data?).

Also, I don't see why you actually need to copy all the data to achieve 
what you're doing.  Can't you cast it "in place" and then deal with the 
negative numbers (etc) as an in-place pre- or post-processing step?

Regards,  Phil.