ICS06 优化程序性能

type

status

date

slug

summary

优化 Optimization

代码优化是提升软件性能的关键步骤。本文将探讨代码优化的核心思想，包括机器无关的普适性优化、机器相关的特殊优化以及循环优化策略，分析现代 CPU 架构对优化策略的影响。此外，讨论编译器优化的局限性以及一些克服这些局限性的方法。最终目标是编写高效的代码，最大限度地利用硬件资源。

性能优化主旨

高效的代码需要关注多个方面。从算法和数据结构的选择，到编译器的有效利用，以及并行计算的应用，都是提升性能的关键。尤其需要注意避免“渐进低效率”的情况，即在小数据集上表现良好，但在实际部署后，由于数据规模的增大，原本的算法或数据结构反而成为性能瓶颈。

编译器（Compiler）

编译器在代码优化中扮演着至关重要的角色。它可以执行寄存器的分配和调度、代码的重新排序和规划，以及赘余代码的消除等操作。然而，编译器的优化策略通常是保守的，以确保程序行为的正确性。这意味着编译器不会进行可能引入风险的优化。大多数优化是在函数内部进行的，跨函数优化由于其复杂性，较少被采用。然而，像GCC等编译器的新版本已经具备了单文件、跨函数优化的能力。

普适性优化（Machine-Independent）

普适性优化策略指的是在不同的处理器和编译器上都有效的优化方法。

减少重复运算

当循环体中存在重复且结果确定的运算时，可以将该运算移出循环体，只计算一次，从而减少运算次数。

降低运算复杂性

通过将复杂的运算转换为简单的运算，例如将乘除法转换为移位操作，可以降低运算的复杂性。当乘法需要多个 CPU 时钟周期时，这种转换可以有效节省时间。

面向编译器优化

在上述示例中，strlen(s) 在每次循环迭代中都会被重新计算。编译器通常不会对此进行优化，因为它无法确定字符串 s 的长度是否在循环体中发生变化，或者 strlen 函数是否会产生副作用（例如修改全局变量）。为了帮助编译器进行优化，可以在进入循环前将字符串长度预先计算并存储在一个变量中。

使用 inline 关键字将一些简单的函数声明为内联函数，可以有效地发挥编译器的优化功能。

面向内存优化

CPU 与缓存/内存的交互需要多个时钟周期，因此应尽可能减少访存次数。然而，编译器有时并不会进行访存优化。

在计算矩阵 A 每行元素的和并存储到向量 B 中的示例中，编译器可能不会对 b[i] += a[i][j] 进行优化，例如使用寄存器变量 sum 进行累加，最后再将 sum 写入 b[i]。这是因为编译器需要考虑内存别名的问题，即指针 a 和 b 是否可能指向相同的或有交集的内存区域。为了避免这种情况，程序员可以手动减少访存次数，例如使用寄存器变量进行中间计算。

内存别名使用: 指的是函数传指针时，两个指针可能指向相同的或有交集的内存区域，而非完全独立。编译器在执行优化时必须谨慎处理指针参数，以避免潜在的内存别名问题。

衡量性能指标：CPE

CPE (Cycle-Per-Element) 指的是每个元素运算所需的时钟周期数。总周期可以表示为，其中是元素数量，是其他开销。通过绘制与的关系图，并计算斜率和截距，可以得到和的值。当数据规模很大时，总周期可以近似为。

特殊优化（Machine-Dependent）

特殊优化策略需要考虑程序运行的特定处理器/ISA 架构。

跳转/条件跳转

当处理器计算跳转目标地址时，编译器可以优化程序，让处理器在跳转前的阶段执行一些不相关的指令。

充分利用 CPU 多个算术单元

现代 CPU 的执行阶段通常包含多个算术单元。在进行多周期运算（例如乘法）时，编译器可以合理安排运算指令，使运算流水线化，并让 CPU 在每个周期内同时执行多个运算。

超标量处理器 (Superscalar Processor):

可以在一个周期内发射 (issue) 和执行 (execute) 多条指令（指令级并行），并且是乱序的。(issue 位于 decode 和 execute 之间的阶段)。现代处理器通常是 4 发射（一次发射 4 条指令）。

现代 CPU（例如 Haswell）

现代 CPU 通常分为指令控制单元 (ICU) 和执行单元 (EU)。

取指阶段: ICU 中的指令控制单元采用分支预测和投机执行。投机执行时，结果不会写入寄存器或内存，以便在预测错误时回溯到分支前的状态。译码阶段将指令分解成许多微操作 (OP/load/store/...), 并发射给 EU 执行。

执行阶段: EU 包含多个功能单元 (Functional Units)，例如 load/store 单元、整数运算器、浮点运算器和分支器等。执行单元之间可以直接交换信息，并使用寄存器重命名 (Register Renaming) 机制来避免数据冲突。

写回阶段: ICU 中的退役单元 (Retirement Unit) 确保操作按照程序的顺序执行，并保存对寄存器堆的修改操作，直到它们被确认为退休（分支预测正确，写入）或清空（分支预测错误，不写入）。

我们以一个简单的例子来说明编译器如何利用多个算术单元进行流水线化和并行运算，假设我们的 CPU 有两个乘法器，每个乘法器的延迟为 3 个周期，但可以流水线化，这意味着每个周期可以开始一个新的乘法运算。

场景： 计算数组中所有元素的乘积。

未优化的代码：

在这个代码中，每次循环迭代都依赖于上一次迭代的结果，因此乘法运算必须顺序执行。如果 n 很大，这将非常耗时。

优化后的汇编代码（概念性示例，实际编译器生成的汇编代码会更复杂）：

解释：

加载两个元素：每次循环迭代加载两个数组元素 arr[i] 和 arr[i+1] 到不同的寄存器 (例如 xmm0 和 xmm1)。

并行乘法：利用两个乘法器，同时执行 product * arr[i] 和另一个乘法运算 (例如与上一个循环迭代的结果的一部分相乘，这取决于具体的流水线安排)。

由于乘法器可以流水线化，即使每个乘法需要 3 个周期，我们也可以在每个周期开始一个新的乘法运算。

这个例子中隐含了循环展开的思想，每次迭代处理两个元素。

最后，需要将两个乘法器的结果合并到最终的 product 中。

通过这种方式，编译器可以充分利用 CPU 的多个算术单元和流水线特性，从而显著提高乘法运算的效率。虽然实际的编译器优化会更加复杂，涉及到指令调度、寄存器分配等细节，但核心思想是相同的：并行执行独立的运算，并利用流水线重叠不同运算的执行时间。

功能单元的性能

每个运算的性能可以用以下指标来刻画：

延迟 (latency): 完成运算所需的总时间。

发射时间 (issue time): 两个同类型运算之间所需的最小周期数。

容量 (capacity): 能够执行该运算的单元数量。

部分指令的最小延迟 (也即 CPE) 超过 1 个周期，但可以被流水线化。例如，load/store (4 周期)、整数乘法 (3)、浮点加法 (3)、浮点乘法 (5) 都可以被流水线化（运算每个周期只占用一部分运算单元），使得 1 个周期可以吞吐 1 条指令 (发射时间为 1，称为 fully-pipelined)。整数除法和浮点除法则需要 3-30 个周期不等的延迟，且不能被流水线化 (因为运算全程均需要占用全部的运算单元，发射时间 = 延迟)。

处理器吞吐量: 吞吐量 = 每时钟周期 (容量 / 发射时间) 个操作。例如，整数操作吞吐量为 (4/1) = 4，整数乘法和浮点加法吞吐量为 (1/1) = 1，浮点乘法吞吐量为 (2/1) = 2。

循环优化

评估循环的制约因素

循环的性能受到循环体内寄存器访问模式的影响。循环寄存器之间的操作链决定了数据相关性，而数据相关性限制了性能。换句话说，循环的性能由所有循环寄存器完成一次循环所需的最长时间（即关键路径（Critical Path）的长度）所制约。

循环展开

循环展开通过增加每次迭代的元素数量来减少循环次数。然而，循环展开只适用于循环控制开销（即对循环变量，如i的运算）大于循环内计算开销的情况。-O3 或更高优化等级时，编译器会自动进行循环展开。例如：

循环分解（多个累积变量）

循环分解将满足交换律和结合律的合并运算分割成多个部分，并在最后合并结果。这种方法适用于循环内的数据相关性是主要制约因素的情况。需要注意的是，浮点加法和乘法并不总是满足结合律。例如：

形式化地，我们记循环展开为k*1循环展开（每次迭代计算k次，数据分割为1份）；记循环分解为k*k循环展开（每次迭代计算k次，数据分割为k份）

循环展开 + 重新结合运算

在k*1循环展开中重新排列运算顺序，优先结合只读元素，可以减少迭代内的数据相关性。例如：

注意：并行度 k 不能无限大。当 k 超过可用寄存器数量时 (寄存器溢出)，编译器会将部分变量存储在内存中，反而降低性能。

补充

SIMD (Single Instruction Multiple Data)

Intel 基于 SIMD 引入了 SSE (Streaming SIMD Extension) 指令集。SSE 使用 AVX 向量寄存器 (32 字节) 和 GPU 等独立部件进行并行计算，适用于向量加法等操作。

预测分支错误

预测分支错误（Mispredict）会导致流水线清空，是现代处理器性能的主要限制之一。使用条件传送指令可以显著降低分支预测错误的概率。

内存性能制约

内存访问速度通常是循环性能的瓶颈。即使运算速度很快，内存访问延迟也会限制整体性能。

总结

编译器优化掣肘 (Optimization Blocker)

影响编译器优化程序的因素有以下几种：

内存别名使用。函数传指针时，两个指针可能指向相同的或有交集的内存区域，而非完全独立。解决方案：传递值而不是指针；手动优化代码逻辑。

函数调用可能的副作用。例如在for循环中调用strlen函数时，编译器无法确定每次调用是否会改变其他的全局状态。解决方案：使用内联函数（finline 以及 O1 或更高优化等级时，编译器会尝试进行单文件内的函数内联，但无法跨文件内联）。然而，在使用 GDB 调试和进行代码剖析评估性能时，避免使用内联函数。

优化思路总结

面向编译器优化: 如上所述，编写代码时应考虑编译器的优化策略。

高级设计: 选择合适的算法和数据结构是优化的第一步。

基本编码原则:

移动代码减少重复运算 (例如将 strlen 移到循环外)。
降低运算复杂性 (例如将乘法改为移位)。
消除不必要的内存引用 (例如使用寄存器变量进行累加)。

低级优化:

循环展开 (+ 重新结合运算)。
循环分解 (多个累积变量)。
使用条件传送指令避免分支预测错误。

总而言之，代码优化是一个迭代的过程，需要结合具体的硬件架构和应用场景进行调整。通过理解编译器的行为和硬件的特性，并运用合适的优化策略，可以显著提升代码的性能。

.lazy-image-placeholder{ background: linear-gradient(90deg,#0001 33%,#0005 50%,#0001 66%) #f2f2f2; background-size:300% 100%; animation: l1 1s infinite linear; } @keyframes l1 { 0% {background-position: right} } ICS06 优化程序性能