c++ - 将 float 数组与 int 数组进行比较

Question

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

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

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

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

那么问题来了。我可以将排序后的 float 数组转换为 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 指出的那样，对 float 据使用整数比较实际上会产生正确排序的 float 组。 (请参阅 http://www.h-schmidt.net/FloatConverter/IEEE754.html 以使用 float 的二进制表示形式。)在使用它之前检查 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 数学运算。

加载并转换整数为 float 指令(x86 cvtsi2ss(有符号整数 2 标量单值))与普通指令一样快，并且占用相同的代码空间加载(movss)。

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

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

许多平台的浮点运算速度不如现代 Intel CPU，因此不要过度使用 float 。