优化嵌套循环的模式填充数组，帮助编译器产生高效的ARM汇编？

Question

我刚刚接到一个任务，让我重写以下C函数，以帮助ARM编译器生成更高效的汇编代码。有谁知道如何做到这一点？

void some_function(int *data)
{
    int  i, j;

    for (i = 0; i < 64; i++)
    {
        for (j = 0; j < 64; j++)
            data[j + 64*i] = (i + j)/2;
    }
}

Answer 1

首先（正如Jonathan Leffler所提到的）编译器很可能已经做得很好了，所以试图通过编写特定的C代码来优化通常在商业上是有问题的，也就是说，你通过开发时间所损失的钱比通过稍微快一点的代码所能赚到的钱更多。但有时它是值得的；让我们假设这里的情况是这样。

如果你确实进行了优化，请在测量的同时进行。很有可能写出的代码最终不那么优化，因为在微妙的情况下，原本可能的编译器优化被破坏了。另外，优化是否有效以及优化的程度取决于环境，也就是说，在所有潜在的环境中进行测量是必要的。

好吧，在这番话之后，这里是我演示评论中提出的优化的代码，其中一个是Jonathan Leffler提出的。

/* Jonathan Leffler */
void some_function(int *data)
{
    int  i, j;
    int  k = 0;

    for (i = 0; i < 64; i++)
    {
        for (j = 0; j < 64; j++)
        {
            data[k++] = (i + j)/2;
        }
    }
}

/* Yunnosch 1, loop unrolling by 2 */
void some_function(int *data)
{
    int  i, j;

    for (i = 0; i < 64; i++)
    {
        for (j = 0; j < 64; j+=2)
            data[j +     64*i] = (i + j  )/2;
            data[j + 1 + 64*i] = (i + j+1)/2;
    }
}

/* Yunnosch 1 and Jonathan Leffler */
void some_function(int *data)
{
    int  i, j;
    int k=0; /* Jonathan Leffler */

    for (i = 0; i < 64; i++)
    {
        for (j = 0; j < 64; j+=2) /* Yunnosch */
        {
            data[k++] = (i + j  )/2;
            data[k++] = (i + j+1)/2; /* Yunnosch */
        }
    }
}

/* Yunnosch 2, avoiding the /2, including Jonathan Leffler */
/* Well, duh. This is harder than I thought... 
   I admit that this is NOT tested, I want to demonstrate the idea.
   Everybody feel free to help the very grateful me with fixing errors. */
void some_function(int *data)
{
    int  i, j;
    int  k=0;

    for (i = 0; i < 32; i++) /* magic numbers I normally avoid, 32 is 64/2 */
    {
        for (j = 0; j < 32; j++)
        {
            data[k     ] = (i + j);
            data[k+1   ] = (i + j);
            data[k  +64] = (i + j);
            data[k+1+64] = (i + j +1);
            k+=2;
        }
        k+=64;
    }
}

最后一个版本是基于以下可观察到的2x2组模式 在期望的结果中，正如在2D解释中看到的那样。

00 11 ...
01 12 ...

11 22 ...
12 23 ...
.. ..
.. ..
.. ..
´´´´

Answer 2

优化C代码，为特定的编译器processor生成 "更高效的汇编代码 "是你通常不应该做的事情。编写清晰易懂的C代码，让编译器来做优化。

即使你在C代码上做了各种手脚，最后为你的特定编译器processor生成了 "更高效的汇编代码"，但结果可能是一个简单的编译器升级就会毁了整件事情，你不得不重新修改C代码。

对于你的代码这么简单的东西，从一开始就用汇编器代码来写。但要知道，你必须是那个处理器汇编语言的真正专家，才能打败一个像样的编译器。

总之... 如果我们要猜的话，这是我的猜测。

void some_function(int *data)
{
    int  i, j, x;

    for (i = 0; i < 64; i++)
    {
        // Handle even i-values
        x = i/2;
        for (j = 0; j < 64; j += 2)
        {
            *data = x;
            ++data;
            *data = x;
            ++data;
            ++x;        // Increment after writing to data twice
        }

        ++i;

        // Handle odd i-values
        x = i/2;
        for (j = 0; j < 64; j += 2)
        {
            *data = x;
            ++data;
            ++x;        // Increment after writing to data once
            *data = x;
            ++data;
        }
    }
}

我们的想法是： 1) 用指针增量代替数组索引 2) 用指针增量代替数组索引 (i+j)/2 用整数增量。

我有 不 做过任何测量，所以我不能确定这是否是一个好的解决方案。我把这个问题留给OP吧。

---

和上面的想法一样，但要多做一些调整（由 @user3386109 提出）。

void some_function(int *data)
{
    for (int i = 0; i < 32; i++)
    {
        // when i is even, the output is in matched pairs
        int value = i;
        for (int j = 0; j < 32; j++)
        {
            *data++ = value;
            *data++ = value++;
        }

        // when i is odd, the output starts with a singleton
        // followed by matched pairs, and ending with a singleton
        value = i;
        *data++ = value++;
        for (int j = 0; j < 31; j++)
        {
            *data++ = value;
            *data++ = value++;
        }
        *data++ = value;
    }
}