c++ - 循环效率: merging loops

Question

我一直认为减少迭代次数是使程序更高效的方法。由于我从未真正确认过这一点，因此我开始进行测试。

我制作了以下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倍以上的时间。

的结果令人惊讶。在我的PC上，func1()大约需要349毫秒，而func2()大约需要32毫秒，第一个功能实际上要慢得多而不是更快。
PC运行Ubuntu 18.04，CPU为i3-8350K。

现在针对问题:我的测试正确吗？合并for循环以最大程度地减少迭代总数是否有用？人们有不同的经历吗？

更改函数调用的顺序将得到相同的结果。测量的时间变化很小(偏差很小)。

Answer 1

这里有三件重要的事情:

1)没有优化的基准测试是没有意义的。事实证明，在这种情况下会产生真正的效果，而这种效果不会随着优化而消失。实际上，在将循环计数器存储在内存中的额外成本(将循环计数器限制为每6个时钟1个对每个时钟1个)以及不自动向量化存储循环的情况下，一种反优化的调试版本隐藏了很多差异。

如果您还不了解为什么会有速度差异的asm + CPU微体系结构详细信息，那么在禁用优化的情况下对其进行测量既不安全也不有用。

2)高速缓存冲突未命中(如果数组都相对于页面边界对齐相同)。 相对于彼此倾斜数组可能会有很大帮助。这自然会发生，具体取决于它们的分配方式，即使它们的大小不是2的大幂。

数组很大，并且分别用new分配，因此它们可能都是页面对齐的(或者在将某些信息(例如大小)放在对象之前的实现中，它们与页面边界的偏移量为16B)。在Linux上，glibc malloc/new通常通过使用mmap()(并使用该模块的前16个字节进行簿记)从OS分配新鲜页面来处理大量分配，而不是移动brk()。

4k别名意味着它们都进入典型的L1d缓存中的同一集合，该缓存在典型的x86 CPU上是8路关联的。 Why is the size of L1 cache smaller than that of the L2 cache in most of the processors?解释了为什么64集* 64B/行= 4096B页面大小(乘以8路= 32kiB)不是巧合，因为这使VIPT L1d缓存像PIPT一样工作而没有同音/同义词问题。另请参阅Which cache mapping technique is used in intel core i7 processor?

第9个存储区将从第一个存储区逐出缓存行，因此每个存储区将逐出一次行，而不是像连续情况那样完全写入。 (除非编译器自动向量化，然后在继续之前将整个存储行缓存到一个阵列中。)x86的强序内存模型需要按照程序顺序将存储缓冲区中的存储提交到L1d，因此无法合并提交之前，将不相邻的同一行存储到一个行中；如果行不连续，则在行进入时提交多个未完成的存储。

(替换策略是伪LRU，不是真正的LRU，因此有时您可能会发现在同一组中驱逐8或9次后，线路仍然很热。)

提醒:，仅当所有数组相对于页面具有相同的对齐方式时，上述内容才适用。过度分配和为其中一个指针执行ptr = 128 + malloc(128 + size)可能会使它相对于其他指针倾斜，这有时是值得做的。

您说您有一台PC，所以我猜是Intel CPU。 (Ryzen的L1d具有相同的几何形状，但推土机家族则没有。)

(Intel's optimization manual第3.6.10节“写入合并”建议对写入四个以上输出流的循环进行循环裂变该建议位于有关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存储(绕过缓存)，在Skylake和更高版本上最多可以有12条输出流，在Broadwell/Haswell和更旧版本上最多可以有10条输出流。 (如果同时读取任何内存，则更少。)那就是这些CPU上的LFB(行填充缓冲区)的数量。较早的CPU(在Nehalem之前)少于10个，也许不能将它们全部用于NT存储。 (Where is the Write-Combining Buffer located? x86)LFB用于进出L1d的所有线路传输，例如挂起的负载丢失需要分配一个LFB来等待L2的那条线。

(使用超线程时，请记住，另一个超线程正在竞争同一物理核心上的LFB，因此除非您可以禁用HT，否则不要依赖于使用所有12个LFB。)

但是您没有在NT商店。

conventional wisdom是，此4输出效率限制也适用于普通(非NT)存储到WB内存，但现代Intel 并非如此。碰巧的是，普通(WB =写回)存储的性能下降的输出流数量与NT存储的数量相同。那篇机械同情的文章猜测了原因，但是我们可以肯定他们听起来不对。

有关一些微基准，请参见https://github.com/Kobzol/hardware-effects/issues/1。 (并查看我自己，BeeOnRope和Hadi Brais之间关于LFB的讨论，该LFB出现在此4输出准则上:https://chat.stackoverflow.com/transcript/message/45474939#45474939，以前在Size of store buffers on Intel hardware? What exactly is a store buffer?下进行评论

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

再次，通过超线程，几乎可以肯定，另一个逻辑核心如果正在运行，则将生成一些内存流量，因此，保守的限制(例如4个输出流)并不是一个坏计划。 但是性能不会在7或8时下降，因此如果花费更多的总精力，则不必裂开循环。

另请参阅Enhanced REP MOVSB for memcpy，以获取有关常规RFO存储与no-RFO NT存储的更多信息，以及许多x86内存带宽问题。 (特别是内存/L3缓存延迟限制了大多数CPU上的单核带宽，但在多核 Xeon上更糟:它们令人惊讶地具有比四核台式机更低的单核内存带宽。当有足够多的核忙时，您可以从四 channel 或六 channel 内存 Controller 中饱和其高聚合带宽；这是针对它们进行优化的情况。)

2.5)DRAM页的位置:当最终从L3(最后一级缓存)中驱出数据时，发生写回内存的操作。脏的缓存行被发送到内存 Controller ，后者可以缓冲并将它们成批地分组，但是仍然会有混合存储(和RFO加载)到所有10个阵列。双 channel 内存 Controller 不能一次打开10个DRAM页。 (我认为每个 channel 只有1个 channel ，但我不是DRAM时序专家。请参阅Ulrich Drepper的What Every Programmer Should Know About Memory，其中有一些详细信息。)https://pubweb.eng.utah.edu/~cs6810/pres/12-6810-15c.pdf提到了针对流存储与分散存储的DRAM打开/关闭页面策略。

最重要的是，即使高速缓存可以处理许多输出流，DRAM也可能会快乐一些。请注意，DRAM“页面”的大小与虚拟内存页面(4k)或大页面(2M)的大小不同。

说到虚拟内存，TLB应该可以有10个输出流:现代的x86 CPU拥有10个以上的L1dTLB条目。希望它们具有足够的关联性，或者条目不是全部别名，因此我们不会在每家商店都遇到TLB遗漏!

3)编译时别名分析

@RichardHodges发现了这个)

您的大型组合循环不会使用gcc或clang 自动向量化。他们无法证明list1[10]也不是list4[9]或其他东西，因此他们无法使用单个16字节存储来存储list1[8..11]。

但是单阵列循环可以轻松地通过SSE或AVX自动矢量化。 (令人惊讶的是，没有wmemset调用之类的东西，仅在gcc -O3或clang -O2处使用常规的自动矢量化程序。这可能会切换到大尺寸的NT存储，这在多个内核争用内存带宽时最有帮助。memset pattern-即使没有自动向量化功能，识别也将是有用的。)

这里唯一需要进行的别名分析是为了证明list1[i] = 2不会修改list1指针值本身(因为该函数读取循环内的全局变量，而不是将值复制到本地)。基于类型的别名分析(默认情况下为-fstrict-aliasing启用)允许编译器证明和/或如果list1指向自身，则在以后的循环迭代中访问对象外部将存在未定义的行为。

当您无法使用__restrict关键字(由C的限制所导致的几个编译器借用)时，在某些情况下(例如，输出数组相对于输入数组)，智能编译器可以并且确实在自动矢量化之前检查是否有重叠。如果存在重叠，它们将退回到安全的标量循环。

但这在这种情况下不会发生:gcc和clang根本不会生成矢量化循环，它们只是在myFunc1中进行标量处理。如果每个存储区都在L1d中导致冲突未命中，那么这将比您为编译器提供足够的信息来完成其工作的性能高4倍。 (或8x和AVX一起用于32字节存储)。通常，当主内存带宽成为瓶颈(不是L1d高速缓存)时，16B与32B存储之间的差异很小，但是在这里，这可能会很重要，因为如果10个输出流全部都是别名，则会破坏L1d的写合并效果。

顺便说一句，将全局变量设为static int *__restrict line1等确实允许gcc自动矢量化myFunc1中的存储。但是，它不会 split 循环。 (可以这样做，但我想它不是在寻找这种优化。这取决于程序员。)

// 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进行的编译。x8632位没有足够的寄存器来将所有指针保留在regs中，因此您会有一些负载。但是这些负载会进入L1d缓存中，而实际上并不会吞吐量瓶颈很大:在每个时钟瓶颈1个存储的情况下，在仅存储常量的情况下，有很多吞吐量可以完成更多工作。)

这种优化就像展开循环4x并重新排列以将4个存储分组到每个数组一样。这就是为什么如果编译器不知道它们是非重叠的，则无法完成的原因。不幸的是，即使使用__restrict，clang也不会这样做。 __restrict保证不重叠的正常使用是在函数args上，而不是在locals或globals上，但是我没有尝试过。

使用全局数组而不是全局指针，编译器将知道它们没有重叠(并且不会在内存中的任何位置存储指针值；数组地址将是链接时常量。)在您的版本中，数组本身具有动态存储，只有指向它们的指针才具有静态存储。

交错的全缓存行存储:

如果myFunc1在继续前进到下一个数组之前将64个字节存储到一个数组中怎么办？然后，您的编译器可以在每次迭代时安全地将其编译为每个数组4个(SSE)，2个(AVX)或1个(AVX512) vector 存储区，覆盖整个64个字节。

如果您将指针对齐64(或者如果编译器进行了别名分析并到达每个输出数组的第一个64字节边界)，则每个存储块将完全写入一个缓存行，而我们不会碰它稍后再试。

这样可以避免L1d冲突失败，对吗？好吧，也许吧，但是除非您使用NT商店来避免RFO，否则硬件预取程序需要先将线拉入L2，然后再将线拉入L1d，然后再尝试提交存储。因此，这并不像您想的那么简单，但是将存储合并到尚未到达的行的写合并缓冲区可以提供帮助。

Intel CPU中的L2流媒体预取器可以跟踪每页1个正向访问和1个向后访问，因此应该没问题(如果阵列在L2中没有别名)。最大的问题是L1d预取。

仍然会大大减少往返于L2的高速缓存行的数量。 如果您遇到了无法轻易 split 为多个循环的循环，请至少展开该循环，以便可以在继续进行之前编写完整的缓存行

AVX512可能会有所作为； IDK(如果Skylake-AVX512上对齐的vmovdqa64 [mem], zmm0可以使高速缓存行进入MESI Modified状态时可以跳过加载旧值，因为它知道它会覆盖整个高速缓存行)。 (如果完成时没有合并掩码)。

即使使用AVX512，gcc8.1也不麻烦对齐输出指针。对于像这样的简单情况(两次写相同的内存都不是问题)的简单情况，可能重叠的第一个和最后一个 vector 可能是一个好的策略。 (与Skylake硬件上的AVX2相比，对齐对AVX512的影响更大。)

4)Unexpectedly poor and weirdly bimodal performance for store loop on Intel Skylake 表明，对于L1d/L2带宽，将伪写入(到同一位置)与存储流进行交织可能比1个连续流更糟。

可能是因为在提交到L1d缓存之前，存储缓冲区中发生了存储合并/合并。但是仅适用于同一高速缓存行的相邻存储(因为x86的强排序内存模型不能允许存储无序地提交给L1d)。

该测试不会遭受缓存冲突问题的困扰。但是连续编写一条整个缓存行也应该对此有所帮助。