c - 更有效的 flooring double 方法来获取数组索引

Question

我有 double x , 和 double y .我需要把它变成 int boxnum ，它被定义为(floored)索引，其中 (x,y)落在 WIDTH x HEIGHT网格大小为 BOX_SIZE .坐标超过WIDTH被包裹起来； HEIGHT 同上.

我目前正在使用:

( (((int)(x))/BOX_SIZE)%WIDTH+ WIDTH*((((int)(y))/BOX_SIZE)%HEIGHT) )

这个语句目前占用了大约 20% 的执行时间，如果我让它对负坐标完全安全，情况会变得更糟(大约 40-50%):

( (( ((int)(x)) /BOX_SIZE)%WIDTH+WIDTH)%WIDTH
    +WIDTH*(( (((int)(y)) /BOX_SIZE)%HEIGHT+HEIGHT)%HEIGHT) )

我实际上正在考虑将应用程序完全转换为定点，只是为了避免这种情况，这样我就可以屏蔽掉我想要的部分，而不是进行这种可怕的转换。

是否有更好的方法来进行这种 double->int 转换？确保0<x<WIDTH*BOX_SIZE值得吗？和 0<y<HEIGHT*BOX_SIZE所以我可以放弃两个余数操作？ (这样做非常困难，不值得用于基准测试，除非它可能是一个重大改进)

编辑:在评论中进行适当的惩罚后，更多细节:

x和 y是一组(多达 10^6 个)粒子的坐标。我正在使用一种算法，该算法要求我在每个时间步对一个盒子内的所有粒子进行一些简单的求和。因此，我遍历粒子，计算粒子在哪个盒子中，然后将其用作添加到该盒子的数组索引。粒子通常移动得足够远，以至于它们过去的位置并不能指示它们 future 的位置。它们也是无序的，这意味着我无法对此做出任何假设。

WIDTH , HEIGHT , 和 BOX_SIZE技术上是免费的，只要WIDTH和 HEIGHT是 BOX_SIZE 的偶数倍.实际上它们都是指定的编译时间，并且是带BOX_SIZE=1的整数。 .我已经从 WIDTH=HEIGHT=4 运行了一切至 WIDTH=HEIGHT=512 ，虽然我通常使用 2 的平方次方(因为为什么不呢？)，WIDTH=37;HEIGHT=193应该可以正常工作。

这种计算不可避免地会在每个粒子每个时间步执行一次；在当前的实现中，它执行了两次。我尝试缓存该值以避免重新计算，但最终基准测试的表现更差，所以我又重新计算了两次。

使用 10 particles/box * 100 WIDTH * 100 HEIGHT* 10000 steps = 1 billion particle*timesteps 进行基本测试在阴凉处跑了一分钟。

这些坐标按照它们的“常规数字”(1-1000) 的顺序排列，所以我离 double 上的任何类型的界限都不远。 .

Answer 1

您的代码的问题在于，(int) 转换导致浮点单元的舍入模式从 IEEE754 默认舍入到最接近更改为 C 标准向零舍入或标准中定义的“截断”。

请参阅 gcc 文档 here有关 IEEE754 舍入模式的更多信息。

在现代深度流水线处理器上，当更改舍入模式时必须刷新整个流水线，导致速度大幅下降，因为流水线在每次 (int) 转换时都会被清空。当您在循环中执行此操作时，您遇到的减速是典型的。

Erik de Castro Lopo(libsndfile 和 secret rabbit code 的作者)就这个问题发表了一篇非常有趣的文章。在他的音频转换例程中，浮点舍入性能至关重要，他使用 POSIX lrintf() 调用以及一些用于非 POSIX 平台的 x86 程序集为该问题提供了一组有趣的解决方案。

文章可以查here.

简短的回答是使用 C99/POSIX lrintf() 函数，或者使用一些内联汇编来执行整数截断而不改变浮点舍入模式。