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

缓存友好的设计原则局部性原理时间局部性频繁访问的数据应保持在缓存中。空间局部性数据存储应连续以利用缓存行预取。减少缓存行浪费数据结构大小应与缓存行对齐通常64字节。避免填充或碎片确保数据紧凑存储。避免伪共享多线程场景下高频修改的变量应独占缓存行。通过填充或编译器指令如alignas隔离变量。预取友好性顺序访问优于随机访问。数据布局应支持线性遍历如数组而非链表。实现案例案例1紧凑数组 vs. 链表数组的连续内存布局减少缓存缺失链表因指针跳转导致性能下降。示例遍历1百万元素的数组和链表耗时对比。案例2结构体拆分SOA vs. AOS数组结构AOSstruct {int x, y, z;}[N]可能浪费缓存行。结构数组SOAstruct {int x[N], y[N], z[N];}提升同类数据局部性。案例3B树 vs. 二叉树B树通过节点内紧凑存储多个键值减少缓存行占用。二叉树节点分散易引发缓存抖动。案例4位图压缩用位图代替布尔数组8个布尔值压缩为1字节减少内存占用。实际优化技巧工具辅助使用perf或VTune分析缓存命中率。编译器指令如__builtin_prefetch手动预取数据。