« November 2005 | Main | January 2006 »

December 30, 2005

当编辑器也成为游戏

最近我们立了个新项目,一个 2d游戏。和另一个主要的 3d 项目同时进行。这样比较方便更充分的利用资源。2d 游戏的技术已经很成熟了,所以我希望在两三个月内可以完工。

虽然以前的 engine 是现成的,但是最近脚本研究的比较多,所以我还是给出了个关于嵌入脚本的计划,把原来的 engine 重新包装一下,改成完全脚本驱动的。

说起做 2d 游戏,一般少不了做一些编辑器,编辑场景,素材什么的。最近动了下念头,想把脚本接口弄的更好用一些,干脆用这玩意做编辑器试试。随手 100 多行脚本写了个简单的场景编辑器。也就是可以往地图上随便扔点什么摆摆位置等。

原本也就是写着玩儿,检验一下脚本封装后的易用性,也好教一下其他做程序同事用脚本。

我把这个玩具交给做美术的 mm 后,同时也教她打开脚本文件,可以通过改一些字符串做一些配置。没想到她居然生出兴趣来,向我问了每一句逻辑的含义,并且兴致勃勃的修改起来。

原来写编辑器本身也可以当作是一个游戏啊,何况交到美术手上,什么图片动画素材都是信手拈来。其实早应该教美术学着写点程序了。似乎他们可以自己完成一些需要的功能,这样开发进度或许能够快很多。

December 27, 2005

基础不等于简单

今天为了我那本书,在 <a href="http://www.china-pub.com/member/bookpinglun/viewpinglun.asp?id=27924">china-pub 书评</a>上跟人理论。

表面上看起来是争论 SendMessage 做线程间如何工作的问题,但是我想表达的是另一个观点。那就是,基础的知识并不简单。

这个朋友对我的书评价很低,不过我想他人很好的,而且出发点应当也无恶意。我拿其中一段评语做文章,即“第五章:Windows类。(本书只负责简单介绍,要精通的自己找去。我推荐两本啦:如Advance Windows和Windows Internals)”

这章内容我花了点时间写,也改过几次稿,还算比较满意的。

Windows 编程的确我讲的是基础,但是扣上简单介绍的帽子却不那么让人接受。其实,越是基础的东西就越不简单。当一个系统做到一定规模后,如果还能继续做下去,那么它的根基就必定有诸多玄妙了。Windows 也是如此,我们从其发展轨迹,从它的结构上可以学到许多正面和反面的经验。这对我们理解 OS 是很有好处的。

我写这一章时,想到的是,一个 Windows 游戏程序员究竟需要怎么了解 Windows。全面的知识是通过实践积累的,但是基础怎么构建却很重要,这决定了整个知识体系的掌握。最终我决定只写最基本的东西,但是要好好的写,尽量写出一些细节,但又可以成为一个封闭的知识体系。如果需要多写一点东西,就牵扯出大堆相关知识,对于这本书是不合适的。

我想这样写我自己也是一个尝试,其实书中讲的一些东西,要到比较专业的 Windows 书中才会提到,而那些书却是一个个大部头,看一遍需要太多的精力。入门简单的 Windows 书籍看起来轻松,却忽略掉太多游戏程序员需要知道的东西。我希望我写的东西可以给没有接触或少接触 Windows 程序设计的程序员一些帮助,可以让他们有一个好的起点。

December 25, 2005

虚拟机之比较,lua 5 的实现

前段把自己的虚拟机和编译器完成后,曾经和 lua5 做过一个比较。比较的结果很沮丧,我的虚拟机只能达到 lua 5 一半多点的速度。所以很不服气的又读了一段 lua5 的源码。而之前我是一段一段的看 lua source code 的,甚至 lua 4 和 lua5 的是在不同时期去读的,当然我也知道其间巨大的不同。

其实,对于简单程序来说,我的虚拟机是有速度优势的,而且比 lua 快很多,我把它归咎于 coding 的技巧。但是在设计方向上却败下阵来。因为 lua 5 早已经是基于寄存器的虚拟机了,而我还在用基于堆栈的虚拟机。虽然我对其做了改良,向基于寄存器方向做了靠拢,但是还是不如纯粹的寄存器虚拟机。

最近几天仔细考虑了基于寄存器的虚拟机的实现难度,虽然自己也可以继续干,但是目前项目很紧,决定先缓一阵子,多来点思考沉淀吧。

今天休假,读了一些信箱里订阅的 lua maillist ,想看看 lua 5.1 到底做了些啥改动。由于最近自己做了好些类似的工作,更容易对 lua 的进展去理解了。最后发现,lua 的改进集中在 GC 上面。这点很合我意,其实我自己实现的东西,最得意的莫过于 gc,绝对是优于 lua 的。lua 现在在做分代 gc ,我在考虑并行的方案。大约都是为了解决 gc 的一些个头痛的东西。不过 lua 的 gc 终究不是内存整理的,在受限内存环境下,表现相对不是特别好。另外,lua 为了最求速度等,在深层次递归的支持上也有些问题,会导致堆栈满。我曾经写过一个用递归算数列和的程序,递归层次过深,lua 就处理不了了,我的虚拟机是可以胜任的。当然这对一般的应用都不是问题。

毕竟 lua 发展了 10 多年,可以借鉴的东西实在太多了。我那区区三周的玩具就当是练手的开始吧。今天仔细读了一遍 <a href="http://www.tecgraf.puc-rio.br/~lhf/ftp/doc/sblp2005.pdf">the implementation of Lua 5.0</a> ,如果有人对脚本语言实现有同样的兴趣,推荐阅读。

从这个 paper 中我们可以了解几件事情,虽然通过读源码也可以了解(我就是先通过阅读源码的)但是读这个可以更休闲一些。

lua5 已经是完全 Register-based virtual machine ,可以说是世界上第一个被广泛应用的register-based 脚本虚拟机了。这点,现在的 Java JVM 还有 .NET 都还是 Stack-based 。据说 perl6 打算做成 Register-based 了 :) 当然我的语言也有此计划 ,呵呵。Registere-based 虚拟机相对难写,看来是个挑战。

lua5 优化了 table 的实现,这点我前面的 blog 里提到过,这篇 paper 也做了详细阐述。

lua5 增加了 coroutine 的实现,这点我考虑过,自从我把自己的虚拟机改成系统堆栈无关后,做多几个 thread 无非创建多一个堆栈而已,不难实现。 lua5 的 coroutine 也是每个 thread 有独立堆栈的。(实际上有两个堆栈)

lua 也是一个one-pass 的基于递归下降算法的 compiler ,paper 中提到,one-pass 的 compiler 是 hard-written 的,这点我是深有体会啊。写 compiler 那几天,脑子里翁翁乱叫,写了两整天不敢向仓库提交一行代码。不过写出来的好处是显而易见的,就和 paper 里说的一样,smaller, more efficient, more portable, and fully reentrant :)

前几天在想,一个弱类型的语言,Object 的描述信息能不能比 lua 这种更小。lua 用了一个独立的字描述类型,然后用 union 来存放不同类型的数据,这个也是我用的方法。前几天想了个办法,那就是一般指针由于对齐的原因,末两位永远都是 0 。(如果我们以 8 对齐的话,末三位都是 0)这样就有点额外的信息来保存数据类型了,整数可以用 30 或 31bit 来表示都是够的。

今天读这篇 paper 发现前人已经用过了,比如 Smalltalk80 ,不过 paper 解释了 lua 不这样做的原因。当然,我自己的语言倒是可以一试的 :)

至于 lua5 用的指令集,每个 instruction 只用 4 个字节,其实现方法还是很巧妙的,这个前几天读源码的时候已经领教过了。当时我想找到我的语言的速度究竟慢在哪里,才发现是循环中, i=i+1 这样的操作。基于寄存器的虚拟机自然可以运行的更快了。而且我的虚拟机的 instruction 是 8 字节的,而 lua 却只用 4 字节,数据短了,效率也能提高。

读完这篇 paper 感觉很多地方 lua 都是鄙视 python 的低效 :) 这点跟我在 GDC2004 上参加的 lua round table 的感觉一样,一下就可以发展成 lua 和python 的"派系斗争" :) 我想 GDC2006 上 lua 派会更理直气壮一些,毕竟两年前用 lua4 的人远不如 lua5 的人,(我发言的时候特地让用 lua5 的人举了次手 :) 这次随着 lua 5.1 的 release ,lua在游戏行业中的地位将不可动摇了。

随便提一下 LuaJIT ,感觉是个有前途的 project
<a href="mailto:http://luajit.luaforge.net/">http://luajit.luaforge.net/</a>

平安夜借机玩了一下

最近工作实在太忙,每天一睁眼就想赶紧来公司写程序,当然还有开会等杂事。

今天是耶教的节日,庆祝他们教派的创始人诞辰的。昨天晚上算是耶老他母亲最值得纪念的一夜了,俗称平安夜。我是不信耶教的,不过现在节日这个概念都淡化了,关键是有机会朋友聚一聚,闹一闹。既然攀友相约,难得开心聚会一晚。

晚上到的人很多,大半我不认识,应该都是这里攀岩的老前辈了,当然还有很多没见过的mm。没想到当场的几乎都被迫上台演节目,我啥都不会,只有稍微拿手的冷笑话,表演的还算成功,几乎没有人笑 :D 还有些拿不出节目的只能干体力活了。好在高手众多,什么爬梯子,过屋檐,钻桌子自是不在话下。

过了十二点跑去天台鬼呼狼嚎,吓着了不少路人。大家兴致很高,结果把所有的 mm 都抛了一次,累的我一身汗。接下来不过瘾,攀岩的朋友估计都是臂力惊人。大多数 GG 也被抛向空中,不过我看大家更多的是受了无极的刺激。只是,GG 们的待遇差点,上去后都不负责下面接的。当然玩户外的人都比较皮实,也摔管了 :D

christmaseve.jpg

December 20, 2005

把结构定义成一个数组

今天读 freebsd 的源码时发现一个小技巧,经过同事指点,恍然大悟。原来 C 里面还是有好多东西自己不知道的啊。

typedef struct _jmp_buf { int _jb[_JBLEN + 1]; } jmp_buf[1];

这个是 setjmp.h 里的一行定义,把一个 struct 定义成一个数组。这样,在声明 jmp_buf 的时候,可以把数据分配到堆栈上。但是作为参数传递的时候则作为一个指针。这样和 c array 的表现一样了。

btw, 读 freebsd 的源码后,感觉头文件组织比 vc 的强太多了。

December 19, 2005

汪达与巨像

以前很喜欢 ico ,在 GDC2004 的时候特地去听了相关的 session,很为制作人员的专注所感动。早就听说《汪达与巨像》,但是最近工作太忙,一直没有玩。今天周末,找同事的游戏玩了一下,果然表现不凡。花了一个晚上干掉5只巨像,太有感觉了。

很有攀岩时的那种控制身体的感觉,指间的力气全发泄到 R1 上了。相比较前几天看人玩的时之砂,高下立分啊。虽然我不会骑马,但是我觉得真正骑马的感觉也应该是游戏里那样的吧。

想玩这个游戏的朋友听我一个忠告,千万不要去看功略,也不要让玩过的人指点。跟 ico 一样,我也是任何资料都没有看的条件下玩的,非常有乐趣。如果游戏的秘密提前知道了,乐趣讲打上折扣。

这才是艺术品啊。

<a href="http://media.ps2.ign.com/media/490/490849/vids_1.html">这有一些预告片可以下载</a>,这些可都是游戏玩的时候的画面,不是过场喔。

December 16, 2005

_ftol 的优化

_ftol 是什么? 当你写 C 程序的时候,(int)float_v 就会被编译器产生一个对 _ftol 这个 CRT 函数的调用。 上个世纪听一个做 3d 的朋友提起过,用 x87 指令实现的 _ftol 会很慢,一般用整数指令提供。当时提在心里,2000 年的时候在 RISC 上做开发 (ARM 指令集) 曾经写过一些整数模拟浮点的函数,曾经写过这个转换函数,日子久了,现在也找不回来代码。不过对浮点的 IEEE 标准还是比较清楚的。去年写过一篇 浮点数的精度控制问题 的帖子放在流言中。当时已经被骂过了。 今天工作时又遇到关于浮点数的问题,再写篇 blog 吧,或许还是找骂贴 :) 懒的重写 _ftol 的整数指令版本了,google 搜了下,发现果然有人也做过。http://www.flipcode.com/cgi-bin/fcarticles.cgi?show=64008 就是这么一个函数: int ftol(float f) { int a = *(int*)(&f); int sign = (a>>31); int mantissa = (a&((1<<23)-1))|(1<<23); int exponent = ((a&0x7fffffff)>>23)-127; int r = ((unsigned int)(mantissa)<<8)>>(31-exponent); return ((r ^ (sign)) - sign ) &~ (exponent>>31); } 当是效率比较高的。我想,日子已经过去这么久了。当初朋友跟我提这个事情的事情大约是 98,99 年。上面翻出来的老帖是 01 年的。我现在的机器不错,今年新买的 P4 双核的,还是测试一下比较放心。 注:这个函数不能直接替换 CRT 中的 _ftol , CRT 的 _ftol 并不通过堆栈传递参数。 马上随手写了下面的测试程序: #include #define RDTSC _asm _emit 0x0f _asm _emit 0x31 #pragma warning (push) #pragma warning (disable: 4035) inline unsigned __int64 timestamp() { __asm RDTSC } #pragma warning (pop) int int_chop (float f) { int a = *(int*)(&f); int sign = (a>>31); int mantissa = (a&((1<<23)-1))|(1<<23); int exponent = ((a&0x7fffffff)>>23)-127; int r = ((unsigned int)(mantissa)<<8)>>(31-exponent); return ((r ^ (sign)) - sign ) &~ (exponent>>31); } int test1(float f) { return int_chop(f); } int test2(float f) { return (int)f; } int test3(float x) { int t; __asm fld x __asm fistp t return t; } void test(int t,int (*f)(float)) { int i; for (i=0;i 运行结果如下:
---timing 0---
use int 4449676
(int)   4583873
use x87 1491980
---timing 1---
use int 6097315
(int)   4603592
use x87 1662360
---timing 2---
use int 2427691
(int)   4532759
use x87 1445269
compiler 内置的 _ftol 表现不怎么样,比整数版还是慢了一倍。那个浮点版本是做参考的,虽然快,但是语义和 C 语言要求的不太一样,依赖 rounding mode 的设置。所以不推荐使用。 关于 double 向 int 转换,参考另一篇 blog :double to int 神奇的 magic number

December 15, 2005

又让 bjam 郁闷了一把

早上到公司,同事告诉我 jamfile 又写错了 :( 在一个上级目录创建出来的 static lib 在下几级目录上想引用的时候,如果逐级在 project 里标上 <library> 就会出错。

这才发现,原来 jamfile 会完全 inherit 父目录上的 jamfile 的 project 属性。这点对 <include>这个 feature 做的很好。inherit 后会加一级 .. 但是 <library> 却不行。(原来我一直用 <source> 的,今天查代码才知道还有个 <library> 的 feature)

上 google 搜了一下,找到这篇: http://www.crystalclearsoftware.com/cgi-bin/boostwiki/wiki.pl?Boost.BuildV2/Todo Core changes 的最后一条: If we put <library> foo//bar in project requirements, then derived projects should get inherit ../foo//bar, otherwise things won't work.

晕死,原来是 ToDo 啊,懒的自己改了,等 bjam 更新吧。

btw, 原来工具太方便,我们对其要求就更高。想当年用 VC IDE 时可没这么许多要求。点鼠标一点点设也这么过来了。

December 14, 2005

收到一些读者的来信

今天又收到几封读者来信,大约会来信给我的读者,多是喜欢这本书的。如果不喜欢,也不至于写 email 来骂吧 :)

最近也看了一些朋友的 blog ,有提到这本书的,当然会仔细读一下。发现,不喜欢的人估计跟喜欢的人一样多。不过也不太失望,指望自己写的东西能迎合所有人本来就不切实际,而且每个人的经历不同,对编程这个事情的理解不同,或者读书的出发点不同,都会可能得到截然不同的结论吧。

而我也了解自己的文字表达能力,实在是不怎么样,心中终究是有一些惭愧的。

不过值得欣慰的是,寄回家的书,妈妈很喜欢。父母读了能高兴,书也就不白写了。

而最近几封热情洋溢的 email,让我感动不已。他们应该是真心的喜爱了,在 email 里写下数千言,仅仅只是给我这个作者分享一下他们的心情,我是由衷的感谢。如果书能帮助一些人,将是我最大的快乐。我从一些朋友身上看到了自己以前的影子,或许几年以后,他们将成为国内游戏行业的主力军,谁又能知道呢。我更希望写的这本书,可以让这些朋友少走一些弯路。

也有一些朋友仅仅是得到了一些共鸣,呵呵,能给人带来回忆的文字其实也是不错的。每天不停的向前走,让工作填满了所有的时间,我现在花在回忆的时间都觉得奢侈了。似乎那是种美好的感觉。

批评的声音通常来至于内容过于分散,而没有重点,这里再次写下我从事游戏编程这么多年来最终沉淀下来的经验:那就是,任何新的技术都不会是重要的东西。而拥有对编程和计算机的本质的了解的基本功,和永远不消逝的好奇心作为学习新东西的动力才是最重要的。

能写在书中的,只有那些我认为应该搞清楚的东西的一部分,而太细节的技术,不是应该由我去总结的。如果愿意读我的书的朋友,我给一点点建议:如果你认为书中写到的章节你觉得艰涩,没有解释清楚,请大略的了解一下。等你对相关知识有足够了解的时候,能想起来的话,再回头看看,说不定能有一些新的启发;如果觉得书中的东西太过浅薄,请不要妄下结论。如果能有多点时间,再仔细的读一读,说不定可以发现一些有趣的东西。因为我在写一些原本以为简单的技术时,也曾经发现自己也有被忽略的死角。

这本书不能抱有太功利的心态来读,我从头至尾都没有提到怎样做好一个游戏的秘籍,也没有不为人知的技术秘密。只想轻松点,把我自己知道的一些东西讲出来。在技术方面,我是没有保留的,也从没想过要保留什么,最近在写 blog,我想以后技术方面的研究,我尽量都写在 blog 上。之所以没有写我所参与的游戏的具体制作相关的东西,是因为我觉得写一个游戏并没有什么神秘的地方,无非就是那些编程的基础知识的累积。

至于对这本书不屑一顾的朋友,我能充分的理解。如果一开始就决定不在上面浪费时间,那么就不用读了。我想这是一本平淡的书,不去读它不会有任何损失的。

如果读者能花一点时间给我提一些建议,或者帮我找出一些印刷错误,那我是十分感激的。这里有一个勘误建议的页面可以自由发言。

<a href="http://blog.codingnow.com/2005/12/printing_errors.html">《游戏之旅——我的编程感悟》勘误建议</a>

ps. 最后列出一些朋友写的 blog,多少跟这本书有点关系,作为收藏吧。
<a href="http://www.dragonson.com/diary.asp?year=2005&month=12&day=10">http://www.dragonson.com/diary.asp?year=2005&month=12&day=10</a>
<a href="http://lixianhuei.cnblogs.com/archive/2005/12/08/292829.html">http://lixianhuei.cnblogs.com/archive/2005/12/08/292829.html</a>
<a href="http://dreamhead.blogbus.com/logs/2005/12/1676755.html">http://dreamhead.blogbus.com/logs/2005/12/1676755.html</a>
<a href="http://spaces.msn.com/members/lawyu/Blog/cns!1pkfBM6aO46LAO_584TwWg_g!132.entry?owner=1">http://spaces.msn.com/members/lawyu/Blog/cns!1pkfBM6aO46LAO_584TwWg_g!132.entry?owner=1</a>
<a href="http://blog.vckbase.com/lostpencil/archive/2005/12/13/15958.html">http://blog.vckbase.com/lostpencil/archive/2005/12/13/15958.html</a>
<a href="http://bbs.gameres.com/showthread.asp?threadid=48869">http://bbs.gameres.com/showthread.asp?threadid=48869</a>

December 13, 2005

让 bjam 支持 fx 文件的编译

我们新的项目已经不再使用 VC 的 IDE ,而当初选择一个合适的 make 工具很花了一番工夫。最开始想用 makefile , 大家都用的。后来觉得很繁琐,不是很适合我们这个项目。然后选择了<a href="http://www.perforce.com/jam/jam.html">jam</a>。(当然其间也试过 Ant 等,在此不表) 花了很长一段时间熟悉 jam 的语法,和 C 也极大的不同。好不容易学会点了,同事怂恿我试试 <a href="http://www.boost.org/tools/build/v2/">bjam</a>,方知道 boost 那帮人的确 BT ,把 jam 这个小玩具的功能发挥到此般。看了人家给 jam 扩展的脚本,自己也就打消了在 jam 的基础上弄出点东西的想法,还是直接拿来用吧。

在 bjam 的基础上扩展东西,其实说容易也不容易。扩展时不用写太多,但是要弄懂 bjam 的脚本到底怎么在工作是件很苦难的事。我想 jam 的思维方式也作实和 C 差的很远,以至于大多数程序员在写 jam 脚本的时候都容易犯错误。要么 bjam (boost build) 怎么这么长时间了还不太稳定呢。

这次,我需要用一个外部工具 fxc.exe 来编译 .fx 的脚本,目标文件是 .fxo 。我想做 3d 的程序员大多用过吧。这里贴出一个 jam 脚本,如果有一天你和我一样选用 bjam 的话,可能用的上。

----fx.jam--------
import type ;
import generators ;
import scanner ;

type.register FX : fx ;
type.register FXO : fxo ;

type.set-scanner FX : c-scanner ;

generators.register-standard fx.inline-file : FX : FXO ;

actions inline-file
{
fxc /nologo /T fx_2_0 /Fo $(<) $(>)
}
----------------------
用的时候在 project-root.jam 中加上 import fx ; 即可。

December 11, 2005

12K 的虚拟机

今天把脚本虚拟机整合到正在开发的引擎中去了,按新引擎的跨平台2进制格式 build 出来,只有 12.6K :D 比 lua 小多了 ^^ 庆祝一下。如果不是现在机器都是 32位了,在 16 位或者 8 位机上,这代码体积还能更小。唉,早几年计算机的地址空间只有 64K 的时候多痛苦啊。

突然想,我们这套引擎给手机用一定很不错 尤其是 gc 部分,比 lua python 什么的更适合小内存环境,可惜我现在对嵌入式开发没啥兴趣。

一个陌生的电话

这周的工作很顺利,居然在周六晚上就可以做完,而没有拖到周日。难得的在家里赖了一下床。

早上接到一条短信,两个电话,其中一个电话打错了。短信是我凌晨发的,索要另一个朋友的电话号码,估计那边朋友已经睡下了,早上起来才回过来。

不过已经很难得了,最近一长段时间,我每个月几乎都没什么话费了,几乎存在于一种闭关的状态,无什么事情干扰。

剩下那个电话,很陌生的声音,“是云风吗?”“我是啊”,“我是 LH(取声母)”,.....
我搜索了一下最近 cache 的记忆,一下想不起是哪位大哥了,实在是心里愧疚。

接下来,就有点莫名其妙了。那边说道,你的那个 blog 不要再写了 ..... 我还没有睡醒,听了半天才稍微明白了点过来。莫非又是前段那些事情?可是我这几天都没空理那事了呀。

再听下去,原来是说 <a href="http://blog.codingnow.com/2005/12/parallel_gc.html">基于并行处理的垃圾回收方法</a> , <a href="http://blog.codingnow.com/2005/12/stack_less_vm.html">实现一个系统堆栈无关的虚拟机</a>这两篇垃圾技术文章不要登出来了,如果没有什么好写的就不要写,免得坏了名声。

我一阵的好奇,原来遇到高人了。这些是我最近的一些工作的记录。原来长期不闻窗外事,已经成了井底之蛙了。花了我些时间做的东西,或许一点价值都没有。听到这里,赶紧发问,关于 gc 是不是有更好的解决方案,这也是我一直关心的问题。可惜了,那个朋友不太肯教我,说是如果面谈,可以告诉我,但是电话里不方便说。

技术问题也不方便说?我追问了一句。高人只好道出实情,他正在被人监视,说话不方便。哇,原来这样啊,为了避免他话说多了说漏嘴,我接着寒碜了几句就挂掉了。

挂掉电话缩进被窝里,不禁有点担心。应该暗示着问一下,是不是需要报个警什么的,脑海中闪过电影中被人威胁打电话的镜头。 或者问到地方,有机会登门拜访讨教一下也好。

December 10, 2005

基于并行处理的垃圾回收方法

最近在做的一个虚拟机是基于垃圾回收(garbage collection)的,采用的是标记整理算法。这种算法的好处在于不需要 太多额外的内存,而且可以将内存中的 garbage 完全压缩掉。至于长期占用的内存空间,会被压到内存块的底部,整理时无须移动。

对于需要长期稳定运行的服务器程序,在 32bit 操作系统下,受限于有限的地址空间, gc 技术是根本解决内存碎片问题的最佳通用方案。

我计划在服务器程序中,全部程序逻辑都放在虚拟机内运行。由于和 client 程序不同,不用太考虑物理内存的占用,所以计划在服务启动的时候就预设 1~2G 的内存块供虚拟机使用。在这个内存块耗尽之前,所以涉及内存分配的操作都会相当的快了。但是一旦发生 gc ,光是扫描一遍内存,都是非常耗时的。所以我不得不考虑解决方案。

很自然的,我想到了并行技术。如果可以在 gc 的过程,不太影响逻辑线程的运行,那么即时 gc 的过程慢一点,我们也是可以接受的。而且如今硬件多核技术的发展,如何充分利用多个 CPU 并行处理,将是未来软件设计的重点方向。

我暂时想到的方案是这样的:

假设对一个 2G 的内存块做 gc 的时间是 10s 。(只是一个估算,没有实测。我想按今天的内存总线的吞吐量,10秒内做完应该不是难事)那么 10s 内,软件产生的新的内存分配的需求应该不是特别的大,比如 8M ,就可以满足其要求。那么我们就预留这么一小块内存做备用。

另外,程序运行堆栈是永远不需要做内存整理的,所以我们也可以把它刨开。剩下的就是一个超过 1G 容量的巨大的内存堆。实际上,在 gc 过程中,能对这个堆做的数据修改也是极少的操作。假如我们可以在 gc 发生的时候,将内存堆以 copy-on-write 的方式共享给另一个进程。unix 下可以直接 fork 子进程,windows 下可以 share memory。在共享的那一刻,我们保证这是一个原子操作。然后, gc 进程对堆的整理操作不再影响逻辑进程。而逻辑进程所以产生的内存分配请求,都在备用的小内存堆中完成。而对正在 gc 的堆的任何写操作,都 log 在备用堆上。

一旦 gc 进程工作完毕,可以把整理过的内存堆切换回逻辑进程。逻辑进程则停止手头的工作,将 log 过的操作逐一提交。(这里,gc进程应该给出做内存整理时产生的新旧地址对照表,需要对 log 的操作信息做一个先期处理) 然后,逻辑进程将备用堆中的信息移动进主内存堆。这些操作虽然繁琐,但是数据量远远小于主内存堆,所以可以在极快的时间内完成。

maillist 上的相关讨论:
<a href="http://codingnow.com/pipermail/cpp/2005-December/000910.html">http://codingnow.com/pipermail/cpp/2005-December/000910.html</a>

实现一个系统堆栈无关的虚拟机

最初设计虚拟机时,bytecode 中的函数调用会产生一个 native code 上的实际的函数调用。似乎这样写比较容易。但是这样做,想实现bytecode单步运行却很困难。只有另开一个线程监护跑虚拟机的线程,在每步运行后可以挂起,而不破坏相关的堆栈。

所以,我想实现一个系统堆栈无关的虚拟机。

把虚拟机改造一下其实是很容易的。实际上,每次虚拟机中的函数调用,堆栈上保存的只有调用点,堆栈顶的位置,而需要多少个返回值。

当前运行中的函数体也需要保留下来,因为我的整套虚拟机的内存管理是 gc 的,包括 bytecode 本身。不记录函数体对象,很可能让函数体本身在一个 gc 中灰飞烟灭。

这样一共是四个参数,单独建一个 table 模拟堆栈放即可。这个堆栈我以前就创建了,只不过只放了函数体对象而已。稍加修改就可以适应新的需求。

在考虑做这个新的虚拟机运行方式的版本时,我考虑了一个问题。如果支持单步运行,那么bytecode运行效率就会下降。为了解决这个问题,我决定保留以前的运行方式。用继承的方法,给虚拟机增加新的运行方式。

由于考虑到,我在单步跟踪环境下,调用 C 函数,C函数中又可能以非单步运行方式回调虚拟机中的函数。我必须保证两种运行方式的堆栈内存布局一致。但是在使用系统堆栈的连续执行方式下,虚拟机内堆栈大部分信息都填nil即可。

有了系统堆栈无关的运行模式,日后加 coroutine 将会非常简单。

原来以为以上工作做起来会比较麻烦,今天晚上试了一下,只花了2小时就搞定了:)
如果有时间,用 .net 做个 IDE 玩玩。到今天为止,整套脚本都实现完毕了,虚拟机和编译器皆工作正常。脚本可以实现有限的 OO 特性。主观臆测,运行效率不差于 lua 。期望在实测中超过 lua 。

肯定强过 lua 的一点是,这个虚拟机是基于真正的内存整理的 gc 算法,应该比较适合服务器程序的长时间工作。数据持久化工作也相对容易。

December 08, 2005

闲话 java

今天收到一封读者来信,顺着 email 找到了他的 blog 。看到上面扯到 java ,<a href="http://dreamhead.blogbus.com/logs/2005/12/1676755.html">http://dreamhead.blogbus.com/logs/2005/12/1676755.html</a> 忍不住也闲话两句。

最初,作为一个 die-hard 的 C++ 程序员,我曾经是很瞧不起 java 的。不知道时候还有朋友保留我在 5 年前,作为一个自由程序员印过的私人名片。当时便直接把自己对 java 的不屑一顾签写在上面。

日子过了好久,人的思想也在一步步改变。在我写那本书的时候,对 java 的态度已经好了许多。至于现在,离那些文字又过去一年,java 于我,可以说很有好感的,了解也逐渐增多。

记得在前不久的 C++ 会议上,曾有对 C++ 的批评。说是对于设计模式这些于现代程序员应该耳熟能详的名词,居然有许多 C++ 高手还很陌生,至少在碰到问题时,脑子里闪现的第一个念头不是这些。而换作一个 java 程序员,即使使刚入门不久,就可以对一个问题该用哪种设计模式而争论不休了。

我们可以看到不同语言的使用者观察问题的层面和角度居然可以有这么大的不同。

或许真的如朋友笑谈,java 封装和统一了太多东西,导致程序员的智慧无初发挥,只能集中到设计模式上发泄了 :) 而 C++ ,却有无数的方法证明你的聪明。

另一个例子也很恰当:如果在 java 社区,宣布了一向新特性,会使整个社区的开发效率明显提高,即使这个特性会使世界上所有的 java 程序效率损失 10% 。大多数 java 程序员还是会拍手称快。反正 java 在运行效率上的名声已经臭名招著了,大家也不再在乎。而换到 C++ 社区,即使这个新特性只有 0.1% 而不是 0 的性能损失,必然招至一片唾骂声,吵上10年也不可能写进 ISO 标准。在效率问题上,java 程序员更加指望那些为他们写虚拟机的人做出新的发明,然后发布一个报告,谈即新的技术可以使 java 程序运行速度加快即可。

不得不说,C++ 和 java 是在两个层次上的语言。一个从机器模型延续而来,一丝一环紧紧相扣。而 java 语言却从机器层面向上一跃,中间留下一个空挡。阻止程序员去跨越。这使整个社区的人力集中于更高的层面,未尝不是一件好事啊。

我在书中,思想毕竟还是局限了一点。用 C++ 角度考虑问题还是偏多了些。或许,慢慢的,游戏行业真的要演变为 C++ 社区最大的根据地了。

ps. 我隐隐感觉, .net 技术有超越 java 之势。
关于 SIMD ,新的 intel 编译器正在重点考虑向量化技术,让C++编译器自动产生使用 SIMD 的代码,成果显著。

December 07, 2005

给脚本加入字符串类型

最近的工作是给虚拟机加上字符串类型的支持,并让编译器可以生成相应的 bytecode 。思路很简单,就是按 lua 的方式,把所有源码中相同的字符串合并,在 bytecode 中只保留一份。所有提到这些字符串的地方直接对其引用。bytecode运行时,产生的任何新的字符串都会产生新的副本。垃圾等到 gc 时回收。

想起来容易,实现起来还是颇为麻烦的。

首先要解决的是,bytecode在内存时,所有提到的 string 都可以直接是一个地址。但是 bytecode 在没有加载到虚拟机前,任何绝对地址都是不允许的。所以加载 byecode 的过程,不再是简单的内存复制。对 string 做操作时,希望尽量是 0 消耗,不希望出现任何惰性初始化的过程。

现在的解决方案是,扫描源码的过程(我的编译器是一遍扫描的),碰到任何的字符串都被编号。在函数定义中,直接把编号压栈。在非函数定义时,则按编号在一个特定的局部table中取出来。非函数内代码,操作 string 是有消耗的,有一次取 table 的过程。不过因为局部 table 读操作也是一行 bytecode 所以空间消耗没有增加。在注册函数时,扫描函数体的 bytecode 转换所有的编号到绝对地址,待到调用时,就是 0 消耗了。

把全部源码编译完后,自动生成一个注册函数,将所有提到的 string 注册到虚拟机中。最后在生成的 bytecode 最前插入一行调用这个自动生成函数。

自己的方案简述完了。至于虚拟机内的处理也是比较麻烦,不过只是麻烦而已,代码还是一样的要写下去的。
这里闲话几句 java 。

java 中的 string 在虚拟机实现的时候跟 lua 这个方案类似。但是许多 java 程序员并不太知晓。一个事件是从李维那听来的,据说是 tomcat 4 里的问题(我有点记不清版本了),在一个内循环中使用了 string += 的操作。结果这个操作被运行了很次后产生了大量的垃圾,致使 gc 频繁调用。

另一个事件是听我的同事说的,说我们公司另一个主用java做项目的部门的人,在一个项目中用到了持久化的操作。在做 codeview 的时候,我那个同事置疑其效率。然后就有人回去做测试,得出的结论是,java 在<strike>持久化</strike> 序列化 string 的时候效率颇高,几乎没有效率问题。当时听到这里我就笑了,虽然我没写过 java 程序,但是直觉告诉我,某人一定用相同的字符串,放到一个循环中去持久化了 :D 难怪事后得出的结论是,java 持久化不仅效率高,还带有压缩功能。

12月8日补遗:
下面有朋友谈到应该是序列化而不是持久化,吾以为然也。就这个问题上看,我们公司的 java 程序员想用这个功能,把一组 string 写到硬盘上,做的是一个持久化操作。作为 java 程序员的一种共性,他们不会去考虑 IO 操作的消耗,序列化数据的消耗等。但是转述这个故事和听故事的我,都是 C++ 程序员,第一反应却是性能的问题。(当时这个是用在一个性能要求很高的应用中)
至于 string += 的操作,对虚拟机实现用一定了解的程序员会很敏感于内存消耗。当时李维举这个例子是想说明有些 java 程序员太不关心 java 的语言细节和性能。当然正确的做法,java 老手都应该明白,我这个不懂 java 的 C++ 程序员也可以猜到。但是错误发生在 TomCat 正式发布版中的确不应当。

December 06, 2005

新闻从业者的素质

写这篇 blog 可能还是会继续得罪人。不过还是想谈谈。
我不是新闻从业者,但是我想“新闻从业者应该是不偏不倚中立的观察者”这个应该在今天被达成共识。我个人是在泡 wiki 百科中,受到这个类似观点的熏陶的。

可惜 wiki 百科现在被封了,不然我可以列一个上面关于条款中立性的文章大家看。很遗憾的看到,在我认为应该在程序员这个高素质团体,在程序员自己的技术网站,其责任编辑却没有应具的基本素质。

这次网易发<a href="http://news.csdn.net/n/20051206/30525.html">第2份声明</a>,老实说我也觉得态度强硬了一些。但是从 csdn 刊发的标题
<strong>“求职受骗事件”后续:网易公司再发声明 仍极力辩护</strong> 来看,以我个人有限的分析能力,我觉得这个标题是不够中立的。可以看出编辑的主观导向。

原本我在 csdn 上发过言后就没再怎么看过,今天同事用一种聊侃的语气跟我说了件事后,就自己去核实了一下。原来我的一篇发言,被编辑特别优待在下面回了几句,还特别加了红。其个人观点表露无疑。

我觉得这绝对不再是站在一个的中立立场上应有的态度,从做新闻这点看,负责这件事情的编辑真的应该好好培养一下职业素质。如果我是 csdn 的编辑,对别人的观点感到不满的话,会用个人帐号平等的发表观点。而现在这样做,更多的是给人感觉是一个愤青,而不是一个专业的新闻工作者,

现在在检讨自己最近是不是话多了一点,弄的自己为了把预先定的计划完成,每天都工作到夜里3,4点。花在一些无聊话题上的时间实在是多了一点了。至于骂我的人,我想转述今天同事在办公室讲的一个佛家的小故事:

说是的有人要送释迦牟尼一件礼物,但是他没有接受。那这件礼物最后是属于送礼人的呢,还是属于释迦牟尼的呢?

骂人的人亦然。

12月8日补遗:
这个故事讲错了,感谢下面网友指正。这个礼非礼物的礼。

《游戏之旅——我的编程感悟》勘误建议

今天拿到了出版社的样书八本,瞬间被分完 :)整个装订还算满意,随手翻了一下,发现了一些印刷错误。当时没有在意,现在回头想一下,应该有个地方列出来,方便读者。下次重印时也好更正。请大家赐教。

我在个人 Wiki 上整理了 勘误表

如果读者发现了错误,可以在这里留言,我会整理到勘误表中。

相关连接:

Douban 上的书评

China-pub 上的书评

Dearbook 上的书评

December 05, 2005

民可使由之 不可使知之

这两天睡觉前翻翻论语,读到泰伯篇,“民可使由之,不可使知之”。传统的理解就是,可以让老百姓按照我们指引的道路走,不需要让他们知道为什么。这句话是孔老夫子说的,(前面写了“子曰”)

从现在的思想看,估计很多人都会抨击这个观点。然后有卫道者改句读,例如“民可,使由之;不可,使知之”或者是“民可使,由之;不可使,知之。”;还有“民可使,由之不可,知之。”什么的。我自己感觉啊,根本用不着替老夫子开脱。我自己是越来越感到很多情况下真的是“民可使由之,不可使知之”了。

很多事情去花时间跟当事人解释清楚未必是件好事。

在脚本语言中一个取巧实现 OO 的方法

今天,脚本编译器连同前段写的虚拟机全部完工了,很有成就感。
跟 lua 一样,复杂的数据类型我只支持了 table ,这个 table 即可以做 array 也可以做 hash_map 用。一般用 lua 的人都会用 table 去模拟 class 。lua 只对这个做了非常有限的扩展:在 lua 的文档中,我们可以看到

function t.a.b.c:f (...) ... end 可以等同于 t.a.b.c.f = function (self, ...) ... end

就我用 lua 的经验,这个转换用途不是特别大,只是少写个 self 而已。

这次我自己设计脚本语言,针对脚本支持 OO 的问题,特别做了些改进。

看一段脚本,这是用我自己定义的语言写的:
A={};
function A.sum (_self)
{
return .a + .b;
}

function A.print (_self)
{
print(->sum());
return _self;
}

a={A,
.a=100,
.b=200,
};

a->print();

这是一个非常简单的例子。全局函数 print 是我测试程序注册的。我是这样想的,把成员函数放到一张 table 里。这里是 A.sum 和 A.print 两个,放进了 A 这个 table。 然后我创建了对象 a={A,.a=100,.b=200};
这里默认 a[0] 放的是 vtbl, 就是 table 初始化队列的第一项。 如果用 -> 来调用函数的话,比如 a->sum() 就在编译时转化成 a[0]->sum(a)

在函数里,如果用 . 开头的变量,就自动展开成 _self.x 。这个 _self 是函数的第一个参数。 需要在函数定义中明确写出来,但是名字可以随便。不过名字必须用 _ 开头。 同理 ->sum() 就展开成 _self->sum()
所以,在一个成员函数中,我们可以看到所有以 . 开头的变量操作都可以看成是成员变量。以 -> 开头的函数调用,可以看成是成员函数调用。当然,这里所有成员函数都和 C++ 中虚函数的概念相同。如果需要给 A 类写个静态函数,即不需要传 self 的话,可以用 A.static_func() 这样调用了。

我在这里用名字来强制约定变量的类型。_ 开头的全部是局部变量,否则就是全局。这样可以方便很多编译的工作,也让代码比较容易读,在弱类型检查的脚本里,还可以避免一些笔失误。

December 03, 2005

网易求职被骗记?

今天白天有个朋友给我转了这个一个帖子,
网易求职被骗记
<a href="http://community.csdn.net/Expert/topic/4418/4418779.xml?temp=4.925174E-02">http://community.csdn.net/Expert/topic/4418/4418779.xml?temp=4.925174E-02</a>

大约讲的是一个 mm 到网易应聘游戏客服,干了 15 天被告之不符合要求没有录用。按照开始的约定,也没有支付这 15 天的工资。这个mm估计巨受打击,她的男朋友很不服气,在 csdn 论坛上贴了这篇慷慨激昂的帖子声讨网易,应者纷纷。

本来看到这帖子我是一笑了之的,没想到半夜里同事跟我打了个电话,我才知道帖子被转到了 csdn 首页,并且把一个所谓网易官方声明。<a href="http://news.csdn.net/n/20051201/30272.html">http://news.csdn.net/n/20051201/30272.html</a> 放到旁边,还做了个专题 (._.!)

同事转达同事的意思是,跟 csdn 交涉无效,想让我借助私人的关系,让 csdn 妥善处理这件事情。我想了一下,动笔写了封 email。这里贴出来吧,反正打算公开了。

--------------
今天同事给我打电话,提起 csdn 首页一个帖子,就是

网易求职被骗记
http://community.csdn.net/Expert/topic/4418/4418779.xml?temp=4.925174E-02

同事想让我跟你们联系把这个东西撤下来。
而我觉得,本着新闻公开的原则,不应该这样要求
csdn,我也不赞成删贴这种不尊重别人发表看法的行为。不过我个人阅读了这个帖子,有些个人想法,希望你们能看看我说的是否有道理。

这个帖子说的是一个家伙女朋友来我们公司求职的事情。里面的是非曲直我不清楚,但是原贴其实已经说明,那个 mm 是应征的客服岗位,也就是游戏 GM
其实就是接玩家电话还有给玩家回信,回帖子等工作,我不知道她试用的时候是否真的参加了这些工作,或者只是一种培训。但是可以肯定的是,工作跟程序员无关,而且也没有什么程序员相关的技术性,纯粹是服务性的。

这个帖子放在 csdn 这样网站的首页上有很大的误导性,事实上也证实了这一条,许多回帖中都转向了程序员这个工作,和臆测网易对程序员如何。而我们公司一向最重视的就是程序员,甚至大大超过其他岗位的高级管理人员(这样说表示绝非我们不重视其他岗位的员工,例如客服),每年在招聘技术人员中也是下了很大的精力和财力。我个人就代表公司
4 年出去招聘技术人员,工作非常的辛苦,每年招聘期间,我每天都只睡不到 8
小时,准备考题,批改考卷,阅读简历,仔细的和面试的朋友同学交流,新的程序员到了公司我个人每周都花1个晚上给新人上课,这需要准备 PPT
和备课,新程序员来了几个月全部都是接受的知识和其他方面的培训,我们技术部老的员工老实说都不敢顺便让新人立刻加入运营的项目。从内心说,这样的帖子借助
csdn 这个程序员的平台,其误导性对我们的技术人员招聘工作伤害非常的大。

ps. 关于帖子中提到的事情,我无权评论,但从个人情感和个人所知所见,我相信帖子有严重的主观情绪,而没有尊重客观事实。

你们可以把我这封 email 公开,我也愿意看到这样做,这样可以让我做为网易的一份子表达自己的看法。可以和前面那个抨击网易的朋友有相同的权利。
--------------

既然这里是我自己的地盘,我就可以多说一点,不用担心被公开去 csdn 引起别人的误解了。
以下都是个人观点,跟公司无关:

招聘这个事情,我认为公司方面的付出远比求职者试用者的代价大。我这几年都在做招聘工作。深知其“劳命伤财”,跟支付一点点试用期工资比,那真是小巫见大巫。请原谅我用“一点点”形容试用期工资,不过在我心里就是这么认为的。我最害怕的就是找到合适的人,花了很多心思,最终人家不来。或者不小心看错人,最终要想办法说服人家离开。因为有时候人家人真的很好,但就是不合适在我们这里工作(不仅仅是技术不好)。

老实说这次我们公司的公关做的真的不是很好,据说是北京公关做的。本来就不关北京的事嘛,广州发生的事情,北京怎么可能很了解。可能他们原来想利用网站之间的关系,让人家撤掉帖子算了。随便发了个声明,就没打算公开的。结果 csdn 可好,连声明都公开了。那种措辞,不被人骂死才怪。

我个人私下了解了一些有关的情况,我还是很能理解 GM 部门的主管的。我现在也做那么一点管理工作,管着十几号人。还都是聪明人,做开发的,已经觉得很难管了。 GM 部门可是大部门,成百上千的,想想也知道有多难。而且我们网络游戏公司一向重视给玩家的感觉,那些接电话的回 email 的,游戏里维持次序的,人员要求一向非常高。得罪玩家可不是件小事情。我们不能苛求玩家素质,但是我们必须要求自己服务人员的素质。

随便说一句,我们游戏的 GM 权利很小,什么改游戏数据啊,利用 GM 身份牟利啊这些根本无法干的出来。管理用的软件,带出公司根本用不了。管理工具有个核心环节必须通过公司内部服务器才能进入游戏,理论上程序带出公司一点用都没有。这个方案当年还是偶提出的 :) 我还记得早年有次有个 GM 偷到了一个密码可以进入游戏改一个什么数据,结果马上被发现辞退,他的上司和上司的上司都受到了严厉的处罚。

在网易,很重视一个人的人品,尤其是诚信,这个是高于一切的。对于程序员我们还有别的一些要求。
比如我们尤其鼓励多读一些人文方面的书,提高自己的修养,尤其是为人方面的东西。我个人觉得网易,至少在游戏这个我所了解的大部门,有一个非常好的环境。这也是我多次拿到比现在待遇好很多的工作机会而不离开的原因之一。

相关:<a href="http://blog.csdn.net/myan/archive/2005/12/06/544469.aspx">给点“正义”就野蛮</a>

December 02, 2005

C++ exception 的问题

今天在 C++ 会议上认识的鲍同学发了封 email 过来,顺着他的 email 我找到了<a href="http://spaces.msn.com/members/wesleybao/">他的 blog</a>。发现最上面谈的是关于 C++ 异常的问题。
<a href="http://spaces.msn.com/members/wesleybao/Blog/cns!1p0i3yoUKRgnWt0UyAV1FMog!935.entry">Exception handling in depth</a>

的确在大会的第2天我去听了这个演讲,老实说,其内容我觉得不符合我的预期,所以半途我跑到隔壁去听荣耀讲模板元编程了。

当时讲师前半段一直在讲 SEH ,和 C++ 关系不大。我本以为会讲 C++ 异常的实现的,我个人以前研究过一些,很有兴趣听听人家的理解,结果没有听到。据说后来那个会场最终吵了起来,很遗憾没有领略那个盛况 :)

鲍同学提到 VC6 的实现问题,我可以证明,VC6 的异常处理,在 happy path 上是没有什么内核 API 调用的。
VC6 的异常处理也不比 icc gcc 什么的差。是不是好点我就说不准了。

unhappy path 的性能我个人不是很关心。我想大家也不会太关心吧。

不过,VC6 上关掉异常是可以提高性能的。因为毕竟有些环境需要设置,VC6 会利用 fs 保存一些环境信息。而且无论是什么编译器实现,因为需要处理 unhappy path 一般需要编译自动生成大量的代码。这比你只用返回值一定会生成更多更长的字节数。只是因为大家现在都不大关心代码体积,这个问题被掩盖了。我个人在某些情况下是在乎这个的。而且代码体积增加也意味着略微的时间效率损失,ICC 或许会优化的好一些,让其在 happy path 上,对性能影响最小,比如调远 unhappy path 的 code 的物理距离等。

除零的问题是这样,一般非数学计算的程序,我们很少用除法,即使用到,大多数情况,程序逻辑可以保证其不为0。而数学计算的程序一般又用的浮点数,除零得到的是无穷大并不抛出异常。所以我并不认为用除0异常来体现异常的优越性有特别大的说服力。

我个人因为特定的项目环境的原因,是不使用异常机制的。大部分情况下,处理 unhappy path 用 goto 足亦。这里就扯到 goto 的问题。goto 在很多人看来很不耻。不过我认为在函数设置一些出口点,然后 goto 是一种很优美的方法。

其实不用异常的好处也很多,首先程序的复杂性降低了,否则程序的流程会比较复杂,对程序员的要求更高。其次,接口的设计也会比较简单,最后性能会有那么一点的提高。而且,我的程序曾经大量使用 coroutine,C++ 异常对此很难支持。呵呵,言多必失,我对异常几乎没怎么用,都是理论知识,不敢多评论了。

其实偶还是支持鲍同学大部分观点的 :)

December 01, 2005

编译器实现有感

脚本虚拟机前段时间就已经做好,如果没有跑在上面的语言,光有虚拟机没太大意义。所以脚本编译器一早就开始做了。中间因为去上海参加 C++ 大会,又去了成都做招聘,弄的心力疲惫。这几天才回来,有那么几天去实现。

编译原理的课程大学本科就应该开过吧,我不是科班出身,反正是没正经上过。不过依稀记得自己是学过的,记得是上中学的时候,跑到一个大学上课,老师教的就是编译原理。那个时候 C 语言还没玩转,最熟的是 basic 和 6502 汇编。理解那些东西很有困难。囫囵吞枣的记了一点,算是有点印象,逢人也可以吹吹牛。

记得前段<a href="http://codingnow.com/mailman/listinfo/cpp">我们 C++ 的 maillist</a> 曾经有人说,不是说会写编译器的就很牛,做 UI 的就没水平。每个领域研究下去都有很多东西。俺深以为然也。记得会有人这么觉得,编译器这玩意应当不大好写吧。

这次我不想用什么 yacc/lex ,甚至不想按什么词法分析,语法分析什么的一遍遍扫描,一步步转换。心里无耻的认为,之所以人家要分那么多步骤,是因为年纪大了,脑子不好使,或者需要好多人一起合作,需要把事情硬拆分成独立的步骤,保持编程时的头脑清晰。偶还年轻,脑子里可以同时多装点东西。我自己大脑看代码的时候可不用多遍扫描,顺着读就能读懂,理论上一遍扫描就 OK 了。

据说当年 turbo pascal 的编译器的原作者就很牛,用汇编写的编译器,应该也是一遍扫描的,编译速度超快,几乎不占什么内存。当然了,一遍扫描,内存就只用保留最少的上下文环境,一但处理完就退回去了,对 CPU cache 的命中率也是极有好处的。把几个分析步骤混杂在一起做,更是可以减少重复运算的步骤。唯一的麻烦就是,对程序员是一个挑战。在编程这件事情上,我一向不惧啥挑战的。

一开始很莽撞,连 BNF 都没列,一点头绪都没有,只知道分析过程一定是递归向下的。人家汇编都写了,我这还是 C++ 呢,不是一个重量级的武器嘛。不过写起来,脑子真是一团糨糊啊。我的语言定义是类 C 的,虽然去掉了那些变态的三元操作符,和复杂的指针解析这种东西。左值右值的问题上还是非常复杂。毕竟还是保留了许多从右向左的运算。比如函数调用,就需要先算参数再算函数引用。而函数本身又可以返回函数引用,一次扫描的时候,最麻烦就是从左向右和从右向左的操作混合。因为有回退问题,有些符号在不同的环境下又有不同的意义,既然我想把几个分析步骤一起做了,自然不会产生太多中间数据增加重复运算。这带来很大的设计难度。

比 C 语言增加的是类 lua 的多返回值设计,这个在没有指针类型的时候,可以提高虚拟机的运行效率。否则返回多个值只能借助 table 了。临时 table 会有内存分配的开销,内存分配有可能引起 gc,导致虚拟机在处理完毕后要多一些检查做代码重定位,效率上会打折扣。而我的目的是让我的脚本效率高于 lua,自然这个特性一定要支持了。

可是多返回值的设定引起了函数调用的返回行为根据上下文的不同,lua 里定义了尾调用,只有当函数调用发生在尾部时,才按真实返回值返回。否则强制切成一个返回值。我照搬了这个设定。不过在实现时折磨了我几个晚上。

这周开始写的时候,距离上次 coding 已经过去了两周,导致以前写的大部分代码不可继续。我觉得这种对于我来说高难度的算法,对编写者我自己来说需要一个思维连续的过程,思路一旦出了脑子里的 cache 就很难找回来了。写注释的帮助不大,顶多在代码中留下许多 todo 提醒自己别漏掉什么。连续奋战了几天后,昨天夜里终于小有成绩了。

回过头来看,核心的编译部分,几乎被翻新了3遍。整个过程基本重复这样一个过程,先用很丑陋的代码把有限的功能搭起来。这些代码是非常 buggy 的,只能完成特定的分析,很容易出错,和大量未完成的特性。然后给自己一个大体的思路后,开始重构。每次都选一种比较简单的情况,换一个方法重新编写,确定比上一版好了以后再逐步取消前一版本的功能。函数并不是逐个改写的。因为设计本身是在变化的。原来几个函数交叉做的事情,改了之后可能合并到另几个函数中。最后发现代码逐渐被全部翻新了。非常可喜的是,总的代码量缩减到最多时的 70%,但是完成的特性却增加了不少。慢慢的程序就清晰了,

在那一刻,有一种豁然开朗的感觉。脑子里翁翁的声音没了,心情非常的愉快。很久没有体验这种味道。或许是自己控制代码的技术提高了许多,长期没有遇到这么复杂的程序了。

下面的工作很简单,好象刚刚把表达式解析做了,上百行代码一气喝成,几乎没有出错,立刻可以解析非常复杂的表达式。再此之前,编译器只能分析只带有 table 操作的式子。这两天打算把各种语句控制块加上,感觉一下就能做了。心里已经在想给语言加各种新特性了,锦上添花的事情本就没啥难度,只是看想不想的到的事情了。

能有自己的代码实现想要的东西真好。

ps. 到最后我都没有把 BNF 列出来 (._.!)