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-05 12:17: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.

Hi Steven,

If the problem were simply that "x86 FP is very slow", then this 
problem would be evident with std::sort as well as your algorithm.  
I've therefore done a simple test with a program like the following:

static inline bool compare_floats_as_ints(float f1, float f2)
{
   int i1, i2;
   memcpy(&i1,&f1,sizeof(int));
   memcpy(&i2,&f2,sizeof(int));
   return i1<i2;
}

int main()
{
   std::srand(0);
   std::vector<float> data(10000000);
   random_fill(data.begin(),data.end());
   pbe::HPtime t_start(pbe::HPtime::now());
   std::sort(data.begin(),data.end(),compare_floats_as_ints);
   pbe::HPtime t_end(pbe::HPtime::now());
   std::cout << "t = " << t_end-t_start << "\n";

   return 0;
}

Note that I haven't actually checked if I get the right answers from 
this, so please let me know if you can see any mistakes!  Also note 
that I have not done any fixup for negative floats, so some small 
additional time would be needed for that.

I've run variations of this code with the following results:

vector<int>, std::sort(begin,end) : 3.71 s
vector<float>, std::sort(begin,end) : 9.12 s
vector<float>, std::sort(begin,end,compare_floats_as_ints) : 4.19 s

So it looks like integer comparisons are two to three times faster than 
float comparisons on this hardware.  This is the sort of difference 
that I would expect.  Sorting floats as integers is a bit slower than 
sorting integers, but significantly faster than sorting them as floats 
(but note that the fixup for negatives etc. is not implemented).

This is with g++-4.3 -O3 -fprofile-generate/use on Linux, on a 1.2 GHz 
VIA C7-M.  Using profile-driven optimisation is important to get good results.

I feel that your observation that FP comparisons are 100X (or even 20X) 
slower than integer comparisons on Intel hardware are implausible.  
There must be some other reason for the slowness.

Regards,  Phil.