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

Question

a1 , b1 , c1 , and d1 point to heap memory, and my numerical code has the following core loop.

 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 上编译，并在 Intel Core 2 Duo (x64) 上为 32 位启用了 SSE2 并进行了全面优化，第一个示例需要 5.5 秒，双循环示例只需 1.9 秒。

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

 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。

原文由 Johannes Gerer 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

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

如果我猜对了您如何分配数组，它们 _很可能与 page line 对齐_。

这意味着您在每个循环中的所有访问都将落在相同的缓存方式上。然而，英特尔处理器拥有 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 个英特尔至强 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 提到了 缓存库冲突。 （那个链接是关于 Sandy Bridge 的，但这个想法应该仍然适用于 Core 2。）

区域 3：

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

区域 4：

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

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

区域 5：

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

---

原文由 Mysticial 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

我无法复制这里讨论的结果。

我不知道是否应该归咎于糟糕的基准代码，或者是什么，但是这两种方法在我的机器上使用以下代码的误差在 10% 以内，并且一个循环通常比两个循环稍微快一点——就像你想的那样预计。

数组大小范围从 2^16 到 2^24，使用 8 个循环。我很小心地初始化了源数组，所以 += 分配没有要求 FPU 添加解释为双精度的内存垃圾。

I played around with various schemes, such as putting the assignment of b[j] , d[j] to InitToZero[j] inside the loops, and also with using += b[j] = 1 和 += d[j] = 1 ，我得到了相当一致的结果。

如您所料，在循环内使用 InitToZero[j] 初始化 b 和 d --- 给组合方法带来了优势，因为它们是回溯到 -分配给 a 和 c ，但仍在 10% 以内。去搞清楚。

硬件是 Dell XPS 8500 ，具有第 3 代 Core i7 @ 3.4 GHz 和 8 GB 内存。对于 2^16 到 2^24，使用 8 个循环，累积时间分别为 44.987 和 40.965。 Visual C++ 2010，完全优化。

PS：我将循环更改为倒数到零，并且组合方法稍微快一些。抓着我的头。请注意新的数组大小和循环计数。

 // MemBufferMystery.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <cmath>
#include <string>
#include <time.h>

#define  dbl    double
#define  MAX_ARRAY_SZ    262145    //16777216    // AKA (2^24)
#define  STEP_SZ           1024    //   65536    // AKA (2^16)

int _tmain(int argc, _TCHAR* argv[]) {
    long i, j, ArraySz = 0,  LoopKnt = 1024;
    time_t start, Cumulative_Combined = 0, Cumulative_Separate = 0;
    dbl *a = NULL, *b = NULL, *c = NULL, *d = NULL, *InitToOnes = NULL;

    a = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    b = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    c = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    d = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    InitToOnes = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    // Initialize array to 1.0 second.
    for(j = 0; j< MAX_ARRAY_SZ; j++) {
        InitToOnes[j] = 1.0;
    }

    // Increase size of arrays and time
    for(ArraySz = STEP_SZ; ArraySz<MAX_ARRAY_SZ; ArraySz += STEP_SZ) {
        a = (dbl *)realloc(a, ArraySz * sizeof(dbl));
        b = (dbl *)realloc(b, ArraySz * sizeof(dbl));
        c = (dbl *)realloc(c, ArraySz * sizeof(dbl));
        d = (dbl *)realloc(d, ArraySz * sizeof(dbl));
        // Outside the timing loop, initialize
        // b and d arrays to 1.0 sec for consistent += performance.
        memcpy((void *)b, (void *)InitToOnes, ArraySz * sizeof(dbl));
        memcpy((void *)d, (void *)InitToOnes, ArraySz * sizeof(dbl));

        start = clock();
        for(i = LoopKnt; i; i--) {
            for(j = ArraySz; j; j--) {
                a[j] += b[j];
                c[j] += d[j];
            }
        }
        Cumulative_Combined += (clock()-start);
        printf("\n %6i miliseconds for combined array sizes %i and %i loops",
                (int)(clock()-start), ArraySz, LoopKnt);
        start = clock();
        for(i = LoopKnt; i; i--) {
            for(j = ArraySz; j; j--) {
                a[j] += b[j];
            }
            for(j = ArraySz; j; j--) {
                c[j] += d[j];
            }
        }
        Cumulative_Separate += (clock()-start);
        printf("\n %6i miliseconds for separate array sizes %i and %i loops \n",
                (int)(clock()-start), ArraySz, LoopKnt);
    }
    printf("\n Cumulative combined array processing took %10.3f seconds",
            (dbl)(Cumulative_Combined/(dbl)CLOCKS_PER_SEC));
    printf("\n Cumulative seperate array processing took %10.3f seconds",
        (dbl)(Cumulative_Separate/(dbl)CLOCKS_PER_SEC));
    getchar();

    free(a); free(b); free(c); free(d); free(InitToOnes);
    return 0;
}

我不确定为什么决定 MFLOPS 是一个相关指标。虽然我的想法是专注于内存访问，所以我试图最小化浮点计算时间。我离开了 += ，但我不知道为什么。

没有计算的直接分配将是对内存访问时间的更清晰的测试，并且将创建一个与循环计数无关的统一测试。也许我在谈话中遗漏了一些东西，但值得三思。如果将加号排除在作业之外，则累积时间几乎相同，均为 31 秒。

原文由 user1899861 发布，翻译遵循 CC BY-SA 3.0 许可协议