« October 2021 | Main

November 16, 2021

C 中访问 Lua 配置表的优化

这两天写代码时用到之前写的一个对 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 中不能迭代配置表。

November 12, 2021

ECS 中同类关联数据的处理

如之前我在 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) 的成本。