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

Question

假设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];
}

编译于 Microsoft Visual C++ 10.0完全优化和SSE2在 Intel Core 2 上启用 32 位Duo(x64)，第一个例子需要5.5秒，双循环例子只需要1.9秒。

第一个循环的反汇编基本上是这样的(这个 block 在整个程序中重复了大约五次):

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]

双循环示例的每个循环都会产生这段代码(下面的代码块重复了大约 3 次):

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/缓存架构之间的差异可能也很有趣。

这是完整的代码。它使用 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。

Answer 1

经过进一步分析，我认为这是(至少部分)由四指针的数据对齐引起的。这将导致某种程度的缓存库/路冲突。

如果我猜对了您分配数组的方式，它们很可能与页面行对齐。

这意味着您在每个循环中的所有访问都将落在相同的缓存方式上。然而，英特尔处理器拥有 8 路 L1 缓存关联性已有一段时间了。但实际上，性能并不完全一致。访问 4 路仍然比 2 路慢。

编辑:实际上看起来您正在分别分配所有数组。通常当请求如此大的分配时，分配器会从操作系统请求新的页面。因此，大型分配很有可能出现在与页面边界相同的偏移量处。

这是测试代码:

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 在评论中指出的那样，这种对齐很可能会导致加载/存储单元或缓存中的错误别名。我搜索了一下，发现英特尔实际上有一个硬件计数器用于部分地址别名停顿:

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

---

5 个区域 - 说明

区域 1:

这个很简单。数据集非常小，性能主要受循环和分支等开销支配。

区域 2:

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

我不确定这里到底发生了什么...正如 Agner Fog 提到的 cache bank conflicts 对齐仍然可以发挥作用. (那个链接是关于 Sandy Bridge 的，但这个想法应该仍然适用于 Core 2。)

区域 3:

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

第 4 区:

我们观察到的是单循环中的性能下降。如前所述，这是由于对齐(很可能)导致假别名在处理器加载/存储单元中停止。

但是，为了发生错误的混叠，数据集之间必须有足够大的步幅。这就是为什么您在区域 3 中看不到它的原因。

5 区:

此时，缓存中没有任何内容。所以你会受到内存带宽的限制。

---