« April 2007 | Main | June 2007 »

May 25, 2007

模块的初始化

组件式的设计中,最难处理的就是模块的初始化次序和退出次序的问题。如果不考虑动态加载卸载问题,则可以简化一些设计。

退出问题解决起来最为容易,安全的退出唯一需要考虑的是对系统资源的释放。这是操作系统的工作,进程被杀掉时,所有占用的资源都会被安全回收,所以我选择的是不作为。

初始化部分要相对复杂一点,我把模块加载和初始化部分分开。加载的过程是静态的,无相互依赖关系的。实际上,做的只有代码和数据段载入内存的过程。(在实现上,要绝对避免隐式的代码运行,例如 C++ 中的全局对象的自动初始化)

初始化过程是惰性的,即:用到再调用初始化入口。每个模块都在自己初始化的时候去调用所依赖模块的初始化(实际上也必须如此,否则拿不到别的模块的句柄,无法使用其它模块内的方法),这样模块之间的初始化次序就自然规整了。只要不人为写出循环初始化的逻辑,是不会出错的。

实际操作中遇到一个问题,某些模块的初始化依赖一些参数。当需要参数传递的时候,初始化流程就变的复杂了。昨天同事提出一个需求:3d 渲染的基础模块需要一个窗口句柄来初始化自己,否则无法使用。那么依赖这个渲染模块的其它模块的初始化部分就必须也知道这个窗口句柄。而窗口句柄是由窗口管理模块初始化后,构造一个窗口才能得到的。其它模块均无法自行构造出窗口来。

我们上一个版本的设计中,模块管理器拥有一快公有数据区,专门用于模块初始过程的数据交换。这种类似 Windows 注册表的设计,隐隐的,一直让我觉得不妥。这次重构代码时,就把它从设计中拿掉了。

重构代码到今天,发现该碰到的问题依旧存在,需要想办法更好的解决这个问题。昨天晚上躺在床上把怪物猎人2中的轰龙一举干掉,一扫几天来的郁闷心情。突然来了灵感,找到一个很简洁的方案解决这个问题。

首先,任何模块的初始化入口依旧不需要传递参数。这如同单件的设计一样,单件永远是自行构造的。这样,每个第一次使用单件的人都有可能触发单件的惰性初始化。若单件的构造还需要参数的话,代码复杂度会上升许多,显然是不合理的。

让需要构造的单件自行读取外部配置来了解如何构造自己,这也是一种解决方案。数据驱动、符合模块设计的原则:能自己解决的问题自己解决,减少数据的传递。但这不是一个普适的方法。因为有些工作就是一步步进行的,我们需要上一步的结果来进行下一步工作。

其实,我们需要的只是一个独立模块单独负责模块初始化阶段的阶段性衔接。

还是以 3d 渲染模块和窗口创建过程的依赖关系为例子。事实上,上层的逻辑并不需要直接驱动这些底层模块的初始化流程,它们只需要在自己初始化时,这些底层模块都已整装待发。所以,我们写一个独立模块初始化掉该初始化的东西即可:在这里,我们随便创建一个窗口,得到窗口句柄,传递给 3d 渲染器初始化。这已经足够单元测试使用。当以后游戏的复杂逻辑需要自定义的窗口时,简单把它换掉就够了。我把这个衔接用的模块起名叫 launch3d 。

我们的单元测试程序,只需要简单依赖一下这个 launch3d 模块。它能保证相关的底层模块都初始化完毕。


这个故事给了我启发:面对二次开发者,引擎开放出来的不一定是上层建筑的接口。整个设计可以是平坦的,无论上层还是下层构件都可以是可定制和可替换的。这样才是良好的设计。

May 24, 2007

DXT 图片压缩

这两天在写 DDS 格式的解码程序。DDS 是微软为 DirectX 开发的一种图片格式,MSDN 上可以查到其文件格式说明:DDS File Reference

其中的 DXT 图片压缩格式,现在已经为绝大多数 3D 显卡硬件所支持。(它使用了由 S3 公司所发明的一种有损图象压缩算法。btw, 在我的那本书中,P232 有所提及)。DXT 格式 也叫作 S3TC ,现在可以被流行看图软件直接显示的图象格式中,只有 .dds 文件支持这种压缩。为了开发方便,我们的引擎也就支持了 .dds 文件的加载。

一起做引擎的同事希望即使在硬件不支持的时候,我们也能正常加载并使用贴图,所以便有了对 DXT 软解码的需求。

好在以前研究过一些,写起来也不麻烦。

DXT1 支持 1 bit 的 alpha 通道。这个其实是可选的。每个 4x4 的块可以根据需要有或没有这个透明通道。不需要 alpha 通道时,每个块可以有四种颜色(其中两个是插值得到的);需要 alpha 通道时,则只能有三种颜色,11 被保留用来描述透明的点。区分是否用通道,要根据每个块开始的两个高彩颜色值:color_0color_1 。如果 color_0 在数值上(当作无符号短整型)大于 color_1 则没有通道。

可惜的是,在 dds 文件的文件头中,没有任何一个地方描述了:整个图片是否有至少一个块包含了 alpha 通道。但是在 3d 程序中,却需要知道这一信息以使程序可以更高效的运行。

对于软解码程序,更需要知道这一信息。因为带通道时,我们需要把数据解码成 RGBA5551 的格式;而不带通道时,则需要解码成 RGB565 格式。

一开始我以为需要扫描整个数据段,检查是否至少有一个块的 color_0 小于等于 color_1 。实际看了几个用工具生成的 dds 文件才发现自己错了。nvidia 的 dxt tools 压缩 DXT1 图片时,需要手动指明是否需要 1 bit 的通道。如果你指定不带通道,那么每个 4x4 数据块头上的两个调色盘颜色值的大小次序是无关的(这样做,由于插值方案的差异,有可能得到更好一点的图象质量)。也就是说,只有压缩图片的人知道图片上是否有通道,而文件头上并无记录。


DXT3 就是在 DXT1 的基础上,增加了 4bit 的 alpha 通道,每个 4x4 块多用了 64bit 来保存这些 alpha 通道信息。(数据储存时,在每个数据块中,alpha 通道信息放在颜色信息的前面)

DXT5 对 alpha 通道的储存作了改进,有点意思,值得一提 :D 。它依旧用 64bit 储存 16 个 alpha 信息。前面 2 个字节(16bit)保存了当前块的最大 alpha 值和最小 alpha 值。接下来的 48 bit ,每个像素占用 3bit 空间,刚好描述 4x4 个像素。

alpha_0 大于 alpha_1 时,我们后面的 3bit 可以表示 8 级的插值;反之则保留 110 和 111 分别表示 alpha 为 0 和 255 的情况,中间可以有 6 级过度的插值。

关于 DXT3 和 DXT5 的压缩算法,在 MSDN 上也可以找到详细的文章:Textures with Alpha Channels


至于 DXT2 和 DXT4 实际用的不多,从数据压缩算法上来讲,它们完全等同于 DXT3 和 DXT5 。区别只在于颜色数据是否经过 alpha 预乘。

既然是否作 alpha 预乘都可以在 dds 文件中使用专门的 4 字节标识,我奇怪的是,DXT1 中那么重要的通道信息居然不在 dds 文件头中表示出来。真不知道设计文件格式的人怎么想的。 >_<

本周游戏

怪物猎人2 继续挑战轰龙中 :( 昨天晚上在训练场用弓箭训练,前三十分钟无伤,最后几分钟一个不小心被秒了。真是郁闷啊。

昨天朋友介绍玩 travian ,感觉有点像 EVE ,不过轻松的多。初期建设过程有很多种选择,很难找到最优策略。反正我们这里几个同事的发展方式都不一样,暂时还看不出明显的优劣。

大话西游III 内测。要了个内测号试试。真是很难挤上去啊,也就上去建了个号就没玩下去了。一开始似乎 Bug 多多,不过我相信他能够长远发展下去。

Palm 上的 Alchemy 我很喜欢。Hard 难度已经超过五千七百分了 :D 有兴趣的朋友可以试玩一下 Windows 版

May 16, 2007

良好的模块设计

这周程序写的比较兴奋,通宵过一次,另一天是四点下班的。做了两件事,一是研究怎样最好的做扩平台,二是做资源管理的模块

第二个目标昨天达成了。觉得整个过程还是攒了些经验,值得写写。那就是“怎样才算设计良好的模块”。这个话题比较大,几次想总结经验都不敢下笔。

这个题目前辈已经论述的太多,而自己的感悟一但落到文字就少了许多东西,难免被方家取笑。

最正确的道理永远是简单的,却因为其简单,往往被人忽略。程序员还是要靠不停的写新的代码,以求有一天醍醐灌顶:原来自己一直懂的简单道理,其实才刚刚理解。

首先说说正交性:

我们都知道保持正交性,可以在非常复杂的设计中降低出错的几率。纯粹的正交设计中,模块内的任何动作都对外部无副作用。

道理简单,但是真正做到很难。所以我们用额外的约束来接近这一点。

我们的模块目标文件可以是标准的 dll 或 so (方便开发期调试),也可以是自定义格式。在自定义格式中,是没有导入导出表的,模块对外的接口只有入口点一个。而如果在开发期用系统的动态模块,则需要在编译时加上 --nostdlib (对应 cl 的 /nodefaultlib)。这样可以拿掉 libc 的隐式链接,并检查有无对外依赖关系。表面上看起来苛刻,但这是一个杜绝副作用的有效途径。这样,自然任何第三方库都不能直接使用了。这也是我不停的再造轮子的源头之一。这条原则我们严格执行了两年,回头看来,其实真正在造轮子上花的精力并不多,况且造好后就不会重复工作了。偶尔有不适用的轮子也可以轻易换掉,这得益于正交性的严格保证。

接下来更重要的是接口的简洁:

从《Unix 编程艺术》上读到一段话:(书中引用了)《C 程序设计语言》上的一句名言,“……限制不仅提倡了经济性,而且某种程度上提倡了设计的优雅”。为了达到这种简洁性,尽量不要去想一种语言或操作系统最多能做多少事情,而是尽量去想这种语言或操作系统最少能做的事情——不是带着假想行动,而是从零开始。

这段话我在不同的时期读过几次,相当的喜欢。为什么 Windows 的 API 看起来丑陋无比?因为它什么情况都能处理,几乎所有的 API 组都为将来留下了诸多扩展的可能性。有的 API 从出生到死亡,lpReserved 伴其一生都没被使用过。学生时代的我,很喜欢 Windows 的这种处世哲学:看吧,只要你会用,你手头的计算机的一切潜能我都能为你挖掘出来。即使现在不行,接口摆在这里,你可以通过接口看到未来的可能性。可惜的是,直到今天,我都不能在 windows 下 fork 一个进程。而 CreateProcess 每次用到都想吐血。

今年开始,我用 C 语言重构项目中 C++ 代码。好在在上一版里,C++ 代码中已经没有用任何高级特性了,故而这件事情做起来还算轻松。一边做一边思考哪些地方可以修改设计,去掉或合并多余的接口。

如今我爱 C 语言,就是爱它的限制。不能方便的 OO ,那么就限制我不去用它或少去用它。没有类定义和名字空间,减少 C 函数接口的数量就成了反复需要考虑的问题。重新用回 C 语言后,我不再 typedef 结构名。union 就是 union ,struct 就是 struct ,何必换个名字减少键击。精简的设计将减少更多的代码字节数。

至于对 OO 或是特定 OO 语言的批评,不能在 blog 里多写,不然一定变成找骂贴。当然已有一个不怕挨骂的前辈 Eric S.Raymond 已经在 TAOUP 4.5 中写了许多了。我想,不赞同这个观点的人即使耐心看完了依然会不赞同,因为这些道理靠文字是没有说服力的。

很惭愧自己在 02 年到 04 年的三年招聘中出了太多关于 C++ 和 OO 的笔试面试题,(02 年在私人名片上,我毫不遮掩的印上了自己对 C++ 的狂热),而我现在背叛了这些。不过对这些了解的再多也不为多,每次面临新的设计时,就可以找到足够的理由不用 C++ 不用 OO 。对,就算是用 OO ,我也可以保证对象设计的整洁清晰;但我更清楚的知道,其实我可以不用它。

做到以上两点,其它的一些就自然做到了:比如永远不要 copy-paste 代码,不要重复实现类似的东西。不要为尚不存在的需求做设计,你要相信你现在设计足够清晰,日后改起来也不吃力……


接下来谈谈这几天的一个设计吧,说不上好,也没有什么特别之处。不过完成它还是费了些工夫,代码总行数不多。留下来的就 1000 来行,写了三四天,低于我的日均生产力 。速度比较慢是因为大量时间花在了不停的修订和裁减接口上了。

模块的需求不多,游戏的客户端在运行时需要加载大量的数据资源。总的字节数按 G 计算,所以面临两大问题:一是总体加载时间过长(由于大部分文件加载过程还需要再次解析,不能直接从硬盘做内存映射),二是 32 位系统的地址空间不够用。结论是,必须动态管理。

给用户暴露的接口理论上只需要一个:load ,这就够了。实际实现的时候,我追加了两个接口 lock 和 collect 。lock 的作用是,保证数据块的所有数据皆存在于内存,并保证其生命期至少维持到下一次的 collect 调用。而 load 本身只保证逻辑层需要的数据被加载进内存,而不保证渲染层需要的数据。(游戏中渲染层需要的数据才是尺寸上的大头)

另外我需要一个可替换和配置的处理加载方式的模块。它可以采用单线程阻塞调用,或是多线程预读模式。还可以允许用户不通过文件系统直接生成一些资源的内存对象,甚至以后有可能增加网络加载模式。另外,数据的来源可以是本地文件系统,也可以是数据库或自定义数据包。

我为游戏的资源设计了一种数据管理格式,可以描述出资源之间天然的依赖关系以及数据类型。这些方便预读模块自动做出合理的判定。在本地文件系统下,这套机制需要用额外的文本文件来模拟数据文件之间的关系。

每种文件根据格式的不同,有不同的解析方式。虽然最基本的文件可以通过直接把文件内容全部加载来完成。但是还有许多文件不能这样做。简单如贴图文件,需要做图象解码,复杂如场景需要在加载的同时生成复杂的内存对象。各种数据的解析器也应当是可配置的选择。

大体上就是要想办法粘合以上三个模块,提供出简洁的接口交给不同的用户。有开发更高层次逻辑的程序员,也有编写不同加载策略的程序员,或是添加新的数据类型的程序员。

面对不同的二次开发人员,接口应该相互独立,隐藏所有可以隐藏的细节。对于外部可配置之模块的开发,不需开发者遵循太多的规则就可以避免潜在的副作用。

这里面比较麻烦的是数据解析模块的扩展接口,它要使后期开发人员可以无视线程模型,即不需要在代码使用任何锁相关的 api 也可以保证线程安全。最终的方案是让开发人员提供一个 parser 的 callback 函数。管理器对其回传三个参数:数据流指针,上下文数据,和内存池指针。回调函数的返回值就是生成好的数据块内存指针。

暂时我们的需求中,加载方案模块在运行期只有唯一的一个(这一个可以通过初始化阶段配置),所以我们可以从其中取到对数据流指针和内存池指针进行操作的方法。由加载方案提供者来保证其线程安全性。

上下文指针的存在是因为我们的资源数据读取被划分成两到三个阶段:数据头的读取和数据内容的读取。上下文指针指向的内容是由解析器自己定义的,并由它自己维护。内存池只能从中分配而不能释放,因为解析器也原本不承担生存期管理的责任。

整个方案的细节描述到此为止。

将其自行对比一开始的一套更为 dirty 的设计,以上要简洁许多。最明显的是一开始的头文件长度是现在的两倍。写代码的时候还曾经暗暗埋怨了一下 C 语言为什么没提供一个简单的 class 机制。直到最后反复考量,删除了一些不必要的方法后,心情好了许多。


ps. 最近一段时间颇有感触的一点:当年认为准确的构造和销毁对象是一种美德。在对象层次过深的时候,这的确是保持正确设计的一种必须。今天看起来,其实大部分对象一旦存在于进程,他们的生存期都是一直维系到进程结束。那我们为什么要准确的,优美的,按照合理的次序,销毁它们?这本该是 os 的进程管理器做的事情啊。在应用层面看待资源的回收,和在 os 层面来看,复杂度完全不在一个数量级。不难理解, os 总是可以做的更好。

一旦我们在代码中正确的位置使用只分配永远不考虑释放的内存/资源管理策略。大量的代码将被简化。数据结构也可能简单许多。不必考虑次序,甚至不必做引用指针(许多引用的存在,都只是为了可以最终启动相应的销毁过程)。

单件或许并不邪恶,只是我们一直在邪恶的用它罢了。


5 月 17 日

前两天估计有点累,昨天 23 点就回家睡了。今天起了个早,特精神。

想到一点补充:

组织代码的时候隐藏细节很重要,所以应该尽量减少头文件的数量和体积。任何信息如果不给模块使用者用,那么就永远不要写到头文件里。

函数原型声明只应该用于对外的接口描述,一切有依赖关系的代码,都可以用前后次序来保证。如果必须在源文件前面提前声明函数原型,或是做结构的前置声明。那说明代码中出现了间接递归。间接递归这个东西往往是坏味道的前奏。间接递归会导致多个东西相互依赖。写到这里,我想到了十几年前刚写程序时,跟人争论的一个问题:为什么 main 函数习惯上总是放在源代码的最后?当时我是说不出太多理由的。如今,我坚信这种习惯的正确性。

如果坚持去避免函数原型声明,马上会发现一个问题,那就是单个模块的主体都需要保持在一个 .c 文件中。这样做有时候会让人不太舒服,比如单个源文件过大,可是这正是说明设计出了问题。当我们把本该放在一起的代码,人为的分开(而不是按模块自然分离)时,就已经开始隐藏而不是解决设计问题了。

May 11, 2007

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

网络游戏的 client 开发中,很重要的一块就是资源管理。游戏引擎的好坏在此高下立现。这方面我做过许多研究和一些尝试。近年写的 blog 中,已有两篇关于这个话题的:基于垃圾回收的资源管理动态加载资源

最近在重构引擎,再次考虑这一个模块的设计时,又有了一些不算新的想法。今天写了一天程序,一半时间在考虑接口的设计,头文件改了又改。最终决定把想到的东西在这里写出来,算是对自己思考过程的一个梳理。

如今的 PC 网络游戏早就今非昔比。为了满足玩家感官上的需要,以及机器性能的提升,整个游戏 client 的数据资源已经开始论 G 计算。在 64 位操作系统普及之前,Windows 下那 2G 用户可用地址空间开始有点相形见绌了。换句话说,无论你多么不重视资源的内存管理,原来用过的最苯最有效的方案:只加载不释放资源的做法,开始不太适用了。设计引擎的程序员必须考虑适时的把一些已读入内存的数据清出内存,并在需要的时候再读回来。当然,如何有效的管理内存也是我这些年做程序员一贯的课题,今天的局面只是逼更多的人跟我一起来研究解决方案 :D

到了 3d 技术普及的今天,3d 游戏的资源面临另一个问题:资源的交叉引用。例如:一张贴图可能被好几个模型引用,但是我们只需要在内存中保留一个拷贝。这种引用关系有可能错综复杂,在场景的构建上尤其突出。一旦我们需要实现无缝连接的超大场景,每个地图区域上物体之间的都会发现直接或间接的关联关系。房子的旁边的树,树的旁边是房子,人物在场景中行动,不停的有新的资源被请求使用,也会有一些资源可以暂时清出内存。

一开始我希望用 gc 技术来简化这个问题的解决方案,经过一段时间后,目前的思路有所改变。我希望可以在内存里保留所有资源的数据头(即部分数据),而在不需要完整数据的时候,将资源的一部分数据卸载。资源数据在游戏开发期就把关联数据构建好,这样所有的资源数据的头信息会一点点加载进内存,完善整个游戏所有资源之间的关系网。在管理这些数据的时候,即不需要引用记数又不需要 gc 链。以目前的系统结构,内存消耗也是可控的。

在软件运行中,会有大量的内存分配请求不再被回收(除了进程结束),我们可以专门写一个特别的内存分配器做这件事情。实现的算法非常简单:递增堆指针,并在堆不够的时候向系统申请新的内存页,足够了。

下面来看一下资源的动态加载方案:

显然,多线程读取资源是首选,我们也不排斥单线程方案。另外有些资源是动态计算出来,或是并不从硬盘加载。所以我们需要同时支持多个加载器。加载器这个东西必须被抽象出来方便后期对引擎的二次开发。资源管理的框架不需要干涉加载的细节,也就是说,它不能有任何线程相关的代码,但需要为异步加载提供接口上的方便。

引擎使用者应该了解的细节越少越好。他只需要通知引擎准备加载什么资源。这通常用字符串来定位,或者通过关联信息。当然,有时候也需要一些额外的请求,比如在内存拮据的时候通知资源管理模块回收适当的内存。

对于加载器开发者,我们需要暴露更多的内部信息,但不是无条件的全部公开。加载器不需要了解管理器的内存数据结构,甚至不必看到资源数据节点上的数据结构。它只需要提供函数供回调加载数据就够了。不过因为我们需要支持异步加载的可能,所以在回调函数的接口设计上,需要传递一个类似状态机的东西,可以分步加载数据。

定下这些需求,下面可以着手设计了。

我希望资源数据被放在硬盘上的假想的数据库里,通常这个数据库就用本地文件系统模拟。或是在发布时打包成一个数据包。我可以用分段的字符串的形式定位数据库中的具体资源;但不需要每个资源都必须有字符串路径,匿名的资源只以唯一数字 id 的形式放在数据库内,这个数字 id 可以存在于别的资源的关联信息中。例如大部分贴图文件就不需要有名字,它们只会被模型引用,而不会由引擎直接加载。

资源的加载通常分两个阶段,数据头加载和全部数据加载。数据头很小,可以常驻内存。通过数据头可以得到数据的尺寸大小信息。这个信息可以帮助管理器的决策。另外,关于匿名资源的加载还会多一个阶段,从 id 映射到数据本身。(对于具名资源,文件头加载完毕后,对应 id 就自然获得)

我设计了一个树结构来保存具名资源,每个具名资源都可以通过类似 URL 的字符串形式得到,并在第一次请求时立刻把文件头加载进内存保存在这个树结构里。这棵数的每个枝干都有一个字符串名字。btw, 为了提高效率,不要使用 string 作 key 的字典结构。因为所有可能出现的字符串是非常有限的,我们可以设计一个字符串池,内存以 hash 表形式组织。这个字符串池也只只增加而不释放的。这样,每个做 key 的 string 都会有一个全局唯一的指针来表示了。这样做可以提高许多树检索的效率,并减少内存消耗。

另外,再用一个 hash 表来保存所有资源 id 的映射。

每个资源都会有一个小结构常驻内存,所以以上两个结构中都可以直接用指针对资源结构做引用。甚至不需要引用计数。这些资源结构我用链表串将起来,每次加载请求,如果内存中不存在,就创建新的节点,并插入链表头部。

加载请求是不会立刻要求加载完整资源数据的。在主逻辑线程运行的间隙,我们可以适量的从这个链表的逐个节点上取得可能的关联资源并做新的加载请求。这部分通常并不需要多线程工作,因为数据头的加载通常非常的快,并且可控,不会影响玩家的操作感。

当程序真正需要用这些资源的数据时,可以通过资源管理模块向加载器发起请求,要求立即加载数据。这时候除了满足加载请求完,还需要把资源本身调整到链表尾部,表示其刚被使用,不要立刻回收。

当内存拮据的时候,我们就可以从链表头部开始一点点回收内存了。

这里,加载器可以做成多线程的工作方式,并且 lock-free 。不过要做到真的 lock-free ,有一些先决条件:首先,我们的内存分配器不设定锁,那么数据加载线程就不得自行分配内存。这一点比较容易实现。因为一旦得到资源的数据头,就能准确计算出整个资源消耗的内存量,可以一次分配出来。而资源数据加载的时候,只在这块已申请内存块中做切割,不会有任何副作用了。

数据加载线程序可以不断的去完成队列中的数据加载请求,一旦加载完毕,就在资源结构中做好标记。而主线程收到数据使用请求时,检查到标记后直接把完整的数据指针复制过来即可。如果没有完成,则自行申请另一块内存,阻塞做数据加载。这样是为了避免冲突,当然也有可能浪费,两条线程恰巧加载同一份资源。由于单个资源体积都不大,这点时间浪费是可以接受的,而空间在数据回收阶段可以完全收回。

ps. 真正用到多线程的项目,我只写过一个。那就是大话西游里的地图动态加载模块。01 年的时候,为了实现这个模块,整整调试了一个月才稳定下来。那是第一次写多线程程序,真是往事不堪回首。做梦都会遇到程序 crash 。后来大话西游II 以及梦幻西游都重写了 client ,就是这个模块无人敢动,一直保留到现在。也算是经受了千万用户的考验了。最后的效果虽然令人满意,玩家可以享受到无缝的场景跳转体验,并且 client 只用了 16M 内存就做到了这一点(完整的地图资源如今已经上 G 了);但是我自己知道,那段代码是极其缺少美感。

至此之后,我不轻易用多线程的设计。我想,只有真正免锁的多线程程序才会显得漂亮吧。

被 insight 折腾了一晚上

我装的 insight 是 6.3 版的,在 mingw 官方网站就可以下载 bin 安装包,用起来也非常方便。

可惜 gdb 的 6.3 版在 windows 下 attach 到一个进程调试时总是不对。如果在代码里写上 int 3 制造一个调试中断。中断发生后,再启动 insight attach 到出错进程,看不到被调试进程正确的堆栈。这一点让我非常郁闷,每次调试程序都必须用 insight 或 gdb 来引导,而不能像以前用 VC 那样,出错了再启动调试器。

下午 google 了一下,这似乎是 gdb 的一个 bug 。从一个帖子上推断,bug 最近被 fix 了。找到 gdb/insight 的官方网站,发现 gdb 现在已经是 6.5 版了,不过只有 source code 下载。我这种懒人当然是希望有人帮我 build 好了。windows 下用这些 GNU 的东西,光是 build 就可以让人脱层皮,我是领教过好几次的。

google 了老半天,硬是没找到有好心人 build 出一个 win32 下用的 6.5 版的 insight 。咬了咬牙,决定自己动手,丰衣足食。

我的 windows 下没有装 cygwin ,只有一个最小安装的 mingw ,所以首先去拉了个 msys 下来。这个是 build 这些 GNU 软件必须要的,否则 shell 脚本都运行不了。装 msys 倒是简单,安装完毕启动后感觉还不错,跟 cygwin 差不多。windows 上用这个的话,至少列目录可以 ls 了,不至于老是敲错。

接下来简直是噩梦。

我怀疑 windows xp 在进程管理上一定有 bug ,用 insight 带的 make 执行一遍,运行到一半就会因为 fork 失败而进行不下去。我们知道 make 的工作机制就是不停的 fork 子进程来干活的。windows 在进程管理上远不如 *nix 的系统,这 make 在我的机器上就是水土不服。出了问题后,怎么杀进程重新来都不行了,只能重启。好在 make 在重启后可以继续。就这样,我重启了 3,4 遍系统后,终于把 make 跑完了。

可到了最后,居然出现一行 Error ,说是 gdb 不支持 native target i686-pc-mingw32 (._.!) 看到这里人都要崩溃了。继续 google 出错信息,发现有人为这个说了 sorry ,据说要交叉编译出 mingw 的版本。真是吐血啊,只好放弃。

今天得到了几个教训:

1.不要把 GNU 的东西放到 Program Files 目录下,我就是因为 vim 被缺省安装到那里,导致人家写的 makefile 中引用这样的带空格的路径,不能正常工作。你只能去诅咒微软为啥把这样重要的目录名中间加个空格,明显制造不兼容嘛。

2.Windows 下不要对 GNU 系列的源码发布包抱太大希望。那些东西是好的,可惜 Windows 不吃这套。如果想用的话,尽量去找人家做好的安装包。

3.Windows 系统真的是滥,我们这样的 Windows 用户之所以总能忍受,是因为我们学会了用特定的方式去用系统,回避了许多可能出现 Bug 的地方。

May 08, 2007

智能 ABC 与拼音输入法

不知道有没有人还记得 天汇DOS ,我接触智能 ABC 输入法就是从那开始的。这一用就是十多年了。我相信同样有很多人都用着智能 ABC 十年以上,但是却发现大部分人根本没用到这个输入法的精髓。否则?怎么这几年新出的一些拼音输入法均未把其最关键的地方学走?

我所说的精髓之处就在于智能 ABC 对笔画码的简单支持,关于这一点的重要性,我在前段时间写的 一篇关于 google 拼音的 blog 中阐述过。

下面,有兴趣的朋友花上五分钟跟我来了解一下吧,我相信绝对能提高智能 ABC 的输入速度,并大量减少聊天时的错别字 :D

很多人喜欢“自然码”,就是因为它是一种简单的音形码,音形码相比形码学习的记忆量要小了很多。却比纯音码更能准确定位单字。不过对大多数普通用户而言,“自然码”的学习记忆依然是一个负担。

可是大多数人都忽略了,智能 ABC 其实也是一种音形码,它对每个汉字单字的编码并非只是拼音,而是还有两个数字的笔画码。不要小瞧了这笔画码,它可以极大的减少重码,在输入单字时极具价值。而记忆方面,对任何人来讲都应该不是负担。

跟手机上常见的 T9 笔画规则不同,智能 ABC 采用了八种不同的笔画,分别是:

1.横;2.竖;3.撇;4.捺(点);5.折(顺时针);6.弯(逆时针);7.叉;8.口

一般我们可以利用这些告诉计算机你要输入的字的偏旁。

比如单人旁就是 32 ,双人旁 33 ,言字旁 46 ,木字边 73 ,提土旁 71 ,厂字头 13 ,宝盖头 44 ,秃宝盖 45 ,草字头 72 ,两点水 41 ,三点水 44 ,金字边 31 ,足字边 82 ,提手旁 15 ……

用过一段时间就自然熟练了,我自己也没认真总结过。

除了输名字,最多时候用到单字输入的就是自造词了。我的个人观点是,如果你打汉字只为了写 blog 或是聊天,输入法词库大小其实并不重要,一个人日常用的词并不多。但是新造词是否方便却非常重要,这是使一个输入法真正变成你的私人工具的重要环节。如果造词不便,很多人就会选择不造词,甚至采用同音的错别字。

偶尔输一个单字,大多数人会选择在心里造一个词打出来,再把不要的字删掉,比如想输入“域”字,可以先输入“区域”再把区字删除。在 ABC 里,可以直接输入 quyu] 来选择 quyu 这个词的后一个字。(同理,[ 可以用来选择前一个字)。但是大多数智能拼音输入法里,你输入了一个词库里没有的词以后,却不能通过类似方法来选字。

举一个例子,原版的智能 ABC 里没有“局域网”这个词,而它现在经常被使用。可是“域”这个字有太多同音字了,造词的时候相当麻烦。但是,我们可以选择输入 “ju5yu71wang2”其中的 yu71 就可以准确定位出“域”这个字了。

写这篇 blog 想让更多的开发输入法的程序员看到,不要去钻牛角尖去想如何提高分词的正确率或是拼命的加大词库了。有时候稍微增加一点非技术难点的小东西,用户就能得到极大的方便。

May 04, 2007

用回 google.com

其实 google.cn 出来的第一天,我就把 opera 里的搜索快捷方式从 .com 改成 .cn 了。我不太关心时政,也不那么愤青。google.cn 不会出现无缘无故的断开连接,让我的用户体验感上升了很多。平时上网大多是为了搜索技术资料,这个活可是非 google 莫属。

最近一段时间发现 google.cn 也有很让我不爽的地方,那就是个人的搜索历史不再被纪录了 :( 这对我是个相当有用的功能。

今天跟在 google 的一个师兄通了几封 email 沟通了一下后,发现用回 google.com 非常简单。选择 google 首页的 google in English 就可以了,你的搜索请求便不会被重定向到 google.cn 。用 opera 的话更简单,只需要修改一下搜索的快捷方式中的 url ,仅需在后面加一个 &hl=en :D

来至 google 的声音说, google.cn 不保留搜索历史也是有苦衷的。据说主要原因是那个 yahoo 事件。希望了解的朋友自己去 google 一下 "Mr.Wang Yahoo" 这两个关键词 :D 既然干脆不纪录了,那么以后也无可出卖。

不过我不赞同这种解决方法,因为相比 yahoo 事件,gmail 才是一个更好的类比。至于个人用的 google accont ,不像 email 必须向外公布。我用我私人的 google accont 纪录私人纪录,别人只要不知道我用的 accont name ,想调查的人根本无从追究。google 作为服务提供商,只需要拒绝纪录连接 ip 和连接时间就让我很有安全感了。

我个人倒希望 google talk 能提供一种安全通讯模式,在 SSL 通讯的基础上多加一层 RSA 加密,只有通讯双方本地才可以得到信息的明文。google talk 的 server 只做 CA 认证就可以了。

正确的向 WinProc 传递 lua_State 指针

在 Windows 下写一些关于窗口的程序时,如果在软件中嵌入 lua ,那么就很有可能遇到一个棘手的问题:如果你需要用 lua 来直接响应一些 Windows 消息,那么如何向 WinProc 传递 lua_State ,也就是那个充斥于 lua 代码中的 L 。

在 Lua 的第 4 版及以前,这个问题并不突出。因为大多数情况下,我们并不需要嵌入多余一个的 Lua 虚拟机。而 L 这个指针,从 Lua 虚拟机被创建出来以后,就不会改变。那么我们只需要把 L 保存在一个全局变量中就可以了。若是你的程序是多线程的,并且每个线程都开有独立的虚拟机,把这个全局变量放到 TLS 中就可以完美的解决问题。当然一些全局变量的排斥者,会想到把 L 放到 Window 对象的 USERDATA 中,这也未尝不是一个体面的方法。

但是,从 Lua 5 开始,因为 coroutine 的引入,即使只打开一个虚拟机,我们也会面对不同 L 的问题。这个问题早在去年就困扰过我,我和同事一起也讨论并研究过这个问题,当时得到了一些解决方法。今天,我重构代码,又想起这个话题,觉得有必要把当初的思考、结论和今天的想法纪录下来。

首先、莫要以为只跟窗口打交道的 api 才会引发这个问题。WinProc 这个回调函数在 Windows 的设计中非常特殊,甚至 Sleep 这个 kernel32 中的 api 都有可能触发一次回调。最简单最安全的方法是,为每个 windows api 加个壳,在调用任一 Win32 API 前都设置一下全局或 TLS 中的 L ,利用外部手段将 L 传递给可能被调用的 WinProc 。固然这不太美观,但却安全有效。如果你想更准确的知道哪些 API 有可能触发 WinProc 回调函数,可以参考一下《Windows 核心编程》中关于 Windows 消息的章节,或是云风的拙作 中 Windows 编程的小节。

上面这个方案最终成了我们项目中的解决方案。

另一个可以考虑的方案是在所有的 coroutine.resume 和 coroutine.yield 操作中纪录下 L 的变更,因为对于一个 Lua 虚拟机来说,正在活动的 L 只有唯一一个。如果你想改造的彻底点,可以给 Lua 添加一个新的 API ,让它可以从任何一个 lua_State 取到相关的正在活动的 L 指针。以我对 Lua 源码的理解,增加这个特性并不困难。只需要在主线程(指 Lua coroutine 的主线程)中纪录下 coroutine 变更即可。而原本任何一个 lua coroutine 都是可以取到主线程的 L 指针的,所以并不需要特别复杂的流程就可以找到活动的 state 指针了。

去年我把这个建议提交到 lua maillist 中去时,意见被开发团队拒绝了。有点遗憾,不过这也是我欣赏 lua 的一个重要点,整个开发团队都在尽力避免 lua 成为下一个庞大的东西,任何 api 的增加都是非常谨慎的。另外比较高兴的是通过这件事交了一些朋友,比如 DM2 的开发者。他那个时候正在考虑在将来版本的 dm2 中嵌入 lua 来做插件。和高水平的开源软件作者的交流也给了我不少技术上的启发 :D

话说回来,这里提到的问题,未必能被许多嵌入 lua 的 windows 项目重视。往往传递了错误的 L 但程序也可以正确运行。关于这个,我们就需要追究一下 lua_State 到底是什么了。

说到底, lua_State 中放的是 lua 虚拟机中的环境表、注册表、运行堆栈、虚拟机的上下文等数据。从一个主线程(特指 lua 虚拟机中的线程,即 coroutine)中创建出来的新的 lua_State 会共享大部分数据,但会拥有一个独立的运行堆栈。我们在 WinProc 中调用的 lua 函数,如果不做任何线程切换操作,那么它运行过程对运行堆栈来说就是干净的,不会带来什么,也不会带走什么。只要给它一个合法的 L 就能够正常的运作。致命的错误只发生在线程切换之时。如果代码工作在非激活状态的 L 上,运行上下文就不能正常工作。想像一下,如果你的软件的整个框架由 Lua 解释器驱动,当你从 WinProc 中俯视 C 的调用栈,你一定能发现在很底层曾经有过一次 lua_call 的调用,被传入的 lua_State 很有可能跟你现在拿到的不同。万一你调用的 lua 脚本中出现了 lua_yield 的调用,被 yield 的就不再是正在活动的的线程。而活动的线程并没有结束本次 C 函数调用。这将触犯使用 lua coroutine 的大忌:coroutine 并非真的线程,它并不拥有 C 层面上的堆栈。这一点才是错误传递 L 可能导致程序 crash 的根源所在。

ps. 让 lua 的 coroutine 成为真正的 C coroutine 也并非不可能。Lua JIT 的作者作的 coco 库就是干这个的。它的内部实现采用了 Windows 的 Fiber ,每个 croutine 拥有真正的 C 堆栈。

May 03, 2007

悠长假期

五一长假,因为护照马上五年期满,出入境管理处假期不上班,我平时又没空回家办这事,所以提前一天回来了。请了一天年假,部门行政提醒我,到六月一日前,我还有六天年假没用掉。哈,这几年,似乎我还没有哪年把年假休满了。对我来说,无所谓工作,白天写写程序,就是件很快乐的事情了。每天能做让自己快乐的事情,又怎所谓假期呢。

到家三天了。归程原先订的是机票,中间因为提前回家的缘故还改签了一次。后来听说火车大提速了,正好碰上博文视点的朋友同行,在他们的怂恿下把机票退掉了。南航电子票这点就是方便,鼠标一点,什么都办好了。火车卧铺夕发朝至倒是方便,床上也好放行李,我便把琴带上。在家八天,不可荒废了功课 :D

可惜这火车还是不对我的生物钟,上车便睡不着,直到把 psp 打的快没电了,怪物猎人中杀了两条龙,终于睡去,早早醒来便到了站。我在想啊,如果这车可以凌晨发车,中午到就完美啦。武昌站正在修缮,门口堵车。不知道什么时候武汉的交通也这么不通畅了。硬是走了快一个小时才打到车,紧接着去办了护照的事情。劳累一天,到家倒在床上睡了一下午。

其实我这人也不是不能累着,就是不能乱了睡觉的时间。否则一天的没精神。

在家也没别的事,就是陪陪父母。这两年老朋友,老同学也渐渐的在武汉见不着了,平常联系的也少。基本上每次长假我都是在家窝着。父亲爱上了养花,整天在家里看护他的花花草草,据说还当上了某个花友论坛的版主,每天还有例行工作去删删广告帖。家里四处望去,露台、窗台上满是绿色,心情舒畅。

前几次回家都是看书,这次只带了本琴谱。这两天每天都花上两三小时练琴。我还没入门,《秋风词》尚弹不来;今天练习《长相思》感觉还不错。只是弹久了左肩胛有点酸痛,自己琢磨着可能是坐姿不对,再研究研究。

晚上睡觉前总要打一局《怪物猎人2》。最近这个游戏又让我有点郁闷了,村长四星任务最后那只风翔龙老是搞不定 :( 。我这个动作游戏苦手偏偏又喜欢上这个极其强调动作感的游戏。这次倒是要看看自己能忍耐到什么程度再放弃。

这次回家破例把工作也带了回来。家里的机器上没装 VC ,从前我是不在这上面做开发的。另一个原因是家里的椅子总感觉没公司的舒服,坐上去没编程的冲动。不过这回,发现自己摆脱 VC 后,编程的兴趣日趋加强了。昨天晚上居然写了一通宵程序依旧精力旺盛。一个舒适的开发环境,还真不关椅子的事儿。

就这样不知不觉的,长假过了一小半。

May 02, 2007

实现一个 timer

前段时间写过一篇 blog 谈到 用 timer 驱动游戏 的一个想法。当 timer 被大量使用之后,似乎自己实现一个 timer 比用系统提供的要放心一些。最近在重构以前的代码,顺便也重新实现了一下 timer 模块。

这次出于谨慎,查了一些资料,无意中搜到这样一篇文章:Linux内核的时钟中断机制 。真是一个不错的设计啊 :D 和我的 timer 实现的思路是一致的,但是在细节上要优秀。

linux 的这个实现方法的优点是把事件按回调时间距离现在的远近分成了多级。我早先的实现考虑到游戏通常不会设置很长远的事件,所以只分了两级。事实上,巧妙的安排每级的数组容量,利用取模操作,处理的速度非常的快,不会因为只分两级或是分成更多级别而受到影响。

昨天晚上重写了一遍 timer 模块,居然只用了 100 行代码就完成了,篇幅较上次写的大为缩短。

我的实现方法和那篇文章中所述 linux 的实现有所区别,这并不是因为我的算法更优秀,而只是因为要解决的问题更简单罢了:

我认为实际上 struct list_head vec[TVR_SIZE]; 这里这个数组只需要开 [TVR_SIZE-1] 大小就够了。因为每级的数组的第 0 项永远都会为空,其内容全部包含在近一级别的各个数组中。而全部 5 个数组正好覆盖 [0,0xffffffff] 。

cascade_timers 这个操作并不需要每次 run 的时候都做,而只需要在恰当的时刻一次做了即可。我们在 add_timer 时不需要理会相对时刻,而只需要处理绝对时刻的事件。

这样做存在两个潜在的问题,一是 run 的时候,速度有所波动,特定时刻需要处理额外的 cascade_timers 操作,比起每次每次都调用 cascade_timers 来说,这个时刻处理的数据量会增加。但我个人认为还不至于造成被人感觉的到的停顿感;二是采用绝对时刻的话,32bit 来表示时间值对于太长时间有可能溢出。好在游戏 client 程序不需要 7*24 小时工作,40 亿个 ticks 足够了。

另外,我认为 del_timer 的需求是完全多余的。如果真的有杀掉事先注册的事件的需求,我们完全可以由 timer 的参数来决定在它被触发的时候是否需要被 cancel 掉。而增加从外面主动杀掉的方法,只会增加接口的复杂性。取消这个设计后,代码会简洁很多。至少在内部实现上,不再需要双向链表。

最近一两年的开发经验让我感觉到,通常游戏中用到的 timer 回调函数往往只有唯一的一个,而仅靠参数就可以区分要做的事情。(这得益于脚本的嵌入,真正的回调函数并不需要是一个独立的 C 函数,而是一个脚本函数)

所以,我们并不需要在 timer 结构中纪录下 callback 函数指针,而只需要在 run 的时候统一传入一个即可。这样的设计比之 linux 的实现有更多的灵活性。如果真的需要支持不同的 C 函数回调,完全可以把函数指针填到参数中。因为大多数情况下,参数并不是一个数字,而是一个结构指针,如果让回调函数去负责回收内存,设计就略显丑陋了。

最终,我的 add_timer 原型只需要这样:void add_timer(void *arg, int time) 。而 run_timer_list 则需要多传递一个 callback function 。如果需要自定义的 c callback function ,可以扩展 arg 结构。例如:

struct timer_arg { void (*callback)(int arg); int arg; int cancel; }; static void timer_callback(void *arg) { struct timer_arg *a=(struct timer_arg*)arg; if (!a->cancel) { a->callback(a->arg); } free(a); } /* 可以使用 run_timer_list(timer_callback); 来处理 timer */