c - 在循环中使用 2 个变量对数组求和(并运行循环 N/2 次)比仅使用一个变量的运行时间更快。为什么？

Question

我有一个大小为 SIZE 的数组。我通过两种方式添加它的元素。
1. 在循环中获取 2 个变量，一个从索引 0 运行，另一个从 SIZE-1 运行，直到它们相交。
2. 取 1 个变量并从 0 运行到 SIZE-1。
为什么第一个方法的运行速度比第二个方法快得多。

我在 GCC 上运行它。
我能看到的唯一区别是比较的次数。

使用 2 个变量

long sum2ptr(int* x, long n) {
    long sum = 0;
    for (int i = 0, j = n-1; i < j; i++, j--) {
        sum += x[i];
        sum += x[j];
    }
    return sum;
}

输出 0.43

使用 1 个变量

long sum1ptr(int* x, long n) {
    long sum = 0;
    for (int i = 0; i < n; i++)
        sum += x[i];
    return sum;
}  

输出 0.50

通用代码

int main(void)
{
    long SIZE = 100000000;
    double start, time = 0;
    int *a = (int*)malloc(SIZE * sizeof(int));

    for (int i = 0; i < SIZE; i++) 
        a[i] = ((i * 2) + 3) % SIZE;

    start = clock();
    sum2ptr(a, SIZE);//called sum1ptr() on second run.
    time += (clock() - start) / CLOCKS_PER_SEC;

    printf("%lf", time);
    return 0;
}

我预计两者之间的差异可以忽略不计。如此巨大的差异背后的真正原因是什么。

Answer 1

执行时间取决于执行指令的数量。指令用于内存访问(a[i])、求和(sum+=a[i])和循环管理(I++、分支)。

如果迭代次数减少，循环管理就会减少，执行时间也会相应减少。您正在考虑的是一种称为“循环展开”的经典代码优化方法的特例。

这是您的代码的修改版本。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>


#define profile(x, fn, n) {\
    start = clock(); \
    sum = 0; \
    fn(x, n); \
    time = (clock() - start) / CLOCKS_PER_SEC; \
}

#define sum2ptr(x, n) {\
    for (int i = 0, j = n-1; i < j; i++, j--) { \
        sum += x[i]; \
        sum += x[j]; \
    } \
}


#define sum1ptr(x, n) {\
    for (int i = 0; i < n; i++) \
    sum += x[i]; \
}

#define sum3ptr(x, n) {\
    for (int i = 0; i < n; i+=4){               \
    sum += x[i]; \
    sum += x[i+1]; \
    sum += x[i+2]; \
    sum += x[i+3]; \
  } \
}

#define SIZE 100000000

int main(void)
{
    double start, time = 0;
    int sum = 0;
    int *a = (int*)malloc(SIZE * sizeof(int));

    for (int i = 0; i < SIZE; i++) 
        a[i] = ((i * 2) + 3) % SIZE;

    profile(a, sum1ptr, SIZE);
    printf("%lf (regular)\n", time);
    profile(a, sum2ptr, SIZE);
    printf("%lf (unrolled twice)\n", time);
    profile(a, sum3ptr, SIZE);
    printf("%lf (unrolled 4)\n", time);

    return 0;
}

我添加了第三个循环，“展开”四次(以更经典的方式)。

使用 gcc -O 编译这是结果。

0.030777 (regular)
0.016292 (unrolled twice)
0.008050 (unrolled 4)

如您所见，展开非常有效。由于优化 (-O)，结果甚至比您的更好。没有优化标志，我们得到

0.222738 (regular)
0.174113 (unrolled twice)
0.164410 (unrolled 4)

差异减少了，这可能就是您添加的内容(但您永远不应该在不优化代码的情况下衡量性能)。