c - 循环展开，性能实验室

Question

我正在尝试通过循环展开来优化此代码，

void naive_flip(int dim, pixel *src, pixel *dst) 
{
    int i, j;
    for (i = 0; i < dim; i++){
        for (j = 0; j < dim; j++){
            dst[RIDX_F(i, j, dim)].red   = src[RIDX(i, j, dim)].red;
            dst[RIDX_F(i, j, dim)].green = src[RIDX(i, j, dim)].green;
            dst[RIDX_F(i, j, dim)].blue  = src[RIDX(i, j, dim)].blue;
        }
    }
}

但是，我以前没有真正做过，所以当我尝试时，我得到了这个

void flip_one(int dim, pixel *src, pixel *dst)
{
    //i will be attempting loop unrolling to optimize code
    int i, j;
    for (i=0; i<dim; i+=32)
    {
        for (int j=0; j<dim; j+=32)
        {
            dst[RIDX_F(i, j, dim)].red   = src[RIDX(i, j, dim)].red;
            dst[RIDX_F(i, j+1, dim)].green = src[RIDX(i, j, dim)].green;
            dst[RIDX_F(i, j+2, dim)].blue  = src[RIDX(i, j, dim)].blue;   
        }
        for (int j=0; j<dim; j+=32)
        {
            dst[RIDX_F(i+1, j, dim)].red   = src[RIDX(i, j, dim)].red;
            dst[RIDX_F(i+1, j+1, dim)].green = src[RIDX(i, j, dim)].green;
            dst[RIDX_F(i+1, j+2, dim)].blue  = src[RIDX(i, j, dim)].blue;   
        }
        for (int j=0; j<dim; j+=32)
        {
            dst[RIDX_F(i+2, j, dim)].red   = src[RIDX(i, j, dim)].red;
            dst[RIDX_F(i+2, j+1, dim)].green = src[RIDX(i, j, dim)].green;
            dst[RIDX_F(i+2, j+2, dim)].blue  = src[RIDX(i, j, dim)].blue;   
        }
        for (int j=0; j<dim; j+=32)
        {
            dst[RIDX_F(i+3, j, dim)].red   = src[RIDX(i, j, dim)].red;
            dst[RIDX_F(i+3, j+1, dim)].green = src[RIDX(i, j, dim)].green;
            dst[RIDX_F(i+3, j+2, dim)].blue  = src[RIDX(i, j, dim)].blue;   
        }
    }
}

运行代码时，它不起作用，并且给出了以下错误:

“错误:尺寸=96，9216 错误

例如，以下两个像素应具有相等的值:

src[9215].{红,绿,蓝} = {22543,1426,53562}

dst[9120].{红,绿,蓝} = {0,0,0}"

任何关于我做错了什么或我应该做什么的帮助都是值得赞赏的

编辑 我用这个更新了我的代码

void flip_one(int dim, pixel *src, pixel *dst)
{
    //i will be attempting loop unrolling to optimize code
    int i, j;
    for (i=0; i<dim; i++)
    {
        for (int j=0; j<dim; j++)
        {
            dst[RIDX_F(i, j, dim)].red   = src[RIDX(i, j, dim)].red;
            dst[RIDX_F(i, j, dim)].green = src[RIDX(i, j, dim)].green;
            dst[RIDX_F(i, j, dim)].blue  = src[RIDX(i, j, dim)].blue;

            dst[RIDX_F(i, j, dim)].red   = src[RIDX(i, j, dim)].red;
            dst[RIDX_F(i, j, dim)].green = src[RIDX(i, j, dim)].green;
            dst[RIDX_F(i, j, dim)].blue  = src[RIDX(i, j, dim)].blue;

            dst[RIDX_F(i, j, dim)].red   = src[RIDX(i, j, dim)].red;
            dst[RIDX_F(i, j, dim)].green = src[RIDX(i, j, dim)].green;
            dst[RIDX_F(i, j, dim)].blue  = src[RIDX(i, j, dim)].blue;

            dst[RIDX_F(i, j, dim)].red   = src[RIDX(i, j, dim)].red;
            dst[RIDX_F(i, j, dim)].green = src[RIDX(i, j, dim)].green;
            dst[RIDX_F(i, j, dim)].blue  = src[RIDX(i, j, dim)].blue;
        }
    }
}

我不再收到错误(耶!)但这实际上并没有加快速度，事实上它减慢了速度。也许我还做错了什么，但是，我不知道是什么。

编辑 我更新了代码，看起来像

void flip_one(int dim, pixel *src, pixel *dst)
{
    //i will be attempting loop unrolling to optimize code
    int i, j;
    for (i=0; i<dim; i++)
    {
        for (int j=0; j<dim; j+=4)
        {
            dst[RIDX_F(i, j, dim)].red   = src[RIDX(i, j, dim)].red;
            dst[RIDX_F(i, j, dim)].green = src[RIDX(i, j, dim)].green;
            dst[RIDX_F(i, j, dim)].blue  = src[RIDX(i, j, dim)].blue;

            dst[RIDX_F(i, j+1, dim)].red   = src[RIDX(i, j+1, dim)].red;
            dst[RIDX_F(i, j+1, dim)].green = src[RIDX(i, j+1, dim)].green;
            dst[RIDX_F(i, j+1, dim)].blue  = src[RIDX(i, j+1, dim)].blue;

            dst[RIDX_F(i, j+2, dim)].red   = src[RIDX(i, j+2, dim)].red;
            dst[RIDX_F(i, j+2, dim)].green = src[RIDX(i, j+2, dim)].green;
            dst[RIDX_F(i, j+2, dim)].blue  = src[RIDX(i, j+2, dim)].blue;

            dst[RIDX_F(i, j+3, dim)].red   = src[RIDX(i, j+3, dim)].red;
            dst[RIDX_F(i, j+3, dim)].green = src[RIDX(i, j+3, dim)].green;
            dst[RIDX_F(i, j+3, dim)].blue  = src[RIDX(i, j+3, dim)].blue;
        }
    }
}

Answer 1

循环展开的基本思想是在循环体中多次显式地编写计算，而不是让编译器根据循环边界和条件来计算。这样，在滚动循环的情况下，地址在编译时就已知，而不是在运行时计算它们。由于检查边界而导致的分支成本也降低了。因此，每个循环嵌套将具有最小展开阈值，该阈值是其边界和循环体中完成的自然计算的函数，超过该阈值展开将导致加速。展开可能无法在所有情况下提供加速。 LLVM 等编译器允许您使用 -mllvm -unroll-count=U 来指定展开因子，这样您就不必手动展开它。我确信 GCC 有一个等效的参数。您可以编写一个脚本来使用不同的展开因子运行循环，以测量加速并达到最佳展开计数。

滚动版本:

for (x = 0; x < N; x++)
 {
     operation(x);
 }

展开计数 = 2:假设 N 为偶数，则将迭代次数减少一半

for (x = 0; x < N; x+=2)
 {
     operation(x);
     operation(x+1);
 }

展开计数 = 4:将迭代次数减少到四分之一，假设 N 可以被 4 整除

for (x = 0; x < N; x+=4)
 {
     operation(x);
     operation(x+1);
     operation(x+2);
     operation(x+3);
 }

如果索引不能被展开计数整除，则需要一个剩余循环来完成任务，这有​​其自身的开销。

展开计数 = 4:将迭代次数减少到四分之一，当 N 不能被 4 整除时

//main loop
for (x = 0; x <= N-4; x+=4)
 {
     operation(x);
     operation(x+1);
     operation(x+2);
     operation(x+3);
 }
 //residual loop
 for ( ; x < N; x++)
 {
     operation(y);
 }

处理残差计算的另一种方法是使用 Duff's device这基本上是基于开关的循环体实现，以确保循环的最后一次迭代处理残差计算，而不必完全编写单独的循环。