每个字节都很重要

# 每一个字节都至关重要 来源：https://fzakaria.com/2026/06/01/every-byte-matters 我的职业生涯中有很大一部分时间都在使用 Java。在那段时间里，你已经习惯了庞大的类。新功能？只需向类中添加一个新方法和字段即可。每个新字段的成本很少被考虑。性能通常是从*经典计算机科学*的角度来考虑的，通过分析所使用的算法和数据结构的渐近分析。 事实证明，即使在你的算法增长规模内，例如一个简单的 for 循环 `O(N)`，如果我们对底层硬件有更深入的了解，时间也可能发生巨大变化。 首先，让我们了解我们当前的机器。让我们看看我们的*缓存行*和*页面*大小。 `` $ lscpu | grep -i cache L1d 缓存： 352 KiB（10 个实例） L1i 缓存： 640 KiB（10 个实例） L2 缓存： 10 MiB（5 个实例） L3 缓存： 12 MiB（1 个实例） $ getconf LEVEL1_DCACHE_LINESIZE 64 `` *实例*数量反映了缓存在 CPU 之间的共享方式。如果我有 10 个 CPU，每个都有自己的 `L1d` 缓存，而其中两个会共享一个 `L2` 缓存。 我们的缓存行大小是 **64 字节**。 `` ┌─────────────────────────────────────────────┐ │ 64 字节 │ │ 字节 0 字节 1 字节 2 ... 字节 63 │ └─────────────────────────────────────────────┘ `` 当你从内存中读取**一个**字节时，硬件会将周围的 64 个字节填充到缓存行中。其思想是数据通常具有时间和空间局部性，意味着数据经常在彼此附近被访问，并且在时间上彼此接近。 我们可以参考 Jeff Dean 著名的“每个程序员都应该知道的延迟数字” (https://colin-scott.github.io/personal_website/research/interactive_latency.html)，但快速回顾一下我们这台机器的数值如下： `` ┌──────────────────────────────────────────────────────────────┐ │ CPU 核心 │ │ ┌───────────┐ │ │ │ 寄存器 │ < 1 ns │ │ └─────┬─────┘ │ │ ▼ │ │ ┌───────────┐ │ │ │ L1d 缓存 │ ~35 KiB/核心 ~4-5 周期 ~1-2 ns │ │ │ │ ~560 条缓存行 │ │ └─────┬─────┘ │ │ ▼ │ │ ┌───────────┐ │ │ │ L2 缓存 │ ~2 MiB/核心对 ~12-15 周期 ~4-5 ns │ │ │ │ ~32,000 条缓存行 │ │ └─────┬─────┘ │ │ ▼ │ │ ┌───────────┐ │ │ │ L3 缓存 │ 12 MiB 共享 ~30-40 周期 ~10-15 ns │ │ │ │ ~196,000 条缓存行 │ │ └─────┬─────┘ │ │ ▼ │ │ ┌───────────┐ │ │ │ DRAM │ ~100-200 周期 ~60-100 ns │ │ │ │ │ │ └───────────┘ │ └──────────────────────────────────────────────────────────────┘ `` 每个缓存的大小是 `lscpu` 返回的数字除以核心数或实例数；即 352 KiB ÷ 10 个实例 = ~35 KiB。然后我们通过将此数字除以 64 来确定缓存行数量；即 35 KiB ÷ 64 字节 = 560 条缓存行。 这一切为何重要？🤔 让我们考虑一个例子，我们要遍历一个单独的结构体 `Monster` 并提取 `boolean is_alive` 来筛选它们。我们创建结构体，在这个特定例子中，我们需要 64 字节来表示一个 Monster。 `` struct Monster { uint32_t id; // 4 字节 float x, y, z; // 12 字节 float vx, vy, vz; // 12 字节 int32_t hp; // 4 字节 int32_t attack; // 4 字节 int32_t defense; // 4 字节 uint8_t is_alive; // 1 字节 uint8_t team; // 1 字节 char name[22]; // 22 字节 }; // 总计：64 字节 `` 如果我们有一个 Monster 数组并遍历它们，缓存行会像这样填充。每个缓存行将填充一个 monster，我们只会获取 `is_alive` 字节。 这通常被称为“结构体数组”。 `` 缓存行 0 缓存行 1 ┌──────────────────────────────┐ ┌──────────────────────────────┐ │ id0 x0 y0 z0 vx0 vy0 vz0 hp0 │ │ id1 x1 y1 z1 vx1 vy1 vz1 hp1 │ │ atk0 def0 alive0 team0 name0 │ │ atk1 def1 alive1 team1 name1 │ │ ▲ │ │ ▲ │ └─────────────┼────────────────┘ └────────────┼─────────────────┘ │ │ 需要这个 需要这个 `` 如果我们改为将数据规范化，使得每个字段都在自己的列表中，我们可以更紧密地打包缓存行。 `` 缓存行 0 ┌───────────────────────────────────────────────────────────────┐ │alive0 alive1 alive2 alive3 alive4 alive5 ... alive62 alive63 │ │ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ │ └──┼──────┼──────┼──────┼──────┼──────┼──────────┼───────┼──────┘ │ │ │ │ │ │ │ │ └──────┴──────┴──────┴──────┴──────┴──────────┴───────┘ 一次性获取全部 64 个 `` `` // SoA 布局 struct Monsters { uint32_t *ids; float *xs, *ys, *zs; float *vxs, *vys, *vzs; int32_t *hps; int32_t *attacks; int32_t *defenses; uint8_t *is_alives; // 连续紧凑排列 uint8_t *teams; char (*names)[22]; }; `` 这种布局类型被称为“数组结构体”。 这能产生多大的影响？ soa 图 (https://fzakaria.com/assets/images/aos_vs_soa.png) 当 Monster 结构体大小为 1KiB 时，我们可以观察到高达 **30 倍**的改进 🤯 当结构体很小时，差异不太明显，因为多个 Monster 结构体仍然可以在单个缓存行中被获取。 这种数据访问非常热。你的 CPU 预取器知道它是顺序进行的，并在你需要之前获取下一个缓存行。你实际上永远不必等待内存被取回。 那随机访问模式呢？ 并非所有访问模式都是顺序的。哈希表、树、图遍历和指针密集型数据结构会跳转到不可预测的位置。CPU 无法预取它无法预测的内容。对于随机访问，CPU 需要整个数组都存在于缓存中，以避免因内存查找而导致的停顿。 这意味着**你的集合的总大小**决定了你的性能层级。 Monsters工作集 (64B)延迟 (64B)工作集 (128B)延迟 (128B)51232 KiB~3 ns64 KiB~11 ns4,096256 KiB~11 ns512 KiB~13 ns32,7682 MiB~29 ns4 MiB~43 ns65,5364 MiB~49 ns8 MiB~65 ns131,0728 MiB~163 ns16 MiB~162 ns将结构体从 64B 翻倍到 128B 会使相同数量 monster 的工作集翻倍，将数据推入更慢的缓存层级。仅 512 个 monster 时，64B 结构体适合 L1d，延迟约 3 ns——但 128B 结构体已经溢出到 L2，延迟约 11 ns。 我们可以通过一个指针追逐基准测试来观察这一点。我们分配 N 个 monster 大小的节点，将它们按随机顺序连接起来，然后追逐指针。每次跳跃都落在一个不可预测的地址上，完全击败了 CPU 的预取器。 soa 图 (https://fzakaria.com/assets/images/cache_staircase.png) 我没有像通常那样以对数方式绘制它（我觉得有时容易忽略细节），而是包含了一个放大的图。我们可以看到所有结构体大小都经历了类似的*阶梯*模式，因为它们经过不同的缓存层级，但更大的结构体大小是*左移*的，意味着它们更早地遇到延迟增加。 这意味着对于随机访问模式，如果你能严格控制总工作集大小，你可以极大地影响时间。 了解你的结构体和工作集大小可以带来显著的差异。