引言内存局部性概念简介时间局部性与空间局部性算法性能与内存访问模式的关系分析性能瓶颈的意义如缓存命中率、吞吐量下降等内存局部性的理论基础缓存层次结构L1/L2/L3缓存、主存、磁盘的访问延迟差异时间局部性重复访问同一数据的高效利用空间局部性连续内存访问的预取优化示例循环遍历数组 vs 随机访问链表常见算法性能瓶颈的局部性根源低空间局部性不规则数据结构如指针跳转、哈希表冲突矩阵的非连续访问如行列优先遍历的差异低时间局部性频繁换出的冷数据如大范围随机访问多线程竞争导致的缓存行失效False Sharing案例分析典型算法的局部性缺陷快速排序递归调用栈的缓存不友好B树查询节点分裂导致的空间局部性中断动态规划高维数组访问的跨步问题Stride图算法随机邻接节点访问如PageRank的稀疏矩阵问题性能优化方法数据布局优化结构体填充Padding减少缓存行冲突数据分块Blocking/Tiling提升空间局部性算法重构循环展开Loop Unrolling减少分支预测开销访问模式改造如Z-order曲线优化多维数据硬件感知设计显式预取指令PrefetchingNUMA架构下的数据亲和性绑定