云风的 BLOG

上周看到了 Redis 作者的新玩具语言 Aocla ，感觉很有启发。它是 FORTH 和 Lisp 的杂合体，又增加了一些内嵌局部变量的支持。非常像我前两年给我们数学库做的一个小东西。最初的想法是为数学库设计一个 DSL 潜入 Lua ，在做复杂的数学计算过程时，可以把计算过程停留在 C Side ，减少 Lua 和 C 之间的边界成本。最初的版本是我模仿 FORTH 设计的基于栈的小语言。希望牺牲一些表达能力，换取一点性能。但实用起来过于别扭，后来又增加了一些特性却没有本质改进。最后终于决定把这个 DSL 彻底从数学库中剥离了 。

看过 Aocla 后，我又有了一些新的想法。Aocla 只有一千多行代码，我判断实现这么一个小玩具应该在 2 天之内，所以实验成本并不高。那么，不如直接动手试试重新实现一个看看。

我并没有看 Aocla 的具体实现。我设想的 DSL 只是提供完整的控制结构，数据类型基于 list 就够了。这方面我已有一些经验 写起来应该很顺手。参与运算的数值类型应该是根据需求从外部注入的，类似 Lua 的 userdata ，但提供更高的效率以及类型支持。毕竟，在 Lua 中实现自定义数据类型最大的问题是它们是二等公民，Lua 和 C 之间的边界成本颇高。

如果是嵌入 Lua 使用，那么原生的 string 类型是不必要的。所有数值都可以是类型加 ID ，它们就有了固定的大小。我们的用 DSL 编写的代码规模并不会太大，代码本身也是 list ，赋予它们 64K 的代码空间是可以合理的限制。

这个 DSL 是一个函数式语言，所有的值都是不变量，包括 list 。这样可以保证执行过程是不修改已有状态的。我们把每个执行过程都看成是栈上的若干输入，经过处理，产生若干输出。运行过程需要的空间，处理栈，还需要有一个存放临时生成 list 的堆，可以采取只分配不释放的原则，我们并不需要实现复杂的 GC 。在每个执行过程完毕后，堆栈都可以直接复位。由于不需要 GC ，所以那些原本需要为回收保留的元信息：引用计数器或垃圾标记都可以省略，数据也会更紧凑，或许 64K 的空间就够完成绝大部分任务了。

上面多次强调 64K 的上限，也是为了让内部索引可以在 2 字节内表示，这能进一步的让数据更紧凑。

在我的版本中，基本采用了 Aocla 的设计。但也有一些不同点：

我把 list 分成了两种不同的子类型，一是由代码注入的不变量，由 parser 从 string 构建出来。它更为紧凑，所有的 word （从 FORTH 中借来的概念）都在 parser 过程翻译成 16bit 的 id 。所以每个 list 就是一个 id 数组。我认为像 42 这样的数字、true false 这样的布尔常量，eval def 这样的内置方法，都应该是同一种东西，它们都对应着一个 C Side 的函数，用来改变运行栈。

比如 "42" 其实是一个把整数 42 压入运行栈的 word ，true 则会在栈上产生一个布尔真。parser 在做翻译的时候，只需要切割 word ，用紧凑的方式组成嵌套 list 的形式就可以了。其中内置数据类型的值以常量表的形式也放在代码块中。

运行时，程序可以动态产生一些 list （称之为 dlist ），它们会把“值” 直接放在 list 内。相比 parser 产生的 word list （称之为 slist），它体积更大一些。dlist 中可以包含 slist 的引用、而 slist 中不会包含 dlist 的引用。最重要的 eval ，同时支持 dlist 和 slist 两种 list 并不是难事。

前面提到了，我并不打算实现 GC ，每段程序运行完都直接用 O(1) 的方法重置堆栈。那么，是否还允许在运行期构建新 word 呢？我觉得这是一个可选的特性，如果有会更方便。

对于构建 word 的 def ，如果它定义的是一个 slist ，那么只需要在单词表中记录一下索引就好了。如果是一个 dlist ，为了阻止数据在运行完后被回收，我把运行堆设计为两端向中间使用的。运行过程中产生的 dlist 顺着堆底部向顶部堆叠，等运行完毕后重置。而如果对 dlist 调用 def 的话，则把该 dlist deepcopy 到堆的顶部，永久保存下来。

对于局部变量，我认为是 Aocla 的设计亮点，自然也继承了下来。我把局部变量的数量上限提高到了 255 个，并使用更长的单词（而不是单字母）。它们会在 parser 过程就翻译成单字节的 ID 。

注意，局部变量的名字和 word 的名字一样，在 VM 中其实是保留了单词表的字面串的，这些信息可以用于输出调试信息。不过为了避免变成的字符串结构，VM 中保存的字符串都是字符串的开头有限字节（16 字节）加上 32bit 的 hash 值。也就是说，如果两个字符串的前 15 字节（添加了 0 结束符）相同，且完整字符串的 hash 值也相同，就认为它们是同一个词。我相信这个限制是合理的，够用了。

Aocla 的 tuple 类型就是为了给局部变量赋值。例如 1 2 3 4 (x y z w) 就相当于 x = 1 , y = 2 , z = 3, w = 4 。这让基于栈的语言写起来更自然。我限制了 tuple 的元素个数不超过 4 个，这样可以把 (x y z w）看作是一个 word ，它由 4 个局部变量 ID 构成，可以放在 32bit 的字段中。如果 tuple 的元素个数不足 4 个，就用 255 填充。

上周四和上周五，我花了两个半天时间把上面的基础功能搭建好。这周一又用了一整天的时间完善以及修理明显的 Bug 。完成了一个粗糙的版本 。它没有完全实现 Aocla 的功能（主要是 list 的运行期构建），但加上并不复杂，因为不再涉及 VM 的细节。

这个版本最大的特色应该是其内部数据结构都用相当简单的基础结构构成的。没有指针，没有动态数组。这让程序运行时没有任何动态内存分配。一旦内存耗尽，能体面的结束计算过程。

Parser 的错误报告很简陋，而且没有实现像注释这样的必要特性。这倒不是我偷懒，而是我觉得它的语法足够简单，所以应该用最简单的代码实现最必要的功能：只解析 list 嵌套和分词即可。如果未来想实用，可以用同样简单的代码以 Lua 的形式（使用模式匹配）重新实现一版。在 Lua 版本中，可以更方便的加入过滤注释、提供解析错误后的完整错误报告等。

我还没有设计注入自定义数据类型的 C API ，想来不复杂。Lua binding 没开始动手。因为我注意到，其实它比 Lua 并没有明显的性能优势（这是我一开始的需求）。这并不意外，因为单从内置的控制结构、内置数据类型的处理流程看，同样是解释语言，Lua 已经优化到了极致。我不可能随手写个玩具就能超过它。

而潜在的优势仅在于它和 C 打交道的部分可以比 Lua 更轻量。代价是我们注入 C 代码时要更小心。不过目前看起来，虽然新的 DSL 比我之前的那版要稍微好用一些，但离好用还远远不够。暂时还只是个玩具吧。

最重要的一点：我的收获和 Antirez 一样，我有两个月没怎么写代码了。精力都放在游戏项目（的非代码工作）上。做这么一个千行级别的玩具项目让我恢复了写代码的感觉，非常的开心。

Posted by 云风 at 10:19 AM | Permalink | Comments (4)

ECS 中，同一个 Entity 是否可以由多个同类型的 Component 构成？在 Unity 中，答案是可以。我们的引擎在设计之初也是可以的。

当时有一个问题：在 Lua 中，如何访问同类型的 Component ？如果有多个同类 Component ，最自然的方式是把它们放在一个数组里。但是、绝大多数情况下我们用不上这个特性，每次访问 Component 都加一次 [1] 或 [0] 的数组索引显得画蛇添足。若单个 Component 不用数组，多个才用数组，写起来又有极大的心智负担。因为这样做，它们就成了两个不同的类型。

后来，我们干脆利用 Lua 的特性，把数组和 Component 本身放在一个 table 中。如果有多个 Component 就把这个数组直接放在第一个 Component 的 table 内。就这样用了一段时间后，最后还是受不了这个脏技巧。等到用 C 编写 luaecs 后，就砍掉了这个特性。

ECS 不是万能灵药。如果需要让相同的 Component 聚合在一起，那么就使用额外的数据结构，或是不只使用一个 world 。这是我们目前实践给出的答案。去年在 luaecs 的 issue 9 也讨论过类似问题。

最近，我们在不同的地方又碰到类似的问题。我觉得这个问题的本质是，ECS 虽然提供了一个高效的、不同于 OOP 中的对象的数据模型，但它对数据结构的实现有很大限制（才能换取高效）。我们应该怎样在这种限制下设计出更有弹性的数据结构。

其中一个问题出在我们引擎的渲染模块上。

通常当我们需要一个弹性数据结构，在 luaecs 中，申明一个 lua table 作为 Component 就可以了。table 内的数据结构可以随心所欲。但如果想从 C Side 访问这个 lua table ，性能势必大打折扣。这对于渲染底层显然有不可接受的性能代价。

所以，我们的渲染层用到的 Component 结构都是定义好的 C 结构。用 C side 访问无额外开销，反之在 Lua side 访问比原生 Lua 结构多一个间接层。但我们只在 Lua side 处理这个结构的初始化和其它的一些低频操作，这是可以接受的。换得的好处是在 C side 直接编写 system 原生的处理渲染过程，这让我们可以让一个基于 Lua 架构的渲染模块可以获得 C/C++ 原生代码编写的渲染模块 90% 以上的性能。

在材质部分，我们遇到了同一个可渲染对象需要多个材质的问题：比如，一个可渲染对象，在普通的渲染流程用到的材质肯定和渲染它的阴影时用到的不同。一些特殊的渲染效果，也会用到不用的材质。

解决方法是，在 C 结构中，直接定义出材质数组。它们是一体的，为同一个 Component 。这样，同一个可渲染对象能同时拥有的不同材质数量就有一个上限。在实践中，我们发现，这个上限可大可小，不同的项目有不同的需求。如果我们把自定义效果做成插件的话，组合过多效果就可以需要更大的上限；若只用基本的渲染模块，又不需要太大。

对于 C/C++ 项目，我们会用动态数组实现这种弹性需求，如果不需要弹性，则在编译期确定数组大小。而对于动态语言，没有也不能在编译期固定数据结构，一切都是动态运行时再确定的。而我们这种混合使用的方式，引入了第三种数据结构的形态：初始化阶段动态构造数据类型，而运行过程中不再变化。这时，C side 看到的是一个材质数组，但数组的长度不是编译期确定的，而是在运行时传入。该长度在程序初始化阶段就确定好了，它取决于我们加载了多少自定义材质的插件。

如果需要在 C Side 处理更有弹性的数据结构怎么办？我和同事讨论过这个问题。我建议用一个 C/C++ 模块管理这种数据类型，以 id 来索引它们。而 luaecs 中只保存 id 。定期比对 ecs 中的 id 集合和 C/C++ 模块中的集合，就能找出已被销毁的那些 id 对应的对象。

另一个问题在我们的游戏逻辑。

我们是一个类似异星工厂的游戏。每个机器都由不同的组件构成。比如一个电力组装机，其实是由一个用电设备和一个组装机以及仓储组件构成的。电网负责给用电设备的电容充电，物流网络负责给仓储供货，组装机消耗电容中的能量和仓储里的原料生产物品。

像电网这样的系统只关心游戏世界中的发电设备和用电设备就够了，而生产系统专心负责转换物品，等等。大多数核心系统我们是用 C/C++ 编写的，而初始化这样的复杂流程则从 Lua 中管理。

最近、我想用多个组装机模块拼合出一个建筑，这涉及了同类 Component 构成 Entity 的问题。具体是这样：我需要一个车辆充电站的建筑，它可以给物流车辆充电。

第一，我想限制充电站的最大充电效率。即使电网功率足够，两辆车充满电驶离充电站的间隔时间也不要太短。即使车需要的电量很少，也不希望它能瞬间充满。

第二，充电站要有蓄能功能，如果车辆充电需求不高，可以在闲时蓄能，忙时还可以连续充电；但如果一直高频入车，整体效率会下降，出车间隔拉长。

第三，如果电网停电，充电站不应完全瘫痪。防止玩家的工厂完全崩溃。因为车辆是我们的主要物流手段。物流停转后，很可能无法发电。btw, 在异星工厂中，作为主要物流系统的传送带是不耗电的。

专门写这么一个组件完成以上需求固然可以，但我更希望用已有的组件拼装起来。

车辆充电其实是一个组装机，它用空车和假象的电池组装成满电的车。这个组装机是不耗电的。同时，充电站内还有另外一个组装机，它消耗电凭空生产出电池来。

当车辆驶入充电站，所有的余电都会转换为对应的数量的电池累加到充电站的充电仓库中。然后车就变成了空车，作为原料之一存放在充电站的仓储内，等待组装成满电的车。每辆车无论余电多少，都需要完成一个完整的组装流程才可以驶出。

电池是一个假象物，玩家并不能直接看到，它堆在充电站的内部仓储内。我们可以有两个类似的组装机凭空制造出电池，直到塞满电池仓库。一个组装速度比较快，但会消耗电网中的能量，一个组装速度很缓慢，但完全不要电能。这样，当电网无法供电时，依然可以缓慢工作；而有电网供电时，效率更高。

异星工厂有很多 mod 也用了类似的组合方式组合出复杂的机器。

比如早期异星工厂是没有液罐火车的，有 mod 就做了一个自动把液体装桶，再把桶放入车厢的装置，同时在另一边可以把桶中的液体倾倒出来。这就是现在原本中装卸车用的液体泵的雏形。

还有著名的太空探索 mod 中有一种冷凝发电机，它用蒸汽发电后能归还 99% 的水。如果直接做一个 100 蒸汽变成 99 水并发电的配方，在电网电力充足的时候会浪费掉多余的能量。所以 mod 作者采用了一个曲折的方法，让一个组装机能把蒸汽变成冷凝蒸汽（另一种液体）并立刻退还水；然后再用冷凝蒸汽作为燃料慢慢的消耗掉发电。

上面我提到的充电站还有其它的实现方法，因为目前 luaecs 还不支持 Entity 中组合多个组装机组件，最终我们也没有使用这种方法。但我思考了给 luaecs 增加这个特性的可行性。

我认为是可行的。

目前我们的 ECS 结构，每种 Component 都单独为一个数组。每个 Component 都持有一个内部 id 。拥有相同 id 的不同类型的 Component 即为同一个 Entity 。这些 id 是单调递增的，所以，从一个 Component 查找同一 Component 上的其它兄弟就是一个二分过程 O(log N)。如果系统是在顺序遍历一类 Component ，那么查找另一个类型的 Component 也近似 O(1) 。

如果我们支持同一个 Entity 可以由多个同类 Component 构成，在数据结构上仅仅只需要允许多个 Component 持有相同的 id 就够了。难点在于 Lua 侧的接口设计。select 某类 Component 的接口应该是怎样的？

我认为、当 select 的主 key 出线多个 Component 在同一个 Entity 身上时，遍历过程应该是多次。即，如果一个 Entity 身上有两个 Component A ，遍历过程应该出现两次 A 。因为处理所有 A 组件时，并不需要关心它们是或不是同一个 Entity 。

对于非主 key ，连带得到的 Component 默认应该只给出同类中的第一个。但用户在 API 层面可以申明需要获得数组，若是这样，无论它有或没有多个，都在迭代器中以一个数组的形式获取。

这个想法需要对 luaecs 做不少改造，谨慎起见，我还没有动手做。

Posted by 云风 at 03:26 PM | Permalink | Comments (0)