C中的快速欧几里德分裂

Question

我有兴趣获得欧几里德分区的其余部分,也就是说,对于一对整数(i,n),找到如下的r:

i = k * n + r, 0 <= r < |k|

简单的解决方案是:

int euc(int i, int n)
{
    int r;

    r = i % n;
    if ( r < 0) {
        r += n;
    }
    return r;
}

但是因为我需要执行这几万次(它在多维数组的迭代器中使用),所以如果可能的话我想避免分支.要求:

• 分枝但更快也是可取的.
• 只适用于正n的解决方案是可以接受的(但它必须适用于负i).
• n事先不知道,可以是> 0和<MAX_INT的任何值

编辑

实际上很容易得到错误的结果,所以这里有一个预期结果的例子:

• euc(0,3)= 0
• euc(1,3)= 1
• euc(2,3)= 2
• euc(3,3)= 0
• euc(-1,3)= 2
• euc(-2,3)= 1
• euc(-3,3)= 0

有些人还担心优化它是没有意义的.我需要这个用于多维迭代器,其中超出范围的项被"虚拟数组"中的项目替换,该虚拟数组重复原始数组.所以如果我的数组x是[1,2,3,4],那么虚拟数组是[....,1,2,3,4,1,2,3,4,1,2,3,4, 1,2,3,4],例如,x [-2]是x 1等...

对于维d的nd数组,我需要每个点都有欧几里德分区.如果我需要在具有内核的^ d数组之间进行相关,我需要n ^ d*m ^ d*d euclidean分区.对于100x100x100点的3d图像和5*5*5点的内核,已经有大约4亿个欧几里德分区.

Answer 1

编辑:没有乘法或分支woot.

int euc(int i, int n)
{
    int r;

    r = i % n;
    r += n & (-(r < 0));

    return r;
}

这是生成的代码.根据MSVC++仪器分析器(我的测试)和OP的测试,它们的表现几乎相同.

; Original post
00401000  cdq              
00401001  idiv        eax,ecx 
00401003  mov         eax,edx 
00401005  test        eax,eax 
00401007  jge         euc+0Bh (40100Bh) 
00401009  add         eax,ecx 
0040100B  ret              

; Mine
00401020  cdq              
00401021  idiv        eax,ecx 
00401023  xor         eax,eax 
00401025  test        edx,edx 
00401027  setl        al   
0040102A  neg         eax  
0040102C  and         eax,ecx 
0040102E  add         eax,edx 
00401030  ret              

Answer 2

我认为280Z28和克里斯托弗的装配高尔夫比我更好,并处理随机访问.

但是,你实际上在做的事情似乎是处理整个数组.显然,出于内存缓存的原因,您已经希望在可能的情况下按顺序执行此操作,因为避免缓存未命中比避免小分支要好很多倍.

在这种情况下,首先使用合适的边界检查,你可以在我称之为"破折号"的内循环中进行.检查下一个k增量不会导致任一阵列上最小维度的溢出,然后使用一个新的更多内部循环"破坏"k步骤,这样每次只增加"物理"索引1做另一个idiv.您或编译器可以展开此循环,使用Duff的设备等.

如果内核很小,特别是如果它是固定大小的话,那么(或者它的多个具有合适的展开以偶尔减去而不是添加)可能是用于"破折号"长度的值.编译时常量短划线长度可能是最好的,因为那时你(或编译器)可以完全展开破折号循环并忽略连续条件.只要这不会使代码太大而不能快,它实际上用整数增量替换整个正模运算.

如果内核不是固定大小,但在其最后一个维度中通常非常小,请考虑为最常见的大小设置不同版本的比较函数,并在每个版本中完全展开破折号循环.

另一种可能性是计算溢出将发生的下一个点(在任一阵列中),然后冲到该值.在dash循环中仍然有一个延续条件,但它只使用增量来尽可能长.

或者,如果您正在进行的操作是数字相等或其他一些简单操作(我不知道"相关性"是什么),您可以查看SIMD指令或其他任何内容,在这种情况下,短划线长度应该是在您的架构上进行最广泛的单指令比较(或适当的SIMD操作).不过,这不是我遇到过的.