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.