April 14, 2019

并发 Hash Map 的实现

Lua 中的短字符串做了 string interning 的处理,即在同一个虚拟机内,值相同的字符串只存在一份。这可以极大的提高用字符串做 key 的 hash 表的查询速度。因为字符串比较的时间复杂度从 O(n) 下降到 O(1) ,比较查询的 key 和 hash 表内的 key 是否一致,只需要对比一下对象的指针是否相同即可。

我在解决多 Lua 虚拟机共享字符串对象这个问题时,合并了不同的 Lua 虚拟机中的短字符串表。让同一进程所有虚拟机共享一个短字符串表( SSM )。

我最初在实现 SSM 的时候,考虑到多虚拟机 GC 的复杂性,采用了只增不减的方案。即让部分短字符串进入 SSM ,设置一个上限,避免 SSM 无线膨胀。但 Lua 并没有把经过 interning 处理的字符串作为独立类型,目前只用字符串长度作为区分,也就是无法和不 interning 的短字符串共存。所以,那些已存在本地虚拟机短字符串表中的字符串,就不从 SSM 中获取对象。

修改过 Lua 的 string interning 算法是这样的:

  1. 查看字符串是否存在于本地字符串表 (LSM) 如果存在,就立刻返回。这一步和原版 Lua 一致。

  2. 查看字符串是否存在于 SSM ,如果存在,就返回。

  3. 检查是否 SSM 上限已到,如果不能再增加新字符串,把字符串添加到 LSM ,返回。

  4. 将字符串添加到 SSM ,返回。

阅读全文 "并发 Hash Map 的实现" »

April 11, 2019

不同虚拟机间共享不变的 Table

这几年,我一直在寻找不同 Lua 虚拟机间共享大量不变的结构化数据的方法。因为这对于游戏这类数据驱动的软件是非常重要的需求。我们现在正在运营的游戏“风之大陆”,服务器上的策划生产出来的数据表格,转换为 Lua 源文件后,就已经达到了 300M 之巨,全部加载到 Lua 虚拟机中,会消耗 700M 内存。

我为这个需求实现过好几套方案:最初是 Sharedata 这个模块,后来又实现了一个叫 DataSheet 的替代品。

过去的方案用的思路都是把数据表放在 C 对象中 。Lua 中建立一个 proxy 对象去访问它。C 对象可以跨虚拟机共享,proxy 对象则在不同的虚拟机中各创建一份。

阅读全文 "不同虚拟机间共享不变的 Table" »

April 03, 2019

为 bgfx 设计了一个 IDL

上个月为 bgfx 贡献了一周多的工作时间,起因是 bgfx 的作者在我的 sproto 项目下发了个 issue (现在已经转到 bgfxidl 项目下)。他想为 bgfx 的接口设计一个 Interface Description Language ,这样可以避免手工维护多语言接口文件,还可以方便做许多代码生成的工作。

我在 2006 年左右尝试利用 COM 的 IDL 做过一些工作,想来这和 COM 面临的问题是一样的。我认为 lua 是一个可以用来做 DSL/IDL 非常好的工具,所以我向 bgfx 项目推荐了它。而且 bgfx 用的构建工具 Genie 就是基于 lua 的,这样工具链就比较统一。

阅读全文 "为 bgfx 设计了一个 IDL" »

March 19, 2019

数学运算模块的改进

我为我们正在研发的 3d 引擎设计了一个非常规的数学运算模块

它和很多为 Lua 封装的数学运算模块不同,并没有用 userdata 或 table 来实现矩阵向量对象,而是采用了 64bit 的整数 id 。其生命期管理是模拟了一个堆栈,我称之为数学栈,和程序运行时存放临时变量的堆栈以示区分。数学栈上存在过的矩阵向量对象的生命期都会维持一个固定周期,通常是一个渲染帧。每帧主动调用重置指令刷新。这个设计减少了在 lua 层面使用矩阵向量对象的心智负担。你不必担心运算产生的临时结果会增加过多 gc 的负担。构造新的矩阵向量对象的成本也非常的小。

阅读全文 "数学运算模块的改进" »

March 14, 2019

Lua 虚拟机间函数原型共享的改进

在我们的服务器框架 skynet 中,往往会在同一进程启动非常多的 lua 虚拟机,而大多数几乎运行着相同的代码(为不同的用户服务)。

因为 Lua 的代码也是数据,和 Erlang 这种天生设计成多服务的语言不通,Lua 并没有为多虚拟机同时运行做内存上的优化。所以,我在 5 年前给 Lua 制作了一个 patch ,可以把不同虚拟机间的函数原型数据提取出来共享一份,节省了不少内存。

不过,这个方案只能功能函数原型中的字节码以及调试信息,无法共享函数原型用到的常量表。这是因为,字符串常量是一个对象,尤其是短字符串,Lua 在虚拟机内部做了 interning 已加快字符串比较速度,使得它们很难在虚拟机间共享。

阅读全文 "Lua 虚拟机间函数原型共享的改进" »

February 24, 2019

跟踪 Component 的修改

在 ECS 框架中,每个 System 在每次更新时,都遍历一类 Component 依次处理。这对于游戏的大多数场景都适用,因为游戏引擎要处理的对象通常是易变的。对于每个对象单独判断是否应该处理反而有性能负担。

但是,总有一些应用场景下,只对一类 Component 中的一小部分做修改,而没有被修改的对象可以保持上次的数据,而不必重复运算。在需要重算的对象数量远小于总量时,每个更新就很不划算了。

为了减少运算量,我们通常的解决方案是增加一个脏标记,修改时设置,设置它。这样就可以在处理的时候只处理被标记过的对象。常规的脏标记实现方案有两种,一是在 Component 上加一个 bool 字段,遍历的时候跳过没有标记的对象;二是在 Entity 上动态添加一个用于 tag 的 Component ,视作脏标记,遍历后再清除这个 tag 。

不过这两种方案在 lua 实现的 ecs 框架中,使用代价都比较大。

阅读全文 "跟踪 Component 的修改" »

February 18, 2019

最近对 ECS 框架的一些想法

我们的游戏引擎采用 ECS 框架。最近一年的开发,为 ECS 框架的应用积累了不少经验。我在 blog 上也写过数篇 ECS 相关的东西:

Lua 下的 ECS 框架

ECS 中的 Entity

最近两个月,结合过去的经验,我们对最初设计的框架做了较大的调整。这主要是源于对框架要解决的事情的更深入的理解,以及在实践过程中针对典型场景总结出来的模式。

阅读全文 "最近对 ECS 框架的一些想法" »

Misc

Categories

Archives

Recent Comments