0
0

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

云风 发表于 2018年02月08日 11:42 | Hits: 1018
Tag: 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

原文链接: https://blog.codingnow.com/2018/01/lua_linalg.html

0     0

评价列表(0)