计算次数完全相同，交换两层循环为什么可能快很多？

发表于 分类于 ， 阅读次数：
高性能 C++ 并行编程 / 07更新于 2026-07-13预计阅读 11 分钟

时间：2026/04/09

假设一个矩阵按行存放在连续数组中，下面两段代码都访问每个元素一次：

1
2
3
4
5
6
7
8
9
// 按行访问
for (std::size_t row = 0; row < rows; ++row)
    for (std::size_t col = 0; col < cols; ++col)
        sum += matrix[row * cols + col];

// 按列访问
for (std::size_t col = 0; col < cols; ++col)
    for (std::size_t row = 0; row < rows; ++row)
        sum += matrix[row * cols + col];

两者都是 O(rows × cols)，加法次数也相同，运行时间却可能相差明显。按列访问时，相邻两次读取跨过整行，CPU 搬进缓存的数据大部分还没利用，就去访问另一块内存。

这说明性能不只由“算多少次”决定，还取决于数据以什么顺序到达计算单元。本文从这个循环交换出发，讲清缓存行（cache line）、局部性、步长、AoS/SoA、分块与伪共享，并说明怎样用可重复测量验证访存优化。

1. CPU 为什么不能把主存当作一个大数组直接使用？

现代处理器的算术单元很快，而主存访问延迟高、可提供的带宽也有限。为了缩小差距，硬件在核心与 DRAM 之间设置多级缓存：

1
2
3
4
5
6
7
8
9
CPU 寄存器
    ↓
L1 cache
    ↓
L2 cache
    ↓
末级缓存（具体层级与共享方式依处理器而定）
    ↓
DRAM

越靠近核心，通常容量越小、延迟越低。具体层级、大小、是否共享和延迟都取决于 CPU 微架构，不能把某台机器的参数当成通用常量。

缓存与内存之间通常按固定大小的缓存行传输，而不是只取当前需要的四个字节。很多现代 CPU 的缓存行是 64 字节，但这不是 C++ 标准保证，也并非所有硬件都相同。

若一个缓存行能装 16 个 float，顺序读取第一个元素时，附近元素往往也被带入缓存。随后连续使用它们，整次传输得到充分利用；若每次只读一行中的一个元素，就可能为四个有效字节搬运整行数据。

2. 局部性怎样解释行访问与列访问的差异？

空间局部性（spatial locality）表示：访问一个地址后，很快还会访问附近地址。顺序遍历连续数组正符合这种模式。

时间局部性（temporal locality）表示：一个数据被访问后，很快还会再次使用。把一小块数据加载进缓存后连续完成多项计算，就是利用时间局部性。

假设一个 4×4 矩阵按行存储：

1
2
3
4
5
内存地址递增方向 →
[00][01][02][03][10][11][12][13][20][21][22][23][30][31][32][33]

按行：00 → 01 → 02 → 03 → 10 → 11 ...
按列：00 → 10 → 20 → 30 → 01 → 11 ...

按行内层循环的步长为一个元素。按列内层循环的步长为 cols 个元素；矩阵越宽，相邻访问地址相距越远。硬件预取器通常更容易识别连续或稳定步长模式，但具体能力依微架构而异，大步长仍可能浪费缓存行和地址转换资源。

3. 如何写一个可运行的行列访问实验？

下面使用一维 std::vector<std::uint32_t> 表示行优先矩阵。两种求和使用 std::uint64_t，避免示例范围内的溢出，并让不同累加顺序得到完全相同的整数结果。

程序使用 C++20 和标准库，不依赖操作系统专属 API：

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <algorithm>
#include <chrono>
#include <cstdint>
#include <iostream>
#include <limits>
#include <span>
#include <stdexcept>
#include <vector>

std::uint64_t sum_by_row(
    std::span<const std::uint32_t> matrix,
    std::size_t rows,
    std::size_t cols) {
    std::uint64_t sum = 0;
    for (std::size_t row = 0; row < rows; ++row) {
        for (std::size_t col = 0; col < cols; ++col) {
            sum += matrix[row * cols + col];
        }
    }
    return sum;
}

std::uint64_t sum_by_column(
    std::span<const std::uint32_t> matrix,
    std::size_t rows,
    std::size_t cols) {
    std::uint64_t sum = 0;
    for (std::size_t col = 0; col < cols; ++col) {
        for (std::size_t row = 0; row < rows; ++row) {
            sum += matrix[row * cols + col];
        }
    }
    return sum;
}

struct Measurement {
    std::uint64_t checksum = 0;
    double best_milliseconds = 0.0;
};

template <class Function>
Measurement measure(Function function, int trials) {
    using Clock = std::chrono::steady_clock;
    double best = std::numeric_limits<double>::max();
    std::uint64_t expected = 0;

    for (int trial = 0; trial < trials; ++trial) {
        const auto begin = Clock::now();
        const std::uint64_t checksum = function();
        const auto end = Clock::now();

        if (trial == 0) {
            expected = checksum;
        } else if (checksum != expected) {
            throw std::runtime_error("inconsistent checksum");
        }

        const std::chrono::duration<double, std::milli> elapsed = end - begin;
        best = std::min(best, elapsed.count());
    }

    return {expected, best};
}

int main() {
    constexpr std::size_t rows = 2048;
    constexpr std::size_t cols = 2048;
    std::vector<std::uint32_t> matrix(rows * cols);

    for (std::size_t i = 0; i < matrix.size(); ++i) {
        matrix[i] = static_cast<std::uint32_t>(i % 251);
    }

    const Measurement row = measure(
        [&] { return sum_by_row(matrix, rows, cols); }, 3);
    const Measurement column = measure(
        [&] { return sum_by_column(matrix, rows, cols); }, 3);

    if (row.checksum != column.checksum) {
        throw std::runtime_error("row/column results differ");
    }

    std::cout << "checksum = " << row.checksum << '\n'
              << "row best ms = " << row.best_milliseconds << '\n'
              << "column best ms = " << column.best_milliseconds << '\n';
}

在提供 C++20 的 Clang 环境中编译：

1
2
clang++ -std=c++20 -O2 -Wall -Wextra -pedantic memory_access.cpp -o memory_access
./memory_access

输出格式如下，其中时间必须以本机实测为准：

1
2
3
checksum = <两种遍历共同的校验和>
row best ms = <本机测量值>
column best ms = <本机测量值>

程序取三轮中的最短时间，只是降低明显调度干扰的简化做法，不是严谨基准框架。CPU、编译器、缓存规模、电源状态和矩阵尺寸都会改变差距；某次运行甚至可能因系统噪声出现反常结果。应重复运行，并用 profiler 或硬件计数器确认缓存未命中和带宽行为。

4. 这个实验真正比较了什么？

两种函数读取相同字节数、执行相同数量的整数加法，并返回相同校验和。主要变量是内层循环访问步长。

行访问按连续地址前进，缓存行中的多个元素会依次使用，硬件预取也容易提前准备后续数据。列访问每次跨越 cols * sizeof(std::uint32_t) 字节；在本例中步长为 8192 字节，同一缓存行带来的其他元素要等到很久以后才访问，届时它可能已经被替换。

不过，计时差异不能全都简单归因于“L1 miss”。地址转换后备缓冲区（TLB）、预取、缓存替换、内存级并行、编译器循环变换和系统调度都可能参与。严谨结论需要结合目标平台计数器验证。

为什么不在循环里使用 volatile？

两个校验和会参与比较和输出，主要计算不能在保持程序语义的前提下被随意删除。把矩阵或累加器声明为 volatile 会强制特殊访问语义，抑制正常优化，测到的不再是普通数组遍历。

为什么不能只跑一次？

首次访问可能包含缺页、缓存冷启动或频率变化；后台任务也会抢占 CPU。至少要预热并重复多轮。正式研究还应交替测试顺序、报告分布并控制机器负载，避免总是让第二个实现享受热缓存。

5. 步长为什么会浪费带宽？

步长（stride）是相邻逻辑访问之间的地址距离。步长为一时，每个缓存行的大部分有效载荷都会消费；步长很大时，可能每次只用其中一个元素。

1
2
3
for (std::size_t i = 0; i < values.size(); i += 16) {
    sum += values[i];
}

这段代码读取的逻辑元素更少，未必比完整遍历耗时更长，但“每个被使用元素所对应的内存流量”可能更高。比较性能时必须区分总耗时、每元素耗时和有效带宽，不能只看循环迭代数。

稳定步长有时仍能被硬件预取器识别；跨页大步长还可能增加 TLB 压力。具体阈值不能仅凭缓存行大小推导，需要结合处理器和数据规模测量。

6. AoS 与 SoA 应该如何根据访问模式选择？

粒子数据常见两种布局。AoS（Array of Structures，结构体数组）把一个对象的字段放在一起：

1
2
3
4
5
6
struct Particle {
    float x, y, z;
    float vx, vy, vz;
};

std::vector<Particle> particles;

SoA（Structure of Arrays，数组结构）把同一字段连续存放：

1
2
3
4
struct Particles {
    std::vector<float> x, y, z;
    std::vector<float> vx, vy, vz;
};
访问模式 AoS 的特点 SoA 的特点
一次读取单个对象的大多数字段 字段相邻，接口自然 需要访问多个数组
批量更新所有对象的少数字段 缓存行夹带未使用字段 目标字段紧凑连续
SIMD 批处理同一字段 可能需要 gather 或重排 通常更容易连续加载
增删一个完整对象 一个容器即可维护 多个数组必须保持长度一致

SoA 并非天然更快。如果核心操作总要读取 x/y/z/vx/vy/vz，AoS 的对象内局部性可能很好；如果只更新 x 和 vx，SoA 能避免搬运其他字段。也可以采用 AoSoA 等分块混合布局，但只有真实内核需要时才值得增加复杂度。

数据布局应围绕热访问路径设计，并用代表性输入测量，不能只根据类型名字选择。

7. 分块为什么能让已经加载的数据多用几次？

矩阵乘法、卷积和 stencil 计算会反复使用邻近数据。若工作集远大于缓存，朴素循环可能在数据被再次使用前就将其逐出。

分块（blocking/tiling）把大问题切成较小区域：

1
2
3
4
5
6
7
完整矩阵
┌───────────────┐
│ [块 1][块 2]  │
│ [块 3][块 4]  │
└───────────────┘

先在块 1 上完成尽可能多的工作，再进入下一块。

目标是缩小活跃工作集，提高时间局部性，而不是“分块”这个动作本身。块太大仍放不进目标缓存，块太小则增加循环边界和调度开销。最佳尺寸还受元素大小、线程数、向量宽度和共享缓存影响，通常需要调参或使用成熟库。

对于只读取一次、没有复用的简单顺序求和，分块通常不会创造额外缓存收益；不要把矩阵乘法经验机械套用到所有循环。

8. 手工预取什么时候可能有帮助？

硬件预取器擅长连续和部分规则步长访问。随机索引或指针追逐中，下一个地址可能依赖当前加载结果，硬件难以及时准备数据。

编译器通常提供预取内建函数，某些架构还有专用指令，但它们不是统一的标准 C++ 性能接口。手工预取需要同时选择地址和提前距离：太晚隐藏不了延迟，太早可能在使用前被逐出，还会占用带宽并污染缓存。

因此，先改善数据布局和访问顺序，再由 profiler 证明延迟确实来自不可预测访问，最后针对固定平台尝试预取。跨平台库还要维护无预取的正确后备路径。

9. 对齐和结构体 padding 真正影响什么？

编译器会为成员对齐插入填充字节：

1
2
3
4
struct Sample {
    char flag;
    double value;
};

sizeof(Sample) 通常大于成员大小之和，但具体布局受 ABI 和平台影响，应使用 sizeof、alignof 和编译器布局工具在目标环境验证。

更紧凑的结构能让一个缓存行容纳更多对象，但盲目打包可能产生未对齐访问、破坏 ABI，甚至在某些架构上带来错误或显著代价。不要对公共结构随意使用打包属性。

对齐也不是“数值越大越快”。alignas(64) 会改变对象布局和数组步长，可能浪费内存；SIMD 指令对未对齐访问的支持和代价依指令集而异。只有算法、分配器和实际地址共同满足对齐条件时，编译器才能安全利用相关假设。

10. 为什么两个线程写不同变量仍可能互相拖慢？

缓存一致性通常以缓存行为单位。两个核心即使修改不同变量，只要变量落在同一缓存行，这一行的写所有权就可能在核心间反复转移，这叫伪共享（false sharing）。

1
2
3
4
struct Counters {
    std::atomic<std::uint64_t> left;
    std::atomic<std::uint64_t> right;
};

线程 A 只写 left，线程 B 只写 right，没有逻辑数据冲突，但可能有物理缓存行争用。原子操作解决数据竞争，不会自动解决伪共享。

一种缓解方式是分离热点写入：

1
2
3
4
5
6
struct alignas(64) Counter {
    std::atomic<std::uint64_t> value{0};
};

Counter left;
Counter right;

这里的 64 只是针对已确认缓存行特征的示例，不是可移植保证。C++17 提供 std::hardware_destructive_interference_size 用于表达实现建议的最小间隔，但某些标准库或编译环境可能不可用，其值也只是实现提供的信息。工程中还要检查对象地址、数组布局和目标硬件。

更常见且更有效的设计是每线程局部累加，阶段结束后统一归约。这样减少共享写频率，也避免每次更新都支付原子成本。

11. 多线程分区为什么通常选择连续块？

假设四个线程处理一个大数组。交错分配让线程分别写 i = thread_id, thread_id + 4, ...，相邻缓存行可能同时被多个核心修改；连续分块让每个线程负责 [begin, end)，通常更符合预取并减少边界处共享。

但连续分块也不是无条件正确：工作量随元素变化很大时，静态块会负载不均；NUMA 系统还要考虑内存首次触碰与节点归属。应在局部性、负载均衡和调度开销之间权衡。

共享只读数据通常不会产生写入失效流量，但总带宽仍可能被所有线程耗尽。线程数增加后性能不再线性增长，往往是内存带宽达到上限，而不是并行框架失效。

12. GPU 上的连续访问为什么又有所不同？

GPU 常强调合并访存（coalesced access）：一组相邻线程访问可被硬件合并的相邻地址，从而提高内存事务利用率。按字段批处理时，SoA 往往更容易形成这种访问。

但具体合并规则、事务粒度、共享内存结构和对齐要求依 GPU 架构及编程模型而异。CPU 上“缓存行友好”的布局不保证在每种 GPU 内核中最佳；跨设备数据结构还要考虑传输、转换和内核访问模式。

13. 如何确认程序真的是访存受限？

仅看到 CPU 利用率不高或循环很简单，不能证明瓶颈在内存。可以按以下顺序调查：

  1. 用采样 profiler 找到真正热点；
  2. 比较不同数据规模，观察超过各级缓存后的变化；
  3. 查看可用的缓存未命中、周期、指令和带宽计数器；
  4. 改变访问顺序或布局，保持计算语义一致；
  5. 在 Release 构建中重复测量并报告分布。

macOS 可使用 Instruments，Linux 常使用 perf，Intel 平台还可使用 VTune。计数器名称、权限和可用性依系统与处理器而异，需要结合当前环境验证。

如果优化后执行指令减少，而缓存行为没有变化，收益可能来自计算；如果线程增加但带宽已饱和，应优先减少流量，而不是继续加线程。

14. 常见误区怎样纠正？

误区一：同为 O(n)，速度应该差不多

不对。复杂度忽略了缓存行利用率、预取、地址转换和带宽等常数因素。大数据上的常数差异可能决定实际吞吐。

误区二：缓存行永远是 64 字节

不对。64 字节很常见，但应查询目标硬件；可移植代码不能依赖固定值维持正确性。

误区三：SoA 总比 AoS 快

不对。布局要匹配字段访问集合。批量使用少数字段时 SoA 常有优势，整对象访问时 AoS 可能更自然且同样高效。

误区四：链表插入是 O(1)，所以比 vector 快

不完整。定位插入点可能不是 O(1)，节点分配、指针追逐和缓存未命中也有成本。必须按整个工作负载测量。

误区五：没有锁争用就没有并发访存问题

不对。伪共享、缓存一致性流量、NUMA 远端访问和总带宽饱和都可能限制扩展性。

误区六：手工预取一定能隐藏内存延迟

不对。错误的地址或距离会浪费带宽、污染缓存。只有测量证明硬件预取不足时才值得尝试。

15. 什么时候值得做访存优化？

访存优化特别适合：

  • 大数组、图像、矩阵和粒子系统的批量处理；
  • profiler 显示缓存未命中或带宽占主导的循环；
  • 多线程统计中存在缓存行争用；
  • 同一数据块会被反复使用的数值内核；
  • CPU/GPU 间需要统一考虑批量字段访问的数据布局。

若数据完全放在缓存中、热点主要是复杂计算、I/O 或锁等待，改变布局可能收益很小。公共 API 和持久化格式的布局变更还会带来兼容成本，不应在没有证据时重构整个对象模型。

16. 总结

回到开头，交换循环没有减少一次加法，却改变了数据到达 CPU 的顺序。行优先访问更充分地使用每次搬入的缓存行，而大步长列访问可能重复支付内存层级成本。

最重要的结论是：

  1. CPU 按缓存行搬运数据，连续访问通常能提高每次传输的有效利用率。
  2. AoS、SoA 和分块没有绝对赢家，必须匹配字段集合与复用方式。
  3. 并行程序除了数据竞争，还要关注伪共享、带宽饱和和 NUMA。
  4. 对齐、预取和固定缓存行假设都与平台相关，不能替代测量。
  5. 正确的实验要保持计算语义一致、消费结果、使用 Release 构建并重复运行。

实践中先画出热循环的地址访问顺序：相邻两次访问相隔多少字节，每个缓存行真正用了多少数据，加载后的数据多久会再次使用。这个简单检查，往往比先改指令更容易找到真正的性能机会。