将 float 数组与 int 数组进行比较

Question

我需要一个针对已排序数字数组的优化二进制搜索算法。我这样做了，发现使用浮点数存储数字比使用整数更快，因为最后我必须计算

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

this->frameNumber[imin] 是小于 frameNumber 的最大帧数，this->frameNumber[imax] 是大于它的最小帧数。该代码用于计算这两个关键帧之间的进度。 frameNumber 数组是静态的。我只需要排序一次。但是通过二分查找多次访问，上面的代码计算进度。

从 int 到 float 的转换花费了一些周期。然后我发现在asm中有很多fpu指令。我担心它们可能比整数慢。

所以问题来了。我可以将排序的浮点数数组转换为 int* 并运行对其进行二进制搜索吗？

这意味着：

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,...);
}

或者我上面的结论是错误的？（例如将int转换为float并不那么昂贵，或者浮点之间的比较与整数一样快？

非常感谢！

Answer 1

这似乎是个坏主意。正如@rlbond 指出的那样，对浮点数据使用整数比较实际上会产生正确排序的浮点数组。（请参阅 http://www.h-schmidt.net/FloatConverter/IEEE754.html 以使用浮点数的二进制表示。）在使用此之前检查 sizeof(int32_t) == sizeof(float)。

并不是真的需要这样的 hack。在现代硬件上，float 比较并不比 int 比较昂贵多少，。（Intel Haswell：ucomiss 是 1 uop，每个周期吞吐量为 1。与内存操作数相比是 2 uops，不过没有微融合。而且它不能像 cmp/jcc 那样进行宏融合）然而，FP add/sub 和 FP mul 的延迟 比它们的整数等价物更高，吞吐量更小。将整个数组转换为 float 似乎很愚蠢，因为你想在最后用最小值和最大值做一些 FP 数学运算。

加载并转换整数为浮点数指令（x86 cvtsi2ss（有符号整数 2 标量单值））速度差不多，并且采用相同的代码 space，作为正常负载 (movss).

如果您的数据最初是整数，而您只使用其中的一部分，请使用 int（避免转换为您以后不需要的值）。如果你确实访问了所有这些，并且只将你的数据用作浮点数，那么将它存储为 float。如果你同时使用它，最好将它存储为 int，因此当你将它用作整数时它会更快，而当你将它用作浮点数时两种方式的速度大致相同。

根据您的代码示例，您只是使用了最小和最大位置的值？查找数组中的最小值和最大值比对整个数组排序要快得多。 min/max 甚至使用最小压缩指令进行矢量化。

许多平台没有像现代 Intel CPU 那样快的浮点运算，所以不要过度使用浮点运算。

将 float 数组与 int 数组进行比较

Compare float array as int array

c

c++

floating-point

floating-point-conversion