[boost] sorting floats by casting to integer

Subject: [boost] sorting floats by casting to integer
From: Steven Ross (spreadsort_at_[hidden])
Date: 2009-07-03 20:59:27

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.

Example source (not templated yet):
#define DATATYPE float
#define CAST_TYPE int
inline void float_as_integer_sort(std::vector<DATATYPE> &input)
{
  if(input.size() < 2)
    return;
  std::vector<CAST_TYPE> cast_vec;
  cast_vec.resize(input.size());
  unsigned neg_index = 0;
  int pos_index = input.size() - 1;
  //Casting to integer and presorting into negative and positive
  for(unsigned u = 0; u < input.size(); ++u) {
    int cast_val = float_mem_cast<DATATYPE, CAST_TYPE>(input[u]);
    if(cast_val < 0)
      cast_vec[neg_index++] = cast_val;
    else
      cast_vec[pos_index--] = cast_val;
  }
  assert((pos_index + 1) == neg_index);
  //Sort the negatives
  integer_sort(&(cast_vec[0]), &(cast_vec[neg_index]));
  //Then the positives
  integer_sort(&(cast_vec[neg_index]), &(cast_vec[0]) + cast_vec.size());
  //casting back negatives
  for(unsigned u = 0; u < neg_index; ++u)
    std::memcpy(&(input[neg_index - u - 1]), &(cast_vec[u]),
sizeof(DATATYPE));
  //Then positives
  for(unsigned u = neg_index; u < cast_vec.size(); ++u)
    std::memcpy(&(input[u]), &(cast_vec[u]), sizeof(DATATYPE));
}