云风的 BLOG

这两天写代码时用到之前写的一个对 Lua 配置表的 cache 模块 。感觉用起来还是不够简洁方便。我今天动手重新设计了一下。

需求是这样的：

项目有非常多的配置信息保存在 Lua 的 （树状层级的）table 中，大部分逻辑代码直接用 Lua 的语法便可直接访问。但是，有少量有性能要求的业务是在 C 中实现的，C function 中也需要读取这些存放在 Lua 中的配置数据。

配置项随着项目开发，变更非常频繁。如果我设计一个小语言，定义出配置表，用代码生成的方式把表项翻译成对应的 C/C++ 结构，再在 C side 根据 Lua 中的数据重建一组 C 数据也未尝不可。这就是 google protobuf 官方采用的方式（用代码生成的方式，根据数据的 schema 构建出 C++ 类，让 C++ 可以方便访问这些数据）。

但我不想搞得这么复杂（浪费？）。大部分业务循环次数很多，而需要读取的配置表象却比较单一（反复取相同的条目）。所以，虽然第一次通过字符串 key 逐级解析 Lua 配置表或许较为低效；但只要在 C side 用一个 cache 模块缓存下高频访问的配置项应该就能解决性能瓶颈。

我采用了一个固定大小的内存块做 hash cache 。key 使用编译时决定的 32bit int 。用宏定义出来。

比如，如果我想读 name 这一项，就定义一个：

PROTOTYPE(name, string)

它表示，有一个配置表项是 "name" ，它的类型是 string 。这个宏会展开为一个 C 函数

const char * get_name(struct cache *c, const char &key);

函数的实现也是由宏展开的，实现内部会给 name 分配一个唯一的 id 。

ps. 一开始我用 __LINE__ 这个宏拼接出一个唯一 id ，只要宏定义不在同一行就不会有冲突。后来发现，现在几乎所有的编译器都支持了 __COUNTER__ 这个宏，它会帮我生成自增 id 。

需要缓存的值有四种类型：int float bool 和 string 。前三种类型都是 32bit 的，而字符串在 64 位平台上是一个 64bit 指针 const char * 。string 类型非常少见（在 C 代码中几乎不会访问到），如果我简单的用一个 union 类型联合该四种类型会比较浪费。因为这样，每个 hash slot 就需要 4 (key) + 8 (value) 字节。考虑到对 cpu cache 友好的话，我会把 key value 连续存放在一起，这样在 64bit 平台上，再考虑对齐问题，每个 slot 可能需要 16 字节 。

经过一点思考，我发现我只需要把少量的 string 类型存放在连续的两个 slot 中，每个 slot 存放一半就可以了。这样，每个 slot 就只需要 4 + 4 字节即可。

这个 cache 的运作算法是这样的：

1. 通过 get_xxx 的 C API 访问 cache ，编译器为 xxx 生成了一个唯一 32bit id 做 key ，以此 key 查询 cache 。如果命中，直接取出 value 项。由于类型信息是编译器决定的，所以可以从 value 的 union 中取出正确的类型。

2. 如果 cache miss ，这通过编译器记录的 key string 去 Lua side 查询具体的 value 。这个过程花少稍长的时间是可以接受的。如果在 Lua side 找不到对应项，则抛出 error 不影响 C cache ；找到的话，就更新对应的 C cache 条目。

3. 当对应的项目是字符串时（编译期决定），计算 hash 时元整到偶数序号的 slot 上，认为该处连续的两个 slot 保存着该条目。需要核对两个 slot 对应的 key ，更新对应的 value 。返回结果需要将两个 slot 上的 value 值合并为一个 const char * 返回。

在使用时，需要把 C side 可能用到的配置表项的 key 全部定义在一个 .h 文件中，方便编译器统一生成 id 。key 可以是点分割的字符串，对应 Lua 中的树状多级表。

在 C 中不提供一次读取一个子配置表的 api 。

在 C 中不能迭代配置表。

Posted by 云风 at 12:26 PM | Permalink | Comments (2)

如之前我在 ECS 模型下的处理模式 中所言，ECS 模式下最难处理的是同类 Component 之间有相互联系的情况。

最方便 ECS 处理的数据是相互独立的，每个数据单元都不和其它数据单元产生联系；如果多个数据单元会有故有的联系时，当可以把它们看作是同一个实体（Entity）下的不同组件（Component）时，那么就可以借用 Entity 的概念来处理它们。我们依旧可以按固定的次序去迭代这些数据。

但是，在复杂系统中，无可避免的，同类数据相互之间也可以产生联系。例如：场景管理中，节点之间有父子关系，计算节点的空间状态的过程对数据的遍历次序有要求。且计算过程还需要访问父节点的状态。解决这类需求是 ECS 框架的一大挑战。

我在最近一年的 ECS 实践中尝试过多种方法：

最早的方案是“使用一种特殊的 Component，它自己独立是一个 Entity，永不删除，但会被复用。”它提供 id ，其它 Entity 用 id 来引用它。

这个方案的好处是，实现引用的额外运行成本不高，接口简单，适合在 C 代码中直接使用，Lua 中稍微扩展一下 select 的语法也可以方便控制。

但缺点也很明显，生命管理成本很高，需要很多额外的代码和设计来保证正确性。用起来就像在 C 语言中不做任何管理，操作 raw 指针。

后来我尝试了一个方案，它只适合在 Lua 接口中使用。即，使用一个 lua table 作为 Entity 中的引用对象，由底层框架负责更新同步它的状态。用它时刻可以索引到底层框架中的某个 Entity 。它被实现成一种弱引用，当 Entity 被删除时，弱引用会感知，并在解引用时报告错误。

这个方案更为通用，不过只适合在 Lua 层使用，也有一定的运行成本。

最近我尝试了第三种方案。

我不再用引用同一块数据的方式来让不同的模块共享同一份数据。而是把需要处理的关联数据额外生成一个副本，放在 ECS 框架之外。而 ECS 框架内也有一个副本。两个副本中均有同一个 id 用来关联查询。

用实例来说，我最近在制作一款类似异星工厂的游戏。里面有一个液体管道系统。需要模拟液体在管道间的流动过程。水流的方向在游戏运行期间不是固定的，它根据每节水管的水压、液体的动量等决定。具体的算法参考了异星工厂的这篇开发日志 。

算法需要把所有的水管放在一起做拓扑排序，沿着水流方向逆向依次处理水管；而不能将每节水管独立处理。这很好理解，因为水管容量有限，你需要让水向下游流出后，才能放上游的水流入。最难处理的是水管的分叉，如果水流会从几个源头汇入，或需要分流到几个岔口，必须综合考虑所有的邻接状态，统一按比例分配。这样才不至于在规则上所有管道都是平等的，而实现却让一些管道比另一些更平等。

我把整个管道网络实现成一个整体，放在 ECS 框架之外。但每节水管都有一个唯一 id 标识。ECS 框架内，水管也有一个对应的组件，但组件内只有水量和 id ，没有其它信息。

从 ECS 框架看，水管都是独立的。可以对单节水管添水或消耗。但水网的流动是在管道模块中处理的。我们只需要每帧把水位同步回来即可。

从 ECS 这边看，流程如下：

1. 让水泵抽水、让消耗水的机器用水。把这个信息通过 id 同步到水网。
2. 水网流动（更新）。
3. 迭代所有水管，根据 id 从水网中取到当前水位，同步到水管组件。

其中，水网每帧有一个依赖拓扑排序的调整过程，维持有一个排过序的次序。方便更新时候可以逆着水流正确更新。根据这里的实际情况，一旦水流动开，次序几乎不会发生变化（回流）；即使发生变化，每次的变化也是极小的，渐变的。这个算法有一定的复杂性，本就不适合在 ECS 框架下实现。（因为 ECS 框架下，只有按固定次序遍历数据是最高效的，不提供随机访问数据的能力）

我们不需要持久维护一张 id 映射表方便两套系统间的数据同步。

这是因为，一旦次序决定，step 1 中，水泵和用水机器几乎总处于排过序的水网单元的两端。所以，可以近似做到 O(1) 的复杂度。

而在 step 3 中，因为 ECS 这边遍历次序总是恒定的，即对象的构建次序。所以，对水网这个模块来说，总是以同样的持续查询那些 id 。这里可以做足够的优化让依次查询几乎都是 O(1) 的成本。

Posted by 云风 at 02:27 PM | Permalink | Comments (5)