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


Answers

好的,正确的答案肯定是要对CPU缓存做些什么。 但要使用缓存参数可能相当困难,尤其是没有数据。

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

@ Mysticial的回答说服了很多人(包括我),可能是因为这是唯一依赖事实的人,但这只是真相的一个“数据点”。

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

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

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

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

  2. 这是唯一的一点,即单循环(即连续分配)击败双循环版本。 (这完全可以使Mysticial的答案成为可能。)

使用初始化数据的结果:

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

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

提案

应该要求每个关于堆栈溢出的低级性能相关问题,以便为整个高速缓存相关数据大小提供MFLOPS信息! 这是浪费每个人的时间来思考答案,特别是与他人讨论他们没有这些信息。

Question

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

const int n = 100000;

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

该循环通过另一个外循环执行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。)




第一个循环交替写入每个变量。 第二个和第三个只会使元素大小变小。

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




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

我不知道糟糕的基准测试代码是否应该归咎于什么,但是这两种方法在我的机器上使用下面的代码在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%以内。 去搞清楚。

硬件是Dell XPS 8500 ,第三代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秒处几乎相同。




想象一下,你正在使用一台机器,其中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个字节的缓存 ,其余的内存明显更慢(比如访问时间延长了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] - 缓存中现在有四个字节, 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] - 缓存中现在有四个字节, a[0], a[1]b[0], b[1] 。 成本= 100 + 100。

  • 从缓存和缓存c[0]c[1]然后d[0]d[1]弹出a[0], a[1], b[0], b[1] ,并设置c[0] = c[0] + d[0]缓存中的c[0] = c[0] + d[0] 。 成本= 100 + 100。
  • 我怀疑你正在开始看到我要去的地方。
  • 总成本= (100 + 100 + 100 + 100) * 2 = 800

这是一个典型的缓存颠簸场景。






Links