缓存友好的数据结构设计原则与实现案例7

缓存友好的设计原则

局部性原理
时间局部性：频繁访问的数据应保持在缓存中。
空间局部性：数据存储应连续，以利用缓存行预取。

减少缓存行浪费
数据结构大小应与缓存行对齐（通常64字节）。
避免填充或碎片，确保数据紧凑存储。

避免伪共享
多线程场景下，高频修改的变量应独占缓存行。
通过填充或编译器指令（如alignas）隔离变量。

预取友好性
顺序访问优于随机访问。
数据布局应支持线性遍历（如数组而非链表）。

实现案例

案例1：紧凑数组 vs. 链表
数组的连续内存布局减少缓存缺失，链表因指针跳转导致性能下降。
示例：遍历1百万元素的数组和链表耗时对比。

案例2：结构体拆分（SOA vs. AOS）
数组结构（AOS）：struct {int x, y, z;}[N]可能浪费缓存行。
结构数组（SOA）：struct {int x[N], y[N], z[N];}提升同类数据局部性。

案例3：B树 vs. 二叉树
B树通过节点内紧凑存储多个键值，减少缓存行占用。
二叉树节点分散，易引发缓存抖动。

案例4：位图压缩
用位图代替布尔数组，8个布尔值压缩为1字节，减少内存占用。

实际优化技巧

工具辅助
使用perf或VTune分析缓存命中率。
编译器指令（如__builtin_prefetch）手动预取数据。