6

我有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我可以放弃两个余数操作？（这样做太难了，不值得作为基准，除非它可能是一个显着的改进）

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

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

WIDTH, HEIGHT, 并且BOX_SIZE在技术上是免费的，只要WIDTH和HEIGHT是 的偶数倍BOX_SIZE。实际上，它们都是指定的编译时间，并且是带有BOX_SIZE=1. 我已经运行了从WIDTH=HEIGHT=4to的所有内容WIDTH=HEIGHT=512，虽然我通常是 2 的平方幂（因为为什么不呢？），WIDTH=37;HEIGHT=193但应该可以正常工作。

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

10 particles/box * 100 WIDTH * 100 HEIGHT* 10000 steps = 1 billion particle*timesteps在阴凉处运行一分钟以上的基本测试。

这些坐标按照它们的“常规数字”（1-1000）的顺序排列，所以我离任何类型的double.

4

2 回答 2

7

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

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

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

Erik de Castro Lopo（libsndfile 和秘密兔子代码的作者）有一篇关于这个问题的非常有趣的文章。在他的音频转换例程中，浮点舍入性能至关重要，他使用 POSIXlrintf()调用以及一些用于非 POSIX 平台的 x86 程序集为这个问题提供了一组有趣的解决方案。

这篇文章可以在这里找到。

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

于 2013-05-09T21:47:51.547 回答
3

除法和余数

评论中暗示的一个问题是除法（和/或余数运算）可能很昂贵。与加法和乘法的单个周期相比，除法需要几十个处理器周期并不少见。

避免这种开销的最简单方法可能是使 WIDTH 和 HEIGHT 编译时常量为 2 的幂。% WIDTH这允许编译器使用或% HEIGHT快速位掩码操作来更改余数操作。类似地，如果 BOX_SIZE 是一个 2 的幂的编译时常量，它允许编译器将除法更改为位移。

这也是我评论更改((int) x / BOX_SIZE % WIDTH + WIDTH) % WIDTH为的原因((int) x / BOX_SIZE + Number) % WIDTH，其中 Number 是 WIDTH 的某个倍数，因此总和保证为非负数。这消除了余数运算。（但是，您提出这个表达式来处理负坐标，它可能有一个缺陷：(int) x / BOX_SIZE将商向零舍入，这可能会为负 x 给出错误的框数。所以在我们考虑优化之前，您可能需要修复这个表达式方面。）

其他

通常，我会怀疑缓存和处理器时间对源代码的不精确归因是索引计算似乎需要 20% 的执行时间的原因。您显示的索引计算没有缓存影响，因为它们不访问内存。但是，编译后的代码往往会产生交错的指令：每条源代码语句都会产生多条指令，不同语句的指令会因为各种原因被交错，而不是作为一条语句的所有指令出现，那么针对不同语句的指令就会出现交错。另一个声明，依此类推。这种交错使得软件性能报告难以准确指示处理器时间消耗的位置。

还有其他影响这种测量的影响。通过采样进行一些测量：处理器每隔一段时间中断一次，并记录中断时程序计数器的值。这表明您是处理器正在等待的东西，而不是它正在等待的东西。例如，如果 to 的转换x正在int等待浮点单元可用，但没有可用的单元，因为前一条指令正在执行完全不相关的数据相加，那么 20% 的样本似乎在(int) x具有误导性。

您正在对一百万个粒子进行操作这一事实与某些数据访问一致，这些数据访问会导致缓存抖动和性能下降。另一方面，添加更多余数运算（用于支持负坐标）使索引计算看起来消耗更多时间这一事实反表明缓存问题。

但是，这些索引计算占用程序大部分时间是不寻常的，除非程序几乎没有做其他工作。

如果您可以显示演示该问题的自包含可编译代码，这可能会有所帮助。

于 2013-05-10T13:19:09.180 回答