« February 2009 | Main | April 2009 »

March 29, 2009

这两周做了好多事情

今天写周报时,还是老样子,记记流水帐。努力的回想本周做了些什么工作,写着写着就发现居然干了如此多的活。许多事情仿佛都是很遥远的日子前做的了,但是却又明明白白可以打上星期几的标签。

这两周居然阅读和修改了超过万行的代码,原创的代码好几千。琐碎的事情也干了许多,白天大多数时间用来处理行政上的事情以及坐在同事身边陪着人写代码(不算 XP)。晚上就写自己的。周末的连续时间更长,也写了更多的东西。

觉得自己新领悟了许多道理,虽然以前似乎就懂。

还是应了那句老话,实践出真知。

这两周,除了睡觉就是在干活。没有把吃饭除掉,因为吃饭的时间几乎可以忽略了,且午饭还是边吃边做事的。

上厕所的时候没有什么新书好看,就是抱着本老书:《UNIX 编程艺术》,随便翻到那些熟的不能再熟的章节重读几句。总能发现警言妙句。

别的许多本该做的事情也没太尽心,算一遗憾吧。本来想拉一牛人入伙,可惜赶上我这正忙的当口,挖角不够努力。罢了,都是缘分。


周末静下心了仔细研究了下 freetype ,然后整合到了 engine 中。并实现了一个自以为很不错的 cache 模块(由于某些可以接受的理由,没有使用 freetype 自带的 cache)。以前这块都是用的 windows 原生 api ,后来要跨平台,又做了点阵字库的支持。最近在同事的强烈要求下,还是把 freetype 整合了。

一开始对长篇大论的文档稍感恐惧,花了周五一个晚上仔细阅读了一遍,发现也没啥。甚至感觉其接口设计的比 Windows 相关部分强多了。昨天今天两天三下五除二的搞定。同时终于理解了,为啥使用 freetype 渲染引擎的许多 linux 软件(比如 opera )默认显示中文网页那么难看。其实不是 freetype 的错,还是得有中国人专心做这事才能弄的漂亮。

其实每家都有本难念的经,英文排版渲染也有其特殊需要注意之处,比如 Kerning 的问题,在中文世界就是不存在的。老外们的精力都去折腾那些去了,却没有相当数量的华人折腾方块字,尤其是中英文混排的诸多问题。


本周因为有朋友来访,我还是开了几局桌面游戏的。有道 的 zhoufeng 同学从美国给我带回来 银河竞逐 的第一扩展包终于有机会玩。感觉乐趣又增加了许多。不过让人郁闷的是,这才费尽周折入手,taobao 上就见着有卖的了;而第二扩展包居然开始预售。


因为忙,把每周四小时的健身房时间从日程表中去掉了。但维持了每周两小时的办公室抱石练习。力量下降了一些,但是技术貌似有点进步。感觉好了一点,希望不是错觉。

不过周二还是不小心把左手中指扭伤了,当天晚上几乎不能敲键盘,还好已经恢复的差不多了。


这个月居然是历史上 blog 产量最大的几个月之一,看来越忙越能瞎扯。:D

March 28, 2009

安全的迭代一个集合

把同质的东西放入一个容器,然后用迭代器迭代这个容器,把里面的内容逐个取出来处理。这是一个非常常见的需求。但是,这个过程往往也会滋生 bug 。因为,若将容器看成一个对象,那么对其迭代的这个操作很难实现原子性。

非原子性导致了,在迭代过程中,十分有可能对容器本身进行修改。或增加若干元素,或删除若干元素。这些都容易造成迭代过程不正常。

所以,最终我们需要根据需求设计以及实现合理的容器。比如管理消息的消息队列,严格的满足尾进头出,没有删除中间数据的需求,就不会导致 bug 。

那么,如果容器是一个集合怎么办?即,允许向其中增加新的元素,也可以移除某些元素。这种数据结构非常有用。比如向某对象注册若干回调函数,一旦满足条件则依次调用。即设计模式中的 Observer 观察者模式。回调函数就极有可能增加新的观察者或某些老的观察者退出。

简洁的解决方案是,使用一个可变长数组维持这个集合,把数组看成一个队列,永远在一端添加。而删除中间节点,仅仅只是做一个记号(标记成不必再处理的观察者)。

在集合中额外保存一个迭代状态堆栈。每次需要迭代时,从堆栈顶分配一个状态容器出来,负责迭代(里面保存迭代到的位置)。

当迭代尚未完成前,一旦回调函数触发对同一集合的新的迭代请求,状态堆栈会返回一个新的状态容器,保证和前次迭代互不干扰。

迭代完成后,如果当前状态堆栈为空,表示外层再无迭代事务。这个时候,可以一次扫描整个集合,把做过删除标记的节点删除,并压缩整个集合(去掉空巢)。

用 lua 实现以后功能非常简单:代码大约是这样的

这段代码实现了一个集合,提供了一个安全的迭代器迭代它。使用 enter 把对象置入集合。enter 会返回一个 closure 用于把对象从集合中移除。

当然,用 C 或 C++ 实现一个也不复杂,就不列代码了。

March 25, 2009

libstdc++ 卸载问题

今天,同事花了一下午时间,终于查到了 周末我碰到的问题 的根本原因。

是因为,GLU 是用 C++ 实现的,而导致 libstdc++.so 会跟随它卸载,而 libstdc++.so 本身有一个 bug ,导致程序崩溃。

当然,显露这个 bug 还有一个前提,我的程序是纯 C 写的,完全没有用到 libstdc++ 。

有兴趣的同学可以查看这个帖子:http://unix.derkeiler.com/pdf/Mailing-Lists/FreeBSD/stable/2006-05/msg00719.pdf

大约是说,crtbeginS.o (C 的运行时库)里有个叫 __deregister_frame_info 的弱符号在 libstdc++.so 加载的时候被重定位到这个 so 的代码段里了,并且在程序退出的时候会运行到。

但是程序退出前,libstdc++.so 已经被卸载,这就会导致进程运行到不存在的地址空间。

以上问题存在于 libstdc++.so.5 ,我在 libstdc++.so.6 下测试貌似没有问题了。

关于地表贴图

首先,我不是混 3d 圈的人,所以我对圈子里各种地表的渲染方法并不熟悉。今天写这一篇,纯粹是因为前段时间帮负责 3d 模块开发的同事解决了一个算法问题。

从我有限的 3d engine 相关知识来看,我最早了解的是类似 2d tile 拼接的地面渲染方式。玩过星际的地图编辑器的就知道我指的什么。等到魔兽三,虽然 engine 改成 3d 的了,但是方法没有大的变化。就是用贴图做成图素去拼接起来。依稀记得无冬之夜也是这种方法,时间太久,不敢确认。

后来,我看了 big world 的方案,就是在地面高度网格的顶点上记录一个贴图混合系数。最多在一个 chunk (记得似乎是 25 格)里最多可以用四张不同的贴图,然后根据地面网格的顶点混合系数,混出最终的效果。

这个方法比较节省资源,听说很多 3d engine 对地面的渲染都这么干。

不过 big world 默认的地面网格,每个格子单位长为 4 米。结果地面的过度就显得非常粗糙了。这点,天下2 的场景美术私下跟我抱怨过。说是不能做出 wow 里的效果。到了创世西游,应美术的强烈要求,单位格被改成了 2 米,很大程度是为了让地表渲染的更漂亮。当然数据量也增加了 4 倍。

如果想近一步增加地表贴图的精细度该怎么办?简单的增加地表格的精度是不合适的。其实高度图不需要太高的精度就可以做的很漂亮。增加的数据量却是很惊人的。

我们的 3d 程序员提出一个方法。其实,贴图的精度可以高于网格的精度。

当然,在渲染时,就不能按以前的方式。我们可以把混合信息保存在独立贴图里,而不是存放在顶点上。

例如,如果一个 chunk 有 32x32 格,如果你用一张 32x32 的贴图,4444 有 4 个通道即可,可以描述出 5 张贴图的混合信息(由于混合系数之和为 1 ,所有第 5 层可以通过前四层计算出来)。效果和保存在顶点上一致,但会多消耗一张贴图。

假设我们采用 64x64 的贴图,贴图混合精度就增加了 4 倍,最高支持到 256x256 甚至 1024 都可以。不过太高的精度混合贴图本身也有很大消耗,可能还不如直接把整张混合结果保存下来。

理论上,我们可以让美术制作的时候,仅在最被玩家关注的地方使用高精度混合贴图,不太关注,尤其是远景,使用 2x2 甚至 1x1 贴图即可。

但是,制作期,编辑工具如何决定该生成怎样精度的混合信息?

这里面有一个 chunk 间接缝的问题。如果一个 chunk 的混合精度较高,衔接的一个 chunk 比较低,缝隙就有可能被看出来。

另外,程序上虽然可以生成不同级别的混合信息,但到底实际该用哪一份也是一个问题。尤其在编辑器中,美术会自由修改。且不应该让美术关系精度问题。


早期我们的编辑器在这个方面做的不太好。前几天,我花了点时间思考这个问题,发现了一个简单可行的方案。

首先,在原来的编辑器中,太多的精度级别是没有意义的。这跟地图刷的定义有关。地图刷虽然有大有小,但无论大小,都是一个中心向四周过度的图案。而且在编辑器中,混合信息是按浮点数保存。

其结果是,如果期望完全无缝,那么最终的混合精度只会留下两类:一是所支持的最高精度。另外就是最低精度(就是纯色)。

那么,如何利用程序支持的多级精度?我的方法是,提供不同粒度(而非大小)的刷子供美术选择。不需要精雕细凿的部分推荐给美术稍微粗粒度的刷子(看起来有更多的马赛克)。

而混合数据,可以以自适应的四叉树方式保存。且直接保存成 4444 的通道形式,而不用浮点数。虽然浮点数有更高精度,但实际渲染结果是用 16 级方式呈现出来。美术是根据视觉反馈来修改场景的。更高的级数没有意义。

这样,四叉树可以用来合并相临的相等混合信息。最终可以根据四叉树的最大深度决定贴图的精度。


btw, 在写四叉树的代码时,发现四叉树的数据序列化非常有趣,可以只用很少的额外信息记录四叉树的形态。(简单的在数据流里插入 bit 表示当前分枝是否需要扩展)

如果用四叉树去表示一个 2 的整数次幂宽度的矩形,也有一个巧妙的方法定位四叉树的叶子。你可以简单的合并需要索引的 x,y 的每个 2 进制位。比如 x 和 y 都是 [0,255] ,表达一个 256 单位长的空间。x 和 y 都是 8bit 。

把 x 和 y 的第 7 bit 合并成一个 2bit 数字,第 6 bit 也合并,依此类推,得到一个 8 个元素的数列。按这个数列去逐级访问四叉树每级上的对应 0~3 象限即可。

这个技巧同样可以用于 8 叉树,由于不需要做任何判断,所以可以提高性能。 :D


这段时间太忙,所以 blog 就只是简单记录下思路了。

March 23, 2009

编程的首要原则

刘未鹏的 blog 上写了一篇 编程的首要原则(s)是什么? ,这段时间在我的 google reader 上被许多人分享。

我问自己,我目前的首要原则是什么?

其实想说的,那篇里都有人说了。如果非要说首要,我也认可最多人认可的:

KISS - Keep It Simple Stupid

不过对 DRY - Don’t Repeat Yourself 我反而认为是次要的,当然是在和 KISS 相冲突的时候。

如果换一句和 KISS 原则相当分量的话,我会说:不要用愚蠢的方法做事。很矛盾?Repeat Yourself 往往代表了一些愚蠢的方案,且并不 simple ,至少会付出更多的体力。我想,KISS 的最后一个 S 指的是大智若愚的愚,而自做聪明则是另一种愚蠢。

在 KISS 的大原则下,我想其实可以分出一些细节的东西,也是别人都提过的:

最近两年我对同事说的最多的几句话,“弄清你的问题是什么”,“你不一定需要解决这个问题” 。

因为什么都不做才是最简单的。要知道什么可以不做,必须了解你的问题。

面向对象以及复杂软件技术的滥用,或是找不到更 Simple 的方案解决问题(以性能、以需求等为借口去实现更复杂的方案)往往都是对需求了解不清,或者眼光太短。把手段当成了目的。(以为达到目的,必须采用某种手段,而如何应用这种手段就变成了目的)

同时,我觉得过度抽象也来源于对问题的认识不清。我还没想好后面要写什么,实现些什么,所以先利用“抽象” 把其它的部分搭起来。久而久之,不分析具体问题,先做抽象就变成了惯性。而抽象层本身往往是软件中最复杂的部分,离 KISS 原则最远的一块。

March 22, 2009

Freebsd 下 glx 的一点问题

最近特别忙,经常连续工作超过 10 小时。所以情绪也有点不稳定,有的应该在半小时处理完的问题,会拖上几个小时。比如昨天就碰到一个。

由于底层代码由我一个人做了大规模重构(在不改变中间层的基础上做的),大约修改了一万多行代码,上百个 C 文件,其中重写了数千行。这样的变动实在太大,以至于出了罕见的问题后,很让人头痛。新的代码在 Windows 和 Ubuntu 上都一切正常,惟独在 Freebsd 上,程序退出的时候会引起一个 core dump 。

我对 gdb 调试器的高阶运用显然经验不足,加上这几年写代码也不怎么调试。(IMHO ,与其增加调试能力,不如提高设计能力和编写高质量代码的能力;让 bug 不容易出现,或是把 bug 限制在很小的范围,比解决 bug 更重要)在尝试过初步的调试后,我还是使用大脑做静态分析。确定问题出在 so 文件的显式关闭 (主动调用 dlclose)的环节。

根据常规推断,如果在 dlclose 后,程序异常,最可能是其它模块引用了其中的代码段,或静态数据段。实际现象中,进程崩溃在 C 的 main 函数返回之后。而我的系统整个是用 C 构建的,不会有 C++ 里那么多的跟这些有关的相关问题。所以可以推断是进程隐式加载的 so 最后卸载时发生的问题。

这个合乎逻辑的推理最终也基本得到证实,看起来很简单。不知道昨天我怎么就吃错药了,足足浪费了 4 小时来得到结论。

实际调试过程是这样的。我用二分法去掉某些代码,想看看把测试程序缩减到什么程度,问题会消失。这显然是个不肯动脑子的傻方案。鉴于精神不佳,姑且原谅一下。凡是愚蠢的方法,在有效的同时,一定是件体力活。干的时间久点就可以理解了。最终我发现,在 X Window 创建之后,为了隐藏鼠标光标,我调用了一个 X 的 API :XCreateBitmapFromData 。如果不调这个 API ,系统结束后就没有问题。但这个 API 本身调用是成功的。

在没有经过大脑的状态下,我拼命的往这个小洞里钻。又是怀疑 API 传入的参数,又是怀疑 XLib 的工作方式。接着,我又发现了另外几个 X 调用会引起问题。全部的现象都是,调用时成功,程序结束时崩溃。当然具体情况也分两类,一类是毫无朕兆,另一类是,调整一些次序,会提前得到 X Server 发过来的错误。这后一类近一步的加深了我的错觉。


最终,我发现,即使不改变代码,修改最终编译的链接参数也会引起问题。

如果程序只链接 GL 库,就一切正常。但是多链接一个 GLU 或是别的跟 openGL 有关的库,例如 GLEW ,就会在程序退出的时候崩溃。即使,我缩减后的测试代码里没有用到任何 GLU 或 GLEW 里的函数也一样。

当然,测试代码里使用了 glx 的一个 API ,必须链接 GL 库。

暂时还不能确定引起进程崩溃的 bug 直接的罪魁祸首在哪个位置。还是多休息一下,精力充沛时再回头来看比较好。好在 freeBSD 上有全部相关源码,我的桌面也是 buildworld 出来的,等周一再仔细看看吧。


虽然程序世界里,因果关系往往都非常明显,远没有现实世界那么复杂。但偶而也会遇到一些棘手的问题。当然是否棘手取决于你对系统的犄角旮旯的了解程度。或许你难以理解的问题,换个具有相关知识的人就变的一览无遗。就好象 Windows 上的木马病毒泛滥,许多用户在中招后毫无察觉;但 Windows Geek 们不装所谓杀毒软件,一有异向就会立刻察觉到。

链接,其实是个很复杂的过程。有经验的程序员一不小心也会中招。我曾经帮同事查过一个跟 lua 有关的问题,最终就是因为错误的链接导致进程内同时存在了两份 lua core 的代码。导致某些静态变量有了两份。这种问题往往会被隐藏很久,最终会以奇怪的形式暴露出来,而超出一般程序员的调试能力。

btw, 我认为,这次遇到的问题以前就存在,只是这次重构暴露出来而已。因为早先的代码,我自己完成了链接和二进制模块加载的过程。这次我想简化这个环节,更依赖系统提供的相关机制。


3 月 25 日补充:

问题的根本原因见:libstdc++ 卸载问题

March 17, 2009

让 GNU Make 把中间文件放到独立目录

今天想把项目用的 Makefile 整理一下,主要是让 .o .a 等等这些中间文件生成到独立目录中去。做这项工作的过程中,发现了一些有趣的问题。

当然最头痛的要属路径名的斜杠转换问题,这里暂时不提。为了描述方便,暂且不考虑 windows 平台。

一开始我想到的方法是:把 .o 这些目标指定到一个独立目录下,比如写依赖关系:

$(ODIR)/%.o : %.c

然后让 gcc 直接编译到 $(ODIR) 下。

接着我发现一个问题,我需要用 gcc 去生成 .c 和 .h 的依赖关系文件。但是用 gcc -MM 生成后,格式都是

xxx.o : xxx.c xxx.h

这样的。也就是说,xxx.o 前面没有我需要的目标路径。

当然,我们可以用 sed 进一步处理这个文件。不过我查了下资料,想到另一个方案,即使用 GNU Make 的 vpath 指令。

注:网友 CHU Run-min 提醒,gcc 有个 -MT 选项可以修改 : 前面的 target 。不过如果想一次处理多个源,还是有一定的麻烦。

我们只需要在模式匹配前写上一句:

vpath %o $(ODIR)

那些,下面,符合 %.o 模式的目标,都会去 $(ODIR) 搜索。如此,我们便可以直接接着写:

%.o : %.c

这样的规则了。

下面的链接过程,可以直接写:

SRCS = xxx.c OBJS = $(OBJS:.c=.o)

a.exe : $(OBJS)

看起来好象一切正确,但是在实际工作中,老是有点问题。第一次运行 make 总报告说找不到某个 .o ;可是再运行一次 make 又正常了。

我仔细分析了一下,原来是这样的:

在依赖规则表建立起来的过程中, a.exe 依赖了若干 .o 文件,在上例中就是 xxx.o

因为当前路径以及 vpath 设置的 ODIR 中, xxx.o 均不存在,所以 make 企图构建 xxx.o ,于是它找到了

xxx.o : xxx.c

这条规则。对于这条规则,我让 gcc 直接把 xxx.o 生成到了 ODIR 下。但是这个发生在 a.exe 的依赖关系处理之前。 a.exe 的依赖表里填的仍然是当前目录下的 xxx.o

当第二次运行 make 的时候,由于 ODIR 下的 xxx.o 已存在,根据 vpath 的规则,make 觉得不需要重新构建 xxx.o 。并且, a.exe 的依赖表中, xxx.o 也被自动扩展到了 $(ODIR)/xxx.o 。这样,就可以正确构建 a.exe 了。

我想了个方法解决这个问题:让 a.exe 的构建过程不直接调用 gcc 的链接,而是用 make 重新跑一个伪目标。看起来是这样的:

all : $(OBJS) a.exe

a.exe : $(OBJS)
    $(MAKE) exe

exe : $(OBJS)
    $(LINK) a,exe $^

如此就能正常工作了。

在 Make 的时候,最先构建 OBJS 。然后试图构建 a.exe 。 而 a.exe 需要 fork 一份 make 构建自己。由于是新的子进程,所以这个时候 OBJS 都已经生成好。就不会有上面的问题。

当然,这不是个完美的解决方案,它依赖 all 后面的依赖次序。如果是多进程编译,还是有可能出问题的(仅是猜测,我觉得出不出问题会跟 make 具体实现有关,不过我自己试了是没有问题的)。等明天再想想更好的方法吧。

GNU Make 处理斜杠的问题

GNU Make 对反斜杠的处理很恶心。用常规方法,你很难弄出单个反斜杠出来。

比如直接写 SLASH = \ 是不可以的,因为 \ 被用来连接下一行的。

而你用 SLASH = \\ 会生成两个反斜杠,而不是一个。

这个问题在 BSD Make 里没有,但在 GNU Make 里是个很让人头痛的问题,尤其是你需要做多平台的时候。

虽然 Windows 下,大多数时候,路径名中使用 \\ 等同于 \ 。但有的时候也会出些小问题,尤其在做很复杂的模式匹配的时候。

今天我下决心搞清楚这个问题怎么解决,最终 google 到了方法。

定义出单个反斜杠可以曲线救国:

SLASH := $(strip \)

更有甚者,在 GNU Make 中,还可以写

/ := $(strip \)

这样定义的好处是,你可以用 $/ 生成一个路径分割符,而不需要用前面定义的 $(SLASH) 。

参考:GNU Make path handling

March 12, 2009

为 lua 封装 C 对象的生存期管理问题

把 C 里的对象封装到 lua 中,方便 lua 程序调用,是很常见的一项工作。

里面最大的问题是生命期管理问题。

通常有两种方案:

第一:编写 C 库的时候,完全针对 lua 设计,所有对象都有 lua_newuserdata 分配内存。对象和对象之间的联系可以使用 userdata 的 环境表,把对象间的引用放在里面,使得 lua 的 gc 过程可以正常进行。

第二:给 C 对象简单加一个壳。lua 的 userdata 中仅仅保存 C 对象指针。然后给 userdata 设置 gc 元方法,在被回收时,正确调用 C 对象的销毁函数。

以上两种方案都依赖 lua 的 full userdata ,这里,我想提供第三种方案,仅使用 lightuserdata 完成这项工作。

这第三方案未必比前两种都好。虽然从字面上理解 light userdata 比 full userdata 更廉价,但诚如 pil 中所言,full userdata 也非过于重量。

最终的方案选择还是要结合实际的设计,仔细考量。

方法很简单:

如果你可以保证,所有对象用户只从 lua 层面创建,并依赖 lua 层的 gc 机制销毁。那么仅需要在 lua 中维护一张弱表,把每个创建出来的 lua 封装对象(一般是一个 table)放在这张表中(其实是一个集合)。

同时,在 C 中也维护一个集合(一个简单的对象指针数组即可)。每次对象创建,便把 C 对象指针放入集合。

这样, C 里的集合引用的对象一定是 lua 中那个集合的超集。下面,仅需要周期性的对比两个集合,把 C 集合中多余的对象销毁掉即可。

真正使用时,尤其是前面提到的前提(所有对象只能从 lua 中管理)不满足时,还需要考虑更多细节,这里不再赘述了。


3 月 14 日 补充:

可以通过向 lua 的对象集合(一个弱表)中放置一个 C 收集器来实现在 lua gc 后自动回收 C 对象。这个 C 收集器实现简单,用一个 userdata 绑定一个 gc 元方法即可。

需要注意的是,创建 C 对象和创建 lua 对象,并将两者绑定需要是一个原子操作。否则中间可能被 gc 打断,导致 C 对象被提前回收。

March 10, 2009

关于游戏中资源管理的一些补充

最近在实践中印证了我的一些想法,是关于资源管理的。确认自己的猜想是正确的总是件开心的事情。

先简单回顾一下以前写的几篇东西:

资源的内存管理及多线程预读

这不是最早的思路,但是是我能找到的最早在 blog 上公开并实际实现的思路。里面提到的部分东西,尤其是多线程设计部分,后来都一一被换掉,理由是过于复杂并实际上没能达到要求。或是细节上很难有 stable 的实现。

胡思乱想续

经过一些思考,以及经历了许多实践后。对上面的东西,一部分做了肯定,一部分做了否定。肯定的是,资源管理的大策略是对的:那就是和其它部分正交化,尤其是要独立于游戏逻辑之外。生存期不应和游戏逻辑耦合。

重构

到目前最后一次在 blog 上记录思考和资源管理相关的问题。认清的最重要一点就是:

至于多线程预读的问题,资源模块已经可以了解资源数据文件间的关联信息。简单的开一条线程 touch 那些未来可能读到的文件即可。把预读和缓冲的工作交给 OS ,这应该是一个简洁有效的设计。并不需要太多顾虑线程安全的问题。

那么今天想说什么?

由于我们的一个疏忽,在最近的一个小程序中,把资源管理模块的调节阀值设到了 6M 内存,也就是说,只要超过 6M 数据,资源管理模块就会自动的清理一些它认为可以清理的数据。

原来我们的计划并不是这么小,当时是为了想尽快发现一些 bug ,让资源管理模块工作的更频繁而设小的。

但是,我们得到了一个惊异的结果。跑了一个很复杂游戏场景的 client ,从 os 的管理器中观察,居然一直都保持在 36M 内存的占用。一开始,大家还都不敢相信。因为 3d engine 本身会固定吃掉大约 30M 内存。而这个 client 却跑了很丰富的游戏场景。最后确认后,合理的解释是,的确 6M 资源数据区就够用了。(这方面 3d 游戏比 2d 游戏更节省内存)

不过为什么 client 依旧跑的很流畅呢?应该是 os 的 cache 机制做的很不错。而那台机器安装了 2G 的内存条。其实,并没有发生太多的硬盘读操作。

我们把 6M 的阀值调到了 128M ,client 迅速的吃满了分配给它的空间,但是 client 的流畅度并没有太大的提高。

反而,如果多开几个类似的程序,还会相互争抢内存。

有了这个数据做基础,前几天写的 关于地图编辑器的一些想法 或许会更加实用。事实上,上面谈到的 client 正是我们临时做的一个符合 editor 协议的观察器(所谓临时,是我们一个程序员花了一天时间,按照协议文档,写的个小程序。注:只是协议文档,我们只规定了通讯协议,还没做成内部通用的 SDK 库)。操作者可以通过连入 editor server 漫游正在编辑的游戏场景,甚至可以实时的观察到别人的编辑更新。

按我的设想,如果美术人员想在编辑时,同时监控场景全貌,或是想从另外一个角度观察他的编辑区。只需要简单的启动一个新的观察器,调整到合适的角度,挂在屏幕一角即可。

更小的内存(以及 CPU )占用,使得这件事情变的便捷。 btw, 我们的编辑器目前所有资源都从网络下载,在百兆 LAN 上也工作的非常流畅。方便了很多人一起工作。

editor server 保存了美术人员左右的工作流程,等游戏做完的时候,我想我会制作一段 video ,展示整个游戏虚拟世界从无到有的过程。

March 09, 2009

关于 manual gc 的代码分析

今天发现 darkdestiny 朋友去年写了一个系列的 manual gc 的源码分析 :D

嗯,那段代码写的比较乱,居然真有人读完了,我真是佩服的紧啊。:D

垃圾收集的那点事(A)

这是第一篇,在那里还有 A-K,有兴趣的朋友可以自己去看。

里面提到 cache_flush 算是这个库最糟糕的一段代码了 ,好吧,我检讨,这段写的是很够戗。

代码写的乱,是我迟迟不敢把很多东西开源的主要原因 :D 。

其实一开始设计的时候,何尝不想写清楚点呢?在我自己的 svn server 上查看这个东西的修改历史,曾经也出过好几个 bug 。所以说,优化是万恶之源啊,可我们又不得不面对现实。

写的这么复杂还是因为性能缘故,希望把内存扫描次数,数据比较、内存移动、内存分配等的次数减到最少,或许以后重写一次会好一点吧。

顺便回答文章最后的一个问题:

Q: 这样这些节点不会在下一次gc_collect的时候被回收。因为弱表的children还引用着他们,维护着依赖关系,即使分配的内存已经回收了。只有用 gc_weak_next 遍历了弱表之后,这些废弃的管理节点才会从children中被删除,最终在gc_collect的时候被回收。 为啥非要主动遍历弱表才能这样呢。。。。

A: 呵呵,因为 id 得保留,不然新分配的内存块分配出来的 id 可能和弱表里记录的重复。这样从弱表里就可能取到和当初放进去不同的内存指针了。关键是在于,回收一块内存时,无法反查到内存被哪些弱表引用着。


这个东西原理其实很简单,也就是标记-清理算法。我觉得有价值开源,是因为在我们项目的实际应用中,的确得到了许多好处。有些优化策略是值得推荐的。

比如把一切事情都推迟到非做不可的时候,这样可以快速合并删除不必要的操作。标记-清理算法本质上需要维护一张内存关系图,但是,我们不必要随时生成和拓展这张图,而可以推迟到收集发生的时候。

把内存关系图和内存块在物理上隔离,也使得系统更健壮,甚至性能更高。发生收集的时候,cpu 可以工作在很小的连续内存地址空间,减少系统内存交换。也为以后升级到并行收集做准备。

另外,如果系统整个建立在 gc 的基础上的话,finalizer 的使用其实很值得推敲。一般说来 finalizer 是用于避免太细的内存粒度,和回收非内存资源用的。如果泛泛的用于类似 C++ 的析构函数的机制,会起不到应有的效果(效果指让 gc 工作的更高效)。

March 07, 2009

降低 lua gc 的开销

周末有同事问我一个问题,说他们猜测在他们系统里 lua 的垃圾回收过程导致了系统开销过大。而其中有些开销是无谓的。

比如在他们的系统中,有大量的结构化数据是只读的,不会和其它数据产生联系。大多为策划设定的游戏逻辑参数。而偏偏这部分数据结构复杂,在 lua 的 gc 过程中会产生大量的遍历。但我们明明知道,这些数据一定不会被回收掉,且不会影响 gc 的结果。那么有什么方法可以优化呢?

首先,我认为这个问题的提出只是在臆测阶段。这部分结构化数据的存在是否实质性的影响了 gc 的效率尚需分析研究。暂时我没有这个条件,暂且认为有这个优化需求,提出方案如下:

首先,有得必有失。如果想出办法减少 gc 的遍历数据量,必然会增加其它方面的开销。

常规来讲,lua 的 VM 是基于标记-清理的方案 gc ,故而需要保留的数据一定要通过标记。我们只能想办法加快标记过程,而不能回避这一点。

可以考虑使用多个 lua state 。成熟的方案有 lua rings 。我们把大量独立数据(可以是只读也可以是可改写的,关键是要独立)放在一个单独的 lua state 中。这样,对于频繁更新的逻辑 state 里,这些数据是一个整体,即一个 state 对象。标记就只需要做一次了。

代价呢?

代价是,state 间传递数据会有比较大的开销。所以需要精心设计。

或许可以建立一个通用的方案,在母体中创建一份 cache ,不用每次从子 state 中复制数据。而这个 cache 可以是一个 weak table ,发生 gc 时整个扔掉即可。

其实,这个做法就是把 gc 遍历复杂数据结构的代价分摊到单个数据元的读取上了。程序员可以权衡其利弊。当然从结构上说,多个 state 可能能增进结构的稳定性。

btw, 这两年,在完成了 C 下的 gc 模块后,从项目中得到了一些可控 gc 的一些使用经验。如果对系统里参于 gc 的对象在心中有数。最简单的 gc 算法反而可以得到最佳效果(简单指,没有什么分代,没有渐进式的扫描回收)。在我们的系统中,被 gc 管理的对象一直保持在千的数量级,在这个数量级下,一切算法都显得敏捷(n 很小时,复杂度上的影响不大)。