循环优化（Loop Optimizations）

循环是几乎所有高性能程序的核心。由于循环代表了大量执行的代码片段，它们占据了执行时间的大部分。在这样的关键代码片段中的微小改变可能对程序性能产生巨大影响。这就是为什么仔细分析程序中热循环的性能并了解可能的改进方法如此重要。

在本节中，我们将介绍针对上述各类瓶颈的最著名的循环优化技术。我们首先在 [LowLevelLoopOpts] 中讨论低级优化，这类优化只在单个循环内移动代码。接着，在 [LoopOptsHighLevel] 中，我们将介绍重构循环的高级优化，这类优化通常会影响多个循环。注意，这里呈现的并非所有已知循环变换的完整列表。关于以下每种变换的更详细信息，读者可参考 [EngineeringACompilerBook] 和 [OptimizingCompilersForModernArchs]。

低级优化（Low-level Optimizations）

让我们从简单的循环优化开始，这些优化变换单个循环内的代码：循环不变量代码外提（Loop Invariant Code Motion）、循环展开（Loop Unrolling）、循环强度削减（Loop Strength Reduction）和循环解开关（Loop Unswitching）。通常，编译器擅长进行这类变换；然而，有些情况下编译器可能需要开发者的协助。我们将在后续章节中讨论这些情况。

循环不变量代码外提（Loop Invariant Code Motion，LICM）：在循环的所有迭代中值从不改变的表达式称为循环不变量（loop invariant）。由于其值在循环迭代中不变，我们可以将循环不变量表达式移出循环。为此，我们将结果存储在临时变量中，并在循环内使用它（见清单 LICM）。¹⁷ 如今，所有优秀的编译器在大多数情况下都能成功执行 LICM。

清单：循环不变量代码外提

for (int i = 0; i < N; ++i)             for (int i = 0; i < N; ++i) {
  for (int j = 0; j < N; ++j)    =>       auto temp = c[i];
    a[j] = b[j] * c[i];                   for (int j = 0; j < N; ++j)
                                            a[j] = b[j] * temp;
                                        }

循环展开（Loop Unrolling）：归纳变量（induction variable）是循环中的一个变量，其值是循环迭代次数的函数。例如 v = f(i)，其中 i 是迭代次数。与其在每次迭代中修改归纳变量，我们可以展开循环，对归纳变量的每次递增执行多次迭代（见清单 Unrol）。

清单：循环展开

                                        int i = 0;
for (int i = 0; i < N; ++i)             for (; i+1 < N; i+=2) {
  a[i] = b[i] * c[i];          =>         a[i]   = b[i]   * c[i];
                                          a[i+1] = b[i+1] * c[i+1];
                                        }
                                        // remainder (when N is odd)
                                        for (; i < N; ++i)
                                          a[i] = b[i] * c[i];

循环展开的主要好处是每次迭代可以执行更多计算。在每次迭代结束时，索引值必须递增和测试，然后如果还有更多迭代要处理，则返回循环顶部。这项工作通常被称为"循环开销"或"循环税"，可以通过循环展开来减少。例如，将清单 Unrol 中的循环按因子 2 展开，可以将执行的比较和分支指令数量减少 2 倍。

我不建议手动展开循环，除非需要打断循环携带依赖，如清单 DepChain 所示。首先，编译器非常擅长自动执行此操作，并且通常能选择最优的展开因子。其次，由于处理器乱序推测执行引擎，处理器有一个"内置展开器"（见 [uarch]）。当处理器等待第一次迭代中的长延迟指令完成时（例如加载、除法、微码指令、长依赖链），它会推测性地开始执行第二次迭代的指令，只等待循环携带的依赖。这跨越了多个迭代，有效地在指令重排序缓冲区（Reorder Buffer，ROB）中展开循环。第三个原因是过度展开可能由于代码膨胀导致负面后果。

循环强度削减（Loop Strength Reduction，LSR）：用更便宜的指令替换昂贵的指令。这种变换可以应用于所有使用归纳变量的表达式。强度削减通常应用于数组索引。编译器通过分析变量值如何在循环迭代中演变来执行 LSR。在 LLVM 中，这被称为标量演化（Scalar Evolution，SCEV）。在清单 LSR 中，对于编译器来说，相对容易地证明内存位置 b[i*10] 是循环迭代次数 i 的线性函数，因此可以用更便宜的加法替换昂贵的乘法。

清单：循环强度削减

for (int i = 0; i < N; ++i)             int j = 0;
  a[i] = b[i * 10] * c[i];      =>      for (int i = 0; i < N; ++i) {
                                          a[i] = b[j] * c[i];
                                          j += 10;
                                        }

循环解开关（Loop Unswitching）：如果循环内有一个不变的条件语句，我们可以将其移出循环。为此，我们复制循环体并将每个版本分别放置在条件语句的 if 和 else 子句内（见清单 Unswitch）。虽然循环解开关可能使代码量加倍，但每个新循环现在可以单独优化。

清单：循环解开关

for (i = 0; i < N; i++) {               if (c)
  a[i] += b[i];                           for (i = 0; i < N; i++) {
  if (c)                       =>           a[i] += b[i];
    b[i] = 0;                               b[i] = 0;
}                                         }
                                        else
                                          for (i = 0; i < N; i++) {
                                            a[i] += b[i];
                                          }

高级优化（High-level Optimizations）

高级循环变换改变循环的结构，通常影响多个嵌套循环。在本节中，我们将介绍循环交换（Loop Interchange）、循环分块（Loop Blocking / Tiling）、循环融合与分裂（Loop Fusion and Distribution / Fission）以及循环展开与合并（Loop Unroll and Jam）。这组变换旨在改善内存访问，消除内存带宽和内存延迟瓶颈。从编译器的角度来看，证明这类变换的合法性并证明其性能收益非常困难。从这个意义上说，开发者处于更有利的位置，因为他们只需要关心其特定代码片段中变换的合法性。遗憾地，这通常意味着我们必须手动进行这类变换。

循环交换（Loop Interchange）：是交换嵌套循环顺序的过程。内层循环使用的归纳变量切换到外层循环，反之亦然。清单 Interchange 展示了交换 i 和 j 嵌套循环的示例。循环交换的主要目的是对多维数组元素进行顺序内存访问。通过按照元素在内存中的布局顺序访问，我们可以改善内存访问的空间局部性，使代码对缓存更友好。这一变换有助于消除内存带宽和内存延迟瓶颈。

清单：循环交换

for (i = 0; i < N; i++)                 for (j = 0; j < N; j++)
  for (j = 0; j < N; j++)          =>     for (i = 0; i < N; i++)
    a[j][i] += b[j][i] * c[j][i];           a[j][i] += b[j][i] * c[j][i];

循环交换只有在循环完全嵌套（perfectly nested）时才合法。完全嵌套循环是指所有语句都在最内层循环中的循环。交换不完全嵌套的循环更难实现，但仍然可能；请查看 Codee¹ 目录中的示例。

循环分块（Loop Blocking / Tiling）：这种变换的思想是将多维执行范围分割成更小的块（blocks 或 tiles），使每个块都能放入 CPU 缓存中。如果算法处理大型多维数组并对其元素进行跨步访问，则很可能导致缓存利用率低下。每次这样的访问可能将未来访问所需的数据从缓存中驱逐出去（缓存驱逐，cache eviction）。通过将算法划分为更小的多维块，我们确保循环中使用的数据在被重用之前一直保留在缓存中。

在清单 blocking 所示的示例中，算法在以行主序遍历数组 a 的元素时，以列主序遍历数组 b。可以将循环嵌套划分为更小的块，以最大化数组 b 中元素的重用。

清单：循环分块

// linear traversal                     // traverse in 8*8 blocks
for (int i = 0; i < N; i++)             for (int ii = 0; ii < N; ii+=8)
  for (int j = 0; j < N; j++)    =>      for (int jj = 0; jj < N; jj+=8)
    a[i][j] += b[j][i];                   for (int i = ii; i < ii+8; i++)
                                           for (int j = jj; j < jj+8; j++)
                                            a[i][j] += b[j][i];
                                        // remainder (not shown)

循环分块是优化通用矩阵乘法（GEneral Matrix Multiplication，GEMM）算法的广为人知的方法。它增强了内存访问的缓存复用，改善了内存带宽利用率和内存延迟。

通常，工程师针对每个 CPU 核心私有缓存的大小来优化分块算法（Intel 和 AMD 的 L1 或 L2，Apple 的 L1）。然而，私有缓存的大小在不同代之间会发生变化，因此硬编码块大小有其自身的挑战。作为替代方案，你可以使用缓存无关²（cache-oblivious）算法，其目标是对任何大小的缓存都能合理地工作。

循环融合与分裂（Loop Fusion and Distribution / Fission）：当独立的循环在相同范围内迭代且不互相引用数据时，可以将它们融合。清单 fusion 展示了循环融合的示例。相反的操作称为循环分裂（Loop Distribution / Fission），即将循环分割成独立的循环。

清单：循环融合与分裂

for (int i = 0; i < N; i++)             for (int i = 0; i < N; i++) {
  a[i].x = b[i].x;                        a[i].x = b[i].x;
                               =>         a[i].y = b[i].y;
for (int i = 0; i < N; i++)             }
  a[i].y = b[i].y;

循环融合有助于减少循环开销（类似于循环展开），因为两个循环可以使用相同的归纳变量。此外，循环融合可以帮助改善内存访问的时间局部性。在清单 fusion 中，如果结构的 x 和 y 成员恰好位于同一缓存行上，最好融合两个循环，因为这样可以避免两次加载同一缓存行。这将减少缓存占用并提高内存带宽利用率。

然而，循环融合并不总是能提高性能。有时最好将循环分割成多个遍（passes），对数据进行预过滤、排序和重新组织等。通过将大循环分裂成多个较小的循环，我们限制了每次循环迭代所需的数据量，并增加了内存访问的时间局部性。这在缓存竞争激烈的情况下很有帮助，通常发生在大循环中。循环分裂还能减少寄存器压力，因为在每次循环迭代中执行的操作更少。此外，将大循环分解为多个较小的循环可能对 CPU 前端性能有利，因为指令缓存利用率更好。最后，分裂后，每个小循环可以由编译器单独进一步优化。

循环展开与合并（Loop Unroll and Jam）：要执行此变换，首先需要展开外层循环，然后将多个内层循环合并（jam / fuse）在一起，如清单 unrolljam 所示。此变换增加了内层循环的指令级并行度（Instruction-Level Parallelism，ILP），因为内层循环中执行了更多独立指令。在代码示例中，内层循环是一个归约（reduction）操作，累加数组 a 和 b 元素之间的差值。当我们以因子 2 展开并合并循环嵌套时，我们实际上同时执行原始外层循环的两次迭代。这通过两个独立的累加器来体现。这打断了初始版本中 diffs 上的依赖链。

清单：循环展开与合并

for (int i = 0; i < N; i++)           for (int i = 0; i+1 < N; i+=2)
  for (int j = 0; j < M; j++)           for (int j = 0; j < M; j++) {
    diffs += a[i][j] - b[i][j];   =>      diffs1 += a[i][j]   - b[i][j];
                                          diffs2 += a[i+1][j] - b[i+1][j];
                                        }
                                      diffs = diffs1 + diffs2;
                                      // remainder (not shown)

只要外层循环没有跨迭代依赖，即内层循环的两次迭代可以并行执行，循环展开与合并就是合法的。此外，如果内层循环的内存访问在外层循环索引（这里是 i）上是跨步的，这种变换才有意义，否则其他变换可能更适用。展开与合并技术在内层循环的行程计数（trip count）较低时特别有用，例如小于 4。通过进行变换，我们将更多独立操作打包到内层循环中，从而增加 ILP。

展开与合并变换有时对外层循环向量化非常有用，在撰写本文时，编译器还无法自动完成外层循环向量化。在内层循环的行程计数对编译器不可见的情况下，编译器仍然可以对原始内层循环进行向量化，希望它会执行足够多的迭代以命中向量化代码（更多关于向量化的内容见下一节）。但如果行程计数较低，程序将使用慢速标量版本的循环。通过执行展开与合并，我们使编译器能够以不同方式向量化代码：将内层循环中的独立指令"粘合"在一起。这种技术也被称为超字级并行（Superword-Level Parallelism，SLP）向量化。

发现循环优化机会（Discovering Loop Optimization Opportunities）

正如我们在本节开头所讨论的，编译器将承担优化循环的繁重工作。你可以依赖编译器对循环代码做出所有显而易见的改进，比如消除不必要的工作、进行各种窥孔优化（peephole optimizations）等。有时编译器足够智能，能自动生成快速版本的循环，但其他时候我们必须进行一些重写来帮助编译器。正如前面所说，从编译器的角度来看，合法且自动地进行循环变换非常困难。当编译器无法证明变换的合法性时，通常必须保守行事。

作为第一步，你可以检查编译器优化报告或检查循环的机器代码¹⁶，寻找易于改进的地方。有时，可以使用用户指令调整编译器变换。有一些控制特定变换的编译器 pragma，如循环向量化、循环展开、循环分裂等。有关用户指令的完整列表，请查阅编译器手册。

接下来，你应该识别循环中的瓶颈，并根据硬件理论最大值评估性能。自顶向下微架构分析（Top-down Microarchitecture Analysis，TMA，见 [TMA]）方法论和 Roofline 性能模型（[roofline]）都可以帮助实现这一点。循环的性能受到以下一个或多个因素的限制：内存延迟、内存带宽或机器的计算能力。一旦识别出循环中的性能瓶颈，尝试应用我们在前几节中讨论的所需变换。

尽管对于特定的计算问题存在众所周知的优化技术，但循环优化仍然是一门随经验积累的"黑色艺术"。我建议你依赖编译器，并在必要时手动变换代码作为补充。最重要的是，保持代码尽可能简单，不要在性能收益可以忽略不计时引入不合理的复杂修改。

¹. Codee：完全循环嵌套 - https://www.codee.com/catalog/glossary-perfect-loop-nesting/ ↩

². 缓存无关算法 - https://en.wikipedia.org/wiki/Cache-oblivious_algorithm ↩

¹⁶. 有时很困难，但总是很有收获的活动。 ↩

¹⁷. 只有当编译器能证明 a 和 c 不存在别名（alias）时，编译器才会执行该变换。 ↩