我在职业生涯中花了很大一部分时间在 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 字节 │ │ byte 0 byte 1 byte 2 ... byte 63 │ └─────────────────────────────────────────────┘ 当你从内存中读取一个字节时，硬件会将周围的 64 字节填充到缓存行中。这个想法是，数据通常是时间和空间上相关的，这意味着数据通常是彼此接近并且在时间上接近地被访问。我们可以参考杰夫·迪安（Jeff Dean）著名的“每个程序员都应该知道的延迟数字”，不过，快速回顾一下我们特定机器的值如下： ┌──────────────────────────────────────────────────────────────┐ │ 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 并提取布尔值 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]; }; 这种布局类型被称为“数组的结构体”。 这会有什么影响？我们可以观察到，当 Monster 结构体大小为 1KiB 时，性能提升可达 30 倍 🤯 当结构体较小时，影响较小，因为多个 Monster 结构体仍然可以在单个缓存行中被获取。但这种数据访问极其频繁。您的 CPU 预取器知道它正在顺序访问，并在您需要之前获取下一个缓存行。您实际上不必等待内存被提取。随机访问模式呢？并不是所有访问模式都是顺序的。哈希映射、树、图遍历等等...