4. 数据结构优化：从内存布局榨取性能

数据结构优化，说白了就是让CPU更舒服地访问你的数据。CPU缓存就那么几十KB，你想想看，如果数据东一块西一块，缓存命中率低得可怜，性能能好才怪。

我刚开始做算法优化时，总觉得算法逻辑对了就行。直到有一次，一个看起来简单的遍历操作，跑起来比预期慢了10倍。查了半天，发现罪魁祸首就是数据结构布局不合理。从那以后，我再也不敢忽视内存布局了。

4.1 紧凑型数据结构设计

紧凑型数据结构，核心目标就一个：用最少的内存，装最多的有效数据。

为什么重要？因为内存带宽是有限的。你每多读一个字节的无效数据，就少读一个字节的有效数据。缓存行（Cache Line）通常只有64字节，能装多少有效数据，直接决定了你的计算效率。

举个例子，一个简单的3D顶点结构：

// 不紧凑的写法
struct VertexBad {
    float x, y, z;      // 12字节
    float nx, ny, nz;   // 12字节
    float u, v;         // 8字节
    uint8_t r, g, b, a; // 4字节
    // 编译器可能填充到40字节
};

// 紧凑的写法
struct VertexGood {
    float x, y, z;      // 12字节
    float nx, ny, nz;   // 12字节
    float u, v;         // 8字节
    uint8_t r, g, b, a; // 4字节
} __attribute__((packed)); // 强制紧凑，共36字节

嗯，这里要注意：__attribute__((packed)) 虽然省空间，但可能导致非对齐访问，在ARM等平台上会触发异常。我建议只在内存敏感的场景使用，并且做好对齐检查。

4.2 缓存行对齐（Cache Line Alignment）

缓存行对齐，就是让关键数据结构正好落在缓存行的起始位置。为什么？因为CPU读取缓存行是整行整行读的。如果你的数据跨了两个缓存行，一次读取就要访问两次内存，性能直接腰斩。

我个人习惯在热数据结构上显式指定对齐：

// 64字节对齐，正好一个缓存行
struct alignas(64) HotData {
    int32_t counter;
    float   values[15]; // 60字节 + 4字节 = 64字节
};

我记得有一次优化一个多线程日志系统，日志队列的头尾指针总是被频繁读写。一开始没做对齐，性能始终上不去。后来把这两个指针分别放到独立的缓存行里，吞吐量直接提升了30%。

4.3 避免伪共享（False Sharing）

伪共享，可以说是多线程编程里最隐蔽的性能杀手。它指的是：两个线程操作不同的变量，但这两个变量恰好在同一个缓存行里。

为什么会这样？因为CPU缓存一致性协议（比如MESI）是以缓存行为单位的。线程A修改了缓存行里的变量a，即使线程B只关心变量b，CPU也会把整个缓存行标记为无效。线程B下次访问b时，不得不重新从内存加载。

我曾经在一个高并发服务里遇到过这个问题。8个线程各自累加自己的计数器，按理说应该互不干扰。结果性能还不如单线程。排查了一整天，最后发现8个计数器紧挨着放在一个结构体里，全挤在一个缓存行上。每个线程累加时，都在互相踢缓存行。

解决方案很简单：用填充（Padding）把每个变量隔开到不同缓存行。

// 伪共享的写法
struct CounterBad {
    int64_t counter1;
    int64_t counter2;
    int64_t counter3;
    int64_t counter4;
};

// 避免伪共享的写法
struct alignas(64) CounterGood {
    int64_t counter1;
    char    padding1[56]; // 填充到64字节
};
struct alignas(64) CounterGood counter_array[4];

嗯，这里要注意：填充会浪费内存。如果计数器数量很大（比如上万个），每个都填充到64字节，内存开销会暴涨。这时候可以考虑用线程本地存储（Thread Local Storage），或者把计数器按NUMA节点分组。

4.4 使用SoA替代AoS

SoA（Structure of Arrays）和AoS（Array of Structures），是两种截然不同的数据组织方式。它们的性能差异，在数据量大、访问模式单一的场景下，可能是数量级的。

特性	AoS（Array of Structures）	SoA（Structure of Arrays）
内存布局	每个元素的所有字段连续存放	每个字段单独一个连续数组
缓存局部性	访问单个元素时好，遍历所有字段时差	遍历单个字段时极好，访问单个元素时差
SIMD友好度	差，字段交错导致无法向量化	好，连续同类型数据可直接加载到SIMD寄存器
典型场景	小数据量、随机访问、对象导向	大数据量、批量处理、数据导向

举个例子，粒子系统：

// AoS写法
struct ParticleAoS {
    float x, y, z;    // 位置
    float vx, vy, vz; // 速度
    float mass;       // 质量
    uint8_t type;     // 类型
};
ParticleAoS particles[100000];

// SoA写法
struct ParticleSoA {
    float* x;      // 所有粒子的x坐标
    float* y;      // 所有粒子的y坐标
    float* z;      // 所有粒子的z坐标
    float* vx;     // 所有粒子的x方向速度
    float* vy;     // 所有粒子的y方向速度
    float* vz;     // 所有粒子的z方向速度
    float* mass;   // 所有粒子的质量
    uint8_t* type; // 所有粒子的类型
};

你想想看，如果只需要更新所有粒子的位置（x, y, z），AoS写法每次缓存行加载会带进来一堆不需要的速度和质量数据。而SoA写法，三个float数组连续排列，一次缓存行加载全是有效数据，还能直接用SIMD指令并行计算。

当然，SoA也不是银弹。如果你需要频繁访问单个粒子的所有属性（比如粒子碰撞检测），AoS反而更好。我建议的做法是：按访问模式决定布局。热路径用SoA，冷路径用AoS，或者干脆维护两份数据。

4.5 知识结构图

下面这张图总结了本章的核心知识点和它们之间的关系：

4.6 避坑指南

最后，分享几个我踩过的坑：

• 不要盲目SoA：如果数据量小（几百个），或者访问模式是随机访问单个对象，AoS反而更好。我建议在数据量超过1万时再考虑SoA。
• 对齐不是万能的：缓存行对齐能解决伪共享，但会浪费内存。如果内存是瓶颈（比如移动端），需要权衡。
• 注意平台差异：x86允许非对齐访问（只是慢），ARM直接报错。跨平台代码一定要用alignas或编译器属性显式控制。
• 用工具验证：别靠猜。用perf stat -e cache-misses、valgrind --tool=cachegrind等工具实际测量缓存行为。

我曾经在一个项目里，把所有结构体都改成SoA，结果性能反而下降了。后来发现是因为数据量只有几百，而且每次都要访问一个对象的所有字段。SoA导致每次都要从多个数组里取数据，缓存行利用率反而更低。嗯，这就是典型的过度优化。

数据结构优化，说白了就是让数据按照访问模式来组织。没有银弹，只有权衡。理解CPU缓存的工作原理，用工具测量，然后针对热路径做优化，这才是正确的方法。