更高效的地板方式可以获得数组索引

Question

我有double x,和double y.我需要将其转换成int boxnum,其被定义为(地板)的索引,其中(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) )

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

有没有更好的方法来进行这种双重> int转换？难道是值得的,以确保0<x<WIDTH*BOX_SIZE和0<y<HEIGHT*BOX_SIZE这样我就可以放下两个余数操作？(这样做很难在基准测试中不值得,除非它可能是一个重大改进)

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

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

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标准回零朝零或"截断",因为它在标准中定义.

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

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

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

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

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