云风的 BLOG

以前我在 blog 写过 Lua 5.1 的 gc 代码分析 ，而 Lua 5.2 对这部分代码改动颇多，暂时也没有精力更新这个系列，先挑重点写吧。

Lua 5.2 的 GC 的最大改进是增加了一种叫 generational 的模式，Lua 的官方文档里是这样解释的。

As an experimental feature in Lua 5.2, you can change the collector's operation mode from incremental to generational. A generational collector assumes that most objects die young, and therefore it traverses only young (recently created) objects. This behavior can reduce the time used by the collector, but also increases memory usage (as old dead objects may accumulate). To mitigate this second problem, from time to time the generational collector performs a full collection. Remember that this is an experimental feature; you are welcome to try it, but check your gains.

看起来 Lua 作者并不自信这个模式一定比之前的 incremental 模式更好，所以一再强调它是试验性质的。在邮件列表，几次表示这个特性有可能在以后的 Lua 版本中移除。主要原因是它增加了 gc 模块的实现复杂度，却很难得到确实证据在实际项目中更有效。

我阅读了 lua 5.2.2 的相关代码，generational 大概是这样实现的。

在 generational 模式下，

清除阶段不再把处理过的黑色对象（不可清除对象）设置回白色（待扫描对象），而是给这个对象增加一个 OLDBIT 标记。由于 Lua 分配新的 GCObject 都是从一头加入对象列表的，所以在清除阶段一旦碰到有 OLDBIT 标记就可以不再遍历这个链表。

清除阶段大致可以只处理上次 gc 到目前新增加的对象，这样就达到了分代的目的。可以极大缩短每次 gc 清理的成本。（过去，比如至少把 VM 中所有对象都遍历一次，把其中的黑色对象变成白色，把白色对象释放）

由于清除阶段不再改变黑色标记，那么在新的一轮扫描的时候，也可以大大减少扫描的对象的数目。这是因为没有被碰过的老对象都是黑色的，而黑色的对象不再遍历。扫描过程只需要处理灰色对象，以及灰色对象引用的新对象（白色）就可以了。这意味着，在两次 gc 间没有被访问过的历史对象都不需要遍历。

generational 模式下，依然会定期触发完整的收集流程，它会比 incremental 模式下单步停留的久，是一个 stop-world 的操作，把所有对象都标记清除一遍。

但是，如果持久内存使用比较稳定，大部分临时对象都是短暂使用的话，触发完整收集的频率是很低的。 而且大部分临时对象都被快速清理过了，所以整体负担要小一些。

我个人认为 generational 模式比较适合在 Lua 程序中大量使用临时 table 或临时 closure 当参数传递的情况。Lua 没有把对象放在 stack 上的概念，所有临时对象都依赖 gc 一个个的回收。在老的 gc 算法下，只要对象增长速度过快，就一定会定期触发 gc ，而每个 gc 循环必须至少访问每个 vm 中的对象两次（一次标记，一次清除或重置标记）。这使得老的 gc 算法的效率严重依赖 vm 中的对象数量。在我们一些对 gc 时间敏感的应用中，都尽量少构造临时对象。这样虽然性能可以提高，却使得代码比较难看。

generational 模式就不太在乎临时对象的构建数量了，只要你不把它挂在老对象上，只在调用过程中临时当参数传递的话，那么 gc 就很廉价。大部分 gc 流程只需要扫描很少的对象，通常是那些从上次 gc 到当前被修改过的而被置灰的对象，以及新创建出来的对象。如果你的程序生成了大量临时对象，用完即弃，就意味着仅仅定期扫描 stack 就可以了。

如果游戏有明显的允许停顿的时刻，比如游戏切换场景，那么在这个时机强制做一次 fullgc 配合 generational 效果会更好。如果是以前的 incremental 模式，定期去做 fullgc 则没有那么明显的帮助。

ps. 在 lua 5.1 以前，用了一个叫 SFIXEDBIT 的标记位专门保护主线程。Lua 5.2 中估计是觉得用一个专门的标记来做这个事情有点多余，所以取消了 SFIXEDBIT 标记，而 OLDBIT 取代了它的位置。相应的改动是不再把 mainthread 和其它对象串在一起，而是在 GCSsweep 流程中对 mainthread 单独处理。

Posted by 云风 at 03:11 PM | Permalink | Comments (7)

C 语言缺乏原生的 string 类型的支持，这使得字符串管理非常烦琐。我在 2006 年左右的一个项目中，我根据项目实际情况，简化了 C string 库，把大部分 string 都做了 string interning ，并直到进程退出再释放 string interning pool 。

但这种用法毕竟不够通用。

今天读到 facebook 开源的 libPhenom ，里面也实现了一个简单的 string 库。我有些想法。

libphenom 的 string 库核心想针对问题是尽量的减少堆上内存的动态分配。它把大部分临时字符串都放在栈上处理，也提供了用户自定义串空间的方法。我觉得这个方向是不错的，但是其实大可不必提供太多的弹性，只要尽量让临时字符串存在于栈上即可。而另一个很重要的功能，也就是 string interning 我认为更有实用性。

string interning 可以实现 symbol 类型，对于类似 json/xml 的解析来说非常有意义。可以节约许多内存，而且可以加快 symbol 的比较和 hash 速度。不过对所有字符串无差别的做 interning 有可能因为外部输入多变也被攻击。对 interning 的字符串做引用计数也会降低性能。

我的想法是，只对短字符串做 interning ，这和 Lua 5.2.2 的策略一致。但是我们可以不再回收 interning pool ，所有短字符串都一直保留在内存中。大部分情况下，这样处理风险不大。

临时字符串一律放在栈上，这可以减少动态内存分配。除非字符串太长，有可能栈溢出才放在堆里去。

如果用户需要长期持有字符串，或是需要把当前栈上的字符串返回，那么再转移到堆上也不晚。堆上的字符串可以使用引用计数来管理，这样对于长字符串的传递，就可以省去逐字节拷贝的代价，又可以及时的回收。

有了这些特性，在此基础上实现 hashmap 等数据结构性能就会比较高。

为了简化生命期管理，如果一个字符串被引用次数太多，也可以把它变成一个永久字符串。一般来说，动态字符串是很难被数万次的引用的。

常量字符串也很重要，尤其是常量字符串比较短时更加重要。这样，经过 interning 的常量字符串和其它变量进行比较时，开销比较小。C 语言的模块没有默认初始化流程，所以只能用 static 变量加惰性初始化来模拟。

我今天花了几个小时实现了这么个玩具，主要是验证一下 string 库的 API 设计构想。目前开源在 github 上了 ，有兴趣的同学可以看一眼。但注意：这只是一个玩具库，我没有用在任何已有的项目上。库里面写了不少线程安全有关的代码，也完全没有被验证过。

好在库篇幅很小，如果有哪些好心的同学想完善它，尽管提交 pull request 。我会一起 review 代码的。 :)

Posted by 云风 at 07:50 PM | Permalink | Comments (17)

简悦科技 现为正在研发中的 MMORPG 斗罗大陆 online 招聘特效制作人员一名。

1. 需要有 3D 游戏特效丰富的工作经验。

2. 需要有较强的沟通能力。

3. 是 3D 游戏玩家。

4. 若熟悉 Unity3D 游戏引擎更佳。

斗罗大陆 online 是一款类似魔兽世界类型的 MMORPG ，计划在明年底上市，目前开发资金和人员齐备，开发进度良好。

工作地点在广州天河区，公司雇有厨师，有自己的食堂安排所有人的中餐和晚餐。早上十点上班，一天八小时工作，周末节假日正常放假。

有兴趣的同学，或有朋友可以推荐的同学可以和我 email 联系 ，或者直接和我们公司的同事 联系。

Posted by 云风 at 04:07 PM | Permalink | Comments (9)

有同学向我反应，自从 skynet 的 IO 库重写后，Mac OSX 上便无法启动了。

我检查了一下，直接原因是 kqueue 部分写的不对。kqueue 和 epoll 的 api 设计还是有些区别的，epoll 的 api 可以合并读写消息，但 kqueue 读是读，写是写。当时随手写好后一直没有在真实环境下测试，所以一直是有问题的，只是这次另外一个问题将它暴露了。

我新写的 IO 库是异步操作的。异步处理针对任何 IO 请求，其中也包括了建立连接以及监听连接。skynet 启动的时候需要启动一个 master 服务，然后再各个分布节点上启动 harbor 服务通过 master 互联。这些连接是通过 IO 模块的 socket connect 建立的。

我希望在 skynet 启动完成前把这些连接（至少是主节点的）都正确建立起来。

按计划，我希望在未来的版本中弱化 skynet 的分布式特性，逐渐把分布式功能提到核心层以外来实现。所以这次重写 IO 模块只是简单的按功能重新实现了 master/harbor 模块，并没有深究如何实现的更好。

连接是异步的就意味着很难准确的将连接建立完成后再进行后续的操作。我用了一个变通但不完善的方案：先注册了消息回调函数只监听连接成功建立的消息。等连接建立成功后，再换成完整的回调函数。这里存在一个明显的问题，当 skynet 节点内部有远程消息需要发出，这个需求先于分布式模块初始化前（master/harbor 连接建立前）的情况下，远程消息便无法发出。

一开始我考虑的是，如果分布式模块未初始化后，该节点就无法获取外界任何消息，也不可能有远程消息的需求，所以我在处理连接的回调函数里加了一处 assert 了事。没想到考虑是不周全的，在 kqueue 模块错误实现的情况下，连接无法建立，问题也就暴露了。

对于这个将来想重新设计的部分，我不想增加太多的代码，比如增加一个消息缓存队列将提前收到的消息先记下来。那么不考虑时序的话，可以在收到不想处理的消息的时候利用 skynet 内置的 forward 功能把消息 forward 回自己。可以简单的记录一下第一个被 forward 的消息，如果再次见到它的时候就 sleep 一下，等待连接建立成功。

后一个方案我花时间考虑过。但这样做会导致消息时序不正确，总感觉不舒服，最后还是决定增加一个阻塞 connect 接口比较简单。

修改过后程序依然有问题，是因为 listen 也是异步操作的。当然 listen 本身无所谓非阻塞操作，只是因为当初设计 IO 模块的时候希望统一。我需要把所有 socket 都从文件 handle 映射成一个内部数据结构，用异步方法把所有操作都发送到一个线程里处理可以简化并行引起的线程安全问题。但如果异步操作 listen 请求的话，由于 skynet 的 bootstrap 阶段并没有启动工作线程，会导致 IO 请求永远不会被处理到，这样，连接当前进程内开启的 master 服务就会失败。

解决这个问题的方案是在发起 listen 请求时，直接调用系统 api 把 socket 建立好，再将 fd 发送到 socket 线程去和自定义数据结构绑定起来，以及做后续的向 epoll/kqueue 添加消息的处理就可以了。

等这个月忙完，我想认真考虑一下我们的项目里如何更好的处理分布式游戏服务器的问题了。我觉得想让 skynet 底层完全将进程内服务和通过 socket 连接在一起的外部服务的区别透明化是不现实的。现实项目一定不可能随意的把工作模块分布在不同的机器上。毕竟在进程内的消息传递以及信息共享的效率和可靠性都是远高于跨机节点的。

Posted by 云风 at 10:42 AM | Permalink | Comments (6)

我们代理的游戏狂刃 客户端用 NSIS 制作成一个 exe 安装包，有 1G 左右。一开始，我们是购买又拍和七牛这种的云服务分发客户端。从用户的下载速度来看可以满意，但费用有点高。所以我们打算另外开发一个采用 BT 协议的下载器，这也是 MMO 客户端分发给客户的标配了。

rainfiel 同学在一个多月前主动领了这个任务，对 BT 的开源库考察一番后使用 libtorrent 开发这个下载器。

最近在测试的时候发现了一个问题，成功下载完安装包后，如果系统安装有 卡巴斯基 或 360 等杀毒软件，就会在调用 ShellExecute 第一次运行安装包时被卡住很久（长达几分钟）。用进程管理器查看，发现是杀毒软件一直在扫描刚下载的 exe 文件。

一开始怀疑是由于某些 bug 导致文件被锁死了。然后试图退出下载程序，重新启动新进程去打开安装包，这样不解决问题。但是，如果把下载文件用程序复制一遍再运行文件的拷贝却不会被卡住。

有网友说可能是 Windows 的 Alternative Data Streams 引起的。我们 google 了一下，找到了这样一篇文章 。文中提到去掉 ADS 的方法也是复制一遍文件，但是通过工具检测却没有发现 ADS 的痕迹。

最后检查 libtorrent 的配置参数才发现，原来是因为它默认把下载文件创建成了 Sparse file 。根据 wikipedia 的说法，Loading executables on Windows (exe or dll) which are sparse takes a much longer time, since the file cannot be memory mapped and not cached. 。这应该是根本原因了。

只是几分钟的扫描时间也过长了点，为什么杀毒软件需要几分钟时间才能加载分析完一个 1G 左右的 exe (远超过复制一遍文件的时间），我猜测是因为 NSIS 其实只是把一组文件打了个包，而杀毒软件期望解包分析包内的文件导致的。杀毒软件若实现的不恰当，解包过程针对 sparse file 随机读性能很低，导致了扫描时间远大于复制一遍文件再扫描的时间。

Posted by 云风 at 02:07 PM | Permalink | Comments (8)

我们的游戏中需要对渲染字体做勾边处理，有种简单的方法是将字体多画几遍，向各个方向偏移一两个像素用黑色各画一遍，然后再用需要的颜色画一遍覆盖上去。这个方法的缺点是一个字就要画多次，影响渲染效率。

前几年有人发明了另一种方法，google 一下 Signed Distance Field Font Rendering 就可以找到大量的资料。大体原理是把字体数据预处理一遍，把每个像素离笔画的距离用灰度的形式记录在贴图上，然后写一个专门的 shader 来渲染字体。好处是字体可以缩放而不产生锯齿，也比较容易缺点边界做勾边处理。缺点是字模数据需要离线预处理。

我们的手游项目以及 3d 端游项目都大量使用了勾边字体，我希望直接利用系统字体而不用离线预处理字体把字体文件打包到客户端中。前段时间还专门实现了一个动态字体的贴图管理模块 。btw, 苹果的平台提供了高层 API 可以直接生成带勾边效果的字模。

但是，勾过边的字模信息中同时包含了轮廓信息和字模主体信息，看起来似乎很难用单通道记录整个字模数据了。这给染色也带来了麻烦。

见这张图，是一张带勾边信息的字模。轮廓是黑色的，字体是白色的。从颜色通道上看，有黑白灰的过渡。但灰色部分 alpha 通道对应量却不相等。轮廓向字体主干过渡的地方，色彩是灰色的，但是 alpha 值为 1.0 。也就是说，alpha 通道是独立的。

我们需要两个通道，颜色通道和 alpha 通道，来保存完整的字模信息才能在最后正确的渲染到屏幕上。很多显卡硬件并不支持两通道贴图，所以要么我们用一个 RGBA 四通道贴图来保存，要么用两张单通道贴图。

我想了个简单的方法只用一个通道就可以保存全部信息，那就是把 alpha 为 1.0 的像素的灰度影射到 0.5 到 1 的区间；把 alpha < 1.0 的部分像素的 alpha 值影射到 0 到 0.5 的区间。这样做可行是因为，经过勾黑边的白字，其 alpha 小于 1.0 的像素一定都是黑色的，也就是 RGBA 都相等。所以信息只损失了一个 bit 就保存了下来。

经过处理后的贴图是这样的。可以看到过渡是均匀的，所以并不会影响纹理采样。最终我们写一个简单的 shader 就可以对字体做染色了。最终效果是这样的：

Shader 也非常简单，只需要取出单通道贴图上的灰度值 G ，

Alpha := clamp(G * 2.0 , 0, 1.0)

Color := clamp((G-0.5) * 2.0, 0, 1.0)

就可以还原出原来的颜色通道和 alpha 通道的信息。

Posted by 云风 at 12:44 PM | Permalink | Comments (7)