内存的惰性初始化
这篇文章从一个 MMO 服务器压力测试的优化场景切入,探讨了当使用 A* 算法在一个巨大的三维网格(10MB 内存)中寻路时,如何解决初始化开销过大的矛盾。 实现者为避免每次调用都 memset 清零,采用在格点中记录版本号的技巧,实现了“用到时再判断”的惰性逻辑,但这依然需要全局保留这块内存。作者从更高层面指出,这本质上是一个用平坦内存空间模拟稀疏矩阵的权衡问题。 为此,他设计了一套惰性初始化的内存结构:以 64 字节(cacheline 大小)为单位划分内存,仅用一个二级标记树(总开销约 20KB)来记录哪些段落已被初始化。访问时检查标记,按需清零。这样,绝大多数未被访问的内存区域永远不会被初始化,将时间开销降至接近于零,同时空间代价极小。 文章结尾更提出了一个巧妙的延伸思路:对于这种障碍物静态且局部的寻路,与其在运行时寻路,不如用巨大的预计算空间将路径全部存储下来,实现 O(1) 查询。这为解决此类特定问题提供了不同的架构视角。