Compare float array as int array

Question

I need a optimized binary search algorithm on a array of sorted numbers. I did this and found that using float to store numbers is faster than using integer, because at the end i must calculate

(frameNumber-this->frameNumber[imin])/(this->frameNumber[imax]-this->frameNumber[imin])

this->frameNumber[imin] is the biggest frameNumber less equal that frameNumber and this->frameNumber[imax] is the smallest one greater equal than that. That code is to calculate the progress between that two keyframes. the frameNumber array is static. I only have to sort it once. But access it many times with a binary search and the above code to calculate the progress.

The conversion from int to float spent some cycles. Then I discovered that in the asm there a a lot of fpu instructions. I'm worrying they might be slower than integer.

So here is the question. Can I convert an array of sorted floating point numbers to an int* and run a binary search on it?

That means:

void binary_search(float key,float* array,...)
{
    int key_integer=*(int*)&key;
    int* array_intege(int*)array;
    binary_search_for_integers(key_integer,array_integer,...);
}

Or my above conclusion are wrong? (Such as casting int to float is not so costy, or comparision between floating points is the same fast as integers?

Thanks a lot!

Answer 1

This seems like a bad idea. Using integer compares on float data actually will result in a correctly ordered array of floats, as @rlbond points out. (See http://www.h-schmidt.net/FloatConverter/IEEE754.html to play with the binary representations of floats.) Check that sizeof(int32_t) == sizeof(float) before using this.

A hack like this is not really needed. float comparison is not much more expensive than int comparison, on modern hardware. (Intel Haswell: ucomiss is 1 uop, with 1 per cycle throughput. Comparing with a memory operand is 2 uops, no micro-fusion, though. And it can't macro-fuse like cmp/jcc) However, FP add/sub and FP mul have higher latencies than their integer equivalents, and less throughput. It seems silly to convert a whole array to float as you're writing to it just because you want to do some FP math with the min and max values at the end.

A load-and-convert-int-to-float instruction (x86 cvtsi2ss (signed-integer 2 scalar single)) is about as fast, and takes the same code space, as a normal load (movss).

If your data originally was integer, and you only use some of it, use int (avoiding the conversion for values you never need later). If you do access all of it, and only ever use your data as floats, then store it as float. If you use it as both, it's probably best to store it as int, so it's faster when you do use it as integer, and about the same speed either way when you use it as float.

From your code sample, you're just using the values at the min and max positions? It's a lot faster to find the min and max values in an array than it is to sort the whole array. min/max even vectorizes with packed-min instructions.

Many platforms don't have as fast floating point as modern Intel CPUs, so don't go overboard with floating point.