云风的 BLOG: 提高 lua 处理向量运算性能的一点尝试

如果用纯 lua 来做向量/矩阵运算在性能要求很高的场合通常是不可接受的。但即使封装成 C 库，传统的方法也比较重。若把每个 vector 都封装为 userdata ，有效载荷很低。一个 float vector 4 ，本身只有 16 字节，而 userdata 本身需要额外 40 字节来维护；4 阶 float 矩阵也不过 64 字节。更不用说在向量运算过程中大量产生的临时对象所带来的 gc 负担了。

采用 lightuserdata 在内存额外开销方面会好一点点，但是生命期管理又会成为及其烦心的事。不像 C 中可以使用栈作临时储存，C++ 中有 RAII 。且使用 api 的时候也会变得比较繁琐。

我一度觉得在 lua 层面提供向量运算的基础模块是不是粒度太细了。曾经也想过许多方法来改善这方面。这两天实践了一下想了有一段时间的方案，感觉能初步满意。

我的应用场合是 3d game engine ，engine 计划用 ecs 框架搭建，这为向量运算模块的优化提供了不错的基础。至少在对象生命期管理方面有了 system/component 的约束，做起来会简单许多。

游戏引擎中用到向量运算的场合主要是两类，一类是处理某项事务时用到的大量临时对象，通常是 3x3 矩阵，vector3 和 vector4 ；另一类是引擎中的对象需要用矩阵记录下其空间状态。我认为，无论是 vector 还是 matrix ，虽然它们的数据尺寸比系统的字宽大，但它们依然应被视为值类型，而不是引用类型。但是由于 vector/matrix 的值长度大于语言支持的原生类型，无法直接在值类型的原生变量中放在，所以一般我们还是要借用某种引用语义。就好比 string 在 lua 中是值语义的，但使用引用类型的方式实现出来的。

也就是说，在设计库的时候，即使支持 A *= B 这样的运算，因为 A 和 B 都是按引用的方式实现的，但也并不是将 A * B 的结果直接覆盖到旧有的 A 引用的值空间上。这和 A = “hello" ; A = A .. " world" 一样，新的字符串 hello world 并没有覆盖已有的 hello 这个字符串。

lua 中的基础数据类型中，属于值类型可以用来做这个封装的有三种：number(id) ，lightuserdata 和 string 。我曾经想过直接用 string 将 vector/matrix 的值用 string.pack 打包，但细想一下并不比 userdata 好多少。lightuserdata 若是直接储存数据在内存中的地址的话，和 C 的裸指针没什么差别，用起来实在是不太放心。所以可选的就只有数字 id 了。

5.3 版以前的 lua 可以保存 52bit 有效精度的数字，5.3 版以后则在大多数平台上有 64bit 精度可用。用作索引 id 号的话绰绰有余。加上 id 这个间接层，我们可以很容易的识别出哪些无效 id ，比用指针安全很多。

因为游戏通常是按帧处理业务的，每帧之间没有特别的联系，如果在帧内没有特别的把某个值记下来，那么通常就不会再使用它了。我想，用帧号（版本号）+ 顺序数字作为值对象的唯一 id ，即可以方便的索引到数据块（使用一大块连续内存数组即可），又能快速排除已经销毁的对象。构造新对象也是 O(1) 的操作，还可以用 O(1) 时间批量作废当前帧用到的所有临时对象。

即，任何向量运算操作，都产生新的值对象，一旦产生，就不再修改其值。每个对象用一个唯一数字 id 来表示。除非特别注明，一个值需要长期保留，这些对象的生存时间都不会长于一帧。每帧结束后，通过递增版本号的方式来让旧的临时 id 失效。

在运算操作方面，每个针对向量的一元或二元操作都增加一次 lua 到 C 的函数调用有时也显得重了。比如两个 vector4 相加，运算量不过是四次加法，而 lua 到 C 的函数调用则远大于此。我觉得借鉴 forth 的设计比较好。单独再设计一个数据栈，操作全部基于数据栈进行；如果设计复杂的操作流程，还可以增加指令栈（暂时还没用到，所以没有实现）。也就是把向量操作的相关操作都基于一个独立于 lua 语言本身的栈上去完成。比如两个矩阵相乘再去逆，可以写成 :

command ( mat1, mat2, "*~") 用来表示 ~ (mat1 * mat2)

也就是先把 mat1 和 mat2 两个 id 压栈， * 会弹出栈顶的两个对象做矩阵乘法，把结果压回。而随后的 ~ 取逆矩阵的操作则将栈顶的对象弹出，做逆矩阵运算，结果再放回去。

这样，一个 command 函数，通过若干参数，就可以完成一系列的运算操作。且连续的运算是通过一个字符串常量传递给 C 模块的，大大的减少了 lua 和 C 的交互次数。这些操作都是基于数据栈的，加上这个数据栈和 lua 本身的交互指令就完备了。

我暂时设计了一系列和数据栈操作有关的指令：

P 把栈顶元素弹出，并将 id 返回到 lua 中。
V 把栈顶元素弹出，并将数据内存地址以 lightuserdata 的形式返回到 lua 中。用来传递到其它（比如渲染）模块，指针保证在当前帧有效。
T 把栈顶元素弹出，并将数据构造为一个 lua table ，方便调试、持久化等。
R 把栈顶元素移除 (不返回到 lua )。
D 复制栈顶元素。
M 把栈顶元素弹出，用其值构造一份新的持久化的值，并把新的持久化对象的 id 返回到 lua 。

操作这个运算模块只有一个函数，通过一些列不同的输入来完成操作。如果参数为 table 则把 table 的内容作为 vector 或 matrix 的值来构造出新的对象压入堆栈。

如果参数为数字，则当作过去构造出来的对象 id 压栈。其中，一个特别的设计是，如果这个 id 对应的是一个持久值（即不会在当前帧结束后失效），在这个 id 重新压会数据栈后，又会变成一个临时对象。这样，你可以放心的写

local a = command (a,b,"*M") -- 即 a = a * b 这个语义。

旧有的 a 即使是一个 M 值，也会被标记为失效。如果这里的 b 是一个持久化的常量，不希望临时回收，则可以采用另一个设定：

local  a = command (a,-b,"*M") -- 当 id 为负的时候，可以返回压栈而不改变其持久化特性。

我昨天在实现的时候做了两个版本，前一个版本把持久化标记加在内部堆的 slot 上，但这样会导致堆空间不连续，每帧重利用的时候，要么加大了回收的负担，要么增加了新构造对象的负担。好处是做持久化标记代价很小。

后来我又实现了一版，把临时对象和持久化对象分开空间储存；临时对象用最简单的栈式连续内存分配，每帧结束复位一下栈顶指针即可。持久对象则用 freelist 管理。所有对象从外部入栈时都一定先放在临时区，用 M 指令转换到持久区，做一次值拷贝。而消除持久化，删除它只需要简单加到 wish freelist 里（按前文所述的规则），待帧结束后合并 freelist 和 wish freelist 两个链表即可，不必再做拷贝。

这块代码将来会随我们的游戏引擎开源并维护。暂时我把昨天一些初步的实现贴在了 gist 上，供参考。注：gist 上这个版本不会维护。

后续改进见：https://blog.codingnow.com/2018/02/linalg_improvement.html