Re: [boost] sorting floats by casting to integer

Subject: Re: [boost] sorting floats by casting to integer
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2009-07-03 21:27:15

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. 
> Does this sound like it's appropriate for Boost?  If so, I'll add it
> to my proposed Boost.Algorithm.Sorting library, which is complete,
> aside from this issue.

Which x86 processors specifically?  Some manufacturers have been known to focus on integer performance and let floating point suffer because floating point performance is usually not a dominant factor in overall performance.  Other x86 processors, however, have quite good floating point performance.  If you think about it, if casting to integer to compare floating point values is faster, why doesn't the processor do that itself?  I have been told that some processors do.

Regards,
Luke