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

Johannes Gerer 2086 c c++ performance vectorization compiler-optimization

假设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上进行了全面优化编译,在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;
    }
}

(它显示不同值的FLOP/n.)

在此输入图像描述

Mysticial.. 1591

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

如果我已经正确猜出了如何分配数组,它们很可能与页面行对齐.

这意味着每个循环中的所有访问都将采用相同的缓存方式.但是,英特尔处理器暂时具有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提到缓存库冲突时, Alignment仍然会起作用.(那个链接是关于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

  • +1:我认为这就是答案.与所有其他答案所说的相反,它不是关于单循环变体固有地具有更多缓存未命中,而是关于导致缓存未命中的阵列的特定对齐. (152认同)
  • 这个; a*错误的混叠*失速是最可能的解释. (28认同)
  • @VictorT.我使用了OP链接的代码.它生成一个.css文件,我可以在Excel中打开并从中生成图表. (7认同)
  • 对于任何感兴趣的人,[这里有关于内存对齐的好读物](http://en.wikipedia.org/wiki/Data_structure_alignment)和[这里有几个](http://en.wikipedia.org/wiki/CPU_cache)[途中的链接](http://alasir.com/articles/cache_principles/cache_associativity.html)[数据缓存在内存中](http://www.pcguide.com/ref/mbsys/cache/funcMapping-c. HTML) (7认同)
  • @Nawaz页面通常为4KB.如果你查看我打印出来的十六进制地址,单独分配的测试都具有相同的模4096.(从4KB边界的起点开始是32字节)也许GCC没有这种行为.这可以解释为什么你没有看到差异. (5认同)
  • 好吧,外循环(测试循环)多次迭代.因此,如果整个数据集不适合缓存,它将重复刷新到内存和从内存刷新. (2认同)

Johannes Ger.. 205

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

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

@Mysticial的回答说服了很多人(包括我),可能是因为它是唯一一个似乎依赖于事实的人,但这只是事实的一个"数据点".

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

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

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

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

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

使用初始化数据的结果:

在此输入图像描述

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

在此输入图像描述

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

在此输入图像描述

提案

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

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

Puppy.. 70

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

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

OldCurmudgeo.. 41

想象一下,你正在开发一台机器,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]在高速缓存-现在有在高速缓存中的四个字节,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.

  • 弹出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

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

  • 这是不正确的.对数组的特定元素的引用不会导致整个数组从磁盘(或从非缓存的内存)中分页; 仅分页相关页面或缓存行. (7认同)

Emilio Garav.. 29

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

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

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

  • 在这种情况下,缓存的大小没有影响.每个数组元素只使用一次,之后如果被驱逐则无关紧要.缓存大小仅在您具有时间局部性时才很重要(即您将来会重复使用相同的元素). (5认同)
  • @OliCharlesworth:如果我必须在缓存中加载一个新值,并且已经有一个已经修改过的值,我首先要把它写下来,这让我等待写入发生. (2认同)
  • 但是在OP代码的两个变体中,每个值都被精确修改一次.您在每个变体中执行相同数量的回写. (2认同)

大智慧.. 18

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

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

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

我打得四处各种方案,如把的分配b[j],d[j]InitToZero[j]环内,并且还用+= b[j] = 1+= d[j] = 1,和我有相当一致的效果.

正如你所期望的那样,初始化bd内循环使用InitToZero[j]了结合方式的优势,因为他们被分配到之前完成背到背部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秒.


James.. 15

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

  • 我不相信缓存大小和数组大小之间存在任何交互.每个数组元素只使用一次,然后可以安全地逐出.但是,如果缓存*行*大小与数组大小之间存在交互,则会导致四个数组发生冲突. (2认同)

大智慧.. 13

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

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


Francis Cugl.. 5

原始问题

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


结论:

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

从这种方法看它,而不涉及硬件,操作系统和编译器如何协同工作以进行涉及使用RAM,缓存,页面文件等的堆分配; 作为这些算法基础的数学表明我们这两者中的哪一个是更好的解决方案.我们可以用一个比喻,其中一个BossSummation那将是一个For Loop有工人之间的旅行AB我们不难看出,第2种情况是至少1/2一样快,如果不是有点超过案例1由于距离差旅行需要和工人之间的时间.这个数学几乎完全符合Bench Mark Times以及装配说明中的差异.

我现在开始解释下面的所有这些是如何工作的.


评估问题

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


我们不知道的

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


我们来调查吧

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


我们的断言:

  • 我们将让循环及其迭代成为一个从1开始并以100000结束而不是从0开始的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两者Sum1Sum2仅包含的位置F1().当我们开始断定第二种算法发生了某种优化时,这也将在后面明显.

通过第一个案例Sum调用的迭代f(a)将添加到它自己,f(b)然后它调用f(c)将执行相同但f(d)为每个调用添加自身100000 iterations.在第二种情况下,我们有Sum1Sum2并且两者的行为相同,就好像它们是连续两次调用的相同函数一样.在这种情况下,我们可以把Sum1Sum2作为只是普通的老Sum地方Sum在这种情况下是这样的:Sum n=1 : [1,100000] { f(a) = f(a) + f(b); }现在这看起来像一个优化,我们可以只考虑它是相同的功能.


类比摘要

根据我们在第二种情况下看到的情况,它几乎看起来好像存在优化,因为两个for循环具有相同的精确签名,但这不是真正的问题.这个问题是不是正在做的工作f(a),f(b),f(c)f(d)在这两种情况下,以及两者之间的比较是在求和在这两种情况下,让你在执行时间的不同行驶的距离差.

的认为For Loops作为是Summations,做迭代作为一个Boss被发号施令两个人AB与他们的工作是肉CD分别拿起从他们一些包并返回它.在这里类比,for循环或求和迭代和条件检查本身实际上并不代表Boss.什么实际上代表了Boss这里是无法直接从实际的数学算法,但是从实际的概念ScopeCode Block的例程或子例程,方法,功能,翻译单元等内的第一算法具有1个范围,其中第二算法具有2连续范围.

在每个调用单上的第一种情况下,Boss转到A并给出订单并A关闭以获取B's包然后Boss转到C并给出命令以执行相同操作并从D每次迭代接收包.

在第二种情况下,Boss直接A用于去获取B's包,直到收到所有包.然后Boss工作与C获取所有D's包相同.

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


测试用例:

第一种情况:在第一次迭代时,Boss必须首先走100英尺才能让订单滑到AA离开并完成他的工作,但随后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部分或算法的责任,它不占实际工作者A,B,C,和D他们必须在每回路的每个迭代做什么.所以老板的工作只占工作总量的15-40%.因此,通过工人完成的大部分工作对将速度差异的比率保持在约50-70%有轻微的影响


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

在这种情况下,它是正在完成的工作过程的结构,它确实表明案例2从具有类似函数声明和定义的部分优化两者中更有效,其中它只是名称不同的变量.我们还看到案例1中的总行进距离比案例2中的距离远得多,我们可以认为这个距离在两个算法之间传递了我们的时间因子.案例1案例2做了大量工作.ASM在两个病例之间的证据中也可以看到这一点.即使已经说了这些情况是什么,它也不会考虑的事实,案例1的老板将不得不等待两个AC找回之前,他可以回到A对下一次迭代一次也没有按不考虑这样一个事实,即如果AB正在花费很长时间,那么Boss其他工人和其他工人也在等待闲置.在案例2中,唯一一个闲置的是Boss工人回来之前.所以即使这对算法也有影响.



OPs修订问题

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

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

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


关于这些问题

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


结局结果

然而; 这并不是说这些新问题不重要,因为它们本身就是,而且它们确实起了作用.它们确实会对程序和整体绩效产生影响,这一点可以从许多给出答案和评论的图表和评估中看出来.如果你留意的类比Boss和两名工人AB谁过的去,并从中检索包CD分别与考虑问题的两种算法的数学符号,你可以看到,如果没有计算机,甚至参与Case 2大约为60%比快Case 1,当你看着这些算法后的图形和图表已应用到源代码,编译和优化,并通过OS执行给定的硬件上执行操作,你甚至可以看到在这些算法的差异之间多一点下降.

现在,如果"数据"组是相当小的,它可能看起来不差的都坏在第一,但因为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个取时,这是显而易见Boss不得不来回之间的最大距离A:C对于第一次迭代后,每一次迭代,而算法2 Boss辗转去A一次,然后正在做用后A,他不得不前往从A去到的最大距离只有一次C.

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


归档时间:

查看次数:

224340 次

最近记录:

12 月 前