在C语言中的循环优化

Question

在C语言中的循环优化

4

我被委以优化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];
        }
    } 
}

我不明白为什么程序现在连返回值都没有。希望能得到帮助。

- user3698112

1

使用调试器。我会让编译器进行优化。我猜这是一些家庭作业！而第二个程序与第一个程序不同，因为在第二种情况下，您只对“数组”求和到101。 - Basile Starynkevitch

6

您的新程序运行时间大约是原来的100倍。 - T.C.

2

@Sky 我会说大约是原来的100倍，因为它执行了两次 sum +=。 - Déjà vu

2

不是你要求的，但你可以完全消除外部循环。在内部循环中，只需使用 sum += array[j] * N_TIMES; 现在，您可以使用指针算术来获得更高的性能，使用 sum += *array++ * N_TIMES; - Chris Taylor

1

说实话，最好的答案可能是使用现代编译器，将其置于最高优化级别，并查看它生成的汇编代码。 - M.M

显示剩余8条评论

3个回答

3

您的程序没有问题...它会返回结果。只是需要比第一个程序多50倍的时间...

在第一个程序中，您有两个for循环：600,000 * 10,000 = 6,000,000,000次迭代。

在第二个程序中，您有三个for循环：600,000 * 10,000 * 50 = 300,000,000,000次迭代...

- nightshade

循环的数量增加了五十倍，但每个循环的工作量也增加了两倍。因此，所需的时间可能会长大约一百倍。 - paxdiablo

是的，这就是为什么我使用了“迭代”而不是“操作”的原因...通过“迭代”，我指的是仅用于控制循环的变量进行比较/增量的次数... - nightshade

啊，我明白了，我只看了“增加50倍”的部分，以为那是时间。对不起。 - paxdiablo

1

循环展开不能加速循环，反而会减慢速度。在早期，它通过减少条件表达式的数目来提高速度。在现代，由于缓存容量的限制，它会使程序变慢。

这里没有明显的循环分裂用例。要拆分循环，需要找到两个或多个明显的迭代分组。你可以把array[j]乘以i而不是进行外部循环，并声称你已经将内部和外部分离，然后丢弃了外部循环。

C数组索引语法只是作为（一种奇特的语法）指针算术定义的。但我猜你想要的是：

sum += *arrayPointer++;

在适当初始化的情况下，可以替换您使用的j。但我怀疑您不会从中获得任何好处。

根据评论，如果这是真实生活中的话，那么您只需让编译器解决这些问题。

- Tommy

1

你可以部分展开循环并仍然保持在代码缓存范围内。不确定效果是否值得，考虑到缓存的速度有多快。但是你是对的，在一个缓存代码的系统中，展开一个10000次迭代的循环可能会使情况变得更糟。 - paxdiablo

@paxdiabli 可能是真的，但你扩展的循环更有可能将其他东西推出缓存，特别是如果它从页面边界开始。但另一方面，你的分支预测器很可能在评估条件的同时运行下一次迭代，使你没有任何好处。所有这些都归结为高度依赖于架构的权衡，最好留给特定于架构的编译器处理。 - Tommy

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- paxdiablo · Accepted Answer

第二段代码既不高效，也是错误的，因为它添加的值比原始代码多。

循环展开（在这种情况下可能是减少，因为您可能不想展开一万次迭代循环）应该是：

// 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)，但乘数远低于六十万，只有一个。可能gcc的疯狂优化级别-O3可以解决这个问题，但我对此表示怀疑。在很多领域中，人类大脑仍然能够胜过计算机。

至少目前是这样的。