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




5 Answers

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

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

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

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

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

请注意,我的初始问题是在n = 100.000 。 这一点(偶然)表现出特殊的行为:

  1. 它在一个和两个循环版本之间存在最大的差异(几乎是三分之一)

  2. 这是唯一的一点,其中一个循环(即连续分配)胜过双循环版本。 (这使得Mysticial的答案成为可能。)

使用初始化数据的结果:

使用未初始化数据的结果(这是Mysticial测试的):

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

提案

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

c++ c performance compiler-optimization vectorization

假设a1b1c1d1指向堆内存,我的数字代码具有以下核心循环。

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。)




想象一下,你正在使用一台机器,其中n只是正确的值,它只能在内存中同时保存两个阵列,但是通过磁盘缓存可用的总内存仍足以容纳所有四个。

假设一个简单的LIFO缓存策略,这段代码:

for(int j=0;j<n;j++){
    a[j] += b[j];
}
for(int j=0;j<n;j++){
    c[j] += d[j];
}

首先会导致ab被加载到RAM中,然后完全在RAM中工作。 当第二个循环开始时, cd将从磁盘加载到RAM中并进行操作。

另一个循环

for(int j=0;j<n;j++){
    a[j] += b[j];
    c[j] += d[j];
}

每次循环时 ,它会在其他两个数组中分页出两个数组和页面。 这显然会慢得多。

您可能没有在测试中看到磁盘缓存,但您可能会看到其他形式的缓存的副作用。

这里似乎有一点混乱/误解,所以我将尝试用一个例子来详细说明。

n = 2 ,我们正在使用字节。 因此,在我的场景中,我们只有4个字节的RAM ,其余的内存明显变慢(比如说访问时间长100倍)。

假设一个相当愚蠢的缓存策略, 如果该字节不在缓存中,把它放在那里并获得以下字节,当我们在它时你会得到这样的场景:

  • for(int j=0;j<n;j++){
     a[j] += b[j];
    }
    for(int j=0;j<n;j++){
     c[j] += d[j];
    }
  • 缓存a[0]a[1]然后b[0]b[1]并在缓存中设置a[0] = a[0] + b[0] - 缓存中现在有4个字节, a[0], a[1]b[0], b[1] 。 成本= 100 + 100。

  • 在缓存中设置a[1] = a[1] + b[1] 。 成本= 1 + 1。
  • 重复cd
  • 总费用= (100 + 100 + 1 + 1) * 2 = 404

  • for(int j=0;j<n;j++){
     a[j] += b[j];
     c[j] += d[j];
    }
  • 缓存a[0]a[1]然后b[0]b[1]并在缓存中设置a[0] = a[0] + b[0] - 缓存中现在有4个字节, a[0], a[1]b[0], b[1] 。 成本= 100 + 100。

  • 从缓存和缓存c[0]c[1]弹出a[0], a[1], b[0], b[1] c[1]然后d[0]d[1]并设置c[0] = c[0] + d[0]缓存中的c[0] = c[0] + d[0] 。 成本= 100 + 100。
  • 我怀疑你开始明白我要去哪里了。
  • 总费用= (100 + 100 + 100 + 100) * 2 = 800

这是一个经典的缓存捶打场景。




我不能复制这里讨论的结果。

我不知道糟糕的基准代码是否应该受到责备,或者是什么,但是这两种方法在我的机器上使用下面的代码在10%之内,并且一个循环通常只比两个快一点 - 就像你一样期望。

阵列大小范围从2 ^ 16到2 ^ 24,使用八个循环。 我小心地初始化了源数组,所以+=赋值并没有要求FPU添加被解释为double的内存垃圾。

我玩了各种方案,例如将b[j]d[j]InitToZero[j]放在循环内的InitToZero[j] ,并使用+= b[j] = 1+= d[j] = 1 ,我得到了相当一致的结果。

正如您所料,使用InitToZero[j]在循环内初始化bd使得组合方法具有优势,因为它们在分配给ac之前背靠背地完成,但仍然在10%之内。 去搞清楚。

硬件是戴尔XPS 8500,具有第3代Core i7 @ 3.4 GHz和8 GB内存。 对于2 ^ 16到2 ^ 24,使用八个循环,累积时间分别为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秒。




第一个循环交替写入每个变量。 第二个和第三个只是元素大小的小跳跃。

尝试用笔和纸隔开20厘米写两条平行的20个十字线。 尝试完成一个然后另一个行,然后通过交替地在每一行中写一个十字来尝试另一次。




它可能是旧的C ++和优化。在我的电脑上,我获得了几乎相同的速度:

一个循环:1.577毫秒

两个循环:1.507毫秒

我在具有16 GB RAM的E5-1620 3.5 GHz处理器上运行Visual Studio 2015。






Related