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

假设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上进行了全面优化并在SSE2 Duo（x64）上为32位启用了Intel Core 2的情况下进行编译，第一个示例花费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个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提到cache bank conflicts一样，对齐仍然可以发挥作用。 （该链接是关于Sandy Bridge的，但该想法仍应适用于Core2。）

区域3：

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

区域4：

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

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

区域5：

在这一点上，没有什么适合缓存。因此，您受内存带宽的束缚。

关于c++ - 为什么单独循环中的元素加法比组合循环中的要快得多？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/19991953/