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

假设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 秒。我的问题是:(请参阅底部的我改写的问题)

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

在此处输入图片说明

答案

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

如果我猜对了如何分配数组,则它们很可能与 page line 对齐

这意味着您在每个循环中的所有访问都将使用相同的缓存方式。但是,一段时间以来,英特尔处理器已经具有 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 个 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 上搜索了一下,发现 Intel 实际上有一个硬件计数器,用于部分地址别名停顿:

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 的,但该想法仍应适用于 Core2。)

区域 3:

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

区域 4:

我们正在观察单循环中的性能下降。并且如前所述,这是由于对齐(最有可能)导致处理器加载 / 存储单元中的假混叠停顿。

但是,为了使假混叠发生,数据集之间必须有足够大的跨度。这就是为什么您在区域 3 中看不到它的原因。

区域 5:

在这一点上,没有什么适合缓存。因此,您受内存带宽的束缚。


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

好的,正确的答案肯定与 CPU 缓存有关。但是使用 cache 参数可能非常困难,尤其是在没有数据的情况下。

有很多答案,引起了很多讨论,但让我们面对现实:缓存问题可能非常复杂,而且不是一维的。它们在很大程度上取决于数据的大小,因此我的问题是不公平的:事实证明这是在缓存图中非常有趣的一点。

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

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

下图显示,根据所使用的确切场景和参数,可以将大多数答案,尤其是对问题和答案的大多数评论视为完全错误或正确。

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

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

  2. 这是唯一的一环(即具有连续分配)优于两环版本的地方。 (这完全使 Mysticial 的答案成为可能。)

使用初始化数据的结果:

在此处输入图片说明

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

在此处输入图片说明

这是一个难以解释的数据:初始化数据,该数据只分配一次,并在以下每个具有不同向量大小的测试用例中重新使用:

在此处输入图片说明

提案

应该要求有关堆栈溢出的所有与低级别性能相关的问题,以提供有关整个高速缓存相关数据大小范围的 MFLOPS 信息!浪费每个人思考答案的时间,尤其是在没有这些信息的情况下与他人讨论答案。

第二个循环涉及较少的缓存活动,因此处理器可以更轻松地满足内存需求。

假设您在一台机器上工作,而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。

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

这是一个经典的缓存崩溃情况。

这不是因为代码不同,而是由于缓存:RAM 比 CPU 寄存器慢,并且 CPU 内部有一个缓存,以避免每次变量更改时都写入 RAM。但是缓存不像 RAM 那样大,因此它仅映射其中的一小部分。

第一个代码修改远处的存储器地址,使它们在每个循环中交替出现,因此需要不断使缓存无效。

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

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

我不知道应该归咎于糟糕的基准测试代码还是什么,但是使用下面的代码,这两种方法在我的机器上的相差不到 10%,并且一个循环通常仅比两个循环快一点 - 如您所愿期望。

使用八个循环,数组大小从 2 ^ 16 到 2 ^ 24。我小心地初始化了源数组,因此+=分配没有要求FPU添加解释为 double 的内存垃圾。

InitToZero[j]了各种方案,例如将b[j]d[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,使用八个循环,累积时间分别为 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 秒。

这是因为 CPU 没有太多的高速缓存未命中(必须等待阵列数据来自 RAM 芯片)。您将不断调整数组的大小,使其超过 CPU 的1 级缓存 (L1)和2 级缓存 (L2)的大小,并绘制代码花费的时间,这将很有趣。对数组的大小执行。该图不应是您期望的直线。

第一个循环交替写入每个变量。第二个和第三个只使元素大小发生很小的变化。

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

原始问题

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


结论:

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

从这种方法来看待它,而不涉及硬件,操作系统和编译器如何一起工作以进行堆分配,这涉及使用 RAM,缓存,页面文件等。这些算法基础上的数学方法向我们展示了这两种方法中哪种更好。我们可以用一个比喻,其中一个BossSummation ,将代表一个For Loop有工人之间的旅行AB ,我们可以很容易地看到, 第 2 种情况是至少1/2,快,如果不是有点超过案例 1由于行驶所需的距离与工人之间的时间差。这个数学运算几乎与基准时间以及汇编指令中的差异几乎完美地吻合。

现在,我将在下面开始解释所有这些工作方式。


评估问题

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 循环的 2 个变体的问题,以及他对缓存行为的修正问题,以及许多其他出色的答案和有用的注释;我想通过对这种情况和问题采取不同的方法来尝试做一些不同的事情。


该方法

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


观点

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


我们所知道的

我们知道他的循环将运行 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)

算法:

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

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()仅存在于Sum1Sum2都只包含F1() Sum中。当我们开始得出结论,第二种算法正在发生某种优化时,这也将在以后显而易见。

通过第一种情况的迭代Sum调用f(a)将添加到其自身f(b)然后调用f(c)进行相同的操作,但每进行100000 iterationsf(d)添加到自身。在第二种情况下,我们有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 ,是将两个人AB下达命令的Boss ,他们的工作分别是给CD求肉,并从他们那里拿走一些包装并返回。以此类推,for 循环或求和迭代以及条件检查本身实际上并不代表Boss 。这里真正代表Boss的不是直接来自实际的数学算法,而是来自例程或子例程,方法,函数,翻译单元等中ScopeCode Block的实际概念。第一种算法具有一个范围,其中第二算法具有 2 个连续范围。

在每个呼叫单的第一种情况下, Boss转到A发出订单,而A转到取回B's包裹,然后Boss转到C发出命令以进行相同的操作,并在每次迭代中从D接收包裹。

在第二种情况下, Boss直接与A一起去取回B's包裹,直到收到所有包裹为止。然后, BossC一起完成获取D's所有程序包的操作。

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


测试案例:

第一种情况:在第一次迭代中, Boss首先必须走 100 英尺才能将订单单交给AA掉下来然后做他的事情,但是随后Boss不得不向C走 500 英尺才能给他单单。然后,在下一次迭代中, Boss之后的所有其他迭代必须在两者之间来回 500 英尺。

第二种情况: The Boss在第一次迭代中必须走 100 英尺才能到达A ,但是之后他已经在那里并且只等A回来直到所有单子都装满。然后, Boss必须在第一次迭代中向C行驶 500 英尺,因为自从与A一起工作后立即调用此Boss( Summation, For Loop )之后Boss( Summation, For Loop ) C距离A 500 英尺,然后像他对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部分或职责,它并没有考虑实际的工作人员ABCD以及他们在 Loop 的每次迭代中必须执行的操作。因此,老板的工作仅占完成工作总数的 15-40%。因此,通过工人完成的大部分工作对将速度差异率保持在 50%到 70%之间有较大的影响。


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

在这种情况下,这是工作过程的结构,它确实表明案例 2比具有部分相似的函数声明和定义的局部优化更为有效,其中仅变量名不同。而且我们还看到, 情况 1所经过的总距离比情况 2 中的要远得多,我们可以认为该距离在两种算法之间经过了时间因子案例 1案例 2有更多的工作要做。在两个案例之间显示的ASM证据中也可以看到这一点。即使已经对这些案例进行了说明,这也不能说明在案例 1中老板必须等待AC都返回,然后才能在下一次迭代中再次返回A ,如果AB花费的时间很长,那么Boss和其他工人也都闲着闲着,这也没有考虑到这一事实。在案例 2 中 ,只有一个闲置的人是Boss直到工人回来为止。因此,即使这也会对算法产生影响。



OP 修订的问题

编辑:问题被证明是不相关的,因为行为严重取决于数组(n)和 CPU 缓存的大小。因此,如果有进一步的兴趣,我重新提出一个问题:

您能否对导致不同缓存行为的细节提供深入的了解,如下图的五个区域所示?

通过为这些 CPU 提供类似的图形来指出 CPU / 缓存体系结构之间的差异也可能很有趣。


关于这些问题

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


最终结果

然而; 并不是说这些新问题并不重要,因为它们本身是重要的,而且它们毕竟会发挥作用。它们确实会影响程序和整体性能,这在许多给出答案和 / 或评论的图表和评估中很明显。如果您注意Boss和两个工人AB的类比,他们不得不分别从CD那里取回包裹,并考虑这两个算法的数学符号,您会发现,甚至没有计算机Case 2Case 1快 60%,当您在将这些算法应用于源代码,通过 OS 进行编译,优化和执行以在给定硬件上执行操作后查看图形和图表时,您甚至会看到一点点这些算法之间的差异会导致更多的降级。

现在,如果 “数据” 集很小,那么乍一看似乎并没有那么差,但是由于Case 1Case 260 - 70%我们可以将此函数的增长看成是时间执行的差异:

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第一次迭代后每次迭代都必须在AC之间最大距离来回移动而算法 2 Boss必须一次又一次到达A时明显可见。有A他不得不从去当行驶的最大距离只有一次AC

因此,试图让Boss集中精力做两件事,而不是专注于连续的类似任务,这会让他在一天结束前很生气,因为他不得不旅行和工作两倍。因此,不要让您的老板陷入插补的瓶颈,因为老板的配偶和子女不会对此感到困惑,因此不会失去局面。

可能是旧的 C ++ 和优化。在我的计算机上,我获得了几乎相同的速度:

一圈:1.577 毫秒

两个循环:1.507 毫秒

我在具有 16 GB RAM 的 E5-1620 3.5 GHz 处理器上运行 Visual Studio 2015。