Compare float array as int array

Question

I need an optimized binary search algorithm in an array of sorted numbers. I did this and found that using float to store numbers is faster than using an integer, because in the end I have to calculate

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

this->frameNumber[imin] is the largest frame number less than frameNumber , and this->frameNumber[imax] is the smallest that is larger than the one. This code is for calculating the progress between these two key frames. the frameNumber array is static. I just need to figure it out. But refer to it many times with binary search and the above code to calculate progress.

Converting from int to float did some loops. Then I discovered that asm has a lot of fpu instructions. I worry that they may be slower than whole ones.

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

It 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 is my conclusion above incorrect? (For example, casting int to float is not as expensive or is comparison between floating points as fast as integers?

Thanks a lot!

Answer 1

This seems like a bad idea. Using integer comparisons over float data will actually result in a properly ordered array of floats, as @rlbond points out. (See http://www.h-schmidt.net/FloatConverter/IEEE754.html for playing with binary representations of floats.) Before using this, make sure sizeof(int32_t) == sizeof(float) .

Such a hack is not needed. Comparing a float not much more expensive than comparing int on modern hardware. (Intel Haswell: ucomiss - 1 microprocessor, with 1 bandwidth in each cycle. Comparison with the memory operand - 2 times, without micro-merging. And this can not be with a macro fuse, for example cmp/jcc ). However, FP add / sub and FP mul have higher delays than their integer equivalents and lower throughput. It seems silly to convert an entire array to a float , because you only write it because you want to do some FP math with the minimum and maximum values ​​at the end.

The load-and-convert-int-to-float cvtsi2ss (x86 cvtsi2ss (single- cvtsi2ss single-digit integer with integer 2)) is about as fast and takes up the same code space as a regular load ( movss ).

If your data was originally integer, and you only use some of it, use int (avoiding conversion for values ​​that you will never need later). If you get access to everything, and only ever use your data as floats, save it as a float . If you use it as both, it is best to save it as an int , so it is faster if you use it as a whole, and at about the same speed when you use it as a float.

From your sample code, are you just using the values ​​in the min and max positions? Finding the min and max values ​​in an array is much faster than sorting the entire array. min / max is even vectorized with instructions with packed minimum values.

On many platforms, there is no such fast floating point as modern Intel processors, so do not go overboard with a floating point.