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


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

const int n = 100000;

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

该循环通过另一个外部执行10,000次 for 循环。为了加快速度,我将代码更改为:

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 在a上启用32位 英特尔酷睿2 Duo(x64),第一个示例需要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;
    }
}

(它显示了不同值的FLOP / s n。)

enter image description here


1996
2017-12-17 20:40


起源


可能是操作系统在每次访问物理内存时搜索物理内存时速度变慢,并且在对同一成员库进行二次访问时具有缓存等功能。 - AlexTheo
您是否正在进行优化编译?这看起来像O2的很多asm代码...... - Luchian Grigore
只是为了挑剔,这两个代码片段由于可能重叠的指针而不相等。 C99有 restrict这种情况的关键字。我不知道MSVC是否有类似的东西。当然,如果这是问题,则SSE代码将不正确。 - user510306
这可能与内存别名有关。有一个循环, d1[j] 可能会混淆 a1[j],因此编译器可能会撤消执行某些内存优化。如果在两个循环中将文章分离到内存中,则不会发生这种情况。 - rturrado
@RocketRoy在你指责人们制造东西之前,你为什么不试着注意一些细节呢?你在答案中说你无法重现它。这个问题是5岁。你有没有考虑过那时处理器有可能改进?看看我的答案,它表明它在Core 2上重现了很长时间,但在Nehalem及其后的情况下则不那么重要。 - Mysticial


答案:


在进一步分析这一点后,我相信这是(至少部分地)由四个指针的数据对齐引起的。这将导致某种程度的缓存库/方式冲突。

如果我已经正确地猜到了你如何分配你的数组,那么他们 很可能与页面行对齐

这意味着每个循环中的所有访问都将采用相同的缓存方式。但是,英特尔处理器暂时具有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 x 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所提到的那样,对齐仍然可以发挥作用 缓存银行冲突。 (那个链接是关于Sandy Bridge的,但这个想法仍应适用于Core 2.)

3区:

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

4区:

单循环中的性能下降是我们所观察到的。如上所述,这是由于(最有可能)导致的对齐 错误的别名 处理器加载/存储单元中的停顿。

但是,为了发生错误混叠,数据集之间必须有足够大的步幅。这就是为什么你在3区没有看到这个。

5区:

此时,没有任何东西适合缓存。所以你受内存带宽的限制。


2 x Intel X5482 Harpertown @ 3.2 GHz Intel Core i7 870 @ 2.8 GHz Intel Core i7 2600K @ 4.4 GHz


1546
2017-12-17 21:17



+1:我认为这就是答案。与所有其他答案所说的相反,它不是关于单循环变体固有地具有更多缓存未命中,而是关于导致缓存未命中的阵列的特定对齐。 - Oliver Charlesworth
这个;一个 错误的别名 失速是最可能的解释。 - Stephen Canon
@VictorT。我使用了OP链接的代码。它生成一个.css文件,我可以在Excel中打开并从中生成图表。 - Mysticial
@Nawaz页面通常为4KB。如果你查看我打印出来的十六进制地址,单独分配的测试都具有相同的模4096.(从4KB边界的起点开始是32字节)也许GCC没有这种行为。这可以解释为什么你没有看到差异。 - Mysticial
对任何有兴趣的人 这里有很好的内存对齐读数 和 这里有几个  途中的链接  数据缓存在内存中 - New Alexandria


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

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

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

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

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

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

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

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

使用初始化数据的结果:

Enter image description here

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

Enter image description here

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

Enter image description here

提案

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


195
2017-12-18 01:29



+1尼斯分析。我并不打算首先将数据保留为未初始化状态。事实上,分配器无论如何都将它归零。所以初始化的数据才是最重要的。我刚刚用结果编辑了我的答案 实际 核心2架构机器,它们更接近您观察的内容。另一件事是我测试了一系列尺寸 n 它显示了相同的性能差距 n = 80000, n = 100000, n = 200000等等...... - Mysticial
@Mysticial我认为操作系统在向进程提供新页面时实现页面清零,以避免可能的进程间窥探。 - v.oddou


第二个循环涉及更少的缓存活动,因此处理器更容易满足内存需求。


63
2017-12-17 20:47



您是说第二种变体会导致缓存未命中次数减少?为什么? - Oliver Charlesworth
@Oli:在第一个版本中,处理器需要一次访问四个内存行 - a[i], b[i], c[i] 和 d[i] 在第二个变体中,它只需要两个。这使得在添加时重新填充这些线条更加可行。 - Puppy
但只要数组不在高速缓存中冲突,每个变体都需要从/到主存储器的完全相同的读写次数。所以结论是(我认为)这两个阵列碰巧一直在碰撞。 - Oliver Charlesworth
我不跟随。每条指令(即每个实例) x += y),有两个读和一个写。这两种变体都是如此。因此,高速缓存< - > CPU带宽要求是相同的。只要没有冲突,缓存< - > RAM带宽要求也是一样的.. - Oliver Charlesworth
如中所述 stackoverflow.com/a/1742231/102916,Pentium M的硬件预取可以跟踪12个不同的正向流(我希望以后的硬件至少能够有效)。循环2仍然只读取四个流,因此完全在该限制内。 - Brooks Moses


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

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

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

首先会导致 a 和 b 加载到RAM然后完全在RAM中工作。当第二个循环开始时, c 和 d 然后将从磁盘加载到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。
  • 重复一遍 c 和 d
  • 总费用= (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。

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

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


37
2017-12-18 01:36



这是不正确的。对数组的特定元素的引用不会导致整个数组从磁盘(或从非缓存的内存)中分页;只有相关的页面或缓存行被分页。 - Brooks Moses
@Brooks摩西 - 如果你走遍整个阵列,正如在这里发生的那样,那么它将会发生。 - OldCurmudgeon
嗯,是的,但这就是整个操作中发生的事情,而不是每次循环时发生的事情。你声称第二种形式“将在循环中每次分页两个数组和其他两个页面”,这就是我所反对的。无论整个数组的大小如何,在这个循环的中间,你的RAM将从四个数组中的每个数组中保存一个页面,并且在循环完成之后,任何内容都不会被分页。 - Brooks Moses
在特定的情况下 n只是一个正确的值,它可以同时在内存中保存两个数组 然后访问的所有元素 四 一个循环中的数组肯定会最终颠倒。 - OldCurmudgeon
你为什么要整整留下2页 a1 和 b1 对于第一个作业,而不仅仅是每个作业的第一页? (你假设5字节的页面,所以页面是你的RAM的一半吗?这不只是缩放,这完全不同于真正的处理器。) - Brooks Moses


这不是因为代码不同,而是因为缓存:RAM比CPU寄存器慢,CPU内部有缓存,以避免每次变量更改时写入RAM。但是缓存并不像RAM那么大,因此,它只映射了一小部分。

第一个代码修改在每个循环中交替它们的远程存储器地址,因此需要连续地使高速缓存无效。

第二个代码不会交替:它只是在相邻地址上流动两次。这使得所有作业都在缓存中完成,仅在第二个循环开始后使其无效。


27
2017-12-17 20:49



为什么这会导致缓存连续失效? - Oliver Charlesworth
@OliCharlesworth:将缓存视为连续范围的内存地址的硬拷贝。如果您假装访问不属于它们的地址,则必须重新加载缓存。如果缓存中的某些内容已被修改,则必须将其写回RAM中,否则它将丢失。在示例代码中,4个100'000整数(400kBytes)的向量最有可能超过L1高速缓存(128或256K)的容量。 - Emilio Garavaglia
在这种情况下,缓存的大小没有影响。每个数组元素只使用一次,之后如果被驱逐则无关紧要。缓存大小仅在您具有时间局部性时才会起作用(即,您将来会重复使用相同的元素)。 - Oliver Charlesworth
@OliCharlesworth:如果我必须在缓存中加载一个新值,并且已经有一个已经修改过的值,我首先要把它写下来,这让我等待写入发生。 - Emilio Garavaglia
但是在OP代码的两个变体中,每个值都被精确修改一次。您在每个变体中执行相同数量的回写。 - Oliver Charlesworth


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

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

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

我玩各种方案,比如把作业分配给 b[j]d[j] 至 InitToZero[j] 在循环内部,以及使用 += b[j] = 1 和 += d[j] = 1,我得到了相当一致的结果。

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

硬件是 戴尔XPS 8500 与第3代 酷睿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秒。


16
2017-12-30 01:34



您在此提及的错位罚分是指未对齐的单个加载/存储(包括未对齐的SSE加载/存储)。但事实并非如此,因为性能对不同阵列的相对对齐很敏感。指令级别没有错位。每个装载/存储都正确对齐。 - Mysticial


这是因为CPU没有那么多缓存未命中(必须等待阵列数据来自RAM芯片)。你可以有意识地不断调整阵列的大小,以便超过大小 1级缓存 (L1),然后是 二级缓存 (L2),你的CPU,并根据数组的大小绘制代码执行所需的时间。图表不应该像您期望的那样是直线。


14
2017-12-17 20:52



我不相信缓存大小和数组大小之间存在任何交互。每个数组元素只使用一次,然后可以安全地逐出。缓存之间可能存在交互 线 但是,大小和数组大小,如果它导致四个数组冲突。 - Oliver Charlesworth
你是对的,这是证明这种效果的错误例子 - James


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

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


12
2017-08-17 15:23





原始问题

为什么一个循环比两个循环慢得多?


评估问题

OP的代码:

const int n=100000;

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

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

考虑

考虑OP关于for循环的两个变体的原始问题以及他对缓存行为的修正问题以及许多其他优秀答案和有用的评论;我想通过对这种情况和问题采取不同的方法来尝试做一些与众不同的事情。


该方法

考虑到两个循环以及关于缓存和页面归档的所有讨论,我想采用另一种方法来从不同的角度来看待这个问题。一个不涉及缓存和页面文件,也不涉及分配内存的执行,实际上这种方法甚至根本不涉及实际的硬件或软件。


透视

在查看代码一段时间之后,很明显问题是什么以及产生什么。让我们将其分解为一个算法问题,并从使用数学符号的角度来看待它,然后对数学问题和算法进行类比。


我们所知道的

我们知道他的循环将运行100,000次。我们也知道 a1b1c1 & d1 是64位架构的指针。在32位机器上的C ++中,所有指针都是4个字节,而在64位机器上,它们的大小是8个字节,因为指针具有固定长度。我们知道在两种情况下我们都有32个字节可供分配。唯一的区别是我们在每次迭代时分配32个字节或2个2-8字节集合,在第二种情况下,我们为每个独立循环的每次迭代分配16个字节。因此,两个循环在总分配中仍然等于32个字节。有了这些信息,我们继续展示它的一般数学,算法和类比。我们知道在两种情况下必须执行相同集合或操作组的次数。我们知道在两种情况下都需要分配的内存量。我们可以评估两种情况之间分配的总体工作量大致相同。


我们不知道的

我们不知道每个案件需要多长时间,除非我们设置一个柜台并进行基准测试。然而,基准分数已经包含在原始问题和一些答案和评论中,我们可以看到两者之间存在显着差异,这就是这个问题对这个问题的整体推理以及对它的回答。首先。


我们来调查吧 

很明显,许多人已经通过查看堆分配,基准测试,查看RAM,缓存和页面文件来完成此操作。还包括了特定的数据点和特定的迭代索引,关于这个特定问题的各种对话让很多人开始质疑其他相关的事情。那么我们如何通过使用数学算法并对其进行类比来开始研究这个问题呢?我们首先做几个断言!然后我们从那里构建我们的算法。


我们的断言:

  • 我们将让循环及其迭代成为一个从1开始并以100000结束而不是从循环开始的Summation,因为我们不需要担心内存寻址的0索引方案,因为我们只对它感兴趣算法本身。
  • 在这两种情况下,我们有4个函数可以使用,2个函数调用,每个函数调用都有2个操作。所以我们将它们设置为函数和函数调用 F1()F2()f(a)f(b)f(c) 和 f(d)

算法:

第一案例:  - 只有一个求和,但有两个独立的函数调用。

Sum n=1 : [1,100000] = F1(), F2();
                       F1() = { f(a) = f(a) + f(b); }
                       F2() = { f(c) = f(c) + f(d);  }

第二个案例:  - 两个求和但每个都有自己的函数调用。

Sum1 n=1 : [1,100000] = F1();
                        F1() = { f(a) = f(a) + f(b); }

Sum2 n=1 : [1,100000] = F1();
                        F1() = { f(c) = f(c) + f(d); }

如果你注意到了 F2() 只存在于 Sum 哪两个 Sum1 和 Sum2 只包含 F1()。当我们开始断定第二种算法发生了某种优化时,这也将在后面明显。

通过第一种情况的迭代 Sum 电话 f(a) 这会增加自我 f(b) 然后它打电话 f(c) 这将做同样但添加 f(d) 为每个人自己 100000 iterations。在第二种情况下,我们有 Sum1 和 Sum2 并且两者的行为相同,就好像它们是连续两次调用的相同函数一样。 在这种情况下,我们可以治疗 Sum1 和 Sum2 就像老了 Sum 哪里 Sum 在这种情况下看起来像这样: Sum n=1 : [1,100000] { f(a) = f(a) + f(b); } 现在这看起来像一个优化,我们可以认为它是相同的功能。


类比摘要

根据我们在第二种情况下看到的情况,它几乎看起来好像存在优化,因为两个for循环具有相同的精确签名,但这不是真正的问题。问题不在于正在进行的工作 f(a)f(b)f(c)f(d) 在两种情况下以及两者之间的比较中,Summation必须在两种情况下都行进的距离的差异给出了时间执行的差异。

想想 For Loops 作为 Summations 将迭代视为a Boss 这是给两个人的命令 A & B 他们的工作就是吃肉 C & D 分别从他们那里拿起一些包裹并归还。在这里类比,for循环或求和迭代和条件检查本身实际上并不代表 Boss。实际代表什么 Boss 这里不是直接来自实际的数学算法,而是来自实际的概念 Scope 和 Code Block 在例程或子例程,方法,函数,翻译单元等中。第一算法具有1个范围,其中第二算法具有2个连续范围。

在每个呼叫的第一个案例中滑动 Boss 去 A 并给出订单和 A 去取 B's 然后包 Boss 去 C 并给出相同的命令并从中接收包裹 D 在每次迭代。

在第二种情况下 Boss 直接使用 A 去取 B's 包装直到收到所有包裹。然后 Boss与...合作 C 为了获得所有这些而做同样的事情 D's 包。

由于我们正在使用8字节指针并处理堆分配,所以我们在这里考虑这个问题。让我们说一下 Boss 距离100英尺 A 然后 A 距离500英尺 C。我们不需要担心这有多远 Boss 最初来自 C 因为执行的顺序。在这两种情况下 Boss 最初来自 A 先到了 B。这个类比并不是说这个距离是准确的;它只是一个使用测试用例场景来显示算法的工作原理。在许多情况下,在进行堆分配并使用缓存和页面文件时,地址位置之间的这些距离在差异上可能不会有太大变化,或者它们可能非常显着地取决于数据类型的性质和数组大小。


测试用例:

第一例: 在第一次迭代时 Boss 最初需要100英尺才能完成订单 A 和 A 离开并做他的事,但然后 Boss 必须前往500英尺 C 给他他的订单单。然后在下一次迭代和之后的每次其他迭代 Boss 必须在两者之间来回500英尺。

第二种情况:  The Boss 必须在第一次迭代时行进100英尺 A,但之后他已经在那里等待了 A 回来直到所有单据都填满。然后 Boss 必须在第一次迭代时行进500英尺 C 因为 C 距离500英尺 A 从此 Boss( Summation, For Loop ) 在工作之后正在被召唤 A 然后就像他一样等待 A 直到全部 C's 订单单已完成。


旅行距离的差异

const n = 100000
distTraveledOfFirst = (100 + 500) + ((n-1)*(500 + 500); 
// Simplify
distTraveledOfFirst = 600 + (99999*100);
distTraveledOfFirst = 600 + 9999900;
distTraveledOfFirst =  10000500;
// Distance Traveled On First Algorithm = 10,000,500ft

distTraveledOfSecond = 100 + 500 = 600;
// Distance Traveled On Second Algorithm = 600ft;    

任意价值观的比较

我们可以很容易地看到600远远低于1000万。现在这不完全正确,因为我们不知道RAM的地址与每个迭代的每个调用的Cache或Page File之间的距离的实际差异是由于许多其他看不见的变量,但这只是评估从最坏情况下要注意并试图查看的情况。

因此,通过这些数字,几乎看起来算法一应该比算法二慢99%;然而,这只是 The Boss's 算法的一部分或责任,它不考虑实际的工人 ABC,& D 以及他们在循环的每次迭代中必须做什么。所以老板的工作只占工作总量的15-40%。因此,通过工人完成的大部分工作对将速度差异的比率保持在约50-70%有轻微的影响


观察:  - 两种算法之间的差异

在这种情况下,它是正在完成的工作过程的结构,它确实表明了这一点 案例2从具有类似函数声明和定义的部分优化两者来看,效率更高,其中只有名称不同的变量。而且我们也看到了旅行的总距离 情况1 远远超过它 案例2 我们可以认为这个距离是我们的 时间因素 两种算法之间。 情况1 还有很多工作要做 案例2 确实。这也是在证据中看到的 ASM 两个案例之间都显示出来。即使已经就这些案例所说的话,它也没有考虑到这一事实 情况1 老板将不得不等待两者 A & C 在他回去之前回来 A 再次在下一次迭代中,它也没有考虑到if的事实 A 要么 B 两个人都花了很长时间 Boss 而其他工人也在等待闲置。在 案例2 唯一一个空闲的是 Boss 直到工人回来所以即使这对算法也有影响。


结论:

情况1 是一个经典的插值问题,恰好是一个效率低下的问题。我还认为这是为什么许多机器架构和开发人员最终构建和设计具有多线程应用程序以及并行编程能力的多核系统的主要原因之一。

因此,即使从这种方法看它,甚至不涉及硬件,操作系统和编译器如何协同工作以进行涉及使用RAM,缓存,页面文件等的堆分配;它背后的数学已经向我们展示了这两个中的哪一个是使用上述类比的更好的解决方案 Boss 或者 Summations 是那些 For Loops 必须在工人之间旅行 A & B。我们很容易看出来 案例2 如果不是多一点,至少要快1/2 情况1 由于行进的距离和所花费的时间的差异。这个数学几乎完全符合Bench Mark Times以及装配指令数量的差异。



OPs修订问题

编辑:问题证明是无关紧要的,因为行为严重依赖于数组(n)和CPU缓存的大小。因此,如果有进一步的兴趣,我重新提出这个问题:

您能否提供一些有关导致不同缓存行为的详细信息,如下图中的五个区域所示?

通过为这些CPU提供类似的图表,指出CPU /缓存架构之间的差异也可能是有趣的。


关于这些问题

正如我毫无疑问地证明的那样,即使在涉及硬件和软件之前也存在潜在的问题。现在关于内存和缓存以及页面文件等的管理,它们在一组集成的系统中一起工作: The Architecture {硬件,固件,一些嵌入式驱动程序,内核和ASM指令集}, The OS{文件和内存管理系统,驱动程序和注册表}, The Compiler {源代码的翻译单位和优化},甚至是 Source Code 本身就有一套独特的算法;我们已经可以看到,在我们将它应用于任意任意机器之前,在第一个算法中发生了瓶颈 ArchitectureOS,和 Programmable Language与第二种算法相比。因此在涉及现代计算机的内在函数之前就已存在问题。


结局结果

然而;并不是说这些新问题不重要,因为它们本身就是,而且它们确实起了作用。它们确实会对程序和整体绩效产生影响,这一点可以从许多给出答案和/或评论的图表和评估中看出来。如果你注意的比喻 Boss 和两个工人 A & B 谁必须去检索包裹 C & D 分别考虑到两个算法的数学符号你可以看到甚至没有计算机的参与 Case 2 大约快60% Case 1 当您将这些算法应用于源代码后查看图形和图表,通过操作系统进行编译和优化并执行以在给定硬件上执行操作时,您甚至会看到这些算法之间的差异稍微降低。

现在,如果“数据”集合相当小,那么起初可能看起来并不是那么糟糕但是从那以后 Case 1 是关于 60 - 70% 慢于 Case 2 我们可以将这个函数的增长看作是时间执行的差异:

DeltaTimeDifference approximately = Loop1(time) - Loop2(time)
//where 
Loop1(time) = Loop2(time) + (Loop2(time)*[0.6,0.7]) // approximately
// So when we substitute this back into the difference equation we end up with 
DeltaTimeDifference approximately = (Loop2(time) + (Loop2(time)*[0.6,0.7])) - Loop2(time)
// And finally we can simplify this to
DeltaTimeDifference approximately = [0.6,0.7]*(Loop2(time)

这个近似值是这两个循环在算法和机器操作之间的平均差异,涉及软件优化和机器指令。因此,当数据集线性增长时,两者之间的时间差也是如此。算法1具有比算法2更多的提取,这在算法2中是明显的 Boss 不得不往返于两者之间的最大距离 A & C 对于第一次迭代后的每次迭代,同时算法2 Boss 不得不前往 A 完成之后一次又一次 A 他离开时只需要行驶一次最大距离 A 至 C

所以试着拥有 Boss 专注于同时做两件类似的事情并且来回摆弄它们而不是专注于类似的连续任务会让他在一天结束时非常生气,因为他必须旅行和工作两倍。因此,让老板陷入内插瓶颈,因为老板的配偶和孩子不会欣赏它,因此不会失去这种情况的范围。


3
2018-01-30 14:00



自从我发布这个答案以来已经有一段时间了,但是我也想添加一个快速的评论,这也可能有助于理解这一点:在我与Boss作为for循环的类比或者循环的总结或迭代中,我们也可以认为这个boss是Stack Frame和Stack Pointer之间的组合,它管理范围和堆栈变量以及for循环的内存寻址。 - Francis Cugler


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

一个循环:1.577ms 两个循环:1.507ms

我在带有16Gb内存的E5-1620 3.5Ghz处理器上运行VS2015


0
2017-07-11 07:00