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

经过进一步分析，我认为这是（至少部分）由四指针的数据对齐引起的。这将导致某种程度的缓存组/方式冲突。

如果我猜对了您如何分配数组，它们很可能与页面行对齐。

这意味着您在每个循环中的所有访问都将落在相同的缓存方式上。然而，英特尔处理器拥有 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 提到的 cache bank conflicts，对齐仍然可以发挥作用。 （那个链接是关于 Sandy Bridge 的，但这个想法应该仍然适用于 Core 2。）

区域 3：

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

区域 4：

我们观察到的是单循环中的性能下降。如前所述，这是由于对齐（最有可能）导致处理器加载/存储单元中的错误混叠停止。

但是，为了发生错误的混叠，数据集之间必须有足够大的步幅。这就是为什么您在区域 3 中看不到这一点的原因。

区域 5：

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

https://i.stack.imgur.com/ElCGL.png

---

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

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

@Mysticial 的回答说服了很多人（包括我），可能是因为它是唯一一个似乎依赖事实的人，但它只是事实的一个“数据点”。

这就是为什么我将他的测试（使用连续分配与单独分配）和@James' Answer 的建议结合起来。

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

请注意，我最初的问题是 n = 100.000。这一点（偶然）表现出特殊的行为：

它具有一环和二环版本之间的最大差异（几乎是三倍） 这是唯一的一点，单环（即连续分配）优于二环版本。 （这使得 Mysticial 的回答成为可能。）

使用初始化数据的结果：

https://i.stack.imgur.com/orxF8.png

使用未初始化数据的结果（这是 Mysticial 测试的）：

https://i.stack.imgur.com/mZPh9.png

这是一个难以解释的问题：初始化数据，分配一次并为以下每个不同向量大小的测试用例重用：

https://i.stack.imgur.com/aiDfv.png

提议

Stack Overflow 上的每个低级性能相关问题都应该要求提供整个缓存相关数据大小范围的 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];
}

将首先导致 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 字节的 RAM，而我们的其余内存明显变慢（比如访问时间长 100 倍）。

假设一个相当愚蠢的缓存策略，如果字节不在缓存中，把它放在那里，当我们在它的时候也得到下面的字节，你会得到这样的场景：

与 for(int j=0;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

缓存 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

这是一个经典的缓存颠簸场景。

---

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

第一个代码在每个循环中交替修改远程内存地址，因此需要不断地使缓存无效。

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

---

我无法复制这里讨论的结果。

我不知道是否应该归咎于糟糕的基准代码，或者是什么，但是这两种方法在我的机器上使用以下代码的误差在 10% 以内，并且一个循环通常比两个循环稍微快一点——就像你想的那样预计。

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

我尝试了各种方案，例如将 b[j]、d[j] 到 InitToZero[j] 的赋值放在循环中，以及使用 += b[j] = 1 和 += d[j] = 1，我得到了相当一致的结果。

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

硬件是 Dell XPS 8500，第 3 代 Core i7 @ 3.4 GHz 和 8 GB 内存。对于 2^16 到 2^24，使用 8 个循环，累积时间分别为 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 的 level 1 cache (L1) 和 level 2 cache (L2) 的大小并绘制代码所用的时间对您来说会很有趣针对数组的大小执行。该图不应像您期望的那样是一条直线。

---

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

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

---

原始问题

为什么一个循环比两个循环慢这么多？

结论：

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

从这种方法来看，不涉及硬件、操作系统和编译器如何协同工作以进行涉及 RAM、缓存、页面文件等的堆分配；作为这些算法基础的数学向我们展示了这两者中哪一个是更好的解决方案。

我们可以将 Boss 类比为 Summation，它表示必须在工人 A 和B。

我们可以很容易地看到，案例 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 循环的两个变体的原始问题以及他对缓存行为的修正问题以及许多其他出色的答案和有用的评论；我想通过对这种情况和问题采取不同的方法来尝试做一些不同的事情。

该方法

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

观点

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

我们所知道的

我们知道的是，这个循环将运行 100,000 次。我们还知道 a1、b1、c1 和d1 是 64 位架构上的指针。在 32 位机器上的 C++ 中，所有指针都是 4 个字节，而在 64 位机器上，它们的大小是 8 个字节，因为指针是固定长度的。

我们知道在这两种情况下我们都有 32 个字节可以分配。唯一的区别是我们在每次迭代中分配 32 个字节或两组 2-8 个字节，其中第二种情况我们为两个独立循环的每次迭代分配 16 个字节。

两个循环的总分配仍然等于 32 个字节。有了这些信息，现在让我们继续展示这些概念的一般数学、算法和类比。

我们确实知道在这两种情况下必须执行同一组或一组操作的次数。我们确实知道在这两种情况下需要分配的内存量。我们可以评估两种情况之间分配的总体工作量将大致相同。

我们不知道的

除非我们设置计数器并运行基准测试，否则我们不知道每种情况需要多长时间。但是，基准已经包含在原始问题以及一些答案和评论中；我们可以看到两者之间的显着差异，这就是针对这个问题提出这个建议的全部原因。

让我们调查一下

很明显，许多人已经通过查看堆分配、基准测试、查看 RAM、缓存和页面文件来做到这一点。查看特定的数据点和特定的迭代指数也包括在内，关于这个特定问题的各种对话让许多人开始质疑其他相关的事情。我们如何开始通过使用数学算法并对其进行类比来看待这个问题？我们从做几个断言开始！然后我们从那里构建我们的算法。

我们的主张：

我们将让我们的循环及其迭代是一个从 1 开始到 100000 结束的求和，而不是像循环中那样从 0 开始，因为我们不需要担心内存寻址的 0 索引方案，因为我们只对算法本身。

在这两种情况下，我们都有四个函数可以使用，两个函数调用，每个函数调用都执行两个操作。我们将这些设置为函数并调用如下函数：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() 仅存在于 Case1 的 Sum 中，其中 F1() 包含在 Case1 的 Sum 和 Case2 的 Sum1 和 Sum2 中。稍后当我们开始得出结论认为第二种算法中正在发生优化时，这一点会很明显。

通过第一种情况 Sum 的迭代调用 f(a) 将添加到其自身 f(b) 然后它调用 f(c) 将执行相同的操作，但每次 100000 迭代将 f(d) 添加到自身。在第二种情况下，我们有 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) 所做的工作。在这两种情况下以及两者之间的比较中，总和在每种情况下必须行进的距离的差异会导致执行时间的差异。

将 for 循环 视为执行迭代的 summations，将其视为向两个人发出命令的 Boss A & B 他们的工作是肉C & D 分别从他们那里取一些包裹并退回。在这个类比中，for 循环或求和迭代和条件检查本身实际上并不代表 Boss。实际代表 Boss 的不是直接来自实际的数学算法，而是来自例程或子例程、方法、函数、翻译单元等中的 Scope 和 Code Block 的实际概念。第一个算法有一个范围，其中第二种算法有两个连续的范围。

在每个调用单的第一个案例中，Boss 去 A 并下达订单，A 去获取 B's 包裹，然后 Boss 去 C 并下达订单相同并在每次迭代时从 D 接收包。

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

由于我们正在使用 8 字节指针并处理堆分配，让我们考虑以下问题。假设 Boss 距离 A 100 英尺，而 A 距离 C 500 英尺。由于执行顺序，我们无需担心 Boss 最初与 C 的距离。在这两种情况下，Boss 首先从 A 移动到 B。这个类比并不是说这个距离是准确的。它只是一个有用的测试用例场景来展示算法的工作原理。

在许多情况下，在进行堆分配以及使用缓存和页面文件时，地址位置之间的这些距离可能变化不大，或者它们可能会根据数据类型和数组大小的性质而显着变化。

测试用例：

第一种情况：在第一次迭代中，Boss 必须先走 100 英尺才能将订单传给 A，然后 A 开始执行他的任务，但是 Boss 必须行驶 500 英尺到 C 才能给他订单单。然后在下一次迭代和 Boss 之后的所有其他迭代中，必须在两者之间来回 500 英尺。

第二种情况：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*1000);
distTraveledOfFirst = 600 + 99999000;
distTraveledOfFirst = 99999600
// Distance Traveled On First Algorithm = 99,999,600ft

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

任意值的比较

我们可以很容易地看到，600 远小于大约 1 亿。现在，这并不准确，因为我们不知道每次迭代中每个调用的 RAM 地址或从哪个缓存或页面文件之间的距离的实际差异将是由于许多其他看不见的变量。这只是对需要了解的情况的评估，并从最坏的情况下看待它。

从这些数字来看，似乎算法一应该99%比算法二慢；但是，这只是算法的 Boss's 部分或责任，它不考虑实际的工作人员 A、B、C 和 & D 以及他们在循环的每次迭代中必须做的事情。所以老板的工作只占正在完成的总工作的15-40%左右。通过工人完成的大部分工作对将速度差异比率保持在 50-70% 左右的影响略大

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

在这种情况下，它是正在完成的工作过程的结构。这表明案例 2 从具有相似函数声明和定义的部分优化中更有效，其中只有变量名称和行进距离不同。

我们还看到，案例 1 中的总行驶距离比案例 2 中的要远得多，我们可以将这个距离视为两种算法之间的时间因子。案例 1 比案例 2 要做的工作要多得多。

这可以从两种情况下显示的汇编指令的证据中观察到。除了已经对这些案例进行了说明外，这还没有说明在 案例 1 中老板必须等待 A 和C 在每次迭代中再次返回 A 之前返回。它也没有考虑到如果 A 或 B 花费了非常长的时间，那么 Boss 和其他 worker 都处于空闲状态等待执行。

在 案例 2 中，唯一空闲的是 Boss，直到工作人员返回。所以即使这样也会对算法产生影响。

OP 的修正问题

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

您能否对导致不同缓存行为的细节提供一些深入的见解，如下图的五个区域所示？

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

关于这些问题

正如我毫无疑问地证明的那样，甚至在涉及硬件和软件之前就存在潜在问题。

现在，关于内存和缓存以及页面文件等的管理，它们都在以下集成系统中协同工作：

架构（硬件、固件、一些嵌入式驱动程序、内核和汇编指令集）。

操作系统（文件和内存管理系统、驱动程序和注册表）。

编译器（源代码的翻译单元和优化）。

甚至是源代码本身及其独特的算法集。

与第二种算法相比，我们甚至在将第一种算法应用到任何具有任意架构、操作系统和可编程语言的机器之前，就已经可以看到在第一种算法中出现了瓶颈。在涉及现代计算机的内在函数之前已经存在一个问题。

最终结果

然而;这并不是说这些新问题不重要，因为它们本身就是重要的，而且它们确实发挥了作用。它们确实会影响程序和整体性能，这在许多给出答案和/或评论的人的各种图表和评估中显而易见。

如果您注意 Boss 和两个工人 A 的类比 & B 必须去 C & D 分别考虑所讨论的两种算法的数学符号；您可以看到，在不涉及计算机硬件和软件的情况下，Case 2 大约比 Case 1 快 60%。

当您在将这些算法应用于某些源代码、编译、优化和通过操作系统执行以在给定的硬件上执行它们的操作之后查看图形和图表时，您甚至可以看到差异之间的降级更多在这些算法中。

如果 Data 集相当小，一开始可能看起来并没有那么糟糕。但是，由于 Case 1 比 Case 2 慢 60 - 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 必须在 A 和C 对于第一次迭代后的每次迭代，而算法 2 Boss 必须前往 A 一次，然后在完成 A 后，从 A 出发时，他必须仅行驶一次最大距离到 C。

试图让Boss同时专注于做两件类似的事情并来回处理它们而不是专注于类似的连续任务，这会让他在一天结束时非常生气，因为他不得不两次旅行和工作很多。因此，不要因为老板的配偶和孩子不会欣赏而让你的老板陷入插值瓶颈，从而失去了情况的范围。

修订：软件工程设计原则

-- 迭代 for 循环中本地堆栈和堆分配计算之间的差异以及它们的用法、效率和有效性之间的差异 --

我上面提出的数学算法主要适用于对分配在堆上的数据执行操作的循环。

连续堆栈操作：如果循环在堆栈帧内的单个代码块或范围内本地对数据执行操作，它仍然会适用，但内存位置更接近它们通常是连续的并且距离差异旅行或执行时间几乎可以忽略不计。由于堆内没有进行分配，因此内存不会分散，也不会通过 ram 获取内存。内存通常是顺序的，并且与堆栈帧和堆栈指针相关。

如果循环在堆栈帧内的单个代码块或范围内对本地数据执行操作，它仍然会适用，但内存位置更接近它们通常是顺序的，并且行进距离或执行时间的差异几乎可以忽略不计。由于堆内没有进行分配，因此内存不会分散，也不会通过 ram 获取内存。内存通常是顺序的，并且与堆栈帧和堆栈指针相关。

当在堆栈上执行连续操作时，现代处理器将缓存重复值和地址，将这些值保存在本地缓存寄存器中。这里的操作或指令的时间是纳秒级的。

连续堆分配操作：当您开始应用堆分配并且处理器必须在连续调用中获取内存地址时，取决于 CPU 的体系结构、总线控制器和 RAM 模块，操作或执行的时间可以在微到毫秒的数量级。与缓存的堆栈操作相比，这些操作非常慢。 CPU 必须从 RAM 中获取内存地址，与 CPU 本身的内部数据路径或数据总线相比，系统总线上的任何东西通常都很慢。

当您开始应用堆分配并且处理器必须在连续调用中获取内存地址时，取决于 CPU、总线控制器和 RAM 模块的体系结构，操作或执行的时间可以是微到毫秒。与缓存的堆栈操作相比，这些操作非常慢。

CPU 必须从 RAM 中获取内存地址，与 CPU 本身的内部数据路径或数据总线相比，系统总线上的任何东西通常都很慢。

因此，当您处理需要在堆上的数据并在循环中遍历它们时，将每个数据集及其相应的算法保留在自己的单个循环中会更有效。与通过将堆上不同数据集的多个操作放入单个循环中来尝试分解连续循环相比，您将获得更好的优化。

可以对堆栈上的数据执行此操作，因为它们经常被缓存，但不适用于每次迭代都必须查询其内存地址的数据。

这就是软件工程和软件架构设计发挥作用的地方。它是知道如何组织数据、知道何时缓存数据、知道何时在堆上分配数据、知道如何设计和实现算法以及知道何时何地调用它们的能力。

您可能拥有与相同数据集相关的相同算法，但您可能需要一种实现设计用于其堆栈变体，而另一种实现设计用于其堆分配变体，这只是因为从其 O(n) 复杂性中可以看出的上述问题使用堆时的算法。

根据我多年来的观察，许多人没有考虑到这一事实。他们将倾向于设计一种适用于特定数据集的算法，并且无论数据集本地缓存在堆栈上还是在堆上分配，他们都会使用它。

如果您想要真正的优化，是的，它可能看起来像代码重复，但概括地说，拥有相同算法的两个变体会更有效。一个用于堆栈操作，另一个用于在迭代循环中执行的堆操作！

这是一个伪示例：两个简单的结构，一个算法。

struct A {
    int data;
    A() : data{0}{}
    A(int a) : data{a}{}
};
struct B {
    int data;
    B() : data{0}{}
    A(int b) : data{b}{}
}

template<typename T>
void Foo( T& t ) {
    // Do something with t
}

// Some looping operation: first stack then heap.

// Stack data:
A dataSetA[10] = {};
B dataSetB[10] = {};

// For stack operations this is okay and efficient
for (int i = 0; i < 10; i++ ) {
   Foo(dataSetA[i]);
   Foo(dataSetB[i]);
}

// If the above two were on the heap then performing
// the same algorithm to both within the same loop
// will create that bottleneck
A* dataSetA = new [] A();
B* dataSetB = new [] B();
for ( int i = 0; i < 10; i++ ) {
    Foo(dataSetA[i]); // dataSetA is on the heap here
    Foo(dataSetB[i]); // dataSetB is on the heap here
} // this will be inefficient.

// To improve the efficiency above, put them into separate loops...

for (int i = 0; i < 10; i++ ) {
    Foo(dataSetA[i]);
}
for (int i = 0; i < 10; i++ ) {
    Foo(dataSetB[i]);
}
// This will be much more efficient than above.
// The code isn't perfect syntax, it's only pseudo code
// to illustrate a point.

这就是我所说的堆栈变体与堆变体的单独实现。算法本身并不重要，您将在其中使用它们的循环结构。

---

它可能是旧的 C++ 和优化。在我的电脑上，我获得了几乎相同的速度：

一个循环：1.577 毫秒

两个循环：1.507 ms

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

---