在C语言中，最快的for循环是什么？

Question

我正在尝试编写优化的代码以访问图像像素，并且需要使for循环快速运行，而不需要降到汇编级别。此外，索引沿着行进行，以最小化缓存未命中。

这是我的代码：

for (indr=0;indr<(height-1)*width;indr+=width) {
        for (indc=0;indc<width;indc++){
            I[indr+indc]= dostuff ;
        }
    }

我不能将它变成单独的循环，因为“dostuff”包括访问不在同一行上的元素。

有更快的方法吗？

编辑：好的，因为我的上一个帖子有点不清楚，我在这里添加了完整的代码。它非常难以阅读，但基本思想是使用积分图像对简单框执行卷积。首先，在左侧和底部填充了ws+1个零，右侧和顶部填充了ws个零。然后将其转换为积分图像Ii。下面的函数接受积分图像并提取卷积，结果Ic与原始图像大小相同。

void convI(float *Ic,float *Ii,int ws, int width, int height)
{
    int W=width+ws*2+1,indR;
    int H=height+ws*2+1,indC;
    int w=width, indr;
    int h=height, indc;
    int jmpA=W*(ws+1),jmpC=W*ws,jmpB=ws+1,jmpD=ws;

    for (indR=W*(ws+1),indr=0;indr<width*(height-1);indR+=W,indr+=width) {
        for (indC=ws+1,indc=0;indc<width;indC++,indc++){
            //Performs I[indA]+I[indD]-I[indB]-I[indC];
            Ic[indr+indc]=
            Ii[indR-jmpA+indC-jmpB]+
            Ii[indR+jmpC+indC+jmpD]-
            Ii[indR+jmpC+indC-jmpB]-
            Ii[indR-jmpA+indC+jmpD];
        }
    }
}

所以这就是"dostuff"部分。循环运行缓慢。

- twerdster

---

循环总是比访问内存更快。展示你的"dostuff"代码，或告诉我们它读取的内存。 - BatchyX

Answer 1

如果你已经开启了所有优化级别，那么其他代码很难比你提供的代码更具有更好的性能。

为什么你怀疑循环本身是瓶颈？没有了解你实际在做什么，很难给出明确的答案。如果你对代码性能存在疑虑，可以对其进行基准测试，并查看其产生的汇编代码。

编辑：在你展示循环内部之后。

有一点潜力可以将索引计算的表达式尽可能多地放在循环外部。由于它与循环变量交织在一起，因此这可能无法像应该那样进行优化。（或者只需重新排列索引计算，使得编译器可以看到并预先计算尽可能多的内容。）

最大的问题可能来自于访问向量的方式。如果你能够更好地计算索引，这也可能会提高性能，因为编译器/系统将会看到你以规则的模式访问向量。

如果这还不起作用，可以重新组织循环，使得向量的加载是递增的而不是储存。加载操作总是必须等待数据就绪才能执行操作，而储存操作相对不那么敏感。

- Jens Gustedt

Answer 2

你可以展开最内层循环。虽然这会降低可读性，但CPU的缓存和预取队列会做得更好。虽然这总是正确的，但我不知道你会获得多少速度提升。

你可以将indc和indr都声明为寄存器变量，并尝试避免重新计算(height-1)*width，而是将其保存在临时变量中。你知道，乘法会消耗很多时钟周期...

- BlackBear

Answer 3

除非你想使用像SSE这样的向量指令，否则不太可能有其他的办法。

- Puppy

---

SSE在iPhone上不可用。 - Clark Gaebel

https://dev59.com/yVDTa4cB1Zd3GeqPM-Fl - BatchyX

你没有提到你的平台。 - Puppy

Answer 4

你的代码看起来很好。如果你想避免进入汇编语言，最好保持简单循环的简单性。GCC很聪明。如果你清楚你想让你的代码做什么，它通常会很好地优化它。然而，如果你使用了在生产代码中不常见的花哨技巧，它可能会有困难推断出你的“真正意图”。

根据 dostuff 实际执行的操作，你可能会发现在临时缓存中缓存 I[indr+indc] 会有所收获，这样你的代码看起来就像...

char t = I[indr+indc];
// do stuff
I[indr+indc] = t;

这段代码不会表现得更糟（我假设您至少开启了基本优化），但如果您的do stuff够高级，它可能会表现得更好。如果您需要，我可以详细说明。

不要听其他人从循环中提取简单的数学运算。真的没有必要。如果您查看在-O1下生成的汇编代码，就会发现每次都为您完成了这一操作。这是最便宜的优化之一。

- Clark Gaebel

Answer 5

在外部循环之前将height-1提升为一个赋值可能会有所收益。但是，我怀疑现代的编译器会将其作为标准优化处理。另外，设置另一个指针为I[indr]，然后从该指针进行索引也可能会稍微提高性能。

这两种方法都需要进行仔细的基准测试才能确定。

- Vatine

Answer 6

// DragonLord style:
float *ic_p = I + (width * height) - 1;  // fencepost  
// Start at the end, and work backwards 
// assumes I is 0-based and wraps, is contiguous

for (indr=(height -1) * width; indr>=0; indr-=width ) {
// Sadly cannot test on indr -= width here
// as the 0 pass is needed for the loop
        for (indc=width; indc--; ){
        // Testing on postdecrement
        // allows you to use the 0 value one last time before testing it FTW
            // indr and indc are both 0-based inside the loop for you
            // e.g. indc varies from (width-1) down to 0
            // due to postdecrement before usage
            printf( "I[ %d + %d ] == %f \n", indr, indc, *ic_p );
            // always use pointers in C/C++ for speed, we are not Java
            *ic_p-- = dostuff ;
        }
    }

如果您在循环内部不需要使用indr，或者可以使用基于1的indc，并且可以通过从height向0倒数，或者使用预减而不是后减来改进性能。在这种情况下，indc应该初始化为（width + 1）：

   for (indc=(width+1); --indc; ){

- DragonLord