设计缓存友好的数据结构需遵循：1. 使用连续内存布局如std::vector提升空间局部性；2. 结构体用alignas避免伪共享，隔离频繁写入变量；3. 采用顺序访问模式，利用预取机制，优先遍历数组或使用B-Tree、SoA等结构；4. 哈希表选用开放寻址法如flat_hash_map，减少指针跳跃。核心是让数据布局与访问模式匹配Cache Line机制，降低Cache Miss。
设计缓存友好的数据结构，核心是让数据访问模式与CPU Cache的工作机制协同，减少Cache Miss。现代CPU访问内存不是以字节为单位，而是以Cache Line（通常64字节）为单位加载。如果程序频繁访问不连续或跨Cache Line的数据，会导致大量Cache失效，拖慢性能。
1. 数据布局：优先使用连续内存
缓存友好的首要原则是数据局部性，尤其是空间局部性。数组比链表更缓存友好，因为数组元素在内存中连续存储，一次Cache Line可以加载多个相邻元素。
建议：
- 用std::vector代替std::list或指针链式结构
- 避免频繁的动态分配，尽量预分配大块内存
- 使用std::array或定长数组，当大小固定时
2. 结构体设计：避免伪共享（False Sharing）
多个线程访问不同变量，但如果这些变量位于同一Cache Line，仍会相互干扰。一个线程修改变量会导致整个Cache Line无效，迫使其他CPU重新加载。
立即学习“C++免费学习笔记（深入）”；
Productivity Google Workspace
下载
Access Gmail, Calendar, Drive, Docs, and Sheets via the gws CLI or Python.
解决方法：
- 将频繁写入的变量按线程隔离
- 使用alignas对齐关键字段到Cache Line边界
- 例如，两个线程计数器可分别放在独立Cache Line：
struct alignas(64) ThreadCounter {
uint64_t count;
};
3. 访问模式：顺序优于随机
CPU Cache会预取（prefetch）连续内存数据。如果你遍历数组是顺序的，硬件预取器能有效工作；但随机跳转（如树结构深层递归）则难以预测。
优化建议：
- 遍历容器时使用迭代器或索引顺序访问
- 考虑用B-Tree或B+Tree代替红黑树，节点包含多个键值，提升Cache利用率
- 游戏开发中常用SoA（Structure of Arrays）代替AoS（Array of Structures）
4. 实例：缓存友好的哈希表设计
传统开链法哈希表使用链表处理冲突，指针跳跃导致Cache Miss严重。改进方案：
- 使用开放寻址法，如Robin Hood hashing，所有元素存在连续数组中
- 探测序列尽量短，控制负载因子（如不超过70%）
- Google的flat_hash_map就是典型缓存友好实现
基本上就这些。关键是理解Cache Line的存在，并让数据和访问方式“顺着”它走。不复杂但容易忽略。
