c - C 中的循环优化

Question

我的任务是优化 C 中的特定 for 循环。这是循环:

#define ARRAY_SIZE 10000
#define N_TIMES    600000

for (i = 0; i < N_TIMES; i++)
{
    int j;

    for (j = 0; j < ARRAY_SIZE; j++)
    {
        sum += array[j];
    }
}

我应该使用循环展开、循环拆分和指针来加快速度，但每次我尝试实现某些东西时，程序都不会返回。到目前为止，这是我尝试过的:

for (i = 0; i < N_TIMES; i++) 
{
    int j,k;

    for (j = 0; j < ARRAY_SIZE; j++) 
    {    
        for (k = 0; k < 100; k += 2) 
        {
            sum += array[k];
            sum += array[k + 1];
        }
    } 
}

我不明白为什么程序现在甚至不返回。任何帮助将不胜感激。

Answer 1

第二段代码效率低下而且是错误的，因为它比原始代码增加了更多的值(value)。

循环展开(或在这种情况下减少，因为您可能不想展开一万次迭代循环)将是:

// Ensure ARRAY_SIZE is a multiple of two before trying this.
for (int i = 0; i < N_TIMES; i++)
    for (int j = 0; j < ARRAY_SIZE; j += 2)
        sum += array[j] + array[j+1];

但是，老实说，愚蠢的编译器时代早已一去不复返了。您通常应该将这一级别的微优化留给您的编译器，而您专注于更高级的内容，例如数据结构、算法和人工分析。

最后一个很重要。由于您将相同的数组添加到累加和中的次数为固定次数，因此您实际上只需要数组的总和一次，然后您可以根据需要多次添加该部分和:

int temp = 0;
for (int i = 0; i < ARRAY_SIZE; i++)
    temp += array[i];
sum += temp * N_TIMES;

它仍然是 O(n)，但 n 的乘数要低得多(一而不是六十万)。 可能 gcc 疯狂的-O3 优化级别可以解决这个问题，但我对此表示怀疑。人脑在很多领域仍然可以超越计算机。

现在，无论如何:-)