这两天和同事讨论一个问题，我写了个小玩意。

事情起因是，我们公司上海的工作室的一个 MMO 项目做服务器压力测试。谈及优化，涉及到服务器中使用的 C 模块。他们把同一套 C++ 加上 namespace 编译了很多份，供多个服务使用。我很好奇，一般来说，Lua 的 C 模块是可以供多个 vm 共用的，并不需要实际链接很多份。仔细探究发现，原来这个代码中用到了一些全局对象（singleton 模式）。

我本能的觉得全局对象的设计中透着糟糕的味道，在逐个分析每个全局对象的必要性时，发现了一个有趣的东西：寻路模块。

寻路模块本身的实现是没有持久状态的，场景地图的障碍信息是独立出去的静态不变数据，全局共享，这是合理的设计。但是一个无状态的 pathfinding 对象却被实例化了很多份，供不同的服务独立使用。

一开始，我很奇怪，一个无状态的寻路函数，为什么需要保存一个全局对象。读了代码后发现，寻路算法的初始化过程需要初始化一大块内存。具体说来，是一个大约 200x200x16 的三维数组，每个单元大约有 16 字节。算法就是很基础的 A* pathfinding ，在这么个三维网格中寻路。需要以开始这个三维数组的内存为全零。大约是 10M 内存。在高频调用下，memset 10M 内存是不小的开销。

实现者为了节省初始化的时间，在每个格子中记录了一个 64bit 的版本号，每次寻路递增版本，使用这些格子时判断一下格子的版本号和当前版本号是否一致，以此为标准来判断这个格子在当前轮次是否有初始化过。

由于真正的寻路过程往往只使用这 10M 内存中的极少空间，所以节约了大量的初始化时间。但这需要全局保留块内存，不能每次寻路都重新构造这么一个对象。

我想了一下这个问题。它本质上的需求是一个 3d 稀疏矩阵。原本我们用一个 hash 表也可以做到，只需要用三个维度的索引连接起来做 key 即可。但是实现者认为这样可能会有不确定的性能问题，宁愿使用空间换时间的方式以巨大的平坦内存结构来让操作这个稀疏矩阵的时候可以以 O(1) 的代价访问。但是，就带来了这一大块内存每次使用的初始化问题。

表达空间的稀疏矩阵除了 hash 表，还有很多方法，比如 KD tree ，八叉树等等，但无论从实现复杂度和访问效率上恐怕都没有说服力。我想，既然服务器上没有空间开销问题，那么能不能从根本上实现一个惰性初始化的内存结构呢？

这里是我随手写的几行代码，我认为可以解决这个问题。

假设 cpu 的 cacheline 是 64 字节，字长是 64bit ，我想以 64 字节为单位去初始化内存是最有效的（把一个字节清零和把 64 字节清零速度是一样的）。那么，10M 内存就可以划分成大约 156K 个段落。我们可以用 1 bit 记录每个段是否有初始化，在访问内存前查看对应的标记位就可以决定是否应该先把对应段落清为零。

156K 个标记位大约需要 2400 个 64bit 的字，也就是将近 20K 的内存来保存。如果也不想初始化这 20K 内存的话（因为大部分格子不会访问到），那么可以依法炮制一个 2 级标记。这一级，我们把这 20K 内存分成 64 段，每段 300 字节左右。最终，我们就用一个 64bit 的字来控制它们的初始化。

最后，用 gcc 开 O2 优化看了下最终生成的汇编代码，感觉编译器优化的结果很好。

这个项目使用的地图高达 4000x4000x16 格。里面保存了网格状的障碍信息。而服务器这个寻路模块要解决的是 NPC 在地图中攻击附近的玩家时能够绕过障碍物的问题。

也就是说，这个寻路模块并不需要解决长距离寻路，要处理的也仅仅是绕开附近的障碍物。且障碍物是静态不变的。

这些场景并不是特别复杂的迷宫，障碍的拓扑结构很有限，所以这个巨大的障碍数组中的信息密度非常之低。我认为，既然花了这么大的空间代价去保存障碍信息，无非就是想让寻路算法简单高效。但其实，这么大的空间，已经足够把 "地图上每个点到附近不太远距离内的任意目标点的路径" 全部记录下来了。

只要经过预运算，用合适的数据结构储存，我们完全可以在 O(1) 时间查询出任意一条路径。具体怎么操作，我下篇 blog 再写。

建议继续学习：

1. Linux内存点滴 用户进程内存空间    (阅读：11496)
2. ps - 按进程消耗内存多少排序    (阅读：11293)
3. Linux Used内存到底哪里去了？    (阅读：9984)
4. Linux操作系统的内存使用方法详细解析    (阅读：8883)
5. linux内核研究笔记(一）内存管理 – page介绍    (阅读：8650)
6. 几个内存相关面试题（c/c++)    (阅读：8034)
7. 内存越界的概念和调试方法    (阅读：6305)
8. 必看！linux系统如何查看内存使用情况    (阅读：6167)
9. Innodb分表太多或者表分区太多，会导致内存耗尽而宕机    (阅读：6170)
10. 如何查看Linux 硬件配置信息    (阅读：5887)