
Boost : 
Subject: Re: [boost] sorting floats by casting to integer
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 20090705 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 floatingpoint 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_endt_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 fprofilegenerate/use on Linux, on a 1.2 GHz
VIA C7M. Using profiledriven 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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk