小编典典

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

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

在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;
    }
}

它显示 FLOP/s 的不同值n

性能图表


阅读 204

收藏
2022-02-08

共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:

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


2 x Intel X5482 Harpertown @ 3.2 GHz 英特尔酷睿 i7 870 @ 2.8 GHz 英特尔酷睿 i7 2600K @ 4.4 GHz

2022-02-08