云风的 BLOG

最近在调整 3d engine 的接口。前段时间把 GC 模块加到底层后，很多部分都需要修改实现了（可以简化许多实现代码）。既然重构代码，不如就再次审查一遍接口的设计，结合最近的一些想法，重新弄一下。

嗯，那么 3d 引擎是什么？跟 3d api （Direct3D 或 openGL）有什么区别？固然，engine 如果只是做 3d api 的一层薄薄的封装，抹平各套 3d api 的差异。那么，就过于底层，显得小了。

如果为特定形式的游戏写死代码，让开发者写一些 MOD 插件就可以形成不同的游戏，那么又显得太高。在这种高层次上，游戏类型会限制于 engine 的实现。比如魔兽争霸 3 就直接用户写 MOD ，并的确有人以此发展出许多玩法。但你永远不可能在 魔兽争霸 3 的基础上写一个 MOD 实现第一人称射击游戏。

所以我指的 3d engine ，是处于 3d 游戏软件结构中间地位的东西。

那么，我们的 3d engine 到底要解决的是什么问题？做 engine 绝对不是以我能在 3d api 的基础上扩展出什么东西为设计向导。因为，对于完成一个软件，是一个从机器实现域映射到问题域的过程。这两个领域的模型是不同的。3d api 完成的是实现域的扩展，engine 则应该完全从实现域到问题域的一个变换，让开发者可以用最接近问题域的语言来表达问题。

跑跑题说的别的。

再提提最近我这里反复提到的老话题，为什么引擎中要有 gc 模块？gc 的机制是远离机器实现域的。计算机的冯诺模型上没有 gc 的概念。C 语言是贴近机器模型的，所以也没有天然的 gc 设施。但是对于问题域的表达，有了 gc 后更为容易，因为资源的生命期管理不属于解决问题的直接部分。

再有一个例子是近几年重新流行的函数式编程语言。函数式编程语言同样是不同于计算机固有模型的。但是，这样的语言却以改变计算机固有模型为代价，提供一个新的域来描述问题，许多问题的解决变得更加方便。

爱因斯坦建立广义相对论，有赖于黎曼几何体系。虽然黎曼几何空间和欧式几何空间可以做等价变换。但是若是没有黎曼几何，直接从欧式几何空间中推导出广义相对论，我想那将是不可完成的任务。

其实，给软件加一个中间层，最大的作用即是变换原有的实现域，提供出新的语言来描述问题。而中间的许多变换由于被集中解决，无论从性能还是稳定性上都会得到提高。

Raymond 在 TAOUP 中提到一句话（4.5 Unix 和面向对象语言，中文版 P103）：“如果你知道自己在做什么，三层就足够了；但如果你不知道自己在做什么，十七层也没用。”为什么不是四层或是更多？云风认为：第一层我们完成了对底层的封装和抽象，排除了不必要的细节。第二层完成了一次转换，提供出最适合的语言来描述问题。第三层我们则用这种语言解决问题。多余的中间层次是无意义的，因为对于问题明确的应用，我们不需要二次转换。而如果我们足够理解系统底层，则不需要在第一个层次上重复做无谓的封装。至于第三个层次，如果你需要做多余的层次划分，那么就证明你的中间层搭建的不好，没能提供最佳的问题描述语言。

我们知道两点间直线最短。但如果要把中国和美国的每个城市都连通为一个交通网。将城市两两相连绝对不是最优的方案。通常我们会修出几条主航线连接两个国家，再在每个国家内部建立局部交通网落。这不仅仅是成本的问题。即使不计成本，让中国的每个城市和美国的每个城市直航，调度消耗的几何级数的增加同样会大大的降低整体的交通效率。

回到正题。那么作为 3d engine ，我们设计者就应该严格的考虑每个功能到底应该提供怎样的接口给人使用。可以最佳的满足问题解决的需要。作为 3d engine 的实现者，我们满脑子可以是矩阵变换、空间矢量、线性代数这些东西。但一旦反应到使用人的一边，这些就不再应该是他们描述问题的语言。engine 需要做的就是隐藏这些细节，换一种方式提供出来。又不能失去使用上的灵活性（比如只能做 RTS 而不能用于 fps）。

下面谈谈最近在做的摄像机的接口。尚未定型，暂作记录。

对于 3d api 来说，摄象机就是绝对空间中一个矢量，有绝对空间坐标和朝向。再加上焦距等一系列属性，便可以描述出要渲染的视野。

但对于要解决的问题（一个可以玩的游戏）来说，这不是合适的描述语言。我们关注的摄象机其实可以是一个实体，它在存在于虚拟世界空间中，它自身的位置往往相对于虚拟场景中的另一个实体，而非以世界绝对坐标的形式提供。比如是 fps 游戏，摄象机可能在主角的身后；对于 RTS ，它在地面的上方；对于赛车，它在驾驶位；对于 日式 RPG 它可能固定在场景中由编辑器预先设定好的位置上，等等。

所以，摄象机只需要绑定在虚拟场景中的一个物件上即可。或者它本身就是一个（不可被渲染的）虚拟物件。

而摄象机的朝向呢？

设置它的朝向不应该让使用者提供一个矩阵，这会让人不知所措。在逻辑表达中，大多数情况下，我们只需要让摄象机指向一个物体即可（对于引擎，还要进一步跟踪这个物体，而不需要每个渲染帧都要求使用者不停的刷新摄象机的状态）。这个物体可以在虚拟世界中真实存在，也可以是一个不被渲染的虚拟物体。比如 FPS 游戏中，我们可以让摄象机指向主角面前 10 米远的地方的虚拟物体。

少数时候，我们需要让摄象机指向一个坐标值（往往在写 demo 的时候用）。当然，我们可以排除后一种情况，当需要让摄象机指向一个特定坐标的时候，我们可以为在这个坐标点上创建一个虚拟物体（如同上一段中提示的 fps 游戏的摄象机设计）。但，我们只需要的是物体的坐标不是？而不是需要物体的全部。

这是一个典型的，可以用面向对象方法解决的问题。我们需要的是：具有获取坐标能力的东西，不管它是什么。

所以，我们可以给虚拟世界中的物件都提供一个方法，这个方法可以取出一个接口，一个获取特定坐标的接口。注意，“取出一个接口”在 C++ 中可以让对象继承这个接口的方式提供出来，但不一定必须如此（如果有 gc 的机制，临时创建一个仅含有这个接口的对象更加方便）。如果在 COM 中，那么就是调用 QueryInterface 得到。实现手法并不重要。

这样一个接口背后的实现需要做的事情是，获取自己相对一个指定坐标系的相对位置。它有可能得到一个非法的相对位置。这是因为，对象本身和目标可能并不在一个世界中。

如果我们需要指定一个特定坐标，可以做一个特别的实现封装一组矢量：比如，将一个位置信息绑定在主角面前 10 米处。

对于实现，没太多好谈的。

由于 3d engine 中虚拟物件通常以树方式组织。那么首先是求出位置对象和目标对象的最近公共祖先（LCA），如果没有公共祖先则返回出错值。如果有，根据公共祖先计算出相对坐标。

需要留意的是，LCA 问题在教科书上提到了许多算法来解决。但我们不要读死书。在 3d engine 的渲染树上，层级通常不多，但在某些层级上节点特别多。层次不深的树即使用最苯的策略寻找公共祖先也不会太慢。

Posted by 云风 at 11:02 PM | Permalink | Comments (36)

最近在玩桌面游戏，大约一到两周一次。纠集些朋友，开车去到很远的一个游戏吧，一玩就是一夜。颇有些意思。

玩了大约十来个桌面游戏，大多不错。我个人比较偏爱欧系的游戏，最近几次玩的比较多的是 shadows over camelot （卡美洛的阴影）。第一次玩的时候被人误导，把许多规则弄错了。不过也正是如此，难度大大降低，让我们几个人迅速的上手游戏。昨天再去玩之前，好好的研究了一下规则，发现了许多设计巧妙之处。

这个游戏简单说就是一个找叛徒的游戏，感觉上部分类似前几年颇为流行的杀人游戏。但是要丰富的多，道具非常的华丽。前几年公司里流行杀人游戏时，我们曾几次修改规则，试图加入更多的身份让游戏更加平衡和有趣，并加快游戏节奏。但始终没能很好的解决游戏进程中先出局的人做什么的问题。

SOC 在这点上做的相当不错，叛徒即使被指认出来后，依然有相当的策略，可以一直奋斗到最后。更是存在谁都不是叛徒而互相猜忌以至于最终集体失败的情况。

昨天我们玩的两局颇有戏剧性，正如后来回家正赶上土耳其那奇迹般的加时赛。

第一场我们五个人玩，我抽中 King Arthur ，虽然一出场就利用规则证明了一个人的清白。但是最后大家连连犯错，指错两人。当我们甚至怀疑叛徒并不存在时，让叛徒拿到了 Lancelot's Armor 。正当他觉得胜卷在握，利用规则再次指错一人扣除一分时（同时向大家暴露了自己）。黑暗势力居然出现一张：全体减一点 HP 。可怜的叛徒由于之前装的太逼真，做任务杀的自己仅留下一点 HP，而被黑暗势力残忍的杀害，正义方顿时大逆转 :D

第二场加了一人到六人，结果叛徒被一不熟悉规则之人一开局就随手指出，相当之不幸。只不过后来正义方也战斗的异常辛苦。最后胜利时，已经有三人牺牲，其中两人是自杀。终于在 Camelot 城被攻陷前一回合（城外已经有十一乘投石车，全部 Merlin 卡都用完）结束了战斗。

据说 SOC 的扩展包 Merlin's company 已经发行，希望不久以后可以玩到。

另外一个推荐是 Tigris & Euphrates （两河流域），这个是我比较早接触的桌面游戏。策略性也颇强。最好是三或四人一起玩，个人感觉比 Catan （卡坦岛）更有趣一点点。昨天还试了一下六人版的 Catan ，比四人版激烈了许多。

btw, 感觉国内没出现太多好的游戏设计，跟缺乏桌面游戏的文化有很大关系。毕竟少了许多沉淀。IMHO

Posted by 云风 at 04:34 PM | Permalink | Comments (28)

面向对象方法被人谈论了二十多年了。我接触它比较晚，直到九十年代中期才开始学习使用它。若说对这个方法做些评价，那还真是大言不惭了。不过这么些年来，也周期性的对面向对象做些思考。或对或错，我想都值得总结一下。一家之言，来看的同学不必太当真。

首先我们要区分一下“基于对象”和“面向对象”的区别。

基于对象，通常指的是对数据的封装，以及提供一组方法对封装过的数据操作。比如 C 的 IO 库中的 FILE * 就可以看成是基于对象的。

面向对象，则在基于对象的基础上增加了多态性。所谓多态，就是可以用统一的方法对不同的对象进行同样的操作。当然，这些对象不能完全不同，而需要有一些共性，只有存在了这些共性才可能用同样的方法去操作它们。我们从 C++ 通常的实现方法的角度来看，A 和 B 在继承关系上都有共同的祖先 R ，那么我们就可以把 A 和 B 都用对待 R 的控制方法去控制它们。

为什么需要这样做？

回到一个古老的话题：程序是什么？

程序 = 算法 + 数据结构

在计算机的世界里，数据就是一个个比特的组合；代码的执行流程就是顺序、分支、循环的程序结构的组合。用计算机解决问题，就是用程序结构的组合去重新排列数据的组合，得到结果。为了从庞大的输入数据（从 bit 的角度上看，任何输入数据都可能非常的庞大），通过代码映射到结果数据。我们就必须用合理的数据结构把这些比特数据组合起来，形成数量更少的单元。

这些单元，就是对象。对象同时也包括了对它进行操作的方法。这样，我们完成了一次封装，就变成了：

程序 = 基于对象操作的算法 + 以对象为最小单位的数据结构

封装总是为了减少操作粒度，数据结构上的封装导致了数据数据的减少，自然减少了问题求解的复杂度；对代码的封装使得代码得以复用，减少了代码的体积，同样使问题简化。

接下来来看 基于对象操作的算法。这种算法必须将操作对象看成是同样的东西。在没有对象的层次上，算法操作的都是字节，是同类。但是到了对象的层次，就不一定相同了。这个时候，算法操作的是一个抽象概念的集合。

在面向对象的程序设计中，我们便少不了容器。容器就用来存放一类有共同抽象概念的东西。这里说有共同概念的东西，而没有说对象。是因为对于算法作用于的集合，里面放的并不是对象实体，而是一个对实体的引用。这个引用表达的是，算法可以对引用的那一头的东西做些什么，而并不要求那一头是什么。

比如，我实现一个 GUI 系统（或是一个 3d 世界）。需要实现一个功能——判断鼠标点选到了什么物件。这里，每个物件提供了一个方法，可以判断当前鼠标的位置有没有捕获（点到）它。

这时最简单的时候方法是：把所有可以被点选的物件都放在一个容器中，每次遍历这个容器，查看是哪一个物件捕获了鼠标。

我们并不需要可被点选的物件都是同类，只需要要求从容器中可以以统一方法访问每个元素的是否捕获住鼠标的这个判定方法。

也就是说，把对象置入容器时，只需要让置入的东西有这一个判定方法即可。了解 COM 的同学应该明白我要说什么了。对，这就是 QueryInterface 的用途。com 的 query interface 就是说，从一个对象里取到一个特定可以做某件事情的接口。通常接下来的代码会把它放在一个容器里，方便别处的代码可以干这些事情。

面向对象的本质就是让对象有多态性，把不同对象以同一特性来归组，统一处理。至于所谓继承、虚表、等等概念，只是实现的细节。

说到这里，再说一下 COM 。COM 允许 接口继承 ，但不允许接口多继承。这一点是从二进制一致性上来考虑的。

为什么没提 实现继承 的事情？因为实现继承不属于面向对象的必要因素。而且，现在来看，实现继承对软件质量来说，是有负面影响的。因为如果你改写基类的虚方法，就意味着有可能破坏基类的行为（继承角度看，基类对象是你这个对象的一部分）。往往基类的实现早于派生类，并不能了解到派生类的需求变化。这样，在不了解基类设计的前提下，冒然的实现继承都是有风险的。这不利于软件的模块化分离和组件复用。

但是接口继承又有什么意义呢？以我愚见，绝大多数情况下，同样对设计没有意义。但具体到 COM 设计本身，让每个接口都继承于 IUnknown 却是有意义的。这个意义来至于基础设施的缺乏。我指的是 GC 。在没有 GC 的环境中，AddRef 和 Release 相当于让每个对象自己来实现 RC （引用计数）的自动化管理。对于非虚拟机的原生代码，考虑到 COM 不依赖具体语言，这几乎是唯一的手段。另外 COM 还支持 apartment 的概念，甚至允许 COM 对象处于不同的机器间，这也使得 GC 实现困难。

QueryInterface 存在于每个 COM 接口中却有那么一点格格不入。它之所以存在，是因为 COM 接口指针承担了双重责任，既指出了一个抽象概念，又引用了对象的实体。但从一个具体算法来看，它只需要对一组相同的抽象概念做操作即可。但它做完操作后，很可能（但不是必须）需要把对象放入另一个不同的集合中，供其它算法操作。这个时候，就需要 QueryInterface 将其转换为另外一个接口。

但是，从概念上讲，让两个不相关的接口相互转换是不合逻辑的。本质上，其实在不相关的接口间转换做的事情等价于：从一个接口中取得对对象的引用，然后调用这个对象的方法，取到新的接口。

如果去掉了 AddRef Release （依赖 GC ）以及 QueryInterface （只在需要时增加一个接口获得对象的引用），IUnknown 就什么都不剩了。那么接口继承也完全不必存在。

回头再来看程序语言。

C++ 提供了对面向对象的支持，但 C++ 所用的方法（虚表、继承、多重继承、虚继承、等等）只是一种在 C 已有的模型上，追加的一种高效的实现方式而已。它不一定是最高效的方式（虽然很少能做到更高效），也不是最灵活的方式（可以考察 Ruby ）。我想，只用 C++ 写程序的人最容易犯的错误就是认为 C++ 对面向对象的支持的实现本身就是面向对象的本质。如果真的理解了面向对象，在特定需求下可以做出特定的结构来实现它。语言就已经是次要的东西了。

了解你的需求，区分我需要什么和我可以做到什么，对于设计是很重要的。好的设计在于减无可减。

你需要面向对象吗？你需要 GC 吗？你需要所有的类都有一个共同的基类吗？你需要接口可以继承吗？你为什么需要这些？

Posted by 云风 at 10:16 PM | Permalink | Comments (52)

本质上来说，引用计数策略和垃圾收集策略都属于资源的自动化管理。所谓自动化管理，就是在逻辑层不知道资源在什么时候被释放掉，而依赖底层库来维持资源的生命期。

而手工管理，则是可以准确的知道资源的生命期，在准确的位置回收它。在 C++ 中，体现在析构函数中写明 delete 用到的资源，并由编译器自动生成的代码析构基类和成员变量。

所以，为 C++ 写一个垃圾收集器，并不和手工管理资源冲突。自动化管理几乎在所有有点规模的 C++ 工程中都在使用，只不过用的是引用计数的策略而非垃圾收集而已。也就是说，我们使用 C++ 或 C 长期以来就是结合了手工管理和自动管理在构建系统了。无论用引用计数，还是用垃圾收集，软件实现的细节上，该手工管理的地方我们依旧可以手工管理。

为什么要用资源生命期自动管理？

让我们来看面向对象，如果一切皆对象，每个对象的生命期就应该由自己负责，我们是可以直接准确的死亡时间的。可惜，有很多东西不是纯粹的对象。最重要的一个就是对象容器。它们除了自身的属性，还保持了对一组同类对象的引用。

一个对象可以分别被几个容器引用，这使得容器区别于猫猫狗狗这些对象实体。因为容器引用一个东西不等于这个东西是这个容器的一部分（有时候可以，有时候不行）。当我们把希望整个世界分成一个个对象时，所有的原子被分到各层的对象上后，就会发现有零零总总的概念无法用对象提取。引用而非拥有，这是无法回避的。

面向对象的本质在于，对许多对象提取出共性放在一起处理。这样，各式容器的使用就是无可避免的了。

也正是如此，对象自己并不知道自己是否已经可以宣告死亡。除非了解自己和别的对象的联系（这种关系不是对象）。资源可以是对象，而自动化管理正是管理的这些对象和对象之间的关系。

引用计数就是最容易实现的一种方案：记录对象被引用的次数，而不具体记录是谁引用了它。这样，降低了建立和解除引用的代价。但是，有得必有失。在引用计数的过程中，我们也丢失了重要的信息：到底是谁引用了自己。所以，引用计数在处理间接引用的问题上代价增加。

对象死亡的判定是：对象和这个世界还有没有联系，无论是直接的还是间接的。所以，一个对象即使还有另外的对象直接引用它，它也可能已经脱离了世界。为了解决这个问题，使用引用计数的系统，必须在对象和世界脱离联系时，通知和它有关联的对象。对象的销毁代价增加，就是引用计数策略的短板。

对象的销毁频率，取决于对象的平均生存时间。而对象的生存时间，一方面受对象粒度的影响，往往对象粒度越细，对象平均生存时间越短（虽然表面上没有直接联系，但是实际设计时往往会导致这个结果）；另一方面，我们往往会把容器和引用关系也实现成一种对象（概念上本不应该是对象）。比如说许多自动维持引用计数的智能指针就是一个小容器，里面保持了对一个对象唯一的引用，它就被实现成一个小对象。

通常，对象本身的性质并不随自己在内存空间中的位置改变而改变。但是引用关系（通常用指针来实现）却和内存地址相关。C++ 缺乏一种对象在内存中移动的语义表达，等价物是，在新的内存块中拷贝构造一个新对象，并销毁原有的。

另一方面，程序的运行序中，函数调用造成的堆栈上的嵌套作用域也可以看成一个个容器，机器指令穿行于这些作用域间，临时构造出的对对象的引用（智能指针），就被放置于这些作用域内。函数调用越频繁，这些作用域的创建和销毁也就越频繁。

这些导致了 C++ 必须依赖大量的 inline 函数，让编译器了解更多的上下文信息，方能减轻小对象（智能指针）创建销毁的负担。 STL 库也必须为其做一些优化，例如 stl port 中，对 POD 类型就做了特例化处理。可惜，智能指针不是 POD ，让编译器聪明到合并执行序列中的引用加减，难度太大（考虑到多线程因素，除非编译器可以知道线程的信息，否则几乎不可能实现）。

C++ 在实现面向对象的编程上，比 C 提供了许多便利。其中之一就是，在描述一个对象是另一个对象的一部分时，通过构造和析构函数机制，可以自动化的维护这相关部分的生命期。但它没能在语言上解决的是，当两者之间只是引用关系时，生命期如何处理。前者，我们有几乎唯一的简洁明了的解决之道；而后者根据实际需要可以有多种选择，顾而 C++ 在语言层面不提供一致解决方案。可惜的是 C++ 却一直每能提供一个简洁好用，带有普适性的 GC 库。大家都偏向于更为容易实现的引用计数的方案，这个结果跟具体实现的复杂度有关。毕竟在实现 gc 的时候，C 缺乏必要的语言支持（而 C++ 在实现层面，是从 C 的基础上发展而来）。

再来看看垃圾收集，比较成熟的算法基于标记清除（或标记整理）或其变体。简单说，就是由收集器框架记录下对象和对象之间的联系（这些联系信息存放的位置不重要，可以在对象的内存布局空间上，也可以在独立的地方，关键在于这些信息可以被收集器访问）。确定一个世界的根，定期的从这个根开始遍历这个世界，把有关联的对象标记起来，最后回收没有被标记的对象。

从算法上来看，建立对象和对象之间的联系的时间代价和引用计数的时间代价数量级上是一致的，都是 O(1) 。但实际实现时，前者的代价通常要大一些。空间代价上也是前者略大，但也没有数量级上的差别。

而 GC 管理的对象，在销毁时的代价要小的多。它不需要通知和它有关联的对象。

这就是为什么，许多使用 GC 的软件有时候比使用引用计数的软件运行效率还高那么一点的缘故。

可是，GC 有一个额外的时间代价来源于标记的过程。完成完整的一次清理过程，必然遍历到世界中每一个活着的对象。代价是 O(N) ，N 随着对象总体数量的增加而增加。所以我们应该减少被 GC 管理的对象的数量，在这一点上，手工管理依然有意义。即，明确一个对象是另一个对象的组成部分时，可以考虑用手工管理的方式。

另一个糟糕的地方是，在实现时，我们往往把对象间的关联信息放在了对象本身的内存布局空间中，遍历这个世界中的对象意味着访问所有对象的内存。当虚拟内存空间大于实际物理内存空间时，这意味着页面交换。我觉得，很大程度上，java 或 C# 这样的语言搭建起来的庞大系统偶尔运行缓慢，根本原因就在这里。当然，这些是可以被改进的。并非算法本身的问题。

可以这样说，GC (garbage collection) 把 RC (reference counting) 中那些短期对象的销毁代价转嫁到了一次性的标记清除过程。这把逻辑处理和资源管理正交分解了。这种被分解的问题，会随着硬件的进步更容易提高性能（比如多核的发展）。但是，在较小规模的软件或独立模块中，这个优势并不会太明显。反而 GC 本身远高于 RC 的复杂性，会成为其软肋。

对于不需要面向对象的软件，甚至连资源自动化管理都不需要。这时，无论是 GC 还是 RC 都无用武之地。

我做的那个简陋的垃圾收集器，也只是想做些简单的尝试，为 C 或 C++ 语言构建软件时多一些选择。

Posted by 云风 at 04:33 PM | Permalink | Comments (18)

我想用 C++ 的人都用过 std::vector 。它是一个可变长的数组，在很多时候都比 C 固有的定长数组要灵活。

C 里没有这样的标准化设施，但是写软件的人通常都会实现一个。正所谓，不厌其烦的重造轮子 :D 。这里我们不讨论造轮子的好坏问题，直接讨论下实现这么个东西的一点小技巧吧。总是固执于用谁做的轮子的问题，眼光就太短浅了。

一般的 vector 的实现，需要记录三个数据：数据空间的地址，空间大小，数组里已存在的元素个数。也可能是这三个元素的变体。比如在 msvc 的 stl 实现中，vector 保存的是三个 iterator：数组头指针、最后一个元素的指针、分配出来的全部空间的末尾指针。

msvc 的 vector 的分配策略是这样的。一开始不于分配空间，当第一个元素被 push back 后，空间扩展。通常，扩展的请求至少要满足请求扩展的尺寸，或者是讲已有的空间容量翻倍。比如，当你已经有 16 个单元的数组空间时，如果再申请 3 个，vector 会自己扩展到 32 个单元；若你一次要求从 16 个单元扩展到 40 个单元（超过 16*2），那么就直接扩展到 40 。

记得 stlport 也是类似的策略吧，实现的可能稍有不同。

正是如此，我们在用 vector 的时候要比较小心。如有可能，最好先 reserve 出需要的空间，而不是一个个的 push back 。否则，如果你从 0 个元素，push back 100 次，其空间会重新分配 8 次（1、2、4、8、16、32、64、128）。btw, 如果你经常这样做，最好实现一个优秀的 allocator 。IMHO ，msvc 的 stl 实现并不比 stlport 差，大多数性能差别都是因为 msvc 的 stl 实现未能给出一个通用的，优化过的分配器而已。（实现一个好的内存分配器，对于大的 C++ 软件项目，都值得去做）

今天想说的并不是怎么优化这个策略。是我这几天在写代码时发现，如果你遵照空间加倍这个策略来运作，其实并不需要三个变量来维持 vector 结构，两个就够了。那个表识容量大小的变量是多余的。:D

下面是段示范代码：

利用二进制逻辑运算的性质，我们只需要把新的尺寸和老的尺寸异或，再和老的尺寸比较，就可以知道，新的尺寸的二进制最高是 1 的那一位的位置是否大于老的尺寸。然后分配新尺寸的两倍，空间是绰绰有余的。

当然，如果你希望空间分配的恰到好处（2^n -1 ），可以稍微写的繁琐一点，以下代码在 32bit 机器上，可以把一个数字从它的二进制为 1 的最高位到最低位都填成 1 。

今天把前两天写的 gc 模块开源了，本来想放到 sourceforge 上，但是我懒的注册帐号。google code 看起来更方便，选了个 bsd 的许可。然后把代码上传了。

project 在这里 http://code.google.com/p/manualgc/ 暂无下载，请直接用 svn check out 。

开源要有勇气，尤其是这么 dirty 的代码。不过话说回来，程序写了这么多年，写代码早就不拘小节了。我感觉这个东西设计上有点意思，现在也没看到有人做类似的玩意，具体实现则是次要的东西。应该还是会对某些同学有点意义的。

暂时还没完整测试过，姑且用之，不喜欢的人请直接无视。

Posted by 云风 at 09:49 PM | Permalink | Comments (14)

粽子节假期，欧洲杯开战。为了晚上不打瞌睡，我决定写程序提神。这三天的成果就是：实现了一个 C 用的垃圾收集器。感觉不错。

话说这 C 用的垃圾收集器，也不是没人做过，比如 这个 。不过它用的指针猜测的方法，总让人心里不塌实，也让人担心其收集的效率。

我希望做一个更纯粹的 gc for C/C++ 模块，接口保持足够简单。效率足够的高。三天下来，基本完成，正在考虑要不要放到 sourceforge 上开源。等过两天彻底测试过再做打算（或许再支持一下多线程收集）。

下面列一下设计目标和实现思路。

首先，采用标记清除的 gc 策略，这是目前公认的最有效的 gc 方案。远强过用引用计数的 boost::smart_ptr 那种。

接口保持足够简单，没有太多多余的东西需要使用者留意。

最重要的是效率，除了收集过程外，所有的 api 调用都要求是近似 O(1) 的时间复杂度。

先谈谈我对传统的标记清除的 gc 算法实现的一些看法。大多数实现中，都需要对 gc 模块分配出来的内存做特殊处理，在内存的头上放一些链接数据和预留标记位。IMHO ，当内存使用量较大，大过物理内存的量时，这种方案会导致收集过程异常缓慢。因为标记的过程需要访问几乎所有的内存块，这会导致大量的虚拟内存交换。就是说，无论你是否立即需要内存块里的数据，在收集过程中，每个内存块都需要碰一下。如果还包括设置标记的话，甚至需要改写虚拟内存中的数据。

我希望改进这一点，也就是说，那所有 gc 相关的数据集中在一起，整个收集过程，除了最终释放那些不再使用的内存外，不会碰用户数据块的内存。

gc 最重要的一点，就是要对堆栈上的数据进行关联。在收集发生时，堆栈上所有临时分配出来的内存块都不应该被释放掉。C 语言本身不提供堆栈遍历的特性，所以要想个自然的方案让用户可以方便的做到这点。

在用户的调用栈上，每个调用级上，临时分配的内存都被自然挂接在当前级别的堆栈挂接点上，一旦调用返回，当前级别的所有临时内存块都应该和根断开。当然，如果内存块作为返回值出现的话，需要保留。在 C 里，我们需要给每个函数的入口和出口都做一个监护，保证 gc 的正确工作。（如果是 C++ ，要稍微方便一点，在函数进入点设置一个 guard 对象即可）因为这个监护过程会非常频繁，对其的优化是重点工作。

最终，我的 gc 库暴露了 5 个 api 供用户使用：

void * gc_malloc(size_t sz, void (*free)(const void *));
void  gc_link(const void *parent, const void *prev, const void *child);
void gc_enter();
void gc_leave(const void *value, ... );
void gc_collect();

要申请内存时，可以调用 gc_malloc 申请 sz 大小的内存。free 函数指针可选。它提供一个机会，在内存真正释放之前做一些事情。

gc_link 用于建立内存块之间的联系。可以让 child 指针依赖 parent 指针。既，child 的生命期不会短于 parent 。这个 api 还可以取消 prev 和 parent 之间的联系。parent prev child 中任何一个都可以传空指针。当parent 为空时，child 挂接到根上。这通常用于维系全局变量的生命期。gc_link 保证 prev 在堆栈上有一次临时的引用。

gc_enter 和 gc_leave 当配对使用，放在一个函数或一段语句块的入口和出口处。夹在 enter 和 leave 之间的 gc_malloc 申请的内存块，生命期不会超过临近的 leave 指令。除非在 gc_leave 的参数中指明需要延长生命期。gc_leave 可以带多个指针，只需要最后一个以 0 结束。这通常用于函数的返回值。

gc_collect 用于垃圾收集，它可以在任何时机调用，把和根没有关联的内存块全部释放掉。堆栈上（没有闭合的 enter / leave 对）的所有 gc_malloc 分配的内存块都会被自动挂接在根上；用户也可以用 gc_link 主动挂接（parent 传 0）。

这套接口设计的应该是足够简洁了。用户只需要自己描述对象和对象之间的关系（使用 gc_link），别的不用太操心。

如果使用 C++ 可以进一步的封装，重载赋值操作符来做到这些。而 C 也可以定义一个宏来辅助（注意宏的一些问题，比如重复计算）。比如：

static void 
eval(void *parent,void **node,void *child)
{
    gc_link(parent,*node,child);
    *node=child;
}

#define EVAL(obj, prop, value) eval( (obj), & ((obj)-> ## prop), (value))

struct tree {
    struct tree *left;
    struct tree *right;
};

struct tree *
new_node()
{
    struct tree *n=(struct tree *)gc_malloc(sizeof(*n),0);
    memset(n,0,sizeof(*n));
    return p;
}

struct tree *
foo()
{
    struct tree *t;
    gc_enter();

    t=new_node();
    EVAL(t,left,new_node());
    EVAL(t,right,new_node());

    gc_leave(t,0);

    return t;
}

上面这个 foo 函数演示了 gc 模块的基本用法：构造了一个节点 t ，以及另外两个临时节点连接到 t 的 left 和 right 两个成员上。最后把 t 返回。

下面谈一下优化：

为了让用户数据块和关联数据分离，所以模块内部实现的时候，将指针映射到了内部 id 上，这里使用了一个 hash map 。这样，可以使用 id 保持相互关联的信息。

对象之间的关联信息是一个图结构。图的边的构建和变动复杂度较大。在实现时，做了一个 cache ，在 gc_link 的时候，不直接增删边。而是缓存对图变更的请求，并在缓冲期间合并一些操作。例如，一些临时的关联信息，可能因为周期很短，在 collect 发生前就已经解除关联，其操作就会被抵消掉。

cache 了大量操作后，对操作进行排序。批量修改图的边时，也可以减少大量的运算。（内部数据结构对图的每个节点的孩子采用一个有序数组保存，比较适合批量增删）

gc_enter 和 gc_leave 是优化的重点。因为这个调用最为频繁。而 gc_collect 发生较少，对象频繁进出堆栈，不需要重复挂接。

采用另一个 cache ，直接保存内存指针，甚至可以不做 hash map 查询（映射到内部 id ），只到 collect 发生时再一次计算。临时对象存在于堆栈上时，是一个树结构，而非图结构的关联关系（每个堆栈上的调用级是一个树节点）。这也有利于优化处理。

整个实现代码只用了 600 多行，但是却写了三个晚上。主要是为了提高处理效率（时间和空间效率），设计了一些精巧的数据结构，控制起来非常麻烦，写起来也很是小心。这次完成后，就可以替换掉去年实现的一个不太地道的 gc 模块了。当时的那个需要依赖一个单根的类树，用起来要麻烦的多。

如果日后开源的话，还有一些事情要做：代码需要更规范，补上更详细的测试代码，以及支持 64 位系统等。

6 月 10 日补充：

今天把它在 google code 上开源了，用的 BSD 的许可协议。第一个版本还很 dirty 。没有怎么测试，可能还有许多 bug 。

有兴趣的同学可以在这里用 svn check out （尚未 release ，没做下载包） ：

http://code.google.com/p/manualgc/

ps. 我的英文很滥，注释和说明可以无视。

Posted by 云风 at 01:52 AM | Permalink | Comments (63)

昨天跟同事聊天，聊到一些老游戏。我忍不住搜了一把，找到读高中时废寝忘食玩的 UFO : Enemy Unknown 。那是 94 年的故事了。

当时我就是很偶然的接触到这个游戏，没有任何人向我介绍，没有任何杂志提过，我也不知道那个 Sid Meier 创办的 MicroProse 曾经发行过文明这种大作。老实说，当时我根本没觉得文明有多么有趣。

和初次接触仙剑奇侠传一样，只是在一张光盘里拿到这个游戏，见到是刚刚发行的，就试着装上。由于全是英文，还都是些科幻色彩比较浓的生僻词，所以需要抱着字典玩。附带的一点好处就是：几年后考 CET-4 ，阅读理解里有个中心词是 craft 航空器，我看着非常熟悉，然后就考及格了。

今天网上可以搜到 MicroProse 后来为 幽浮 1 做的 windows 版的 Golden Edition 。已经没有当年我玩的 1.0 版中的诸多 bug 了（有个 bug 会导致游戏后期超大型飞碟战时程序异常，以至于我玩了两年都没通关），平衡也重新调过。记得早期的版本，士兵可以通过升级练到比坦克还凶猛。

ps . 网上流传的这个版本在 windows xp 下有个显示 bug （我测是因为 X-Mode 导致的），需要打上玩家做的一个补丁修复。具体见 X-COM: UFO Defense Bug FAQ

下载下来一不小心又玩了一通宵（选择最高难度），320x200 的图象分辨率，在 17 寸液晶显示器上全屏都不觉得难看。游戏性也比今天大多数游戏要好，玩起来很有深度。绝对不是因为我怀旧而产生的偏见。操作感也很不错，除了不支持鼠标滚轮。呵呵那个年代的鼠标好象还没有滚轮呢。

推荐对单机策略游戏有爱的同学重温一下这旧日经典。

今天还真是个特别的日子啊。google 三天两头的换 logo 图案，也就今天慎重其事的在 google 黑板报上写了一篇提示一下 。摘录最后一句：

“今天，我们以更换首页 logo 的方式，来纪念那些为人类进步做出不懈努力和尝试的人们。”

呵呵，一转眼十几年过去了。那个年代，我还没长大。

Posted by 云风 at 07:56 PM | Permalink | Comments (13)

虽然很残忍，但是我们每个人都清楚一件事：你认识的每个人，有一天都会死去。

今天母亲打了个电话过来，说一位老人离去了，我唤他叫爷爷的那位。他和我们家没有任何血缘关系，岁数比我的外公大许多，是母亲刚参加工作时的师傅。退休后身体一直很好，鳏居，平日里无人拜访。七十多岁时，还自己骑车去郊外钓鱼。

他唯一的女儿的老公中风也需要人照顾，不能守在身边。我的母亲就时常去看望他。因为老人有气管炎，需要定期服药，母亲就每周帮他去医院开药（由于福利，药是免费的，但是每次不能多拿）。

想来，我的母亲于这位老人，那真算是一日为师，终生为父。几十年的感情，是比亲生女儿还亲的。

每次我有机会回家，母亲都要带我去看望一下老人。记得前两年的时候，他精神颇好，嗓音洪亮中气十足。门口晒晒太阳，读读报纸，聊起天来，那些时政要闻比我知道的还清楚。

去年的时候，已有些糊涂。我见他的时候开始跟我聊解放军解放台湾，打到日本。说是做梦梦见了，煞有其事的样子。可精神还好。

到今年过年再见，已经半坐在床上，不太走动了。请了个保姆在家看护（一开始不舍得花钱，一直不愿意）。见了我只是嘱咐，早点结婚生子，日后可以在退休前看见下一辈成家。

老人走的时候，上个月十八号。那天母亲在我这里，接了个电话。老人住院不肯吃饭，医生护士谁劝都不吃，非要 LCY（母亲的名字）去见他。医院里的人不知 LCY 是何人，叫来他的女儿一问才知道，电话这就拨了过来。妈妈在电话里劝他好好吃饭，明天就回去看他。然后去买了十九号的车票。

但是终将没有见到最后一面。据说老人挂掉电话后，好好的吃了晚餐，沉沉睡去，再也没有醒来。

妈妈在电话里转述了老人临终前对他女儿的嘱咐，“ YY（我的小名）结婚时，一定要包上两千块的红包”。听到这里，我的眼泪一下涌了出来。

Posted by 云风 at 06:28 PM | Permalink | Comments (35)

我知道很老，但是大家不要说出来 :D 推荐一下 bbLean ，玩了一下午加一晚上，已经调整的很满意了。一开始不太习惯，后来调好了（操作习惯可以调成和标准 windows explorer 一模一样的）就很方便了，而且插件很强大。

如果还需要一个 Explorer Replacement 的话，freeware 似乎只有 xplorer² lite 可以选了。还凑合吧，就是需要自己改注册表才能替代掉 explorer 来打开文件夹。

全部整好了后，重启系统，发现启动时间明显缩短了。

ps. bbIconBox 那个插件推荐安装，很有用。而默认的 bbLeanSkin 其实可以关掉。我另外装了些小玩意，比如 bbPutty bbNote bbMemo bbRun 等等。

Posted by 云风 at 01:21 AM | Permalink | Comments (18)