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