Skip to content
Published on

Mechanical Sympathy(机械同感)：写硬件喜欢的代码

🇰🇷KO🇺🇸EN🇯🇵JA🇨🇳ZH
필사 모드
分享
Authors

引言 — 相同复杂度，不同速度

算法课教我们用时间复杂度来评判代码。O(n) 比 O(n²) 快，常数倍数可以忽略。这个视角大体是对的，也很有用。但一旦在实务中深入性能问题，就会撞上一堵奇怪的墙。明明同样是 O(n)，一段代码却比另一段快 10 倍，有时甚至快 50 倍 — 尽管两者都只把每个元素访问了一次。

这个差距不是来自算法，而是来自硬件。现代 CPU 并不是我们想象中那种单纯的计算器，而是一台复杂的机器，里面挤满了多层缓存、提前猜测分支走向的预测器，以及把多条指令叠在一起执行的流水线。理解这台机器的运作方式、并据此写代码的态度，被称为机械同感(mechanical sympathy)。这个说法原本来自 F1 车手杰基·斯图尔特(Jackie Stewart)的一句话——"懂机器的车手开得更快"——放到软件上同样成立。

本文要讲的是：为什么对硬件友好的代码会更快，以及如何写出这样的代码。核心主题包括缓存、数据局部性、分支预测、伪共享，以及数据布局。

内存层级 — 速度的悬崖

理解性能的起点，是意识到"内存"其实不止一种。CPU 和主内存(RAM)之间夹着好几层缓存，每一层在速度和容量上都天差地别。越往上越快越小，越往下越慢越大。

  层级          大致延迟         相对速度         大小
  ------------------------------------------------------------
  寄存器        ~0.3 ns          1倍(基准)        数百字节
  L1 缓存       ~1 ns            约慢 3 倍        32~64 KB
  L2 缓存       ~4 ns            约慢 10 倍       256KB~1MB
  L3 缓存       ~12 ns           约慢 40 倍       数~数十 MB
  主内存        ~100 ns          约慢 300 倍      数~数百 GB
  SSD           ~100,000 ns      约慢 30 万倍     数百 GB~数 TB

这张表里最重要的一点是：层与层之间的落差陡得像悬崖。从 L1 缓存读数据和从主内存读数据，大约相差 100 倍。对 CPU 来说，100 ns 几乎是一种永恒 — 这段时间足够执行数百条指令。

把这个延迟换算成人的时间感受，会更有实感。

  如果把 CPU 的 1 个周期当作 1 秒:
  L1 缓存访问    = 约 3 秒
  L2 缓存访问    = 约 10 秒
  L3 缓存访问    = 约 40 秒
  主内存访问     = 约 5 分钟
  SSD 访问       = 约几天

也就是说，CPU 等待主内存的这段时间，换算成人的尺度，相当于出去喝杯咖啡再回来。所以现代性能优化的很大一部分，不是"减少计算"，而是"减少内存等待"，即尽量把数据留在缓存里。计算本身已经足够快了，慢的是把数据取过来这件事。

缓存行 — 缓存不会一个一个字节地搬运

理解缓存的核心概念是缓存行(cache line)。当 CPU 把数据从内存搬进缓存时，它并不会只取你请求的那一个字节，而是把包含这个字节的一整块固定大小的数据全部取来。这一整块就是缓存行，在大多数现代 CPU 上是 64 字节。

  即使只请求一个 int(4 字节):

  内存:  [.. 包含所请求 int 的整个 64 字节缓存行 ..]
                        |
                        v
  缓存:  [整条 64 字节缓存行都被加载]

  也就是说，附近的 60 字节数据也"顺带"进了缓存

这个事实带来了巨大的连锁效应。只要访问某个数据，它旁边的数据就会免费搭车进入缓存。所以如果连续访问在内存中彼此靠近的数据，大部分都已经在缓存里了，速度非常快。反过来，如果访问的是散落在内存各处的数据，每次都要取一条新的缓存行，速度就会很慢。

这正是接下来要讲的数据局部性的物理基础。"连续使用相邻的数据"这条建议，说到底就是"让一条缓存行多用几次"。

数据局部性 — 数组 vs 链表

最能体现数据局部性威力的例子，是数组和链表的比较。按教科书的说法，两者存在权衡：数组随机访问快、插入慢；链表插入快、随机访问慢。但实际测量遍历性能时，链表往往比数组慢得多得多，甚至在插入、删除频繁的场景下，数组胜出也是常事。原因就是缓存。

  数组: 元素在内存中连续排列
  [e0][e1][e2][e3][e4][e5][e6][e7] ...
   └── 一条缓存行会带来多个元素 ──┘
   遍历时大多是缓存命中 → 快

  链表: 节点散落在内存各处
  [node2] ......... [node0] ..... [node3] ... [node1]
      每走到一个节点都要沿指针跳转
      大多是缓存未命中 → 慢(每次都要往返内存)

数组把元素连续排列在内存中。所以从头到尾遍历数组时，一条缓存行就能带来多个元素，大部分访问都会命中缓存。不仅如此，CPU 还能识别这种顺序模式，提前把接下来要用的数据预取(prefetch)过来。

链表则不同。每个节点都散落地分配在堆的各处，节点之间只靠指针相连。所以遍历链表，就得沿着指针在内存各处跳来跳去。每个节点都要取一条新的缓存行，更糟的是，只有读了当前节点才知道下一个节点在哪儿，这让预取也变得困难。结果就是一连串的缓存未命中。

核心教训是这样的：大 O 记法只计算访问次数，但实际速度很大程度上取决于这些访问是缓存命中还是未命中。对于顺序遍历的工作，使用连续内存的数组(或向量、动态数组)在大多数情况下都会胜出。

访问模式就是一切 — 行优先 vs 列优先

即使是同一份数据，访问顺序不同，速度也会天差地别。来看一个经典例子——遍历二维数组。大多数语言(C、NumPy 的默认方式等)把二维数组按行优先(row-major)存储在内存中，也就是说，一行里的元素在内存中是连续排列的。

import numpy as np
A = np.zeros((10000, 10000))

# 方式 1: 按行优先遍历(与内存顺序一致)
total = 0.0
for i in range(10000):
    for j in range(10000):
        total += A[i][j]     # 内层循环扫描连续内存 → 快

# 方式 2: 按列优先遍历(与内存顺序错位)
total = 0.0
for j in range(10000):
    for i in range(10000):
        total += A[i][j]     # 每次访问都要跳过一整行的大小 → 缓存未命中激增

这两段代码累加的是完全相同的元素，累加次数也完全相同，在算法上完全等价。但实际运行时，方式 1 却比方式 2 快上好几倍。根据语言和数组大小的不同，差距有时能达到 5 倍到 10 倍以上。

原因还是缓存行。方式 1 的内层循环，沿着内存中连续排列的一行顺序扫描，一条缓存行就能带来多个元素，大部分访问都命中。方式 2 的内层循环则是沿着列往下走，而在行优先存储下，同一列的元素在内存中相隔了整整一行的距离(此处是 1 万个元素)。所以每次访问都要取一条新的缓存行，而取来的那条缓存行剩下的 63 字节还没被用上就被丢弃了。

教训很明确：按数据存储的顺序去访问它。如果是多维数组，就要弄清楚内存布局(是行优先还是列优先)，并让最内层的循环沿着连续内存扫描。这一条简单的原则，带来的性能提升往往比任何算法上的改进都大。

分支预测 — CPU 在猜测未来

现代 CPU 之所以快，另一个秘诀是流水线(pipelining)。CPU 不是执行完一条指令再开始下一条，而是像流水线作业一样，把多条指令重叠起来处理。但这里有个问题：一旦遇到像 if 这样的分支，CPU 就必须在条件结果出来之前，决定"接下来把哪一侧的指令送进流水线"。

于是 CPU 使用分支预测器(branch predictor)。它根据过去的模式，猜测"这个分支大概率会成立(或不成立)"，提前把那一侧的指令填进流水线开始执行。如果猜对了，就毫无损失地继续快速推进；但如果猜错了，就得把已经提前执行的那些指令全部丢弃(流水线刷新，pipeline flush)，重新从正确的一侧开始。这个惩罚可能高达数十个周期。

这个事实引出了一个著名的观察：处理已排序的数据，可能比处理未排序的数据更快。

# 在一个大数组中，只累加大于阈值的值
threshold = 128
total = 0
for x in data:
    if x >= threshold:      # 这个分支能否被预测，决定了速度
        total += x

如果 data 是已排序的，这个分支会先持续为假，从某个点开始又持续为真。预测器很容易学到这种规律的模式，几乎每次都能猜中。反过来，如果 data 是随机的，分支结果就会毫无规律地跳动，预测器大约一半时候会猜错。每一次误判都会刷新流水线，同样一段代码可能因此慢上好几倍。

由此可以得到几条实务上的洞见。第一，可预测的分支代价很低，不可预测的分支代价很高。第二，有时干脆消除分支本身(无分支代码，branchless)会更划算。比如说，把"根据条件决定要不要加上某个值"这件事，用算术而不是分支来表达，就能避开误预测的惩罚。

# 用算术代替分支(不会有误预测)
# (x >= threshold) 会被当作 True/False = 1/0 处理
total += x * (x >= threshold)

当然，无分支代码不见得总是更快，还可能损害可读性，所以不该无条件套用。核心在于要意识到：热循环(hot loop)里不可预测的分支，可能是一个隐藏的性能杀手。

伪共享 — 看不见的竞争

在多线程代码里，有一个特别隐蔽的性能陷阱，叫伪共享(false sharing)。多个线程各自修改互不相干的变量，逻辑上完全没有冲突，性能却会急剧下降。罪魁祸首再一次是缓存行。

前面提到过，缓存是以 64 字节为单位的一条条缓存行来搬运的。而每个 CPU 核心都有自己的缓存，当多个核心缓存同一份数据时，就必须维持一致性(coherence)。一旦某个核心修改了某条缓存行，其他核心持有的那条缓存行的副本就会被作废(invalidate)。

问题在于，即便是完全不同的变量，只要碰巧落在同一条缓存行里，就会被当成是在争抢同一份数据。

  假设线程 A 修改 counter[0]，线程 B 修改 counter[1]。
  如果这两个变量恰好落在同一条 64 字节缓存行里:

  [ counter[0] | counter[1] | ... 同一条 64 字节缓存行 ... ]
       ^A 写入        ^B 写入

  A 每次写入都会使 B 的缓存行失效，
  B 每次写入都会使 A 的缓存行失效。
  两个线程逻辑上互相独立，却在缓存行上来回"乒乓"，彼此拖慢对方。

这就是伪共享。它不是真正的数据共享(各自操作的是不同变量)，而是因为共享了缓存行才产生的假性竞争。它的症状很棘手：代码完全正确地运行，但线程数增加了，性能却不见提升，甚至反而下降。

解决办法是把出问题的变量推到不同的缓存行上。常见做法是插入填充(padding)，让每个线程的数据各自占据一条独立的缓存行。

  解决方案: 在各线程的数据之间插入填充(padding)，把它们分到不同的缓存行

  [ counter[0] + 填充(填满一整行) ][ counter[1] + 填充 ]
        线程 A 专属的缓存行              线程 B 专属的缓存行

  这样双方就不再触碰对方的缓存行，乒乓效应随之消失

伪共享不容易被察觉，诊断起来也很麻烦。如果你把代码改成了多线程却发现扩展不了，不妨怀疑一下：各线程碰的数据，是不是恰好挤在了同一条缓存行里。

数据布局 — SoA vs AoS

在设计层面处理"数据该如何摆在内存里"这个问题的话题，就是结构体数组(Array of Structures, AoS)与数组结构体(Structure of Arrays, SoA)。装的即便是同一份数据，这两种方式在缓存效率上也天差地别。

AoS 是我们自然而然会想到的方式。把每个实体做成一个结构体，再把这些结构体放进一个数组。

  AoS (结构体数组, Array of Structures):
  struct Particle { float x, y, z; float mass; ... };
  Particle particles[N];

  内存: [x0 y0 z0 m0][x1 y1 z1 m1][x2 y2 z2 m2] ...
        同一个粒子的所有字段挨在一起

SoA 正相反，按字段分别建立数组。

  SoA (数组结构体, Structure of Arrays):
  struct Particles { float x[N]; float y[N]; float z[N]; float mass[N]; };

  内存: [x0 x1 x2 x3 ...][y0 y1 y2 ...][z0 z1 z2 ...] ...
        同一个字段的数据连续排列在一起

为什么这个差异很重要?设想一种只对某个特定字段做大批量扫描的工作。比如有一个物理模拟循环，只更新每个粒子的 x 坐标。

在 AoS 里，x 坐标在内存中彼此相隔很远(因为中间夹着 y、z、mass)。所以哪怕只扫描 x，缓存行里也会顺带带上用不到的 y、z、mass，白白浪费缓存空间。而在 SoA 里，x 坐标连续排在同一个数组里，缓存行会被 x 塞得满满当当。缓存被节俭地利用，而且因为是顺序访问，预取效果也很好。此外，SoA 对 SIMD(用一条指令处理多份数据)向量化也更友好。

  只批量处理 x 坐标时:

  AoS: 缓存行里只有一个 x + 被浪费掉的 y,z,mass  → 缓存效率低
  SoA: 缓存行被 x 塞得满满当当                  → 缓存效率高，对 SIMD 友好

不过 SoA 也不是永远正确。如果经常要一次性处理某个实体的全部字段(比如整体读取并处理一个粒子)，AoS 反而更有利，因为它把这个实体的字段都聚在同一条缓存行里。关键在于访问模式——要看"是按字段扫描，还是按实体扫描"来决定布局。游戏引擎、物理引擎、数据处理系统之所以经常选择 SoA，是因为这类系统的热循环大多只对特定字段做大批量扫描。

可预测的访问模式才是核心

贯穿以上所有内容的，是一条统一的原理：CPU 和缓存喜欢可预测的顺序访问，讨厌随机、散乱的访问。

CPU 内置了硬件预取器(prefetcher)。它会观察内存访问模式，一旦察觉到有规律的顺序访问，就提前把接下来要用的数据拉进缓存。所以对于像顺序扫描数组这样可预测的模式，数据往往在真正需要之前就已经到达缓存了。有了预取器的帮助，内存延迟几乎被隐藏了起来。

反过来，如果访问是随机的，预取器就读不出模式，也帮不上忙。那些四处追着指针跑的数据结构(链表、树、哈希表的链式冲突处理)，以及索引杂乱无章的访问，都会让预取器失效。

由此可以整理出一些实务上的原则。

  • 顺序访问。 尽可能按数据存储的顺序去扫描它。
  • 偏好连续内存。 无论对缓存还是对预取器来说，连续的数组都比散落的节点更有利。
  • 按访问模式安排数据布局。 把经常一起使用的数据放得靠近(落在同一条缓存行里)；如果是按字段扫描，就考虑 SoA。
  • 让热循环里的分支可预测。 必要时可以排序数据，或者干脆消除分支。
  • 多线程场景下要避免伪共享。 把各线程的数据分散到不同的缓存行上。

这些原则最终都收敛到同一种态度上：写代码时，始终意识到数据在内存中是如何布局的、又是以怎样的顺序被访问的。这就是机械同感的实践。

什么时候该在意，什么时候可以忽略

读到这里，你可能会想"那是不是所有代码都该这样优化",但并非如此。机械同感不是一条时时刻刻都要套用的规则，而是一件在需要时才拿出来用的工具。

大多数代码的瓶颈根本不在性能上。可读性和正确性重要得多，过早的底层优化只会让代码变得复杂。就像唐纳德·克努斯(Donald Knuth)那句名言——"过早优化是万恶之源"。所以第一条原则永远是先测量。用性能分析器(profiler)找出真正的热点，然后只专注在那里。

机械同感真正重要的场合是明确的：反复处理海量数据的热循环、游戏与物理引擎和图形学中的实时渲染，以及高频交易或大规模数据处理这类延迟本身就是成本的系统。在这些场合，哪怕算法复杂度已经打磨到位，缓存优化依然能带来数倍的额外收益。

比较均衡的态度是这样的：平时写清晰、简单的代码，但要理解硬件是怎么运作的。这样一来，真正需要性能的那一刻到来时，你才知道该在哪里、该怎么下手。机械同感不是要强迫套用到所有代码上的执念，而是在需要的那一刻才施展的眼光。

结语

同样时间复杂度的代码，实际运行速度却能相差数十倍，原因在于：计算机并不是教科书里那种抽象的计算器，而是一台充满缓存、流水线和预测器的实体机器。内存层级存在速度的悬崖，缓存以行为单位搬运，数据局部性左右着遍历速度，分支预测决定热循环的成败，伪共享阻碍多线程的扩展，数据布局(AoS 与 SoA)则决定缓存效率。

机械同感，就是体察这台机器的"心思"来写代码的态度：把数据连续摆放，顺序访问，让分支可预测，按访问模式安排布局。所有这些，最终都归结为一条原理——按硬件喜欢的方式来处理数据。

大 O 记法依然是宝贵的起点。但在它之下，还有一个仅靠它无法解释的性能世界。理解那个世界的开发者，即便用同样的算法，也能写出快得多的代码——就像懂机器的车手开得更快一样。

参考资料

Discuss on Twitter • View on GitHub