第05章：优化程序性能

我们可以做的更好

导读

程序性能优化是计算机科学中一个永恒的话题。在理想情况下，编译器应该能够将我们编写的任何正确程序都转换为最高效的机器代码，但现实远非如此。编译器必须在有限的时间内完成编译工作，而且它必须保证优化后的程序在所有合法输入下都与原始程序行为完全一致——这种对安全性的保守要求使得编译器往往会放弃一些激进的优化机会。

因此，作为程序员，我们有责任以一种"对优化器友好"的方式来编写代码。这并不意味着我们要手动编写汇编代码或者使用编译器特有的内联汇编指令，而是要理解编译器的优化能力和局限性，理解现代处理器的执行模型，然后在此基础上编写出既清晰又可被高效执行的代码。

本章的核心目标是帮助你建立一种"性能意识"。当你写下一个循环、一次函数调用、一个数组访问时，你应该能够大致判断这段代码在硬件层面会发生什么，以及是否存在改进的空间。性能优化不是事后的修补工作，而应该贯穿于程序设计的整个过程——从算法选择、数据结构设计，到代码编写和编译器选项配置，每一个环节都可能对最终性能产生深远影响。

需要特别强调的是：优化必须以正确性为前提。在开始任何优化工作之前，必须确保原始程序的功能是正确的，并且有完善的测试用例可以验证优化后的程序行为没有发生变化。一个运行得更快但结果错误的程序没有任何价值。正如业界常说的那句话："Nothing can fix a dumb algorithm!"——没有什么能修正一个愚蠢的算法。在考虑性能优化之前，首先要确保你选择了正确的算法和数据结构。

优化的层次

程序优化可以在多个层次上进行：

算法层面：选择时间复杂度和空间复杂度更优的算法，这是影响最大的优化手段，可以带来数量级上的性能提升。

代码层面：通过改写代码结构来帮助编译器更好地进行优化，包括消除不必要的内存引用、减少过程调用开销、利用循环展开等技术。

编译器层面：通过调整编译器选项（如 -O2、-O3、-march=native 等）来启用更激进的优化策略。

硬件层面：理解目标处理器的特性（如超标量执行、SIMD 指令、流水线结构），编写能够充分利用硬件并行性的代码。

本章主要关注代码层面和编译器层面的优化技术，同时会涉及硬件层面的基本概念。

核心概念详解

一、编译器优化的能力与局限

编译器是程序员的第一个性能优化工具。一个现代编译器（如 GCC、LLVM/Clang）内部包含了数百种优化 Pass，它们在不同的编译阶段对程序进行各种变换。理解编译器能做什么和不能做什么，是写出高效代码的前提。

编译器能做的优化

代码移动（Code Motion）：如果编译器能够确定某个表达式的值在循环执行过程中不会改变，它就会把这个表达式移到循环体外面，避免在每次迭代中重复计算。这个优化看似简单，但在实际代码中却经常出现编译器无法安全执行代码移动的情况。

考虑以下代码：

void set_row(long *dest, long n, long *matrix_row) {
    long i;
    for (i = 0; i < n; i++) {
        dest[i] = matrix_row[n * i];
    }
}

表面上看，n * i 中的 n 在循环中不会改变，编译器似乎应该把 n 的乘法提取出来。但问题在于，dest[i] 的写入可能会改变 n 所指向的内存位置（如果 dest 和 matrix_row 存在重叠的话），所以编译器必须保守地每次迭代都重新计算 n * i。

常量折叠与常量传播：编译器会在编译期计算常量表达式的值，并将已知值传播到后续使用处。例如 int x = 3 + 5; 会被直接替换为 int x = 8;。更进一步的，如果一个变量在某处被赋值为常量，且后续没有被修改，编译器会直接用常量值替换该变量的所有使用。

死代码消除：如果某段代码的计算结果永远不会被使用，编译器会将其完全删除。这不仅包括明显的无用代码，还包括通过复杂的控制流分析推导出的不可达路径。

函数内联：对于小型函数，编译器会将其调用点直接替换为函数体代码，消除函数调用的开销（参数传递、栈帧创建、跳转指令等）。内联不仅消除了调用开销本身，更重要的是它为后续的优化打开了更多的机会——内联之后，编译器可以在更大的上下文中进行常量传播、死代码消除等优化。

循环优化：包括循环展开（Loop Unrolling）、循环融合（Loop Fusion）、循环分裂（Loop Fission）、循环交换（Loop Interchange）等多种变换。这些优化的目标是减少循环控制的开销、改善数据局部性、暴露更多的指令级并行性。

编译器的局限性：过程副作用

编译器在优化时面临的一个根本困难是过程副作用（Procedure Side Effects）问题。当一个函数被调用时，编译器通常无法确定这个函数内部到底做了什么——它可能修改了全局变量，可能通过指针修改了调用者传入的参数所指向的内存，可能执行了 I/O 操作。因此，编译器对函数调用的优化往往非常保守。

long counter = 0;

long increment_counter() {
    return ++counter;
}

long test(long n) {
    long i;
    long result = 0;
    for (i = 0; i < n; i++) {
        result += increment_counter();
    }
    return result;
}

在这个例子中，编译器无法将 increment_counter() 内联或优化掉，因为它必须保证全局变量 counter 的副作用被正确执行。即使从逻辑上看，这个循环的结果可以用数学公式直接计算（result = n*(n+1)/2），编译器也不敢做这样的变换。

一种帮助编译器克服这个局限的方法是使用 static 函数——将函数声明为 static 告诉编译器该函数只在当前编译单元内可见，编译器可以看到它的完整实现，从而进行更激进的优化。

编译器的局限性：内存别名

另一个严重影响编译器优化能力的问题是内存别名（Memory Aliasing）。当两个指针可能指向同一内存位置时，编译器必须假设通过一个指针的写入可能影响通过另一个指针的读取结果。这种保守假设会阻止大量优化的执行。

void twiddle1(long *xp, long *yp) {
    *xp += *yp;
    *xp += *yp;
}

void twiddle2(long *xp, long *yp) {
    *xp += 2 * (*yp);
}

这两个函数在大多数情况下功能等价，但 twiddle2 只读取 *yp 一次，看起来应该更快。然而，如果调用者传入 twiddle1(&x, &x)，即两个指针指向同一位置，那么 twiddle1 和 twiddle2 的结果是不同的——twiddle1 会将 x 增加 4x（第一次 x += x 使 x 变为 2x，第二次 x += 2x 使 x 变为 4x），而 twiddle2 只会将 x 增加 2x。

C99 标准引入了 restrict 关键字来解决这个问题。当指针被声明为 restrict 时，程序员向编译器承诺：在该指针的生命周期内，所有通过该指针（或其副本）对内存的访问都不会与通过其他 restrict 指针的访问产生别名。这个承诺使得编译器能够进行更激进的优化，但代价是将正确性的责任部分转移给了程序员。

void twiddle_restrict(long *restrict xp, long *restrict yp) {
    *xp += *yp;
    *xp += *yp;
}

编译器现在可以安全地将两次 *yp 读取合并为一次，因为它知道 xp 的写入不会影响 yp 指向的值。

编译器优化选项

现代编译器提供了多个优化级别：

-O0：不优化（默认），编译速度最快，便于调试。
-O1：基本优化，包括死代码消除、常量传播等低风险优化。
-O2：中等优化，在编译时间和性能提升之间取得平衡，是生产环境推荐的默认选项。包括指令调度、寄存器分配、循环优化等。
-O3：激进优化，在 -O2 基础上增加函数内联、循环展开、向量化等。编译时间更长，但不一定总是比 -O2 更快。
-Os：优化代码大小，适合嵌入式系统等内存受限的场景。
-Ofast：在 -O3 基础上放宽对 IEEE 浮点标准的严格遵守，允许重排浮点运算顺序。
-march=native：生成针对当前 CPU 架构优化的代码，可以使用特定的指令集扩展（如 AVX2、AVX-512）。

二、减少过程调用与内存引用

减少过程调用

过程调用（函数调用）在 C 语言中看似开销不大，但在性能关键的循环内部，累积的调用开销可能非常显著。每次函数调用涉及以下开销：保存调用者的寄存器状态、设置被调用者的栈帧、传递参数、执行跳转指令、返回时恢复状态等。在 x86-64 架构上，一次函数调用大约需要 15-20 个时钟周期。

更重要的是，函数调用会阻止编译器的许多优化。当编译器遇到一个函数调用时，它必须假设这个函数可能修改任何全局变量或堆上的数据，可能通过指针参数修改任何可访问的内存。这种保守假设迫使编译器放弃大量优化机会。

减少过程调用的常见策略包括：

将函数调用移出循环：如果函数的返回值在循环中不会改变，就将其提取到循环外部。

内联小函数：对于频繁调用但逻辑简单的函数，手动内联或使用 inline 关键字建议编译器内联。

使用宏或内联函数替代：在 C 语言中，static inline 函数是最安全的内联方式。

// 优化前：每次循环都调用 strlen
void to_uppercase(char *str) {
    for (int i = 0; i < strlen(str); i++) {
        if (str[i] >= 'a' && str[i] <= 'z') {
            str[i] -= 32;
        }
    }
}

// 优化后：将 strlen 调用移出循环
void to_uppercase(char *str) {
    int len = strlen(str);
    for (int i = 0; i < len; i++) {
        if (str[i] >= 'a' && str[i] <= 'z') {
            str[i] -= 32;
        }
    }
}

减少内存引用

内存访问的速度远远慢于寄存器操作。从内存中读取一个值到寄存器大约需要 4-100 个时钟周期（取决于是否在缓存中），而寄存器之间的操作只需要 1 个时钟周期。因此，减少不必要的内存引用是提升性能的重要手段。

核心思想是：引入临时变量，将循环中反复读取或写入的内存位置缓存到寄存器中。

// 优化前：每次迭代都通过指针访问内存
void vector_sum_a(long *v, long *dest, long n) {
    long i;
    *dest = 0;
    for (i = 0; i < n; i++) {
        *dest += v[i];
    }
}

// 优化后：使用临时变量减少内存引用
void vector_sum_b(long *v, long *dest, long n) {
    long i;
    long sum = 0;
    for (i = 0; i < n; i++) {
        sum += v[i];
    }
    *dest = sum;
}

在 vector_sum_a 中，每次循环迭代都需要从 *dest 读取当前值并写回新值，产生了 2n 次内存引用（n 次读 + n 次写）。而在 vector_sum_b 中，累加操作在寄存器中完成，只在循环结束后写回一次 *dest，总共只有 1 次写操作。这个优化在现代编译器中通常会被自动完成（在 -O1 及以上），但理解其原理对于更复杂的场景至关重要。

三、循环展开与多次迭代并行

循环展开（Loop Unrolling）是最经典且最有效的循环优化技术之一。其核心思想是通过在每次迭代中处理多个元素来减少循环控制的开销，并暴露更多的指令级并行性。

基本原理

一个典型的循环包含两类操作：循环控制操作（比较、递增、跳转）和循环体操作（实际的数据处理）。对于小型循环体，循环控制操作的开销可能占总执行时间的相当比例。循环展开通过减少迭代次数来摊薄循环控制的开销。

// 原始版本：每次迭代处理 1 个元素
long sum_array(long *arr, long n) {
    long sum = 0;
    for (long i = 0; i < n; i++) {
        sum += arr[i];
    }
    return sum;
}

// 2x1 循环展开：每次迭代处理 2 个元素
long sum_array_unroll2(long *arr, long n) {
    long sum = 0;
    long limit = n - 1;
    long i;
    for (i = 0; i < limit; i += 2) {
        sum += arr[i] + arr[i + 1];
    }
    for (; i < n; i++) {
        sum += arr[i];
    }
    return sum;
}

// 4x1 循环展开：每次迭代处理 4 个元素
long sum_array_unroll4(long *arr, long n) {
    long sum = 0;
    long limit = n - 3;
    long i;
    for (i = 0; i < limit; i += 4) {
        sum += arr[i] + arr[i + 1] + arr[i + 2] + arr[i + 3];
    }
    for (; i < n; i++) {
        sum += arr[i];
    }
    return sum;
}

循环展开带来了两方面的好处：第一，减少了循环控制的开销——如果展开因子为 k，循环控制的执行次数减少为原来的 1/k；第二，更重要的是，它为编译器提供了更多的机会来利用指令级并行性。

多次迭代并行（Multiple Accumulation）

在循环展开的基础上，可以进一步引入多个累加变量的技术。即使循环展开后，如果所有操作都存在数据依赖（如连续累加到同一个变量），处理器也无法并行执行这些操作。通过引入多个独立的累加变量，可以打破这种依赖链，让处理器的多个功能单元同时工作。

// 2x2 循环展开：每次处理 2 个元素，使用 2 个累加变量
long sum_array_2x2(long *arr, long n) {
    long sum0 = 0, sum1 = 0;
    long limit = n - 1;
    long i;
    for (i = 0; i < limit; i += 2) {
        sum0 += arr[i];
        sum1 += arr[i + 1];
    }
    for (; i < n; i++) {
        sum0 += arr[i];
    }
    return sum0 + sum1;
}

// 4x4 循环展开：每次处理 4 个元素，使用 4 个累加变量
long sum_array_4x4(long *arr, long n) {
    long sum0 = 0, sum1 = 0, sum2 = 0, sum3 = 0;
    long limit = n - 3;
    long i;
    for (i = 0; i < limit; i += 4) {
        sum0 += arr[i];
        sum1 += arr[i + 1];
        sum2 += arr[i + 2];
        sum3 += arr[i + 3];
    }
    for (; i < n; i++) {
        sum0 += arr[i];
    }
    return sum0 + sum1 + sum2 + sum3;
}

在 sum_array_2x2 中，sum0 和 sum1 的累加操作是完全独立的——它们之间没有数据依赖。现代超标量处理器可以同时发射和执行这两个独立的加法操作，从而将吞吐量提高近一倍。

循环展开的权衡

循环展开并非没有代价。首先，代码体积会增大——展开因子越大，生成的机器代码越多，可能增加指令缓存的压力。其次，展开后的代码需要处理数组末尾不足一个展开块的元素（即"尾部处理"），增加了代码复杂度。最后，过大的展开因子可能导致寄存器压力增大——需要更多的寄存器来保存多个累加变量，如果寄存器不够用，就会发生寄存器溢出到内存，反而降低性能。

实践中，展开因子通常选择 2、4 或 8。现代编译器在 -O3 级别通常会自动进行循环展开，展开因子的选择取决于目标处理器的寄存器数量和流水线特性。

四、超标量处理器与指令级并行

要真正理解程序优化的原理，必须了解现代处理器的执行模型。现代高性能处理器是超标量（Superscalar）的——它们每个时钟周期可以发射和执行多条指令。

流水线执行

现代处理器采用流水线（Pipeline）结构，将指令的执行分为多个阶段：取指（IF）、译码（ID）、执行（EX）、访存（MEM）、写回（WB）。理想情况下，流水线中的每个阶段在每个时钟周期都在处理不同的指令，从而实现指令的重叠执行。

一条典型的整数运算指令在流水线中可能经历以下阶段：

取指：从指令缓存中获取指令。

译码：解析指令的操作码和操作数，从寄存器文件中读取操作数。

执行：ALU 执行运算。

访存：对于 load/store 指令，访问数据缓存。

写回：将结果写回寄存器文件。

超标量执行

超标量处理器在流水线的基础上更进一步——它拥有多条并行的功能单元（如多个 ALU、多个 load/store 单元、多个分支单元），每个时钟周期可以同时发射多条指令到不同的功能单元。

以 Intel Core 系列处理器为例，一个典型的超标量处理器可能包含以下功能单元：

2 个整数 ALU（可以执行整数运算和逻辑运算）
1 个整数乘除单元
2 个浮点/向量 ALU
1 个浮点乘加单元（FMA）
2 个 load 单元
1 个 store 单元
1 个分支单元

处理器的指令发射宽度（Issue Width）决定了每个时钟周期最多可以发射多少条指令。例如，Intel Skylake 微架构的发射宽度为 4，意味着每个时钟周期最多可以发射 4 条微操作（micro-ops）到不同的功能单元。

指令级并行性的限制

尽管超标量处理器具有同时执行多条指令的能力，但实际的指令级并行性（Instruction-Level Parallelism, ILP）受到以下因素的限制：

数据依赖：如果指令 B 使用了指令 A 的结果，那么 B 必须等待 A 完成后才能开始执行。这种依赖关系形成了关键路径（Critical Path），决定了程序执行的下界时间。例如，连续的累加操作 sum += arr[i] 形成了严格的串行依赖链——每次加法必须等待上一次加法的结果。

结构冒险：当两条指令需要同一个功能单元时，它们不能同时执行。例如，如果处理器只有 2 个整数 ALU，但有 3 条整数运算指令要同时发射，第 3 条必须等待。

控制依赖：分支指令的结果决定了后续指令的执行路径。在分支结果确定之前，处理器无法确定应该执行哪些后续指令。现代处理器使用分支预测技术来缓解这个问题——它猜测分支的方向并提前执行预测路径上的指令，如果预测错误则回滚。

操作数前推（Operand Forwarding）

现代处理器通过操作数前推（也称为旁路，Bypassing）技术来减少数据依赖带来的延迟。当一条指令产生结果后，结果可以直接被下一条需要该结果的指令使用，而无需等待结果写回寄存器文件再读出。这使得某些连续依赖的操作可以在相邻的时钟周期内执行，而不需要等待完整的流水线延迟。

理解超标量处理器的执行模型对于编写高性能代码至关重要。前面介绍的循环展开和多次迭代并行技术，本质上都是为了打破数据依赖链，为处理器的多个功能单元提供足够的独立工作。

五、存储器山模型

存储器山（Memory Mountain）是理解和量化程序内存访问性能的一个重要模型。它由 CSAPP 教材的作者提出，通过系统地测量不同步长（stride）和不同工作集大小（working set size）下的内存读取吞吐量，绘制出一个三维的"山形"曲面图。

存储器山的两个维度

存储器山的两个关键维度是：

工作集大小（Working Set Size）：程序访问的数据总量。从几 KB 到几 GB 不等，跨越 L1 缓存、L2 缓存、L3 缓存和主存的容量范围。

步长（Stride）：连续两次内存访问之间的地址间隔。步长为 1 表示连续访问相邻的元素（如顺序遍历数组），步长越大表示跳跃式访问。

存储器山的特征

存储器山呈现出以下典型特征：

山脊（Ridge）：当步长为 1（连续访问）且工作集大小在缓存容量范围内时，吞吐量达到最高值。这是因为连续访问具有最好的空间局部性，缓存预取机制可以高效地工作。

山坡（Slope）：随着工作集大小的增加，当数据量超过某一级缓存的容量时，吞吐量会出现明显的下降——程序开始更多地访问下一级更慢的存储器。这种下降在 L1→L2、L2→L3、L3→主存的边界处尤为明显，形成存储器山的"悬崖"。

山谷（Valley）：随着步长的增大，空间局部性急剧恶化，缓存行的利用率降低（每次只使用缓存行中的一个或几个字节），吞吐量显著下降。

存储器山的实践意义

存储器山模型为程序员提供了几个重要的实践指导：

顺序访问优于随机访问：步长为 1 的顺序访问可以充分利用缓存的空间局部性和硬件预取机制，吞吐量远高于大步长的跳跃访问。

小数据优于大数据：能够放入缓存的数据访问速度远快于需要访问主存的数据。算法设计应尽量减小工作集大小，或在可能的情况下将数据分块处理。

缓存友好的数据结构：选择连续存储的数据结构（如数组）而非分散存储的数据结构（如链表），可以显著提高缓存命中率。

循环嵌套顺序：对于多维数组的访问，循环嵌套的顺序应该与数组的存储顺序一致（C 语言中行优先，所以最内层循环应该遍历行元素）。

量化分析

一个典型的现代处理器（如 Intel Core i7）的存储器性能参数大致如下：

存储层级	典型延迟	典型带宽	典型容量
L1 缓存	~4 周期	~100 GB/s	32-64 KB
L2 缓存	~12 周期	~50 GB/s	256 KB-1 MB
L3 缓存	~30-40 周期	~30 GB/s	4-32 MB
主存	~200-300 周期	~20-50 GB/s	8-256 GB

从表中可以看出，L1 缓存到主存的延迟差异可达 50-75 倍。这意味着一个缓存命中率 99% 的程序，其有效内存访问时间可能只有主存访问的 1/20。而一个缓存命中率只有 90% 的程序，有效内存访问时间可能接近主存访问的 1/2。这种巨大的性能差异使得缓存优化成为程序性能优化的关键。

六、向量化与 SIMD 优化

SIMD（Single Instruction, Multiple Data，单指令多数据）是现代处理器提供的一种并行执行机制。它允许一条指令同时对多个数据元素执行相同的操作。例如，一条 AVX2 指令可以同时对 4 个 64 位整数执行加法操作。

SIMD 的基本原理

传统的标量处理器每条指令只处理一对操作数（如 a + b），而 SIMD 处理器的一条指令可以处理一组操作数（如 [a0, a1, a2, a3] + [b0, b1, b2, b3]）。x86 架构的 SIMD 演进历程如下：

MMX（1997）：57 条指令，8 个 64 位寄存器。
SSE（1999）：引入 128 位 XMM 寄存器，支持浮点 SIMD。
SSE2（2001）：扩展 SSE，支持整数和双精度浮点 SIMD。
AVX（2011）：引入 256 位 YMM 寄存器，支持 8 个双精度浮点的并行运算。
AVX2（2013）：扩展 AVX，支持整数 SIMD 和 gather 操作。
AVX-512（2016）：引入 512 位 ZMM 寄存器，支持 16 个双精度浮点的并行运算。

自动向量化

现代编译器在 -O3 或 -O2 -ftree-vectorize 选项下会尝试自动将循环向量化。但自动向量化有严格的条件限制：

循环的迭代次数必须在进入循环时已知（或可以计算）。

循环体内不能有条件分支（或分支可以被转换为条件移动指令）。

循环中的内存访问不能有别名冲突。

操作必须可以映射到 SIMD 指令。

为了帮助编译器进行自动向量化，程序员可以：

使用简单的循环结构，避免复杂的控制流。

使用 restrict 指针消除别名疑虑。

使用对齐的内存分配（如 aligned_alloc）和 __attribute__((aligned(32))) 声明。

使用编译器 pragma（如 #pragma GCC ivdep）提示循环迭代之间没有依赖。

// 有助于自动向量化的代码模式
void vector_add(float *restrict a, float *restrict b, float *restrict c, int n) {
    for (int i = 0; i < n; i++) {
        c[i] = a[i] + b[i];
    }
}

手动向量化

当编译器无法自动向量化时，程序员可以使用编译器内置函数（intrinsics）手动编写 SIMD 代码。这种方式可以获得最大的性能控制，但代码可读性和可移植性较差。

#include <immintrin.h>

void vector_add_avx2(float *a, float *b, float *c, int n) {
    int i;
    for (i = 0; i <= n - 8; i += 8) {
        __m256 va = _mm256_loadu_ps(&a[i]);
        __m256 vb = _mm256_loadu_ps(&b[i]);
        __m256 vc = _mm256_add_ps(va, vb);
        _mm256_storeu_ps(&c[i], vc);
    }
    for (; i < n; i++) {
        c[i] = a[i] + b[i];
    }
}

七、性能分析的实践方法

优化不能凭直觉——必须基于测量数据。性能分析（Profiling）是优化工作的基础。

性能度量工具

`time` 命令：最基本的性能度量工具，报告程序的总执行时间、用户态时间和内核态时间。

`perf` 工具：Linux 性能分析套件，可以统计硬件事件（如缓存未命中、分支预测失败、指令数等）。

`valgrind --tool=cachegrind`：模拟缓存行为，统计各级缓存的命中和未命中次数。

`gprof`：函数级性能分析器，统计每个函数的执行时间和调用次数。

CPE（Cycles Per Element）

CPE 是衡量循环密集型程序性能的标准指标。它表示处理每个数据元素平均需要的时钟周期数。CPE 越低，性能越好。

// 测量 CPE 的典型方法
#include <time.h>

double measure_cpe(void (*func)(long *, long), long *data, long n, int iterations) {
    struct timespec start, end;
    clock_gettime(CLOCK_MONOTONIC, &start);
    for (int i = 0; i < iterations; i++) {
        func(data, n);
    }
    clock_gettime(CLOCK_MONOTONIC, &end);
    double elapsed = (end.tv_sec - start.tv_sec) + (end.tv_nsec - start.tv_nsec) / 1e9;
    double total_ops = (double)n * iterations;
    double cycles_per_element = elapsed * CPU_FREQ_GHZ / total_ops;
    return cycles_per_element;
}

代码示例

综合优化示例：矩阵向量乘法

以下通过一个矩阵向量乘法的例子，展示逐步优化的过程：

// 版本1：基础实现
void matvec1(long **matrix, long *vec, long *dest, long n) {
    long i, j;
    for (i = 0; i < n; i++) {
        dest[i] = 0;
        for (j = 0; j < n; j++) {
            dest[i] += matrix[i][j] * vec[j];
        }
    }
}

// 版本2：减少内存引用
void matvec2(long **matrix, long *vec, long *dest, long n) {
    long i, j;
    for (i = 0; i < n; i++) {
        long sum = 0;
        for (j = 0; j < n; j++) {
            sum += matrix[i][j] * vec[j];
        }
        dest[i] = sum;
    }
}

// 版本3：循环展开 + 多次迭代并行
void matvec3(long **matrix, long *vec, long *dest, long n) {
    long i, j;
    for (i = 0; i < n; i++) {
        long sum0 = 0, sum1 = 0;
        long *row = matrix[i];
        long limit = n - 1;
        for (j = 0; j < limit; j += 2) {
            sum0 += row[j] * vec[j];
            sum1 += row[j + 1] * vec[j + 1];
        }
        for (; j < n; j++) {
            sum0 += row[j] * vec[j];
        }
        dest[i] = sum0 + sum1;
    }
}

// 版本4：使用连续内存布局（一维数组模拟二维矩阵）
void matvec4(long *matrix, long *vec, long *dest, long n) {
    long i, j;
    for (i = 0; i < n; i++) {
        long sum0 = 0, sum1 = 0;
        long *row = &matrix[i * n];
        long limit = n - 1;
        for (j = 0; j < limit; j += 2) {
            sum0 += row[j] * vec[j];
            sum1 += row[j + 1] * vec[j + 1];
        }
        for (; j < n; j++) {
            sum0 += row[j] * vec[j];
        }
        dest[i] = sum0 + sum1;
    }
}

版本1到版本2的改进消除了内层循环中对 dest[i] 的反复内存读写。版本3引入了循环展开和两个独立累加变量以利用指令级并行性。版本4将指针数组改为连续内存布局，改善了空间局部性，减少了缓存未命中。

实验解读

实验：观察编译器优化效果

实验目的：通过实际编译和运行，观察不同优化技术对程序性能的影响。

实验步骤：

编写一个包含多种优化版本的矩阵向量乘法程序。

使用 gcc -O0 编译，测量各版本的执行时间。

使用 gcc -O2 和 gcc -O3 分别编译，对比性能差异。

使用 perf stat 统计各版本的缓存未命中数和指令数。

使用 objdump -d 查看反汇编代码，观察编译器做了哪些优化。

预期结果：

-O0 编译时，手动优化版本（版本2、3、4）显著快于基础版本。
-O2 编译时，编译器自动完成了部分优化（如减少内存引用），手动优化的差距缩小。
-O3 编译时，编译器自动进行了循环展开和向量化，手动优化的优势进一步缩小，但在某些场景下仍然有效（如连续内存布局带来的缓存友好性）。

关键观察：

使用 perf stat 可以观察到版本4（连续内存）的 L1 缓存命中率显著高于版本1（指针数组）。
反汇编代码中可以看到 -O3 级别下编译器自动插入了 SIMD 指令（如 vmovdqu、vpaddd）。