« November 2007 | Main | January 2008 »

December 17, 2007

个人主页发布十周年纪念

十年前的今天: 1997 年 12 月 17 日,我将主页的第一个 html 文件上传到了网易的服务器。有留言本为证 :)

我没有特地记住这个日子,但是在今天回复留言 的时候突然想到了维护这个网站已经差不多有十年了。查了下最早的留言,居然就是今天。

可惜我再也起不了那么早了。十年前那天,我起了早床,逃课去全校唯一对学生开放可以上网的机房占位置。由于不准携带软盘,不能在寝室把主页事先准备好。在网易申请了个人空间后,我现学现卖写了几个 html 文件上传。

看那条自己留言的记录,大约是早上九点。机房是八点开门的。也就是说,主页的第一版大约用 notepad 写了一个小时。可惜没保留截图。否则可以怀旧一下的 :)


12 月 18 日补充:

ps. 居然发现这个也在 douban 被人推荐,看的人还满多。估计很多人喜欢怀旧。那么我再公开更多的留言历史档案 ,希望大家喜欢。

December 16, 2007

胡思乱想续

接着昨天的写。

昨天谈到了对象生命期管理的问题。我们来看操作系统是怎么管理资源的。

对于资源的集合体,操作系统抽象出进程的概念。每个任务可以向系统索取资源,操作系统放在进程的集合内。进程在,资源在;进程死,资源收回。从操作系统看出去,一个个对象都是独立的,不用理会相互的依赖关系,有的只有对象 handle 。收回这些对象的次序是无所谓的,跟发放他们的次序无关。

这里比较重要且特殊的是内存资源,操作系统其实不直接发放物理内存给用户,用户看到的只有虚拟地址空间。真正分配出去的是地址空间。而且空间是按页分配的,到了用户那里,再由用户自行切割使用。

这么看,内存管理的确是最复杂的部分。因为用户通常不能像文件 handle 那样,拿来是什么还回去还是什么。一个简单的引用记数就可以管理的很好。内存资源必须做多层次的管理。或许未来 64 位系统普及后,这个问题会简单很多,但谁叫我们主流应用还是跑在 32 位平台上呢?而且 64 位系统未必不会出现新的问题。我们现在看 64 位系统,估计跟当年在 dos 实模式下写程序时曾经幻想以后随随便便就有 4G 内存用的感觉一样。

除去资源管理,操作系统通常都会抽象出线程这个代码执行流程,加以统一管理。线程本身会作为一种资源放在进程的管理集合中。但是操作系统又需要对所有线程的集合做统一的调度。从这个角度看,仅仅分层归组管理是不够的。

其实不仅是线程,像 socket 这样的资源同样不能简单置于进程的层次之下。一个 tcp 连接是不能简单的在进程结束后直接干脆的抹掉。另外负责网络通讯的核心模块也需要有轮询系统中所有 socket 的能力。

综上看来,对象的生命期管理在同一层次上似乎应该有交叉的两条线。一条是拥有共同的生命期的集合;另一条是同类对象的集合。


先不忙下结论,再谈谈我们现在自己设计的引擎用到的一些管理策略和最近发现的一些不足吧。

我认为,在游戏客户端程序中(或许也可以拓展到许多别的软件),程序工作时内存里的数据分两类:持久资源和上下文相关的临时数据。

持久资源指开发期生成的地图、模型、贴图、动画骨骼等等在运行期只读的数据;以及一些可以在运行期通过运算或网络加载固定下来的数据,例如连接游戏服务器后传过来的各项游戏世界的资料;另有一些不太变化的临时数据,例如通过预运算合成的带阴影的场景贴图等等。

这些资源对象相互之间有较为复杂的依赖关系,并不总能用树结构描述他们的从属关系。但是他们有一个共同特点,即是生成数据的流程相对简单(大多数通过文件加载),并且总的数量有限。后一点非常重要,我们总能预期在极限情况下,进程中会有多少个资源对象。

最简单的处理方式是,在程序初始化时把所有的资源加载到内存不再删除,对于生命期不会短于代码执行序的生命期的数据,连引用计数都是多余的。大多数其他软件都是这样干的,如果你担心启动软件的时间过长,完全可以在需要的时候再加载。

可惜现代 PC 游戏做不到这一点了。如果你的硬盘上安装有著名网络游戏《魔兽世界》的客户端,看看安装文件夹的大小就可以明白我的意思,它足有 7 个 G 以上。

固然采取动态管理的方式是个不错的方案。但换个思路或许更好。我们不能把所有数据都加载到内存,却能为所有资源对象都在内存中保留一个固定的 handle 以及少量的数据。

也就是说,当你加载一张贴图时,引擎为其分配一个 handle ,无论这张贴图用过之后是否还有人继续引用,这个 handle 就永久的分配给了它。当内存不够时,引擎可以把贴图数据清理出内存,一旦再次有人使用,重新从磁盘加载回来即可。我们只需要保留重建方法既重建需要的数据(例如文件名)即可。

这样,资源对象数据部分的生命期管理就从引擎的上层中剥离了出来。我们不再关心数据被谁引用,实际上它只和一个惟一的 handle 绑定。而 handle (通常就是一个内存指针)和重建它的方法只占用少量的内存,且总量有一个上限,完全可以全部放在单个进程的地址空间内。

ps. 把资源对象全部独立出来还有一个好处就是可以在数据头中描述相互的依赖关系,方便多线程预加载,提高用户运行时的流畅性。这部分的设计可以参考我以前写的一篇:资源的内存管理及多线程预读


资源以外的数据其实并不多。我们依旧可以把数据继续仔细分类。

例如大多数字符串都是可以被提取出来统一管理的。程序中用到的许多字符串都固定不变,这些字符串多用于数据和数据、模块和模块间的松耦合。跟大多数动态语言一样,我赞成建立一个字符串池,把有限的不变字符串放进去,并且通过 hash 表查询。在程序员可以预知它的代码不会无限次的生成不同的字符串时,我们根本不用考虑字符串的生命期问题。这样还带来一个额外好处:字符串比较只需要比较一下指针即可。

除去一些较难处理的对象后,剩下来的数据量就不大了。我很反对在数据结构描述时滥用指针,更勿谈智能指针。在数据量较小时,值拷贝可以做的足够快,且能降低复杂度,甚至节约不少内存。如果有一天要考虑并发,或许还有更大的好处。

让对象的数据结构都是 POD 的吧,每个对象都占据一片连续的内存,而不是里面若干个指针指来指去。这样你甚至可以获得许多调试的便利。指针多应用于管理器的容器中,而非对象数据之间。

在管理器加上一些简单的标记扫描策略,我们可以实现一个简单的垃圾收集设施,方便的清除死亡对象。


以上,是我们已经实现的东西。而新的发现来至于昨天提到的那个有关 timer 的 bug 。

让我们谈谈 closure 。

C/C++ 的 function 都不是 first-class ,所以并不直接提供语言层面的 closure 支持 。但我们无法回避这个概念。C 里面通常用一个函数指针加一个 void * 来模拟 closure ,而 C++ 则用一个纯虚类的对象指针。无所谓形式了,况且今天我也不想局限在特定语言里。

timer 就是一个必须依赖 closure 的设施。我们需要把一个执行序和相关对象打包,放在未来的某个时间运行。执行序总是跟要处理的对象有关。那么这个未来的时间如果超过对象的生命期该怎么办?这不是简单的用 gc 能解决的问题。

来看 timer 的问题:timer 的管理器对每个 closure 有引用,closure 对其操作的对象有引用。所以 closure 没有被 timer 管理器执行并删除前,对象就至少有一个活引用了。

或者我们应该反过来,让对象对 closure 做引用。借用 lua 中弱引用的概念,让 timer 管理器只对 closure 有一个弱引用,似乎可以解决这个生命期问题。对象本身除被 timer 中的 closure 使用到以外没有活引用时,通过收集过程,管理器可以自动取消没有执行的 closure 。

不过这样做会有新的问题,一个执行序并不能简单的归属给一个指定对象。或许使用异常机制会让问题简单一点。当访问已经死亡的对象时从另一个出口退出。不过这样又增加了新的复杂度。

看起来,我们把引用计数和垃圾收集结合起来用也不错。

我们以生命期为标准,给对象分类(就像操作系统以进程为单位分组一样),一组对象都有一个共同的最长生存期(这又类似 Apache 的内存管理机制,允许用户把一堆的内存资源绑定在一个连接上,和连接共存亡)。这组对象之间可以用垃圾收集的方式提前释放一些资源。又可以保证上层建筑最终能够在死亡时间到来时干净的一锅端。

对于其中一些需要提取出来的相互有所作用的同类对象,附加一个引用计数。用来做一些善后工作。


以上,不是我的结论,如标题所言,胡思乱想而已。

以下,轻松一点,谈谈最近玩的几个游戏。

NDS 上的《动物之森》不错,我玩的 1479 英文版的。只有玩这类游戏,才觉得游戏可以做的很活泼,而不像大多数网络游戏那么赤裸裸的功利和单调。

周末还打了两天 PSP 上的《最终幻想 VII 核心危机(Crisis Core)》。也是个发行了很久的游戏了。不要说我老,是太忙了。作为最终幻想的粉丝,我强烈推荐没玩过的朋友试试,难度很低,玩起来相当轻松。虽然表面看起来是即时战斗的模式,但本质上还是用的 ATB 系统。而操作上甚至比菜单操作的 ATB 更容易上手。对比而言,我觉得这个版本的战斗系统会比最终幻想 XII 更容易让玩家接受。

作为 RPG 最重要的故事性,打着最终幻想的招牌当然没的说了。此外,人物造型相当漂亮,CG 也颇有水准。怎么看都是个值得收藏的大作。


喔,最后报告点正经事。这两周继续在读《秦制研究》,等有机会再写写吧。

December 15, 2007

胡思乱想

这两周过的很混乱,主要是从程序部分脱出来,在写游戏的策划案。没怎么写代码,人有点空虚。策划案都是文字活,脑子里想是一回事,写出来又是回事。还有很多细节似乎是因为没想明白,所以表达不清。还得努力。

今天有个 blog 的读者在 gtalk 上督促俺,很长时间没更新了,不准偷懒,好多人看着呢。我从一开始就没打算为别人写 blog ,自己想到啥就写啥,没在意多少人在看。就这样有一茬没一茬的写着,为自己做一个记录。

今天写这么一篇,倒不全因为有美女鼓励。其实在下午百无聊赖的时候就想敲点什么了,一摸键盘又觉得没想清楚。在 blog 管理界面里已经有好几篇这样的稿子,写完了就那么放着而没有公开。生活若不是为了生存,那么就自然会充斥着胡思乱想,这些年我就这么个状态。偶尔想明白点什么,就写下来。而更多的,来也也快去的也快。

其实最开始想写的还是技术上的东西,大致有两点。

第一个是关于网络对时的,这个问题反反复复折磨我很多年了(去年写过一篇 blog,但相关纠缠着我们项目的问题不仅于此)。当然我不是要在这里向谁寻求答案,所以如果读完这篇 blog 想跟我讨论 NTP 协议或是相关技术细节的朋友,在下就不奉陪了。这也不是个什么复杂不能解决的难题,下面是想写一个衍生问题:

我们现在大多数的软件模型是不考虑时间因素的。我们关心的是输入和输出。各种编程语言也是如此,只见到语言的设计和实现去追求运行时的时间效率,不见从语言上严格定义一段代码的运行时间。当然,绝对时间是不能定义的,它会随着硬件发展而变化。但相对时间理论上可被定义的,可最终还是被人忽略了。我们研究算法,也只探讨时间复杂度而已。当然这跟现在计算机的模型有关系,在现有模型下,一段代码的严格运行时间甚至是不可能精确测度的。

可惜,很多软件却不得不考虑时间因素。我们把核电站之类先放在一边。那些对时间极其敏感,又危及人类性命的工业系统肯定对时间控制更为重要。还是轻松一点,只谈游戏。做这种实时交互系统,有人参于其中的时候,光是结果输出正确是不够的,必须是输出结果在数据数值上满足预期,又需要在规定的时刻输出,这才称作游戏软件的功能正确。

因为对于大多数互动游戏,人的感觉才最重要。

这几天在重读一本很早出版的科普读物《宇宙的琴弦》。这本书 02 年的时候在北京买过一本,黑皮的。当时是特地想看,可武汉没买到。正好那几天去北京游玩,一个网友陪我在海淀逛书店,走了几家才找到。花了不到一周时间读完后,被一个朋友借走。然后这本书就消失了。

前几天又是在北京,陪表妹逛书店,发现这本书再版了,顺手买了下来。时间过的真快呀,一晃就是五年。唉,想读第二遍的书还是不要轻易出借的好。

没事重读了几页,前面花了一大篇讲相对论。不同于我前段看的《相对论的意义》,这本书基本是通俗版的。不谈数学,但是说的很清楚。读着书,胡思乱想下去,时间到底是什么?没有运动,时间毫无意义。人理解的时间,恐怕更多的是映射为一种心理感觉(心理活动?)。你永远无法确定你的一秒和另一个人心里的一秒是不是一致,只能从人的生理结构上推断两个人作为两个系统基本相似。

我一直以来最喜欢用的软件调错手段就是录象。记录下软件的所有输入,在调试过程回放。采用白盒的方法,跟踪进入系统内部,找到每个错误的根源,然后修正。对于如今软件行业流行的单元测试方法,在我经历的软件项目中,反而是颇为不屑采用的。

和同行交流时,提到这点。太多朋友表示在实际项目进行时,录象机制难以实施。我的个人看法是,那完全是因为没有把录象机制放在最根本的位置去考虑软件的结构设计。以现在的计算机模型,录象机制总可以被建立起来。且即使系统复杂如人脑,任何问题都可以通过录象回放精确找到根源。(ps. 同时也要注意到,电脑现在的所用模型和人脑有相当大的差异。“系统复杂如人脑”只是一个比喻)

这就好比我们把一个复杂系统的时间无限拉伸(单步跟踪调试,或是添加更为详尽的追踪记录),用人脑去做细致分析。对于系统本身,时间是无关因素。(因为以现在的机器模型,时间是以数据的形式加在上层的,也可以作为输入的一部分。)无论实际运行还是被剖析,系统都可以严格保持表现一致。

当然,因为现在各种庞大的软件,都依赖着各种闭源的第三方库,以及诸多操作系统级的软件设施,而这些设施并没有建设在统一的录象模块的基础上。使得我们的工作变的复杂许多。如果需要让录象回放系统正确工作,还需要为它们各做一个中间层隔离。在中间层加入我们统一的录象部件。

在实现录象回放机制时,给交互系统加入心跳显得尤为重要。心跳是一种隔离交互系统中时间维度对软件影响的简洁方案。如果输入的数据是时间敏感的,那么通过心跳控制,可以把原本无法准确度量的时间信息限制在一个较粗的粒度上。从而使记录输入数据变的简单。当然心跳控制的作用绝不仅于此,我写过一篇游戏服务器中设置专门的 心跳控制服务器 的文章,可供一读。

在这类问题上,我也曾经跟公司别的项目组的同事有过争论。即使是录象,心跳控制也不是必须的。不过设置心跳控制模块,有它的内在哲学——隔离时间维度,让别的部分设计更简单。不光是服务器的设计,图形客户端也是如此。只是客户端需要更高的频率来满足人的手眼交互的舒适感。

btw, 我一直对 3d 游戏过分追求高帧速度是持反对意见的。我们只知道跑 100 帧的游戏就是比 50 帧时要更舒适(对于 fps 游戏,帧数的差别的确不是心理作用),但是却没有从根源上去找原因。或是不太在意其原因,只管把程序优化的可以跑的更快就够了。这个问题今天不展开写了。


胡乱写这么多,起因是我们前几天碰到一个跟时间有关的 bug 。因为涉及服务器组的多个进程和客户端,调试费了好大的劲。bug 的表现是几个数据包没有在预计的时间从客户端传到最终处理这个包的服务器进程,大约比预想的多了 0.2 秒左右。但一切数据逻辑都是正常的。

我们为找这个 bug 简直抓狂了。幸好我们的 client 可以跑在 X-Window 上,甚至可以用远程显示。结果我们让 server 组全部进程和 3d client 全部跑在一台 freebsd 的机器上,最终定位到了问题。


再写写第二个问题,关于对象的生命期管理。

还是缘起于上周项目里的一个 bug:我有一个注册到 timer 系统里的 closure 其实是跟连接有关的。Client 程序因为不需要考虑多个连接,我一直没在意做连接管理的工作。结果,在 Client 断线登出后,这个 closure 没有从 timer 系统中去掉,导致重新登陆后,系统中重复注册了这个时间事件处理函数。

Bug 定位到了以后,修正倒是简单。但这个问题让我想到,其实对象生命期管理其实一直都是个头痛的问题。虽然我们新版的 engine 从设计上已经帮后期开发开发人员解决了许多复杂度,但依然不够。我想说的是,还是不够 KISS 。可能我依旧忽略掉了什么,需要重新整理一下思路。

下面继续随便写写,想法还没成型,姑且看之。什么地方说的不对,多多包涵。

常见的对象生命期管理策略有两大类:手动管理和垃圾收集。它们各有优劣。单从性能上讲,无论从时间性能还是空间性能,都无法严格意义上的区分出那种更好。手动管理的策略更快,或是垃圾收集的策略会吃掉更多的内存都是一种偏见,我今天不想对次发表更多的评论。

从构建一个健壮的系统的角度上来看,无疑垃圾收集的策略更为有效。如果 C++ 的粉丝们蹦出来叫嚣正确的使用智能指针理论上可以获得跟 gc 系统同样的健壮性。这会让我想起另一个笑话:微软告诉我 Windows 系统其实提供了更细致复杂的安全机制和健全的 API ,它可以做的比 Unix 系统更安全。

相信程序员!多好的语言设计哲学啊。精确的控制每一行代码,每一个对象的构建和删除,我们总可以把事情做对,不是吗?

问题其实不在于我们没能力把每件事情做对,而在于在强大的工具(我指各种语言设施)的帮助下,我们在用正确的方法做错误的事情。

更多的时候,我们细致的控制每个对象的生命期,加大了系统结构的复杂度,直到复杂度蔓延到不在我们预期的犄角旮旯里。

请仔细考虑一下,为什么很多软件的退出速度这么慢?为什么 Windows 连系统关机这么简单的过程都容易出错(我的 Windows 系统经常不能正确的做完关机流程)?PC 不应该跟电视或是游戏机一样,不用了按一下电源就 OK 吗?

接下来说说 gc 的坏话。

当语言有了 gc 的支持后,并非高枕无忧。很多问题只是被隐藏起来了而已。

java 的应用软件那是出了名的吃内存,同样的功能比 C/C++ 实现的版本要多占用许多。前几年听 李维 讲过一节课,分析各个开源项目的代码。其间提了一段有关 TomCat 的某个恶评的版本。我不玩 java ,所以记不清当时提到的版本号了。

大体意思是说,其实代码实现和设计上都没啥逻辑错误,可是就是压力一上去系统就崩溃。最终发现问题跟内存管理有关系。大约是在一个内层循环用了字符串连接,导致了瞬间产生了大量的内存垃圾。

当然,这个可以算是 java 的错误使用了。换用 StringBuilder 就可以解决问题。不过我这次想谈的不是如何正确使用语言的问题。

再插一个例子,我们的 大话3 公测时,系统压力一上来,就老是因为内存耗尽而系统崩溃。整个服务器大部分都是 Lua 写的,这是一个支持 gc 的动态语言。按道理不会有 C/C++ 项目里的内存泄露问题。但是实际上,问题就是出在程序员不小心漏把一些数据解引用,导致垃圾数据堆积。

对于对象不能正确回收的问题, java 这样成熟的语言应该有许多好的工具去检查了。实际上,后来我们也为 Lua 做了类似的东西。这些工具和 C/C++ 项目中用的内存泄露和越界检查工具处于同等的地位。可我不想谈工具,工具只是用来解决已经存在的麻烦,却无法消除问题的根源。


如果说这两类对象生命期管理策略都存在问题的话,可是相比 C/C++ 或 java 这类命令式语言,函数式语言更容易处理好对象的生命期管理。函数式语言同样依赖垃圾收集,但可以避免 java 中的许多内存问题。

我不是想鼓吹函数式语言,本质上我还是习惯命令式语言的思维方式。它和我们目前用的计算机模型相同。如果继续采用命令式语言做软件,换个角度看,是否是我们在设计上有了缺陷?

或许我们对现实的问题模型映射到计算机的模型这个过程本身认识就远远不够。如何“正确”的表达要完成的事情的结构还是值得继续探讨的。所谓“正确”:简洁、层次分明。

问题出在哪里?

如果只考虑静态数据,其实无论是手工管理还是垃圾收集都无所谓,都可以做的很好。就好比打扫一张脏乱的桌面,手工管理其实就是有什么东西要用了放上面,不用了立刻收走;而垃圾收集则是在桌子堆满了后,把要用的挑出来,然后把剩下的东西全部扔掉。两个方式都能工作的很好。

可惜程序=数据+处理流程,数据并非静态存在,它往往跟处理它的流程绑定。这或许才是关键。


今天太晚了,没想到随手写来就写了四个小时,已经凌晨两点半了。明天再接着写。

点这里继续

December 06, 2007

学习从历史开始

我有一个忘记从哪继承来的观点:无论我们想学什么,都应该从学习他的历史开始。极端点说,无论学什么,都是在学他的历史。

前几天在北京见到了我的小表妹,她刚上初一,人极为聪明。七年前我在北京工作时,她还没有上小学。那个时候我就回答过她许多科普问题。一个五岁的小姑娘的理解能力曾让我感叹不已。

知道小妹妹居然在写 blog 而且文笔不错,觉得挺高兴的。但听说她最近一次考试数学成绩不是特别好,有些令人担忧。我一直认为中学所谓文理分科就是件巨傻的事(似乎现在慢慢的不再分了)。但如果一味的去追求所谓文科上的造诣,怕是会耽误理性思维的发展。在迈入科学的殿堂的门槛上,一步错就能耽误十年啊。

小孩子一开始在学校学习或许更多的是为了比同龄人强,为了完成长辈的期望,为了达到别人设定的目标。但终有一天,长大了的后会发现,学习其实就是因为自己想知道。

所以吃饭的时候,我多说了几句。无论学什么,都要先培养出兴趣。理科的东西老师教起来很枯燥,那么就可以从读他们的历史开始。一段段故事,一个个鲜活的人,就会变得生动。深一层的道理需要慢慢的去体会:无论学什么,都是在学他的历史。以前的人如何考虑这些问题,为何研究这些问题。他们怎样去归纳、总结。他们的思考怎样延伸出去,为什么又有了局限性。后人怎样做出了突破。人性是共通的,人的智力水平也相差无多。按着前人的路,没有太难理解的道理。而课堂上现在的教法,把历史上长长的思考过程压缩,裁减掉所有的错误和累赘,压缩成一条条公式与冷冰冰的推导。背了那些,除了考出完美的答卷,就没太多意义了。

我带她去书店逛了一下午,买了不少书。逛书店这个点子一提出来,小姑娘心中的高兴完全写在了脸上。我想找一本有趣点的数学史的书,没有物色到。最后挑了一本科普的《从一到无穷大》;转到科普的柜台,她居然知道《时间简史》。我想了想还是买了本,但是告诫说,这个年纪读可能还太小,留到高中再看吧。再后来又买了些小说……

写了这么一大段,其实我还是想绕回来写写 软件开发2.0大会 上的故事,以及接下来几天的活动。

2005 年 C++ 大会上领教过陈榕“忽悠”人的工夫,所以这次无论如何他的 session 都要参加的。可惜陈榕没当标题党,导致那个 session 居然没把会议室坐满。不禁感叹大家还是没有参加此类活动的经验。其实技术的 conference 上选课关键是要看是谁讲,至于讲什么根本不重要。这就跟读书一样,作者远比书名重要。

和上次一样,陈榕调侃了许多大公司,尤其是微软。但他更语重心长的讲了一个浅显的道理:微软的人并不比大家苯,当然也不比大家聪明。我们都能看到的问题,比如系统臃肿,软件结构不合理,等等,不可能微软自己人就意识不到。种种问题,绝对不能只用当局者迷,旁观者清来解释。

我们只有从历史看过来,方能理解历史的局限性。做出那些错误决定的无奈放在大背景上大多会得到一个合理的解释。也只有这样,我们才可以领悟到未来正确的路。


周末,博文视点 组织了一些作者搞了个座谈会的活动。我有一本书《我的编程感悟》是他们出的,应邀参加。经历了北京惨烈的交通状况后,从城西晃到城东,没想到最后摸到了微软的地头。那天在那里认识了微软的林毅。晚餐的时候林毅从我那本书引出去开始想当年,我们聊了下 Z80 和 6502 的汇编。这让我突然想起,当初没有把那部分过时的内容从书稿里删除,其中一个原因就是,我需要有一个地方记录我所了解的历史。即使是游戏编程这个计算机领域小小的分支,同样有它的历史。了解了历史方能展望未来。我自己写的不好,但是我写就是想表明,了解历史是有价值的。

长期以来,自己总结我在编程方面取得的成绩的缘因,最重要的一条就是无功利心的学习。

并不是因为我需要用到什么领域的知识而去学习,而只是单纯的我想知道,我想弄明白。搞明白之后,到底有什么价值,可以创造多少财富,这是我从来不关心的。反而这样,知识给予的回馈是最大的。

别看计算机科学的历史只有短短几十年,可今天很多问题,人们早在几十年前就开始思考了。现在我还经常翻《计算机程序设计艺术》;我的同事 soloist 办公桌上常备一本《C Interfaces and Implementations》;那天晚上 周爱民 强烈建议博文再版《结构程序设计》。这些书成书都很早。看来大家转了一圈后,今天又都返回去在故纸堆里寻找答案。

December 05, 2007

多核环境下的内存屏障指令

本来不打算立刻写关于这次 软件开发大会 的事情。太多可以写的东西,反而不知道怎么写起。今天才有机会上网到处转转,转到 周伟民老师 的 blog 上,看到这么一篇 。里面既然提到我,就想在上面回上两句。可惜 csdn 的 blog 系统实在是太烂了(这个话题我们在周六的沙龙上集体声讨过,暂且按下不表),硬是没发上留言。那么我还是在自己的地盘单独提出来说说吧。


周老师那个 session 正好排在我的前面。同一间会议室,而且内容我也颇有兴趣。也就顺理成章的听了。讲的东西其实满不错的,唯一的抱怨是太像在大学里授课,互动少了点。会场气氛远不如后来 Andrei 讲 Lock-Free Data Structures 那么精彩。

周老师讲的这块内容,正巧我前几年写多线程安全的内存分配器时碰到过,有点研究。加上前几年对 Intel 的东西颇有兴趣,便有了发言的冲动 :) 。当时的会场上下文环境正好是有个朋友提问说:实际上,InterlockedIncrement 的调用是多余的。(事后交换名片得知,提问的这个哥们是来至 google 的程序员)

如果换在几年前,我是赞同这个哥们的观点的。记得 04 年左右,我们公司内部的 maillist 上曾经有类似的讨论。即,在 32 位系统上,写一个 dword 本身就是原子的,如果 cpu 可以保证程序逻辑上的执行次序(program ordering),那么简单的利用写操作就可以替代锁操作。我们在操作完一大片内存数据后,只需要在最后更改关键的标记字,那么不需要加锁也可以保证安全。(还有一个隐含的前提是数据必须被 32bit 对齐)

btw, 当天晚上 Andrei 讲 Lock-Free Data Structures 时向大家提的问题:那个 hazard list 为什么要用单向链表实现?大约也是这个意思,因为链表指针可以被原子的修改而无需加锁。

单核时代它是对的,因为单核 CPU 要求读写操作 self-consistent 。多嘴两句解释一下,现代 CPU 工作时的指令执行次序(process ordering)是可以不同于程序编制的次序(program ordering)的,即乱序执行技术。这个技术可以极大的提高流水线的工作效率。单核 CPU 保证读写操作的 self-consistent 意味着,等到真正读入操作数据时,数据符合 program ordering 上的正确性。

可问题也出在这里。随着多核的发展,为了提高每个核上的流水线效率,多核环境不再保证其安全。在每一个核上,cpu 内部工作时指令都可能被乱序执行。那么逻辑次序上后写入内存的数据未必真的最后写入。核与核之间作为一个整体看的话,却不保证 self-consistent 了。

也就是说,如果你不做多余的防护措施,在一个核上写入一批数据后,如果你期望最后写一个标记数据表示前面的数据都已经准备好;然后从另一个核上依靠判断这个标记位来判定一切数据就绪。这个策略并不可靠。标记位可能被先写入,但其它数据尚未真正写入内存。

解决的方法是,在标记位被写入前,强迫 CPU 串行化。InterlockedIncrement 和它的兄弟们可以提供这种安全性。翻译成 Intel 指令,会发现它在汇编指令前加了 lock 前缀。也就是在这些读写内存的指令在发起时,cpu 会向总线发出一个 lock# 的信号,阻塞住其它内存访问请求。

但这么做未免效率太低。这种影响总线的指令会随着核越来越多而变的越来越低效。可以想象,任意一个核上发起 lock 几乎会让所有的核都短暂的停止工作(除非完全不访问内存?)。我们今天只有两个或四个核,性能影响微乎其微。但是等到机器拥有 32,64 甚至更多核时,就可能相当严重了。

ps. 上面这个说法也不全然正确。因为既然内存锁在多线程编程中运用的非常广泛,自然在芯片设计上是要做优化的。在 Pentium Pro 以后,当被访问内存处于 cache 中时,lock# 信号不会被发到总线上,取而代之的是锁住 cache 。这样代价会小的多,但是在某些情况下依旧昂贵。(当多个核 cache 住同一块内存时会受影响)

轻量一点的方案是执行一条 CPUID 指令,它也可以保证前面的操作被串行化。到了Pentium III ,Intel 在 IA32 指令集中增加了 SFENCE 指令用来提供更细的控制粒度以更少的代价解决这个问题。在指令序列中插入 SFENCE 可以保证在此指令之前的写操作全部完成(非写操作的指令依旧允许乱序执行)。这样我们在另一个核里读相同内存时,几乎不会出错。

在这里我用了“几乎”,是因为诸如访问单项链表,判断标志数据的编程逻辑,对内存的读操作都是上下文相关的。我们可以断言执行次序不会被乱序执行影响。构造一个可能因为乱序读内存而有出错隐患的合适例子不太容易。但是从 Pentium 4 开始,严格上讲,我们需要用 LFENCE 指令(Pentium 3 没有提供也不需要这条指令)配合使用。它可以保证在此之前的 program ordering 上的读内存操作已经完成(否则逻辑结果可能因为多核间同步 cache 等原因而受到影响)。另外有 MFENCE 指令粒度粗一点,可以同时保证读写内存操作都已完成。


本来不打算翻资料,凭印象写的。写完这篇 blog 审了一遍,还是担心留下重大错误。就又一次翻阅了 2005 年在 Intel 网站上免费索取的 IA-32 Intel Architecture Software Developer's Manual Volume 3 的 Chapter 7 :Multiple-processor management 。

核对后,我想大概意思应该写清楚了,如果有小 bug 还请行家多多包涵。真有兴趣把这点东西搞清楚的朋友,莫信我的一家之言,查 Intel 的手册吧,它写的更加清楚和权威。btw ,不要问我该去哪找,去问 google 。