提问



假设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秒。我的问题是:(请参阅我在底部重新提出的问题)[196] [197] [198]


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宏来禁用它:[199]


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




最佳参考


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


如果我已经正确猜出了如何分配数组,那么 可能会与页面行对齐


这意味着每个循环中的所有访问都将采用相同的缓存方式。但是,英特尔处理器暂时具有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[200]





5个地区 - 说明



区域1:


这个很容易。数据集非常小,以至于性能受到诸如循环和分支之类的开销的支配。


区域2:


这里,随着数据大小的增加,相对开销量下降,性能饱和。这里有两个循环较慢,因为它有两倍的循环和分支开销。


我不确定到底发生了什么......当Agner Fog提到缓存库冲突时,对齐仍然可以发挥作用。 (这个链接是关于Sandy Bridge的,但这个想法应该适用于Core 2。)[201]


区域3:


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


区域4:


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


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


区域5:


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









其它参考1


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


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


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


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


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


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



  1. 它拥有一个和两个循环ed版本(差不多三倍)之间的最大差异

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



使用初始化数据的结果:





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





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





提案



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

其它参考2


第二个循环涉及更少的缓存Activity,因此处理器更容易跟上内存需求。

其它参考3


想象一下,你正在一台机器上工作,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。

  • 从缓存中弹出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



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

其它参考4


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


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


第二个代码不要交替:它只是在相邻地址上流动两次。这使得所有工作都在缓存中完成,只有在第二个循环启动后才会使它失效。

其它参考5


我无法复制此处讨论的结果。


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


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


我玩了各种方案,比如在循环中把b[j]d[j]赋值给InitToZero[j],还使用+= b[j] = 1+= d[j] = 1,我得到了相当一致的结果。


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


硬件是戴尔XPS 8500,具有第3代Core i7 @ 3.4  GHz和8 GB内存。对于2 ^ 16到2 ^ 24,使用八个循环,累积时间分别为44.987和40.965。 Visual C ++ 2010,完全优化。[203] [204]


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

其它参考6


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

其它参考7


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


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

其它参考8


原始问题



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






评估问题


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





我们不知道


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





让我们调查


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





我们的断言:



  • 我们将让循环及其迭代成为一个从1开始并以100000结束而不是从0开始的求和,因为我们不需要担心内存寻址的0索引方案,因为我们是只对算法本身感兴趣。

  • 在这两种情况下,我们有4个函数可以使用,2个函数调用,每个函数调用都有2个操作。因此,我们将这些函数和函数调用设置为F1()F2()f(a)f(b)f(c)f(d)。/li>





算法:


第一种情况: - 只有一次求和,但有两次独立的函数调用。


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)在两种情况下,两者之间的比较是Summation必须在两种情况下旅行的距离的差异给你时间执行的差异。


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


在每个调用单的第一种情况下,Boss进入A并给出顺序,A关闭以获取B's包,然后Boss转到C并给出相同的命令并在每次迭代时从D接收包。


在第二种情况下,Boss直接与A一起工作以获取B's包,直到收到所有包。然后BossC一起工作以获得所有D's包。


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





测试用例:


第一种情况: 在第一次迭代时,Boss最初需要100英尺才能将订单单给AA去关闭并完成他的事情,但是Boss必须行进500英尺到C才能给他下订单。然后在Boss必须在两者之间来回500英尺之后的下一次迭代和每隔一次迭代。


第二种情况: The Boss必须在第一次迭代时移动100英尺到A,但之后他已经在那里等待[[A回到所有单据填满之前。然后Boss必须在第一次迭代时行进500英尺C,因为C距离A 500英尺,因为这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之前回来并且它也没有说明如果AB花了很长时间,那么两者都是Boss和其他工人也在等待闲置。在案例2 中,唯一一个空闲的是Boss,直到工人回来。所以即使这对算法也有影响。





结论:


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


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








OPs修订问题



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







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







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






关于这些问题


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





结局结果


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


现在,如果数据集相当小,那么起初可能看起来并不差,但由于Case 1Case 2Case 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之后,他必须仅行进最大距离一次从AC


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

其它参考9


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


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


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