文章摘要
GPT 4
此内容根据文章生成，并经过人工审核，仅用于文章内容的解释与总结
投诉

软件性能工程—多角度讨论性能优化

[!NOTE]

前情提要

Ben尝试优化以下代码：

1
2
3
4
5
6
7
/* The elements of A and B are known to be nonnegative and not
aliased */
/* k is known only at runtime */
static const int N = (1 << 30);
for (int i = 0; i < N; i++) {
A[i] = k * B[i];
}

他优化后的代码如下：

1
2
3
4
5
6
7
8
9
10
/* The elements of A and B are known to be nonnegative and not
aliased */
/* k is known only at runtime */
static const int N = (1 << 30);
A[N - 1] = -1;
int *a = A , *b = B;
while (*a >= 0) {
*(a++) = k * *(b++) ;
}
*a = k * *b;

他使用 gcc -O3 模式分别编译两段代码，竟然发现优化后代码比未优化的代码还要慢😭，为什么❓

解答

提到了gcc -o3，我们首先探究一下, gcc的不同级别优化

1. -O0（无优化）

  • 目标：不进行任何优化，保持代码的原始结构。
  • 特点：
    • 编译速度最快。
    • 生成的代码与源代码几乎一一对应，适合调试。
  • 适用场景：开发阶段，尤其是调试代码时。
  • 具体优化：
    • 无优化，保留所有调试信息。

2. -O1（基本优化）

  • 目标：在减少代码大小和执行时间的同时，保持编译速度。
  • 特点：
    • 优化程度较低，编译时间较短。
    • 生成的代码仍然易于调试。
  • 适用场景：对性能和编译时间有平衡需求的场景。
  • 具体优化：
    • 常量传播：将常量值直接替换到表达式中。
    • 死代码消除：移除不会被执行的代码。
    • 简单函数内联：将小函数直接内联到调用处。
    • 跳转优化：优化跳转指令，减少不必要的跳转。

3. -O2（中等优化）

  • 目标：显著提高程序性能，同时保持合理的编译时间。
  • 特点：
    • 优化程度较高，生成的代码性能显著提升。
    • 编译时间较长，但生成的代码仍然可靠。
  • 适用场景：生产环境中的大多数应用。
  • 具体优化：
    • 循环优化：
      • 循环展开（Loop Unrolling）：将循环体展开，减少循环控制的开销。
      • 循环不变代码外提（Loop Invariant Code Motion）：将循环中不变的代码移到循环外。
    • 指令调度：重新排列指令，以充分利用 CPU 的流水线。
    • 函数克隆：为不同的调用场景生成特定版本的函数。
    • 分支预测优化：优化分支指令，减少分支预测错误。
    • 全局优化：跨函数优化，例如跨过程常量传播。

4. -O3（最高级别优化）

  • 目标：最大限度地提高程序性能，即使以增加代码大小为代价。
  • 特点：
    • 优化程度最高，生成的代码性能最优。
    • 编译时间最长，生成的代码可能较大。
  • 适用场景：对性能要求极高的场景，如科学计算、游戏引擎、高性能计算等。
  • 具体优化：
    • 循环向量化：将循环中的操作转换为 SIMD（单指令多数据）指令，利用 CPU 的向量寄存器。
    • 自动并行化：尝试将循环中的操作并行化。
    • 过程间优化（IPA）：跨函数进行更激进的优化。
    • 更激进的函数内联：将更多函数直接内联到调用处。
    • 内存访问优化：优化内存访问模式，减少缓存未命中的情况。

因此我们可以针对 -o3对于不同代码的优化效果谈谈

1. 循环展开

对于第一种可能会是：

1
2
3
4
5
6
7
8
9
10
int i;
for (i = 0; i <= N - 4; i += 4) {
    A[i] = k * B[i];
    A[i + 1] = k * B[i + 1];
    A[i + 2] = k * B[i + 2];
    A[i + 3] = k * B[i + 3];
}
for (; i < N; i++) {
    A[i] = k * B[i];
}
  • 减少循环控制开销：循环变量更新和条件检查的次数减少为原来的 1/4。
  • 提高指令级并行性：展开后的循环体可以更好地利用 CPU 的流水线。
  • 减少分支预测错误：循环条件检查的次数减少，分支预测错误的概率降低。

对于第二种则是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
while (1) {
    if (a[0] < 0) break;
    a[0] = k * b[0];
    if (a[1] < 0) break;
    a[1] = k * b[1];
    if (a[2] < 0) break;
    a[2] = k * b[2];
    if (a[3] < 0) break;
    a[3] = k * b[3];
    a += 4;
    b += 4;
}
if (*a >= 0) {
    *a = k * *b;
}
  • 第一种循环（固定次数）：GCC 可以完全自动展开，展开效果显著。
  • 第二种循环（动态终止条件）：GCC 也可以尝试展开，但由于循环次数动态确定，展开的难度较大，优化效果可能不如固定次数循环明显。

    2. 循环向量化

这是o3对于循环展开的进一步优化

  • 对于第一种代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <immintrin.h> // AVX2 头文件

static const int N = (1 << 30); // N = 2^30
__m256i vec_k = _mm256_set1_epi32(k); // 将 k 广播到向量寄存器
int i;
for (i = 0; i <= N - 8; i += 8) {
    __m256i vec_b = _mm256_loadu_si256((__m256i*)&B[i]); // 加载 B 的 8 个元素
    __m256i vec_a = _mm256_mullo_epi32(vec_b, vec_k);    // 并行乘法
    _mm256_storeu_si256((__m256i*)&A[i], vec_a);         // 存储结果到 A
}
for (; i < N; i++) {
    A[i] = k * B[i]; // 处理剩余元素
}

可以注意到之前串行运行的乘法运算可以并行计算了

  • 对于第二种代码，想要进行并行乘法计算就需要多很多代码量：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <immintrin.h> // AVX2 头文件

static const int N = (1 << 30); // N = 2^30
A[N - 1] = -1; // 设置哨兵值
int *a = A, *b = B;
__m256i vec_k = _mm256_set1_epi32(k); // 将 k 广播到向量寄存器

while (1) {
    // 检查是否满足终止条件
    if (a[0] < 0) break;
    if (a[1] < 0) {
        a[0] = k * b[0];
        break;
    }
    if (a[2] < 0) {
        a[0] = k * b[0];
        a[1] = k * b[1];
        break;
    }
    if (a[3] < 0) {
        a[0] = k * b[0];
        a[1] = k * b[1];
        a[2] = k * b[2];
        break;
    }

    // 处理 4 个元素
    __m256i vec_b = _mm256_loadu_si256((__m256i*)b); // 加载 B 的 8 个元素
    __m256i vec_a = _mm256_mullo_epi32(vec_b, vec_k); // 并行乘法
    _mm256_storeu_si256((__m256i*)a, vec_a);         // 存储结果到 A

    // 更新指针
    a += 4;
    b += 4;
}

// 处理剩余元素
if (*a >= 0) {
    *a = k * *b;
}

当然这也只是大概的样子，不过可以看出其复杂性，并且并没有第一种优化程度大。

3. 分支预测

  • 对于第一种代码：

在循环展开后，判断次数减少，分支预测次数减少；由于循环条件 i < N 是一个简单的比较操作，且 N 是常量，GCC 会生成高效的机器指令。

用T表示判断正确F表示判断错误的话，循环条件的判断应该是：TTTTTTTTTTTTF这种，分支预测的错误率会很低。

  • 对于第二种代码：

虽然每次判断的结果也是TTTTTTTTTTF这种，但是由于：

(1) 内存访问的延迟

  • *a >= 0 需要从内存中加载 *a 的值，而内存访问的延迟较高。
  • 在加载 *a 的值之前，分支预测器无法确定条件的结果，因此可能只能基于历史行为进行预测。

(2) 数据依赖性的不确定性

  • *a 的值可能受到其他因素的影响（如其他线程的修改），导致分支预测器难以准确预测。
  • 即使 *a >= 0 在结束之前总是 T，分支预测器也无法确定何时会变为 F。

(3) 分支预测器的局限性

  • 分支预测器通常基于局部历史记录进行预测，而 *a >= 0 的行为可能不够规律，导致预测失败。
  • 如果 *a 的值在循环过程中变化较大，分支预测器的准确率会进一步降低。

因此第二种分支预测准确率没有第一种高

条件类型 规律性 内存访问延迟 数据依赖性 预测准确率
i < N 高度规律 无 无 非常高（接近 100%）
*a >= 0 可能不规律 有 有 较低（取决于数据）

[!NOTE]

以上三种分析方向为gcc优化方向，以下为cpu执行角度分析

缓存预取

对于第一种代码

  • 数组 A 和 B 是顺序访问的，即每次迭代访问 A[i] 和 B[i]。

  • 这种顺序访问模式非常容易被硬件预取器预测。

  • 硬件预取器会检测到顺序访问模式，并自动预取 A 和 B 的后续数据。

  • 由于访问模式简单且规律，硬件预取器可以非常有效地工作，从而减少内存访问的延迟。

而对于第二种，

  • 数组 A 和 B 仍然是顺序访问的，但循环条件 *a >= 0 依赖于内存中的值。
  • 由于 A[N - 1] 被设置为 -1，循环会在访问到 A[N - 1] 时结束。
  • 硬件预取器仍然可以检测到顺序访问模式，并自动预取 A 和 B 的后续数据。
  • 但由于循环条件依赖于内存中的值，硬件预取器可能无法准确预测循环的结束位置。
特性 第一种代码 第二种代码
数据访问模式 顺序访问，规律性强 顺序访问，但循环条件依赖内存中的值
硬件预取器的适用性 非常适用，预取效果好 适用，但预取效果可能受限
显式预取的必要性 通常不需要 可能无效，甚至导致缓存污染
缓存性能 缓存命中率高，内存延迟低 缓存命中率较高，但可能略低
  • 由于循环条件依赖于内存中的值，硬件预取器可能无法完全有效地工作。
  • 缓存命中率可能略低于第一种代码，尤其是在循环结束附近。

所以从缓存预取的角度看，第一种代码效果略好

触发缓存写回

对于第二种代码：

  • 在每次迭代中，*a 的值会被加载到缓存中。
  • 由于 A 是顺序访问的，硬件预取器会将 A 的后续数据预取到缓存中。

  • 因此，在大多数情况下，*a 的值会从缓存中命中，而不是从内存中加载。

  • 在循环中，*a 的值会被修改，因此对应的缓存行会被标记为脏的。

  • 如果缓存行被替换时是脏的，则需要写回主存。

  • 由于 A 是顺序访问的，缓存行的替换频率较低，缓存写回的次数也较少。

  • 由于 A 和 B 是顺序访问的，硬件预取器可以有效地预取数据，减少内存访问的延迟。

  • 循环条件 *a >= 0 的值通常会从缓存中命中，因此不会显著增加内存访问的延迟。

因此从缓存写回的角度看差距不大。