元素级加法在单独循环中比组合循环中快的原因

技术背景

在进行元素级加法操作时，我们常常会遇到这样的疑问：为什么将操作放在单独的循环中执行，会比放在一个组合循环中执行要快呢？这一问题涉及到CPU缓存、内存访问模式等多个方面的知识。理解这个问题，对于优化代码性能具有重要意义。

实现步骤

代码示例

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <ctime>

int main() {
    const int n = 100000;

#ifdef ALLOCATE_SEPERATE
    double *a1 = (double*)malloc(n * sizeof(double));
    double *b1 = (double*)malloc(n * sizeof(double));
    double *c1 = (double*)malloc(n * sizeof(double));
    double *d1 = (double*)malloc(n * sizeof(double));
#else
    double *a1 = (double*)malloc(n * sizeof(double) * 4);
    double *b1 = a1 + n;
    double *c1 = b1 + n;
    double *d1 = c1 + n;
#endif

    //  Zero the data to prevent any chance of denormals.
    memset(a1, 0, n * sizeof(double));
    memset(b1, 0, n * sizeof(double));
    memset(c1, 0, n * sizeof(double));
    memset(d1, 0, n * sizeof(double));

    //  Print the addresses
    std::cout << a1 << std::endl;
    std::cout << b1 << std::endl;
    std::cout << c1 << std::endl;
    std::cout << d1 << std::endl;

    clock_t start = clock();

    int c = 0;
    while (c++ < 10000) {

#if ONE_LOOP
        for (int j = 0; j < n; j++) {
            a1[j] += b1[j];
            c1[j] += d1[j];
        }
#else
        for (int j = 0; j < n; j++) {
            a1[j] += b1[j];
        }
        for (int j = 0; j < n; j++) {
            c1[j] += d1[j];
        }
#endif

    }

    clock_t end = clock();
    std::cout << "seconds = " << (double)(end - start) / CLOCKS_PER_SEC << std::endl;

    system("pause");
    return 0;
}

测试结果

在不同配置下进行测试，结果如下：

#define ALLOCATE_SEPERATE
#define ONE_LOOP
00600020
006D0020
007A0020
00870020
seconds = 6.206

#define ALLOCATE_SEPERATE
//#define ONE_LOOP
005E0020
006B0020
00780020
00850020
seconds = 2.116

//#define ALLOCATE_SEPERATE
#define ONE_LOOP
00570020
00633520
006F6A20
007B9F20
seconds = 1.894

//#define ALLOCATE_SEPERATE
//#define ONE_LOOP
008C0020
00983520
00A46A20
00B09F20
seconds = 1.993

从结果可以看出，在某些情况下，单独循环的执行时间明显短于组合循环。

核心代码

组合循环

for (int j = 0; j < n; j++) {
    a1[j] += b1[j];
    c1[j] += d1[j];
}

单独循环

for (int j = 0; j < n; j++) {
    a1[j] += b1[j];
}
for (int j = 0; j < n; j++) {
    c1[j] += d1[j];
}

最佳实践

考虑数据对齐

数组的分配方式可能会导致数据对齐问题，从而影响缓存性能。尽量避免多个数组的访问落在同一缓存路径上，可以通过将数组打包在一起的方式来打破对齐。

减少缓存冲突

单独循环可以减少缓存的活动，使得处理器更容易满足内存需求。当数据无法全部存放在缓存中时，组合循环可能会导致频繁的缓存换页，从而降低性能。

区分栈和堆操作

对于在栈上分配的数据，组合循环和单独循环的性能差异可能较小；而对于在堆上分配的数据，单独循环通常更高效。因此，在设计算法时，应根据数据的分配位置选择合适的循环结构。

常见问题

无法复现性能差异

有些情况下，可能无法复现单独循环比组合循环快的结果。这可能是由于硬件配置、编译器优化等因素导致的。可以尝试不同的编译器选项、调整数组大小等方法来进行测试。

对MFLOPS指标的疑问

MFLOPS（每秒百万浮点运算次数）通常用于衡量浮点运算的性能，但在这个问题中，重点是内存访问，因此MFLOPS可能不是一个相关的指标。可以通过减少浮点运算的时间，来更准确地测试内存访问时间。