For循环效率：合并循环
For-loop efficiency: merging loops
我一直认为减少迭代次数是提高程序效率的方法。由于我从未真正确认过这一点，所以我开始对此进行测试。
我制作了以下 C++ 程序来测量两个不同函数的时间：
- 第一个函数执行单个大循环并使用一组变量。
- 第二个函数执行多个同样大的循环，但每个变量一个循环。
完整测试代码：
#include <iostream>
#include <chrono>
using namespace std;
int* list1; int* list2;
int* list3; int* list4;
int* list5; int* list6;
int* list7; int* list8;
int* list9; int* list10;
const int n = 1e7;
// **************************************
void myFunc1()
{
for (int i = 0; i < n; i++)
{
list1[i] = 2;
list2[i] = 4;
list3[i] = 8;
list4[i] = 16;
list5[i] = 32;
list6[i] = 64;
list7[i] = 128;
list8[i] = 256;
list9[i] = 512;
list10[i] = 1024;
}
return;
}
// **************************************
void myFunc2()
{
for (int i = 0; i < n; i++)
{
list1[i] = 2;
}
for (int i = 0; i < n; i++)
{
list2[i] = 4;
}
for (int i = 0; i < n; i++)
{
list3[i] = 8;
}
for (int i = 0; i < n; i++)
{
list4[i] = 16;
}
for (int i = 0; i < n; i++)
{
list5[i] = 32;
}
for (int i = 0; i < n; i++)
{
list6[i] = 64;
}
for (int i = 0; i < n; i++)
{
list7[i] = 128;
}
for (int i = 0; i < n; i++)
{
list8[i] = 256;
}
for (int i = 0; i < n; i++)
{
list9[i] = 512;
}
for (int i = 0; i < n; i++)
{
list10[i] = 1024;
}
return;
}
// **************************************
int main()
{
list1 = new int[n]; list2 = new int[n];
list3 = new int[n]; list4 = new int[n];
list5 = new int[n]; list6 = new int[n];
list7 = new int[n]; list8 = new int[n];
list9 = new int[n]; list10 = new int[n];
auto start = chrono::high_resolution_clock::now();
myFunc1();
auto elapsed = chrono::high_resolution_clock::now() - start;
long long microseconds = chrono::duration_cast<chrono::microseconds>(elapsed).count();
cout << "Time taken by func1 (micro s):" << microseconds << endl << endl;
//
start = chrono::high_resolution_clock::now();
myFunc2();
elapsed = chrono::high_resolution_clock::now() - start;
microseconds = chrono::duration_cast<chrono::microseconds>(elapsed).count();
cout << "Time taken by func2 (micro s):" << microseconds << endl << endl;
delete[] list1; delete[] list2; delete[] list3; delete[] list4;
delete[] list5; delete[] list6; delete[] list7; delete[] list8;
delete[] list9; delete[] list10;
return 0;
}
编译：g++ main.cpp -O3 -o main.o
现在我有相互矛盾的假设：一方面，两个函数的操作量相同，只是设置了一些变量。尽管另一方面，第二个函数经历了 10 倍以上的循环，因此（也许）也应该花费 10 倍以上的时间。
结果令人惊讶。在我的电脑上，func1() 大约需要 349 毫秒，func2() 大约需要 32 毫秒，第一个函数实际上要慢得多而不是更快。
PC 运行 Ubuntu 18.04，CPU i3-8350K。
现在问题：我的测试正确吗？合并 for 循环以最小化迭代总数是否有用？人们有不同的经历吗？
改变函数调用的顺序会得到相同的结果。测得的时间变化很小（偏差很小）。
您从单个循环中获得的好处是您失去了循环变量的递增。所以在这种情况下，循环的内容是如此微不足道，分配（和测试）会产生很大的不同。
你的例子也没有考虑到什么；是连续内存访问通常比随机访问更快。
在一个循环花费更长的时间的函数中（尝试让睡眠而不是赋值）你会发现差异并不大。
获得性能改进的方法是从数学开始 - 正确的算法总是会带来最大的改进。理想情况下，这是在手指敲击键盘之前完成的。
如果我不得不冒险猜测，我会说您看到的是第一个函数中更频繁的内存缓存未命中的结果。
myFunc1() 本质上是以随机访问方式执行 10e8 次内存写入。
myFunc2() 正在执行 10e7 个字的 10 次顺序内存写入。
在现代内存架构上，我希望第二个更高效。
此代码创建变量：
list1 = new int[n]; list2 = new int[n];
list3 = new int[n]; list4 = new int[n];
list5 = new int[n]; list6 = new int[n];
list7 = new int[n]; list8 = new int[n];
list9 = new int[n]; list10 = new int[n];
但它几乎肯定不会创建实际的物理页面映射直到内存被实际修改。有关示例，请参阅 Does malloc lazily create the backing pages for an allocation on Linux (and other platforms)?。
因此您的 func1() 必须等待创建实际的 RAM 物理页面，而您的 func2() 则不需要。更改顺序，映射时间将归因于func2()性能。
根据您发布的代码，最简单的解决方案是 运行 func1() 或 func2() 在 执行您的定时 运行s.
如果您在进行任何基准测试之前没有确保实际物理内存已经被映射，那么当您第一次修改内存。
尝试对代码进行基准测试时，您需要：
- 编译时启用优化标志。
- 运行 每次测试 多次 次，以便收集 平均值.
你没有做到这两点。例如，您可以使用 -O3，至于平均值，我这样做了（我将函数 return 设为列表中的一个元素）：
for(int i = 0; i < 100; ++i)
dummy = myFunc1();
然后，我得到了这样的输出：
Time taken by func1 (micro s):206693
Time taken by func2 (micro s):37898
这证实了你所看到的，但差异是一个数量级（这是一个非常大的问题）。
在单个for循环中，你做一次内务处理，循环的计数器增加一次。在几个 for 循环中，它被扩展（并且您需要执行与您拥有的 for 循环一样多的次数）。当循环体有点微不足道时，就像你的情况一样，那么它就会有所作为。
另一个问题是数据局部性。第二个函数的循环将一次填充一个列表（这意味着将以连续的方式访问内存）。在第一个函数的大循环中，您将一次填充列表的一个元素，这归结为内存的随机访问（因为 list1 例如将被带入缓存，因为您填充了一个元素它，然后在你的代码的下一行，你将请求 list2，这意味着 list1 现在没用了。但是，在第二个函数中，一旦你将 list1 放入缓存，您将继续从缓存中使用它（而不是必须从内存中获取它），这会大大加快速度。
我相信这个事实在这里优于其他（大循环 VS 几个小循环）。因此，您实际上并没有对您想要的进行基准测试，而是 随机内存访问 VS 连续内存访问 .
我相信它比这更复杂。单个循环是否比多个循环快取决于几个因素。
程序迭代一组数据这一事实会让你付出一些代价（递增迭代器或索引；将 iterator/index 与某个让你知道循环已结束的值进行比较）所以如果你除法一个循环变成几个更小的循环，你为多次迭代同一组数据付出更多。
另一方面，如果循环更小，那么优化器的工作更容易，并且有更多的方法来优化代码。 CPU 也有可能使循环 运行 更快，通常它最适合小循环。
我有一些代码片段在将循环分成更小的部分后变得更快。我还编写了一些算法，当我将几个循环合并为一个循环时，这些算法表现得更好。
通常有很多因素，很难预测哪一个占主导地位，所以答案是您应该始终测量和检查几个版本的代码，以找出哪个更快。
你的假设基本上是有缺陷的：
循环迭代不会产生大量成本。
这就是 CPU 的优化目的：紧密循环。 CPU 优化可以达到为循环计数器使用专用电路（例如 PPC bdnz 指令），以便循环计数器开销恰好为零。 X86 确实需要一个 CPU 周期或两个 afaik，但仅此而已。
影响性能的通常是内存访问。
从 L1 缓存中获取值已经需要三到四个 CPU 周期的延迟。来自 L1 缓存的单个加载具有比循环控制更多的延迟！更多用于更高级别的缓存。 RAM 访问需要很长时间。
因此，要获得良好的性能，您通常需要减少访问内存所花费的时间。这可以通过
来完成
避免内存访问。
最有效但最容易被遗忘的优化。你不为你不做的事付出代价。
并行内存访问。
避免加载一些值并让下一个需要的值的地址依赖于此。这种优化很难做到，因为它需要清楚地了解不同内存访问之间的依赖关系。
此优化可能 需要一些循环融合或循环展开以利用不同循环之间的独立性bodies/iterations。在您的情况下，循环迭代彼此独立，因此它们已经尽可能并行。
此外，正如 MSalters 在评论中正确指出的那样：CPU 的寄存器数量有限。多少取决于体系结构，例如 32 位 X86 CPU 只有八个。因此，它根本无法同时处理十个不同的指针。它将需要将一些指针存储在堆栈上，从而引入更多的内存访问。显然，这违反了上面关于 避免 内存访问的要点。
顺序内存访问。
CPUs 是在知道绝大多数内存访问是顺序访问的情况下构建的，并为此进行了优化。当您开始访问数组时，CPU 通常会很快注意到，并开始预取后续值。
最后一点是您的第一个函数失败的地方：您在 10 个完全不同的内存位置访问 10 个不同的数组之间来回跳转。这会降低 CPU 推断应从主内存中预取哪些缓存行的能力，从而降低整体性能。
这里有三件重要的事情：
1) 没有优化的基准测试是没有意义的。事实证明，在这之下有一个真正的效果，不会随着优化而消失。事实上，反优化的调试版本 隐藏了 在内存中存储循环计数器的额外成本下的很多差异（将循环限制为每 6 个时钟 1 个与每个时钟 1 个） ，加上不自动向量化存储循环。
如果您还不知道为什么存在速度差异的 asm + CPU 微架构细节，那么在禁用优化的情况下测量它既不安全也没有用。
2) 缓存冲突未命中（如果数组都相对于页面边界对齐）。 相对于彼此倾斜数组可能会有很大帮助。这可能会自然发生，具体取决于它们的分配方式，即使它们的大小不是 2 的大幂。
这些数组都很大并且是用 new 单独分配的，所以它们可能都是页面对齐的（或者在放置一些信息（如大小）的实现中从页面边界偏移 16B）在对象之前）。在 Linux 上，glibc malloc/new 通常通过使用 mmap() 从 OS 分配新页面来处理大量分配（并使用前 16 个字节作为该块的簿记），而不是移动 brk().
4k 别名意味着它们都进入典型的 L1d 缓存中的同一组，这在典型的 x86 CPUs 上是 8 路关联的。 Why is the size of L1 cache smaller than that of the L2 cache in most of the processors? explains why it's not a coincidence that 64 sets * 64B/line = 4096B page-size (times 8-way = 32kiB), because that makes VIPT L1d cache work like a PIPT without homonym/synonym problems. See also
第 9 个存储将从第一个存储中逐出缓存行，因此每个存储将逐出一次行，而不是像连续情况那样完全写入。 （除非编译器自动矢量化并在继续之前将整个缓存行充满存储到一个数组。）x86 的强顺序内存模型需要按程序顺序将存储缓冲区中的存储提交到 L1d，因此它不能合并在提交之前将同一行的非相邻存储合并到一个条目中，或者在一行确实进入时提交多个未完成的存储（如果它们不连续）。
（替换策略是伪LRU，不是真正的LRU，所以有时你可能会发现同一个集合中的8、9次驱逐后一条线仍然很热。）
提醒：以上仅适用于所有数组相对于页面具有相同对齐方式的情况。为其中一个指针过度分配和执行 ptr = 128 + malloc(128 + size) 会使它相对于其他指针倾斜，有时值得这样做。
你说你有一台 PC，所以我猜是英特尔 CPU。 （Ryzen 的 L1d 具有相同的几何结构，但 Bulldozer 系列没有。）
(Intel's optimization manual section 3.6.10 Write Combining 建议对写入超过 4 个输出流的循环使用循环裂变 这建议在有关 NT 存储和 WC 内存的部分中；它可能仅适用于这种情况。无论哪种方式，4 都不是现代英特尔的正确数字，除非您保守地考虑另一个超线程。
(Intel's) Assembly/Compiler Coding Rule 58. (H impact, L generality) If an inner loop writes to more than
four arrays (four distinct cache lines), apply loop fission to break up the body of the loop such that only
four arrays are being written to in each iteration of each of the resulting loops.
TL:DR：对于 NT 存储（缓存绕过），最多 12 个输出流在 Skylake 和更新版本上似乎没问题，或者在 Broadwell/Haswell 和更早版本上最多 10 个。 （如果您同时读取任何内存，则更少）。那是那些 CPU 上的 LFB（行填充缓冲区）的数量。较早的 CPUs（在 Nehalem 之前）少于 10 个，并且可能无法将它们全部用于 NT 商店。 () LFB 用于所有行 to/from L1d 的传输，例如挂起的加载未命中需要分配一个 LFB 以等待来自 L2 的那条线。
（使用超线程时，请记住另一个超线程正在竞争同一物理内核上的 LFB，因此除非您可以禁用 HT，否则不要依赖于使用所有 12 个 LFB。）
但你不是在做 NT 商店。
conventional wisdom是，这个 4 输出效率限制也适用于正常（非 NT）存储到 WB 内存，但是不是现代英特尔的情况。正常（WB = 回写）存储的性能在与 NT 存储相同数量的输出流时下降，这纯属巧合。那篇机械同情文章对原因进行了一些猜测，但我们很确定它们听起来不对。
见https://github.com/Kobzol/hardware-effects/issues/1 for some microbenchmarks. (And see discussion between myself, BeeOnRope, and Hadi Brais about LFBs where this 4-output guideline came up: https://chat.whosebug.com/transcript/message/45474939#45474939 which was previously in comments under
@BeeOnRope 还在 Skylake 上发布了 a bar graph for regular (non-NT) stores interleaved to 1 to 15 output streams。 在 Skylake 上，对于最多约 6 个流的任何数量，性能都有些恒定，然后在 7 和 8 处开始变差（如果阵列全部对齐相同，则可能是 L1d 冲突未命中方式），从 9 点开始更显着，直到接近 13 到 15 点的平台。（大约是 1 到 6 流良好情况下性能的 1/3）。
同样，使用超线程时，如果另一个逻辑内核完全 运行ning，它几乎肯定会产生一些内存流量，因此像 4 个输出流这样的保守限制也不错计划。 但是性能不会在 7 或 8 时跌落悬崖，所以如果总工作量更多，则不必裂变你的循环。
另请参阅 ，了解有关常规 RFO 存储与非 RFO NT 存储的更多信息，以及许多 x86 内存带宽问题。 （特别是 memory/L3 缓存延迟在大多数 CPU 上限制了单核带宽，但在多核 Xeons 上更糟：它们令人惊讶地具有较低的 单核 内存带宽高于四核台式机。如果有足够多的核心忙碌，您可以从四通道或 6 通道内存控制器中饱和它们的高总带宽；这就是它们针对的情况进行了优化。）
2.5) DRAM 页面局部性：当数据最终从 L3（最后一级缓存）中逐出时，会发生回写内存。脏缓存行被发送到内存控制器，内存控制器可以将它们缓冲并分组，但所有 10 个阵列仍将混合存储（和 RFO 加载）。双通道内存控制器不能同时打开 10 个 DRAM 页。 （我认为每个通道只有 1 个，但我不是 DRAM 时序方面的专家。请参阅 Ulrich Drepper 的 What Every Programmer Should Know About Memory which does have some details.) https://pubweb.eng.utah.edu/~cs6810/pres/12-6810-15c.pdf 提到 DRAM open/closed 流媒体与分散存储的页面策略。
这里的底线是，即使高速缓存可以处理很多输出流，DRAM 可能会更快乐地处理更少的输出流。请注意，DRAM "page" 与虚拟内存页 (4k) 或大页 (2M) 的大小不同。
说到虚拟内存，TLB 应该有 10 个输出流：现代 x86 CPUs 有超过 10 个 L1dTLB 条目。希望它们具有足够的关联性，或者条目不都是别名，这样我们就不会在每个存储区都出现 TLB-miss！
3) 编译时别名分析
@RichardHodges 发现了这个）
您的大组合循环不会使用 gcc 或 clang 自动矢量化。他们不能证明 list1[10] 也不是 list4[9] 之类的，所以他们不能用一个 16 字节的存储来存储 list1[8..11]。
但是单数组循环可以使用 SSE 或 AVX 轻松自动矢量化。 （令人惊讶的是，不是 wmemset 调用或其他东西，只是在 gcc -O3 或 clang -O2 处使用常规自动向量化器。这可能会切换到 NT 存储以获得大尺寸，这将有助于大多数如果多个内核竞争内存带宽。memset 模式识别是/即使没有自动矢量化也是有用的。）
这里唯一需要的别名分析是为了证明 list1[i] = 2 不会修改 list1 指针值本身（因为函数在循环内读取全局，而不是将值复制到本地人）。基于类型的别名分析（-fstrict-aliasing 默认情况下启用）允许编译器证明，and/or 如果 list1 指向自身，那么从外部访问将会有未定义的行为稍后循环迭代中的对象。
当您未能使用 __restrict 关键字（由多个编译器从 C 的 restrict 中借用）时，在某些情况下（例如输出数组与输入数组的输出数组），智能编译器可以并且确实会在自动矢量化之前检查重叠.如果有重叠，它们会退回到安全的标量循环。
但在这种情况下不会发生这种情况：gcc 和 clang 根本不会生成矢量化循环，它们只是在 myFunc1 中执行标量。如果每个存储都导致 L1d 中的冲突未命中，那么这比您为编译器提供足够的信息来完成其工作的情况差 4 倍。 （对于 32 字节存储，使用 AVX 的 8x）。通常情况下，当主内存带宽成为瓶颈（不是 L1d 缓存）时，16B 与 32B 存储之间的差异很小，但在这里它可能是一个大问题，因为如果 10 个输出流全部别名，则会破坏 L1d 的写入组合效果。
顺便说一句，使全局变量 static int *__restrict line1 等等确实允许 gcc 自动矢量化 myFunc1 中的存储。但是，它不会裂变循环。 （它会被允许，但我想它不是在寻找那种优化。这取决于程序员。）
// global modifier allows auto-vec of myFunc1
#define GLOBAL_MODIFIER __restrict
#define LOCAL_MODIFIER __restrict // inside myFunc1
static int *GLOBAL_MODIFIER list1, *GLOBAL_MODIFIER list2,
*GLOBAL_MODIFIER list3, *GLOBAL_MODIFIER list4,
*GLOBAL_MODIFIER list5, *GLOBAL_MODIFIER list6,
*GLOBAL_MODIFIER list7, *GLOBAL_MODIFIER list8,
*GLOBAL_MODIFIER list9, *GLOBAL_MODIFIER list10;
我把你的代码 on the Godbolt compiler explorer with gcc8.1 and clang6.0 加上那个更改 + 一个从数组之一读取的函数，以阻止它们完全优化（它们会这样做，因为我让它们 static。）
然后我们得到这个内部循环，它可能 运行 比做同样事情的标量循环快 4 倍。
.L12: # myFunc1 inner loop from gcc8.1 -O3 with __restrict pointers
movups XMMWORD PTR [rbp+0+rax], xmm9 # MEM[base: l1_16, index: ivtmp.87_52, offset: 0B], tmp108
movups XMMWORD PTR [rbx+rax], xmm8 # MEM[base: l2_17, index: ivtmp.87_52, offset: 0B], tmp109
movups XMMWORD PTR [r11+rax], xmm7 # MEM[base: l3_18, index: ivtmp.87_52, offset: 0B], tmp110
movups XMMWORD PTR [r10+rax], xmm6 # MEM[base: l4_19, index: ivtmp.87_52, offset: 0B], tmp111
movups XMMWORD PTR [r9+rax], xmm5 # MEM[base: l5_20, index: ivtmp.87_52, offset: 0B], tmp112
movups XMMWORD PTR [r8+rax], xmm4 # MEM[base: l6_21, index: ivtmp.87_52, offset: 0B], tmp113
movups XMMWORD PTR [rdi+rax], xmm3 # MEM[base: l7_22, index: ivtmp.87_52, offset: 0B], tmp114
movups XMMWORD PTR [rsi+rax], xmm2 # MEM[base: l8_23, index: ivtmp.87_52, offset: 0B], tmp115
movups XMMWORD PTR [rcx+rax], xmm1 # MEM[base: l9_24, index: ivtmp.87_52, offset: 0B], tmp116
movups XMMWORD PTR [rdx+rax], xmm0 # MEM[base: l10_25, index: ivtmp.87_52, offset: 0B], tmp117
add rax, 16 # ivtmp.87,
cmp rax, 40000000 # ivtmp.87,
jne .L12 #,
（当然，这是为 x86-64 编译的。x86 32 位没有足够的寄存器来将所有指针保存在 regs 中，所以你会有一些负载。但那些会在 L1d 中命中缓存，实际上并不是很大的吞吐量瓶颈：在每个时钟 1 个存储的瓶颈下，在这种情况下，您只需存储常量，就有足够的吞吐量来完成更多工作。）
这种优化就像将循环展开 4 次，然后将 4 个商店重新排列到每个数组中。这就是为什么如果编译器不知道它们不重叠就不能完成的原因。不幸的是，即使使用 __restrict，clang 也不会这样做。通常使用 __restrict 来保证不重叠是在函数参数上，而不是局部变量或全局变量，但我没有尝试过。
使用全局数组而不是全局指针，编译器会知道它们没有重叠（并且不会有指针值存储在内存中的任何地方；数组地址将是 link-时间常数.) 在您的版本中，数组本身具有动态存储，只有指向它们的指针具有静态存储。
交错式全缓存行存储：
如果 myFunc1 在移动到下一个数组之前将 64 个字节存储到一个数组中会怎么样？然后你的编译器可以安全地将它编译为每次迭代每个数组 4 (SSE)、2 (AVX) 或 1 (AVX512) 向量存储，覆盖完整的 64 字节。
如果您将指针按 64 位对齐（或者如果编译器进行了一些别名分析并到达每个输出数组中的第一个 64 字节边界），那么每个存储块都会完全写入一个缓存行，而我们以后不会再碰了
这样可以避免 L1d 冲突未命中，对吧？也许吧，但除非您使用 NT 存储来避免 RFO，否则硬件预取器需要在存储尝试提交之前将线路拉入 L2，然后拉入 L1d。所以它并不像您想象的那么简单，但是将存储组合到尚未到达的缓存行的写组合缓冲区可以提供帮助。
Intel CPUs 中的 L2 streamer 预取器可以跟踪每页 1 次前向访问和 1 次后向访问，所以它应该没问题（如果数组在 L2 中没有别名）。 L1d 预取是个大问题。
它仍然会大大减少跳转 to/from L2 的缓存行的数量。 如果你有一个循环不能轻易分裂成多个循环，至少展开它，这样你就可以在继续之前写一个完整的缓存行
AVX512 可能会有所作为； IDK 如果 Skylake-AVX512 上的对齐 vmovdqa64 [mem], zmm0 可能会在将缓存行进入 MESI 修改状态时跳过加载旧值，因为它知道它正在覆盖整个缓存行。 （如果在没有合并掩码的情况下完成）。
gcc8.1 即使使用 AVX512 也不会费心去对齐输出指针；一个可能重叠的第一个和最后一个向量可能是一个很好的策略，对于像这样的简单情况，在这种情况下，两次写入相同的内存不是问题。 （与 Skylake 硬件上的 AVX2 相比，对齐对 AVX512 的影响更大。）
4) Unexpectedly poor and weirdly bimodal performance for store loop on Intel Skylake 显示交错的虚拟写入（到 相同 位置）与存储流可以使对于 L1d / L2 带宽，它比 1 个连续流差。
可能是因为在提交到 L1d 缓存之前存储缓冲区中发生了存储合并/合并。但仅适用于同一缓存行的相邻存储（因为 x86 的强序内存模型不允许存储乱序提交到 L1d）。
该测试没有缓存冲突问题。但是，连续写入整个缓存行应该也会有所帮助。
我一直认为减少迭代次数是提高程序效率的方法。由于我从未真正确认过这一点，所以我开始对此进行测试。
我制作了以下 C++ 程序来测量两个不同函数的时间：
- 第一个函数执行单个大循环并使用一组变量。
- 第二个函数执行多个同样大的循环，但每个变量一个循环。
完整测试代码：
#include <iostream>
#include <chrono>
using namespace std;
int* list1; int* list2;
int* list3; int* list4;
int* list5; int* list6;
int* list7; int* list8;
int* list9; int* list10;
const int n = 1e7;
// **************************************
void myFunc1()
{
for (int i = 0; i < n; i++)
{
list1[i] = 2;
list2[i] = 4;
list3[i] = 8;
list4[i] = 16;
list5[i] = 32;
list6[i] = 64;
list7[i] = 128;
list8[i] = 256;
list9[i] = 512;
list10[i] = 1024;
}
return;
}
// **************************************
void myFunc2()
{
for (int i = 0; i < n; i++)
{
list1[i] = 2;
}
for (int i = 0; i < n; i++)
{
list2[i] = 4;
}
for (int i = 0; i < n; i++)
{
list3[i] = 8;
}
for (int i = 0; i < n; i++)
{
list4[i] = 16;
}
for (int i = 0; i < n; i++)
{
list5[i] = 32;
}
for (int i = 0; i < n; i++)
{
list6[i] = 64;
}
for (int i = 0; i < n; i++)
{
list7[i] = 128;
}
for (int i = 0; i < n; i++)
{
list8[i] = 256;
}
for (int i = 0; i < n; i++)
{
list9[i] = 512;
}
for (int i = 0; i < n; i++)
{
list10[i] = 1024;
}
return;
}
// **************************************
int main()
{
list1 = new int[n]; list2 = new int[n];
list3 = new int[n]; list4 = new int[n];
list5 = new int[n]; list6 = new int[n];
list7 = new int[n]; list8 = new int[n];
list9 = new int[n]; list10 = new int[n];
auto start = chrono::high_resolution_clock::now();
myFunc1();
auto elapsed = chrono::high_resolution_clock::now() - start;
long long microseconds = chrono::duration_cast<chrono::microseconds>(elapsed).count();
cout << "Time taken by func1 (micro s):" << microseconds << endl << endl;
//
start = chrono::high_resolution_clock::now();
myFunc2();
elapsed = chrono::high_resolution_clock::now() - start;
microseconds = chrono::duration_cast<chrono::microseconds>(elapsed).count();
cout << "Time taken by func2 (micro s):" << microseconds << endl << endl;
delete[] list1; delete[] list2; delete[] list3; delete[] list4;
delete[] list5; delete[] list6; delete[] list7; delete[] list8;
delete[] list9; delete[] list10;
return 0;
}
编译：g++ main.cpp -O3 -o main.o
现在我有相互矛盾的假设：一方面，两个函数的操作量相同，只是设置了一些变量。尽管另一方面，第二个函数经历了 10 倍以上的循环，因此（也许）也应该花费 10 倍以上的时间。
结果令人惊讶。在我的电脑上，func1() 大约需要 349 毫秒，func2() 大约需要 32 毫秒，第一个函数实际上要慢得多而不是更快。
PC 运行 Ubuntu 18.04，CPU i3-8350K。
现在问题：我的测试正确吗？合并 for 循环以最小化迭代总数是否有用？人们有不同的经历吗？
改变函数调用的顺序会得到相同的结果。测得的时间变化很小（偏差很小）。
您从单个循环中获得的好处是您失去了循环变量的递增。所以在这种情况下，循环的内容是如此微不足道，分配（和测试）会产生很大的不同。
你的例子也没有考虑到什么；是连续内存访问通常比随机访问更快。
在一个循环花费更长的时间的函数中（尝试让睡眠而不是赋值）你会发现差异并不大。
获得性能改进的方法是从数学开始 - 正确的算法总是会带来最大的改进。理想情况下，这是在手指敲击键盘之前完成的。
如果我不得不冒险猜测，我会说您看到的是第一个函数中更频繁的内存缓存未命中的结果。
myFunc1() 本质上是以随机访问方式执行 10e8 次内存写入。
myFunc2() 正在执行 10e7 个字的 10 次顺序内存写入。
在现代内存架构上，我希望第二个更高效。
此代码创建变量：
list1 = new int[n]; list2 = new int[n];
list3 = new int[n]; list4 = new int[n];
list5 = new int[n]; list6 = new int[n];
list7 = new int[n]; list8 = new int[n];
list9 = new int[n]; list10 = new int[n];
但它几乎肯定不会创建实际的物理页面映射直到内存被实际修改。有关示例，请参阅 Does malloc lazily create the backing pages for an allocation on Linux (and other platforms)?。
因此您的 func1() 必须等待创建实际的 RAM 物理页面，而您的 func2() 则不需要。更改顺序，映射时间将归因于func2()性能。
根据您发布的代码，最简单的解决方案是 运行 func1() 或 func2() 在 执行您的定时 运行s.
如果您在进行任何基准测试之前没有确保实际物理内存已经被映射，那么当您第一次修改内存。
尝试对代码进行基准测试时，您需要：
- 编译时启用优化标志。
- 运行 每次测试 多次 次，以便收集 平均值.
你没有做到这两点。例如，您可以使用 -O3，至于平均值，我这样做了（我将函数 return 设为列表中的一个元素）：
for(int i = 0; i < 100; ++i)
dummy = myFunc1();
然后，我得到了这样的输出：
Time taken by func1 (micro s):206693
Time taken by func2 (micro s):37898
这证实了你所看到的，但差异是一个数量级（这是一个非常大的问题）。
在单个for循环中，你做一次内务处理，循环的计数器增加一次。在几个 for 循环中，它被扩展（并且您需要执行与您拥有的 for 循环一样多的次数）。当循环体有点微不足道时，就像你的情况一样，那么它就会有所作为。
另一个问题是数据局部性。第二个函数的循环将一次填充一个列表（这意味着将以连续的方式访问内存）。在第一个函数的大循环中，您将一次填充列表的一个元素，这归结为内存的随机访问（因为 list1 例如将被带入缓存，因为您填充了一个元素它，然后在你的代码的下一行，你将请求 list2，这意味着 list1 现在没用了。但是，在第二个函数中，一旦你将 list1 放入缓存，您将继续从缓存中使用它（而不是必须从内存中获取它），这会大大加快速度。
我相信这个事实在这里优于其他（大循环 VS 几个小循环）。因此，您实际上并没有对您想要的进行基准测试，而是 随机内存访问 VS 连续内存访问 .
我相信它比这更复杂。单个循环是否比多个循环快取决于几个因素。
程序迭代一组数据这一事实会让你付出一些代价（递增迭代器或索引；将 iterator/index 与某个让你知道循环已结束的值进行比较）所以如果你除法一个循环变成几个更小的循环，你为多次迭代同一组数据付出更多。
另一方面，如果循环更小，那么优化器的工作更容易，并且有更多的方法来优化代码。 CPU 也有可能使循环 运行 更快，通常它最适合小循环。
我有一些代码片段在将循环分成更小的部分后变得更快。我还编写了一些算法，当我将几个循环合并为一个循环时，这些算法表现得更好。
通常有很多因素，很难预测哪一个占主导地位，所以答案是您应该始终测量和检查几个版本的代码，以找出哪个更快。
你的假设基本上是有缺陷的：
循环迭代不会产生大量成本。
这就是 CPU 的优化目的：紧密循环。 CPU 优化可以达到为循环计数器使用专用电路（例如 PPC
bdnz指令），以便循环计数器开销恰好为零。 X86 确实需要一个 CPU 周期或两个 afaik，但仅此而已。影响性能的通常是内存访问。
从 L1 缓存中获取值已经需要三到四个 CPU 周期的延迟。来自 L1 缓存的单个加载具有比循环控制更多的延迟！更多用于更高级别的缓存。 RAM 访问需要很长时间。
因此，要获得良好的性能，您通常需要减少访问内存所花费的时间。这可以通过
来完成避免内存访问。
最有效但最容易被遗忘的优化。你不为你不做的事付出代价。
并行内存访问。
避免加载一些值并让下一个需要的值的地址依赖于此。这种优化很难做到，因为它需要清楚地了解不同内存访问之间的依赖关系。
此优化可能 需要一些循环融合或循环展开以利用不同循环之间的独立性bodies/iterations。在您的情况下，循环迭代彼此独立，因此它们已经尽可能并行。
此外，正如 MSalters 在评论中正确指出的那样：CPU 的寄存器数量有限。多少取决于体系结构，例如 32 位 X86 CPU 只有八个。因此，它根本无法同时处理十个不同的指针。它将需要将一些指针存储在堆栈上，从而引入更多的内存访问。显然，这违反了上面关于 避免 内存访问的要点。
顺序内存访问。
CPUs 是在知道绝大多数内存访问是顺序访问的情况下构建的，并为此进行了优化。当您开始访问数组时，CPU 通常会很快注意到，并开始预取后续值。
最后一点是您的第一个函数失败的地方：您在 10 个完全不同的内存位置访问 10 个不同的数组之间来回跳转。这会降低 CPU 推断应从主内存中预取哪些缓存行的能力，从而降低整体性能。
这里有三件重要的事情：
1) 没有优化的基准测试是没有意义的。事实证明，在这之下有一个真正的效果，不会随着优化而消失。事实上，反优化的调试版本 隐藏了 在内存中存储循环计数器的额外成本下的很多差异（将循环限制为每 6 个时钟 1 个与每个时钟 1 个） ，加上不自动向量化存储循环。
如果您还不知道为什么存在速度差异的 asm + CPU 微架构细节，那么在禁用优化的情况下测量它既不安全也没有用。
2) 缓存冲突未命中（如果数组都相对于页面边界对齐）。 相对于彼此倾斜数组可能会有很大帮助。这可能会自然发生，具体取决于它们的分配方式，即使它们的大小不是 2 的大幂。
这些数组都很大并且是用 new 单独分配的，所以它们可能都是页面对齐的（或者在放置一些信息（如大小）的实现中从页面边界偏移 16B）在对象之前）。在 Linux 上，glibc malloc/new 通常通过使用 mmap() 从 OS 分配新页面来处理大量分配（并使用前 16 个字节作为该块的簿记），而不是移动 brk().
4k 别名意味着它们都进入典型的 L1d 缓存中的同一组，这在典型的 x86 CPUs 上是 8 路关联的。 Why is the size of L1 cache smaller than that of the L2 cache in most of the processors? explains why it's not a coincidence that 64 sets * 64B/line = 4096B page-size (times 8-way = 32kiB), because that makes VIPT L1d cache work like a PIPT without homonym/synonym problems. See also
第 9 个存储将从第一个存储中逐出缓存行，因此每个存储将逐出一次行，而不是像连续情况那样完全写入。 （除非编译器自动矢量化并在继续之前将整个缓存行充满存储到一个数组。）x86 的强顺序内存模型需要按程序顺序将存储缓冲区中的存储提交到 L1d，因此它不能合并在提交之前将同一行的非相邻存储合并到一个条目中，或者在一行确实进入时提交多个未完成的存储（如果它们不连续）。
（替换策略是伪LRU，不是真正的LRU，所以有时你可能会发现同一个集合中的8、9次驱逐后一条线仍然很热。）
提醒：以上仅适用于所有数组相对于页面具有相同对齐方式的情况。为其中一个指针过度分配和执行 ptr = 128 + malloc(128 + size) 会使它相对于其他指针倾斜，有时值得这样做。
你说你有一台 PC，所以我猜是英特尔 CPU。 （Ryzen 的 L1d 具有相同的几何结构，但 Bulldozer 系列没有。）
(Intel's optimization manual section 3.6.10 Write Combining 建议对写入超过 4 个输出流的循环使用循环裂变 这建议在有关 NT 存储和 WC 内存的部分中；它可能仅适用于这种情况。无论哪种方式，4 都不是现代英特尔的正确数字，除非您保守地考虑另一个超线程。
(Intel's) Assembly/Compiler Coding Rule 58. (H impact, L generality) If an inner loop writes to more than four arrays (four distinct cache lines), apply loop fission to break up the body of the loop such that only four arrays are being written to in each iteration of each of the resulting loops.
TL:DR：对于 NT 存储（缓存绕过），最多 12 个输出流在 Skylake 和更新版本上似乎没问题，或者在 Broadwell/Haswell 和更早版本上最多 10 个。 （如果您同时读取任何内存，则更少）。那是那些 CPU 上的 LFB（行填充缓冲区）的数量。较早的 CPUs（在 Nehalem 之前）少于 10 个，并且可能无法将它们全部用于 NT 商店。 (
（使用超线程时，请记住另一个超线程正在竞争同一物理内核上的 LFB，因此除非您可以禁用 HT，否则不要依赖于使用所有 12 个 LFB。）
但你不是在做 NT 商店。
conventional wisdom是，这个 4 输出效率限制也适用于正常（非 NT）存储到 WB 内存，但是不是现代英特尔的情况。正常（WB = 回写）存储的性能在与 NT 存储相同数量的输出流时下降，这纯属巧合。那篇机械同情文章对原因进行了一些猜测，但我们很确定它们听起来不对。
见https://github.com/Kobzol/hardware-effects/issues/1 for some microbenchmarks. (And see discussion between myself, BeeOnRope, and Hadi Brais about LFBs where this 4-output guideline came up: https://chat.whosebug.com/transcript/message/45474939#45474939 which was previously in comments under
@BeeOnRope 还在 Skylake 上发布了 a bar graph for regular (non-NT) stores interleaved to 1 to 15 output streams。 在 Skylake 上，对于最多约 6 个流的任何数量，性能都有些恒定，然后在 7 和 8 处开始变差（如果阵列全部对齐相同，则可能是 L1d 冲突未命中方式），从 9 点开始更显着，直到接近 13 到 15 点的平台。（大约是 1 到 6 流良好情况下性能的 1/3）。
同样，使用超线程时，如果另一个逻辑内核完全 运行ning，它几乎肯定会产生一些内存流量，因此像 4 个输出流这样的保守限制也不错计划。 但是性能不会在 7 或 8 时跌落悬崖，所以如果总工作量更多，则不必裂变你的循环。
另请参阅
2.5) DRAM 页面局部性：当数据最终从 L3（最后一级缓存）中逐出时，会发生回写内存。脏缓存行被发送到内存控制器，内存控制器可以将它们缓冲并分组，但所有 10 个阵列仍将混合存储（和 RFO 加载）。双通道内存控制器不能同时打开 10 个 DRAM 页。 （我认为每个通道只有 1 个，但我不是 DRAM 时序方面的专家。请参阅 Ulrich Drepper 的 What Every Programmer Should Know About Memory which does have some details.) https://pubweb.eng.utah.edu/~cs6810/pres/12-6810-15c.pdf 提到 DRAM open/closed 流媒体与分散存储的页面策略。
这里的底线是，即使高速缓存可以处理很多输出流，DRAM 可能会更快乐地处理更少的输出流。请注意，DRAM "page" 与虚拟内存页 (4k) 或大页 (2M) 的大小不同。
说到虚拟内存，TLB 应该有 10 个输出流：现代 x86 CPUs 有超过 10 个 L1dTLB 条目。希望它们具有足够的关联性，或者条目不都是别名，这样我们就不会在每个存储区都出现 TLB-miss！
3) 编译时别名分析
@RichardHodges 发现了这个）
您的大组合循环不会使用 gcc 或 clang 自动矢量化。他们不能证明 list1[10] 也不是 list4[9] 之类的，所以他们不能用一个 16 字节的存储来存储 list1[8..11]。
但是单数组循环可以使用 SSE 或 AVX 轻松自动矢量化。 （令人惊讶的是，不是 wmemset 调用或其他东西，只是在 gcc -O3 或 clang -O2 处使用常规自动向量化器。这可能会切换到 NT 存储以获得大尺寸，这将有助于大多数如果多个内核竞争内存带宽。memset 模式识别是/即使没有自动矢量化也是有用的。）
这里唯一需要的别名分析是为了证明 list1[i] = 2 不会修改 list1 指针值本身（因为函数在循环内读取全局，而不是将值复制到本地人）。基于类型的别名分析（-fstrict-aliasing 默认情况下启用）允许编译器证明，and/or 如果 list1 指向自身，那么从外部访问将会有未定义的行为稍后循环迭代中的对象。
当您未能使用 __restrict 关键字（由多个编译器从 C 的 restrict 中借用）时，在某些情况下（例如输出数组与输入数组的输出数组），智能编译器可以并且确实会在自动矢量化之前检查重叠.如果有重叠，它们会退回到安全的标量循环。
但在这种情况下不会发生这种情况：gcc 和 clang 根本不会生成矢量化循环，它们只是在 myFunc1 中执行标量。如果每个存储都导致 L1d 中的冲突未命中，那么这比您为编译器提供足够的信息来完成其工作的情况差 4 倍。 （对于 32 字节存储，使用 AVX 的 8x）。通常情况下，当主内存带宽成为瓶颈（不是 L1d 缓存）时，16B 与 32B 存储之间的差异很小，但在这里它可能是一个大问题，因为如果 10 个输出流全部别名，则会破坏 L1d 的写入组合效果。
顺便说一句，使全局变量 static int *__restrict line1 等等确实允许 gcc 自动矢量化 myFunc1 中的存储。但是，它不会裂变循环。 （它会被允许，但我想它不是在寻找那种优化。这取决于程序员。）
// global modifier allows auto-vec of myFunc1
#define GLOBAL_MODIFIER __restrict
#define LOCAL_MODIFIER __restrict // inside myFunc1
static int *GLOBAL_MODIFIER list1, *GLOBAL_MODIFIER list2,
*GLOBAL_MODIFIER list3, *GLOBAL_MODIFIER list4,
*GLOBAL_MODIFIER list5, *GLOBAL_MODIFIER list6,
*GLOBAL_MODIFIER list7, *GLOBAL_MODIFIER list8,
*GLOBAL_MODIFIER list9, *GLOBAL_MODIFIER list10;
我把你的代码 on the Godbolt compiler explorer with gcc8.1 and clang6.0 加上那个更改 + 一个从数组之一读取的函数，以阻止它们完全优化（它们会这样做，因为我让它们 static。）
然后我们得到这个内部循环，它可能 运行 比做同样事情的标量循环快 4 倍。
.L12: # myFunc1 inner loop from gcc8.1 -O3 with __restrict pointers
movups XMMWORD PTR [rbp+0+rax], xmm9 # MEM[base: l1_16, index: ivtmp.87_52, offset: 0B], tmp108
movups XMMWORD PTR [rbx+rax], xmm8 # MEM[base: l2_17, index: ivtmp.87_52, offset: 0B], tmp109
movups XMMWORD PTR [r11+rax], xmm7 # MEM[base: l3_18, index: ivtmp.87_52, offset: 0B], tmp110
movups XMMWORD PTR [r10+rax], xmm6 # MEM[base: l4_19, index: ivtmp.87_52, offset: 0B], tmp111
movups XMMWORD PTR [r9+rax], xmm5 # MEM[base: l5_20, index: ivtmp.87_52, offset: 0B], tmp112
movups XMMWORD PTR [r8+rax], xmm4 # MEM[base: l6_21, index: ivtmp.87_52, offset: 0B], tmp113
movups XMMWORD PTR [rdi+rax], xmm3 # MEM[base: l7_22, index: ivtmp.87_52, offset: 0B], tmp114
movups XMMWORD PTR [rsi+rax], xmm2 # MEM[base: l8_23, index: ivtmp.87_52, offset: 0B], tmp115
movups XMMWORD PTR [rcx+rax], xmm1 # MEM[base: l9_24, index: ivtmp.87_52, offset: 0B], tmp116
movups XMMWORD PTR [rdx+rax], xmm0 # MEM[base: l10_25, index: ivtmp.87_52, offset: 0B], tmp117
add rax, 16 # ivtmp.87,
cmp rax, 40000000 # ivtmp.87,
jne .L12 #,
（当然，这是为 x86-64 编译的。x86 32 位没有足够的寄存器来将所有指针保存在 regs 中，所以你会有一些负载。但那些会在 L1d 中命中缓存，实际上并不是很大的吞吐量瓶颈：在每个时钟 1 个存储的瓶颈下，在这种情况下，您只需存储常量，就有足够的吞吐量来完成更多工作。）
这种优化就像将循环展开 4 次，然后将 4 个商店重新排列到每个数组中。这就是为什么如果编译器不知道它们不重叠就不能完成的原因。不幸的是，即使使用 __restrict，clang 也不会这样做。通常使用 __restrict 来保证不重叠是在函数参数上，而不是局部变量或全局变量，但我没有尝试过。
使用全局数组而不是全局指针，编译器会知道它们没有重叠（并且不会有指针值存储在内存中的任何地方；数组地址将是 link-时间常数.) 在您的版本中，数组本身具有动态存储，只有指向它们的指针具有静态存储。
交错式全缓存行存储：
如果 myFunc1 在移动到下一个数组之前将 64 个字节存储到一个数组中会怎么样？然后你的编译器可以安全地将它编译为每次迭代每个数组 4 (SSE)、2 (AVX) 或 1 (AVX512) 向量存储，覆盖完整的 64 字节。
如果您将指针按 64 位对齐（或者如果编译器进行了一些别名分析并到达每个输出数组中的第一个 64 字节边界），那么每个存储块都会完全写入一个缓存行，而我们以后不会再碰了
这样可以避免 L1d 冲突未命中，对吧？也许吧，但除非您使用 NT 存储来避免 RFO，否则硬件预取器需要在存储尝试提交之前将线路拉入 L2，然后拉入 L1d。所以它并不像您想象的那么简单，但是将存储组合到尚未到达的缓存行的写组合缓冲区可以提供帮助。
Intel CPUs 中的 L2 streamer 预取器可以跟踪每页 1 次前向访问和 1 次后向访问，所以它应该没问题（如果数组在 L2 中没有别名）。 L1d 预取是个大问题。
它仍然会大大减少跳转 to/from L2 的缓存行的数量。 如果你有一个循环不能轻易分裂成多个循环，至少展开它，这样你就可以在继续之前写一个完整的缓存行
AVX512 可能会有所作为； IDK 如果 Skylake-AVX512 上的对齐 vmovdqa64 [mem], zmm0 可能会在将缓存行进入 MESI 修改状态时跳过加载旧值，因为它知道它正在覆盖整个缓存行。 （如果在没有合并掩码的情况下完成）。
gcc8.1 即使使用 AVX512 也不会费心去对齐输出指针；一个可能重叠的第一个和最后一个向量可能是一个很好的策略，对于像这样的简单情况，在这种情况下，两次写入相同的内存不是问题。 （与 Skylake 硬件上的 AVX2 相比，对齐对 AVX512 的影响更大。）
4) Unexpectedly poor and weirdly bimodal performance for store loop on Intel Skylake 显示交错的虚拟写入（到 相同 位置）与存储流可以使对于 L1d / L2 带宽，它比 1 个连续流差。
可能是因为在提交到 L1d 缓存之前存储缓冲区中发生了存储合并/合并。但仅适用于同一缓存行的相邻存储（因为 x86 的强序内存模型不允许存储乱序提交到 L1d）。
该测试没有缓存冲突问题。但是，连续写入整个缓存行应该也会有所帮助。