为什么在单独的循环中元素添加比在组合循环中快得多？

假设a1 ， b1 ， c1和d1指向堆内存，我的数字代码具有以下核心循环。

const int n = 100000;

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

该循环通过另一个外部for循环执行 10,000 次。为了加快速度，我将代码更改为：

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

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

在 MS Visual C ++ 10.0 上进行了全面优化编译，在Intel Core 2 Duo（x64）上为 32 位启用了SSE2 ，第一个示例需要 5.5 秒，双循环示例仅需 1.9 秒。我的问题是:(请参考我在底部的改写问题）

PS：我不确定，如果这有帮助：

第一个循环的反汇编基本上看起来像这样（这个块在整个程序中重复大约五次）：

movsd       xmm0,mmword ptr [edx+18h]
addsd       xmm0,mmword ptr [ecx+20h]
movsd       mmword ptr [ecx+20h],xmm0
movsd       xmm0,mmword ptr [esi+10h]
addsd       xmm0,mmword ptr [eax+30h]
movsd       mmword ptr [eax+30h],xmm0
movsd       xmm0,mmword ptr [edx+20h]
addsd       xmm0,mmword ptr [ecx+28h]
movsd       mmword ptr [ecx+28h],xmm0
movsd       xmm0,mmword ptr [esi+18h]
addsd       xmm0,mmword ptr [eax+38h]

双循环示例的每个循环都会生成此代码（以下块重复约三次）：

addsd       xmm0,mmword ptr [eax+28h]
movsd       mmword ptr [eax+28h],xmm0
movsd       xmm0,mmword ptr [ecx+20h]
addsd       xmm0,mmword ptr [eax+30h]
movsd       mmword ptr [eax+30h],xmm0
movsd       xmm0,mmword ptr [ecx+28h]
addsd       xmm0,mmword ptr [eax+38h]
movsd       mmword ptr [eax+38h],xmm0
movsd       xmm0,mmword ptr [ecx+30h]
addsd       xmm0,mmword ptr [eax+40h]
movsd       mmword ptr [eax+40h],xmm0

事实证明这个问题没有关系，因为行为严重依赖于数组（n）和 CPU 缓存的大小。因此，如果有进一步的兴趣，我重新提出这个问题：

您能否提供一些有关导致不同缓存行为的详细信息，如下图中的五个区域所示？

通过为这些 CPU 提供类似的图表，指出 CPU / 缓存架构之间的差异也可能是有趣的。

PPS：这是完整的代码。它使用TBB Tick_Count来实现更高分辨率的时序，可以通过不定义TBB_TIMING宏来禁用它：

#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>

//#define TBB_TIMING

#ifdef TBB_TIMING   
#include <tbb/tick_count.h>
using tbb::tick_count;
#else
#include <time.h>
#endif

using namespace std;

//#define preallocate_memory new_cont

enum { new_cont, new_sep };

double *a1, *b1, *c1, *d1;


void allo(int cont, int n)
{
    switch(cont) {
      case new_cont:
        a1 = new double[n*4];
        b1 = a1 + n;
        c1 = b1 + n;
        d1 = c1 + n;
        break;
      case new_sep:
        a1 = new double[n];
        b1 = new double[n];
        c1 = new double[n];
        d1 = new double[n];
        break;
    }

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

void ff(int cont)
{
    switch(cont){
      case new_sep:
        delete[] b1;
        delete[] c1;
        delete[] d1;
      case new_cont:
        delete[] a1;
    }
}

double plain(int n, int m, int cont, int loops)
{
#ifndef preallocate_memory
    allo(cont,n);
#endif

#ifdef TBB_TIMING   
    tick_count t0 = tick_count::now();
#else
    clock_t start = clock();
#endif

    if (loops == 1) {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++){
                a1[j] += b1[j];
                c1[j] += d1[j];
            }
        }
    } else {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                a1[j] += b1[j];
            }
            for (int j = 0; j < n; j++) {
                c1[j] += d1[j];
            }
        }
    }
    double ret;

#ifdef TBB_TIMING   
    tick_count t1 = tick_count::now();
    ret = 2.0*double(n)*double(m)/(t1-t0).seconds();
#else
    clock_t end = clock();
    ret = 2.0*double(n)*double(m)/(double)(end - start) *double(CLOCKS_PER_SEC);
#endif

#ifndef preallocate_memory
    ff(cont);
#endif

    return ret;
}


void main()
{   
    freopen("C:\\test.csv", "w", stdout);

    char *s = " ";

    string na[2] ={"new_cont", "new_sep"};

    cout << "n";

    for (int j = 0; j < 2; j++)
        for (int i = 1; i <= 2; i++)
#ifdef preallocate_memory
            cout << s << i << "_loops_" << na[preallocate_memory];
#else
            cout << s << i << "_loops_" << na[j];
#endif

    cout << endl;

    long long nmax = 1000000;

#ifdef preallocate_memory
    allo(preallocate_memory, nmax);
#endif

    for (long long n = 1L; n < nmax; n = max(n+1, long long(n*1.2)))
    {
        const long long m = 10000000/n;
        cout << n;

        for (int j = 0; j < 2; j++)
            for (int i = 1; i <= 2; i++)
                cout << s << plain(n, m, j, i);
        cout << endl;
    }
}

（它显示不同n值的 FLOP / s。）

在此处输入图像描述

答案

在进一步分析这一点后，我相信这是（至少部分地）由四个指针的数据对齐引起的。这将导致某种程度的缓存库 / 方式冲突。

如果我已经正确猜出了如何分配数组，它们很可能与页面行对齐 。

这意味着每个循环中的所有访问都将采用相同的缓存方式。但是，英特尔处理器暂时具有 8 路 L1 缓存关联性。但实际上，表现并不完全一致。访问 4 种方式仍然比说 2 种方式慢。

编辑：它实际上看起来像你分别分配所有数组。通常，当请求这样大的分配时，分配器将从 OS 请求新的页面。因此，大量分配很可能出现在与页边界相同的偏移处。

这是测试代码：

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
    cout << a1 << endl;
    cout << b1 << endl;
    cout << c1 << endl;
    cout << d1 << 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();
    cout << "seconds = " << (double)(end - start) / CLOCKS_PER_SEC << endl;

    system("pause");
    return 0;
}

基准结果：

编辑：实际 Core 2 架构机器上的结果：

2 x Intel Xeon X5482 Harpertown @ 3.2 GHz：

#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

观察：

一个循环6.206 秒 ，两个循环2.116 秒 。这完全再现了 OP 的结果。
在前两个测试中，阵列是分开分配的。您会注意到它们都具有相对于页面的相同对齐方式。
在后两个测试中，阵列被打包在一起以打破对齐。在这里你会发现两个循环都更快。此外，第二个（双）循环现在是您通常所期望的较慢的循环。

正如 @Stephen Cannon 在评论中指出的那样，这种对齐很可能会导致加载 / 存储单元或缓存中的错误混叠 。我用 Google 搜索，发现英特尔实际上有一个硬件计数器用于部分地址别名停顿：

http://software.intel.com/sites/products/documentation/doclib/stdxe/2013/~amplifierxe/pmw_dp/events/partial_address_alias.html

5 个地区 - 解释

1 区：

这个很容易。数据集非常小，以至于性能受到诸如循环和分支之类的开销的支配。

2 区：

~~这里，随着数据大小的增加，相对开销量下降，性能 “饱和”。这里有两个循环较慢，因为它有两倍的循环和分支开销。~~

我不确定究竟发生了什么...... 当 Agner Fog 提到缓存库冲突时， Alignment 仍然会起作用。（那个链接是关于 Sandy Bridge 的，但这个想法仍应适用于 Core 2.）

3 区：

此时，数据不再适合 L1 缓存。因此性能受到 L1 <-> L2 缓存带宽的限制。

4 区：

单循环中的性能下降是我们所观察到的。并且如上所述，这是由于对齐（最有可能）导致处理器加载 / 存储单元中的错误混叠停顿。

但是，为了发生错误混叠，数据集之间必须有足够大的步幅。这就是为什么你在 3 区没有看到这个。

5 区：

此时，没有任何东西适合缓存。所以你受内存带宽的限制。

2 x Intel X5482 Harpertown @ 3.2 GHz 英特尔酷睿i7 870 @ 2.8 GHz 英特尔酷睿i7 2600K @ 4.4 GHz

好的，正确的答案肯定要对 CPU 缓存做一些事情。但是使用缓存参数可能非常困难，尤其是没有数据。

有许多答案，导致了很多讨论，但让我们面对现实：缓存问题可能非常复杂，并不是一维的。它们在很大程度上取决于数据的大小，所以我的问题是不公平的：事实证明它在缓存图中非常有趣。

@Mysticial 的回答让很多人（包括我）相信，可能是因为它是唯一一个似乎依赖于事实的人，但它只是事实的一个 “数据点”。

这就是为什么我结合他的测试（使用连续分配和单独分配）和 @James 答案的建议。

下图显示，根据所使用的确切方案和参数，大多数答案，特别是对问题和答案的大多数评论可以被认为是完全错误或真实的。

请注意，我的初始问题是在n = 100.000 。这一点（偶然）表现出特殊的行为：

它在一个和两个循环版本之间存在最大的差异（几乎是三分之一）
这是唯一的一点，其中一个循环（即连续分配）胜过双循环版本。（这使得 Mysticial 的答案成为可能。）

使用初始化数据的结果：

在此输入图像描述

使用未初始化数据的结果（这是 Mysticial 测试的）：

在此输入图像描述

这是一个难以解释的问题：初始化数据，分配一次并重复用于以下每个不同矢量大小的测试用例：

在此输入图像描述

提案

应该要求 Stack Overflow 上的每个低级性能相关问题为整个缓存相关数据大小提供 MFLOPS 信息！浪费每个人的时间来思考答案，特别是在没有这些信息的情况下与他人讨论答案。

第二个循环涉及更少的缓存活动，因此处理器更容易满足内存需求。

答案

编辑： 实际 Core 2 架构机器上的结果：

5 个地区 - 解释

提案

编辑：实际 Core 2 架构机器上的结果：