Main

June 26, 2017

浅谈《守望先锋》中的 ECS 构架

今天读了一篇 《守望先锋》架构设计与网络同步 。这是根据 GDC 2017 上的演讲 Overwatch Gameplay Architecture and Netcode 视频翻译而来的,所以并没有原文。由于是个一小时的演讲,不可能讲得面面俱到,所以理解起来有些困难,我反复读了三遍,然后把英文视频找来(订阅 GDC Vault 可以看,有版权)看了一遍,大致理解了 ECS 这个框架。写这篇 Blog 记录一下我对 ECS 的理解,结合我自己这些年做游戏开发的经验,可能并非等价于原演讲中的思想。

Entity Component System (ECS) 是一个 gameplay 层面的框架,它是建立在渲染引擎、物理引擎之上的,主要解决的问题是如何建立一个模型来处理游戏对象 (Game Object) 的更新操作。

传统的很多游戏引擎是基于面向对象来设计的,游戏中的东西都是对象,每个对象有一个叫做 Update 的方法,框架遍历所有的对象,依次调用其 Update 方法。有些引擎甚至定义了多种 Update 方法,在同一帧的不同时机去调用。

这么做其实是有极大的缺陷的,我相信很多做过游戏开发的程序都会有这种体会。因为游戏对象其实是由很多部分聚合而成,引擎的功能模块很多,不同的模块关注的部分往往互不相关。比如渲染模块并不关心网络连接、游戏业务处理不关心玩家的名字、用的什么模型。从自然意义上说,把游戏对象的属性聚合在一起成为一个对象是很自然的事情,对于这个对象的生命期管理也是最合理的方式。但对于不同的业务模块来说,针对聚合在一起的对象做处理,把处理方法绑定在对象身上就不那么自然了。这会导致模块的内聚性很差、模块间也会出现不必要的耦合。

我觉得守望先锋之所以要设计一个新的框架来解决这个问题,是因为他们面对的问题复杂度可能到了一个更高的程度:比如如何用预测技术做更准确的网络同步。网络同步只关心很少的对象属性,没必要在设计同步模块时牵扯过多不必要的东西。为了准确,需要让客户端和服务器跑同一套代码,而服务器并不需要做显示,所以要比较容易的去掉显示系统;客户端和服务器也不完全是同样的逻辑,需要共享一部分系统,而在另一部分上根据分别实现……

May 27, 2017

epoll 的一个设计问题

问题的起因是 skynet 上的一个 issue ,大概是说 socket 线程陷入了无限循环,有个 fd 不断的产生新的消息,由于这条消息既不是 EPOLLIN 也不是 EPOLLOUT ,导致了 socket 线程不断地调用 epoll_wait 占满了 cpu 。

我在自己的机器上暂时无法重现问题,从分析上看,这个制造问题的 fd 是 0 ,也就是 stdin ,猜想和重定向有关系。

skynet 当初并没有处理 EPOLLERR 的情况(在 kqueue 中似乎没有对应的东西),这个我今天的 patch 补上了,不过应该并不能彻底解决问题。

我做了个简单的测试,如果强行 close fd 0 ,而在 close 前不把 fd 0 从 epoll 中移除,的确会造成一个不再存在的 fd (0) 不断地制造 EPOLLIN 消息(和 issue 中提到的不同,不是 EPOLLERR)。而且我也再也没有机会修复它。因为 fd 0 被关闭,所以无法在出现这种情况后从 epoll 移除,也无法读它(内核中的那个文件对象),消息也就不能停止。

March 14, 2017

sproto 的一些更新

sproto 是我设计的一个类 google protocol buffers 的东西。

在很多年前,我在我经手的一些项目中使用 google protocol buffers 。用了好几年,经历了几个项目后,我感觉到它其实是为静态编译型语言设计的协议,其实并没有脱离语言的普适性。在动态语言中,大家都不太愿意使用它(json 更为流行)。一个很大的原因是,protobuffers 是基于代码生成工作的,如果你不使用代码生成,那么它自身的 bootstrap 就非常难实现。

因为它的协议本身是用自身描述的,如果你要解析协议,必须先有解析自己的能力。这是个先有鸡还是先有蛋的矛盾。过去很多动态语言的 binding 都逃不掉引入负责的 C++ 库再加上一部分动态代码生成。我对这点很不爽,后来重头实现了 pbc 这个库。虽然它还有一些问题,并且我不再想维护它,这个库加上 lua 的 binding 依然是 lua 中使用 protobuffer 的首选。

February 14, 2017

跟踪数据结构的变更

这两个月,我的主要工作是跟进公司内一个 MMORPG 项目,做一些代码审查提出改进意见的工作。

在数月前,项目经理反应程序不太稳定,经常出一些错误,虽然马上就可以改好,但是随着开发工作推进,不断有新的 bug 产生。我在浏览了客户端的代码后,希望修改一下客户端的 UI 框架以及消息分发机制等,期望可以减少以后的 bug 出生概率。由于开发工作不可能停下来重构,所以这相当于给飞行中的飞机换引擎,做起来需要非常小心,逐步迭代。

工作做了不少,其中一个小东西我觉得值得拿出来写写。

我希望 UI 部分可以严格遵守 MVC 模式来实现。其实道理都明白,但实际操作的时候,大部分人又会把这块东西实现得不伦不类。撇开各种条条框框,纸上谈兵的各种模式,例如 MVC MVP MVVM 这些玩意,我认为核心问题不在于 M 和 V 大家分不清楚,而是 M 和 V 产生联系的时候,到底应该怎么办。联系它们的是 C 还是 P 或是 VM 都只为解决一个问题:把 M 和 V 解耦。

January 23, 2017

一个简单的 lua 对象回收再利用方案

昨天在 review 我公司一个正在开发的项目客户端代码时,发现了一些坏味道。

客户端框架创建了一个简单的对象系统,用来组织客户端用到的对象。这些对象通常是有层级关系的,顶层对象放在一个全局集里,方便遍历。通常,每帧需要更新这些对象,处理事件等等。

顶层每个对象下,还拥有一些不同类别的子对象,最终成为一个森林结构,森林里每个根对象都是一颗树。对象间有时有一些引用关系,比如,一个对象可以跟随另一个对象移动,这个跟随就不是拥有关系。

这种设计方法或模式,是非常常见的。但是在实现手法上,我闻到了一丝坏味道。

September 19, 2016

ephemeron table 对 property tables 的意义

今天在公司群里,Net bug 同学提出了一个问题,围绕这个问题大家展开了一系列讨论。讨论中谈及了 lua 中的一个常见的模式:property table ,我觉得挺有意思,记录一下。

最初的问题是:当一个对象的某些属性并不常用,希望做惰性初始化的话,应该怎么实现。

我认为,property table 是一个很符合这个案例的常见模式。

比如,对象 f 有三个可能的成员 a b c ,我们可以不把 f.a f.b f.c 记录在 f 这个 table 里,而是额外有三张大表,a b c 。利用 metatable ,可以在访问 f.a 的时候,实际访问的是 a[f] 。也就是说,所有同类对象的 a 属性,都是从 a 这张表里访问的。

a 这张表的 key 就是对象,value 是对象对应的 a 属性值。

January 17, 2016

嵌入式 lua 中的线程库

无论是客户端还是服务器,把 lua 作为嵌入语言使用的时候,都在某种程度上希望把 lua 脚本做多线程使用。也就是你的业务逻辑很可能有多条业务线索,而你希望把它们跑在同一个 lua vm 里。

lua 的 coroutine 可以很好的模拟出线程。事实上,lua 自己也把 coroutine 对象叫做 thread 类型。

最近我在反思 skynet 的 lua 封装时,想到我们的主线程是不可以调用阻塞 api 的限制。即在主干代码中,不可以直接 yield 。我认为可以换一种更好(而且可能更简洁)的封装形式来绕过这个限制,且能简化许多其它部分的代码。

下面介绍一下我的新想法,它不仅可以用于 skynet 也应该能推广到一切 lua 的嵌入式应用(由你自己来编写 host 代码的应用,比如客户端应用):

January 06, 2016

基于引用计数的对象生命期管理

最近在尝试重新写 skynet 2.0 时,把过去偶尔用到的一个对象生命期管理的手法归纳成一个固定模式。

先来看看目前的做法:旧文 对象到数字 ID 的映射

其中,对象在获取其引用传入处理函数中处理时,将对象的引用加一,处理完毕再减一。这就是常见的基于引用计数的对象生命期管理。

常规的做法(包括 C++ 的智能指针)是这样的:对象创建时,引用为 1 (或 0)。每次要传给另一个处地方处理,或保留待以后处理时,就将其引用增加;不再使用时,引用递减。当引用减为 0 (或负数)时,把对象引用的资源回收。

由于此时对象不再被任何东西引用,这个回收销毁过程就可视为安全且及时的。不支持 GC 的语言及用这些语言做出来的框架都用这个方式来管理对象。


这个手法的问题在于,对象的销毁时机不可控。尤其在并发环境下,很容易引发问题。问题很多情况是从性能角度考虑的优化造成的。

加减引用本身是个很小的开销,但所有的引用传递都去加减引用的话,再小的开销也会被累积。这就是为什么大多数支持 GC 的语言采用的是标记扫描的 GC 算法,而不是每次在对象引用传递时都加减引用。

大部分情况下,你能清楚的分辨那些情况需要做引用增减,哪些情况下是不必的。在不需要做引用增减的地方去掉智能指针直接用原始指针就是常见的优化。真正需要的地方都发生在模块边界上,模块内部则不需要做这个处理。但是在 C/C++ 中,你却很难严格界定哪些是边界。只要你不在每个地方都严格的做引用增减,错误就很难杜绝。


使用 id 来取代智能指针的意义在于,对于需要长期持有的对象引用,都用 id 从一个全局 hash 表中索引,避免了人为的错误。(相当于强制从索引到真正对象持有的转换)

id 到对象指针的转换可以无效,而每次转换都意味着对象的直接使用者强制做一个额外的检查。传递 id 是不需要做检查的,也没有增减引用的开销。这样,一个对象被多次引用的情况就只出现在对象同时出现在多个处理流程中,这在并发环境下非常常见。这也是引用计数发挥作用的领域。

而把对象放在一个集合中这种场景,就不再放智能指针了。


长话短说,这个流程是这样的:

将同类对象放在一张 hash 表中,用 id 去索引它们。

所有需要持有对象的位置都持有 id 而不是对象本身。

需要真正操作持有对象的地方,从 hash 表中用 id 索引到真正的对象指针,同时将指针加一,避免对象被销毁,使用完毕后,再将对象引用减一。

前一个步骤有可能再 id 索引对象指针时失败,这是因为对象已经被明确销毁导致的。操作者必须考虑这种情况并做出相应处理。


看,这里销毁对象的行为是明确的。设计系统的人总能明确知道,我要销毁这个对象了。 而不是,如果有人还在使用这个对象,我就不要销毁它。在销毁对象时,同时有人正在使用对象的情况不是没有,并发环境下也几乎不能避免。(无法在销毁那一刻通知所有正在操作对象的使用者,操作本身多半也是不可打断的)但这种情况通常都是短暂的,因为长期引用一个对象都一定是用 id 。

了解了现实后,“当对象的引用为零时就销毁它” 这个机制是不是有点怪怪的了?

明明是:我认为这个对象已经不需要了,应该即使销毁,但销毁不应该破坏当下正在使用它的业务流程。


这次,我使用了另一个稍微有些不同的模式。

每个对象除了在全局 hash 表中保留一个引用计数外,还附加了一个销毁标记。这个标记只在要销毁时设置一次,且不可翻转回来。

现在的流程就变成了,想销毁对象时,设置 hash 表中关联的销毁标记。之后,检查引用计数。只有当引用计数为 0 时,再启动销毁流程。

任何人想使用一个对象,都需要通过 hash 表从 id 索引到对象指针,同时增加引用计数,使用完毕后减少引用。

但,一旦销毁标记设置后,所有从 id 索引到对象指针的请求都会失败。也就是不再有人可以增加对象的引用,引用计数只会单调递减。保证对象在可遇见的时间内可被销毁。

另外,对象的创建和销毁都是低频率操作。尤其是销毁时机在资源充裕的环境下并不那么重要。所以,所有的对象创建和销毁都在同一线程中完成,看起来就是一个合理的约束了。 尤其在 actor 模式下, actor 对象的管理天生就应该这么干。

有了单线程创建销毁对象这个约束,好多实现都可以大大简化。

那个维护对象 id 到指针的全局 hash 表就可以用一个简单的读写锁来实现了。索引操作即对 hash 表的查询操作可遇见是最常见的,加读锁即可。创建及销毁对象时的增删元素才需要对 hash 表上写锁。而因为增删元素是在同一线程中完成的,写锁完全不会并发,对系统来说是非常友好的。

对于只有唯一一个写入者的情况,还存在一个小技巧:可以在增删元素前,复制一份 hash 表,在副本上慢慢做处理。只在最后一个步骤才用写锁把新副本交换过来。由于写操作不会并发,实现起来非常容易。

November 30, 2015

RPC 之恶

起因是最近有人在 skynet 邮件列表里贴了段错误 log ,从 log 显示,他在 table.sort 的比较函数里调用了 skynet 的 snax rpc 去获取远程数据。然后被 lua 无情的报了 attempt to yield across a C-call boundary 。

就 table.sort 不能 yieldable 的问题,其实在 lua 邮件列表里讨论过 。老大的说法是,这个 C 实现是递归的,想要在 C 层面保留上下文非常困难,如果勉强实现,也会大大降低正常不需要 yield 的 case 的性能,非常不划算。

通过这件事,我反而觉得 none-yieldable 的限制反而提前阻止了一个错误的实现,其实是应该庆幸的。

April 27, 2015

sproto rpc 的用法

sproto 是我自己设计, 用在我们新项目中取代过去用到的 google protocol buffers 的东西。

为什么不用 protobuf ? 这个问题我有足够的发言权。在 lua 语言为主的项目中,sproto 更合适。google 官方并没有给 protobuf 加入 lua 支持。现在在网上流传的 protobuf lua 方案,被人用的最多的两种,一个是 pbc 的 lua binding ,另一个是 protoc-gen-lua 。前者是我在开发维护,并使用了多年;后者是在我过去的项目中,项目中的同事因为需要而开发的。

另外,在我的项目的副产品中,还有开源的 protobuffer 的 as3 库以及 erlang 库,都有许多用户。所以,我相信我对 protobuf 有足够长时间的使用经验以及对它有足够的了解。这也是放弃 protobuf 而转向自己设计的 sproto 的底气所在。

在这一篇 blog 中,不想讨论 protobuf 的优劣,只谈谈 sproto 中如何使用 rpc 的 api 。这是 sproto 的 api 文档中没有写明,而很多想用它的同学问起的问题。


March 13, 2015

给 sproto 增加 unordered map 的支持

花了两天给 sproto 增加了 unordered map 的支持。

问题是这样的:

sproto 支持数组,但很多情况下,业务处理中,我们并不用数组来保存大量的相同类型的结构数据。因为那样不方便检索。

比如你要配置若干地图表、NPC 表等等的信息,固然可以用 sproto 的 array 来保存。但是在运行时,你更希望用定义好的 id 来检索它们。如果 sproto 不支持 unordered map 的话,你就需要在 decode 之后,对 array table 做一次遍历,用一张新表来建立索引。

google protocal buffers 2 也有这个问题,据说第 3 版要增加 map 用来兼容 json ,这个话题最后再说。

September 21, 2014

ejoy2d shader 模块改进计划

由于有公司很多同事参与 ejoy2d 的开发,所以 ejoy2d 这个项目已经转移到 ejoy 的 github 名下。

有更多项目的参与的情况下,原来 ejoy2d 的简单构架慢慢显出一些局限性。主要是不同的项目会根据项目的需要(通常是针对某些特定需求的优化,以及特别的效果需求)修改底层 shader 的部分。最早设计的时候,因为考虑到只是用于 2d 游戏的开发,所以把 shader 模块实现的比较简单。特别是 attribute layout 是固定的,而 uniform 管理也没有留下太多扩展性。

在现代手机的 GPU 架构下,从渲染层渲染层 API 看,其实 2d 和 3d 其实没有本质上的区别。都是基于三角片渲染的。需要把顶点上传到 GPU 中由 vs 处理,在最后对像素做 fs 渲染出来。

而 2d engine 和 3d engine 的区别通常在于 2d engine 的顶点变换很简单。不需要用 projection matrix 和 view matrix 做变换。2d engine 中的对象多半是四边形,数量很多,常见的优化手法是将大量的四边型合并到同一个渲染批次中;所以 world matrix (以平移变换为主)在 CPU 中和顶点计算再提交更常见一些。

2d engine 从应用上说,就是在处理一张张图片。所以对图片(四边型)的处理的变化要多一些。这使得 fs 要多变一点,需要引擎提供一定的可定制性。但很少去处理 3d engine 常见的光照投影这些东西。更多的是为了优化贴图用量等目的而技巧性的去使用一些图片。

突出 2d engine 的专门面对的业务的特性,而简化 GPU 提供的模型,用简短的代码构建 engine 框架,是 ejoy2d 设计的初衷。而且我也相信,简单可以带来更好的性能。所以一开始设计 ejoy2d 的时候,shader 模块的很多东西都被写死了,以最简单的方式达到目的。仅暴露了很少的外部接口,再在这些有限的接口上设计数据结构,做性能优化。

August 12, 2014

STM 的简单实现

STM 全称 Software transactional memory

在前年的项目里,我制作了一个类似的东西。随着 skynet 的日趋完善,我希望找到一个更为简单易用的方法实现类似的需求。

对于不常更新的数据,我在 skynet 里增加了 sharedata 模块,用于配置数据的共享。每次更新数据,就将全部数据打包成一个只读的树结构,允许多个 lua vm 共享读。改写的时候,重新生成一份,并将老数据设置脏标记,指示读取者去获取新版本。

这个方案有两个缺点,不适合实时的数据更新。其一,更新成本过大;其二,新版本的通告有较长时间的延迟。

我希望再设计一套方案解决这个实时性问题,可以用于频繁的数据交换。(注:在 mmorpg 中,很可能被用于同一地图上的多个对象间的数据交换)

一开始的想法是做一个支持事务的树结构。对于写方,每次对树的修改都同时修改本地的 lua table 以及被修改 patch 累计到一个尽量紧凑的序列化串中。一个事务结束时,调用 commit 将快速 merge patch 。并将整个序列化串共享出去。相当于快速做一个快照。

读取者,每次读取时则对最新版的快照增加一次引用,并要需反序列化它的一部分,变成本地的 lua table 。

我花了一整天实现这个想法,在写了几百行代码后,意识到设计过于复杂了。因为,对于最终在 lua 中操作的数据,实现一个复杂的数据结构,并提供复杂的 C 接口去操作它性能上不会太划算。更好的方法是把数据分成小片断(树的一个分支),按需通过序列化和反序列化做数据交换。

既然序列化过程是必须的,我们就不需要关注数据结构的问题。STM 需要管理的只是序列化后的消息的版本而已。这一部分(尤其是每个版本的生命期管理)虽然也不太容易做对,但结构简单的多。

July 28, 2014

sproto 的实现与评测

这个周末,我实现了上周设计的简化版 protocol buffers 协议 ,并重新命名为 sproto

在实现过程中,发现了许多编码格式上可以优化的地方,所以一边实现一边做调整,使结构更适合编码和解码,并且更紧凑。

做了如下改动:

由于这个东西主要 binding 到 lua 这样的动态语言中使用,所以我不需要按 Cap'n Proto 那样,直接访问编码后的数据结构(直接把数据结构映射为 C/C++ 对象),所以数据对齐是不必要的。

编码时的 tag 如果要求严格升序也可以更快的处理数据,减少实现的复杂度。数据段也要求按持续排列,且不准复用。这样可以让数据中有更多的 0 方便压缩。

把 boolean 数组按位打包的意义也不太大(会增加实现的复杂度)。

暂时先不实现 64bit id 的类型。(以后再加)

最终的 Wire Protocol 是这样的:

July 24, 2014

设计一种简化的 protocol buffer 协议

我们一直使用 google protocol buffer 协议做客户端服务器通讯,为此,我还编写了 pbc 库

经过近三年的使用,我发现其实我们用不着那么复杂的协议,里面很多东西都可以简化。而另一方面,我们总需要再其上再封装一层 RPC 协议。当我们做这层 RPC 协议封装的时候,这个封装层的复杂度足以比全新设计一套更合乎我们使用的全部协议更复杂了。

由于我们几乎一直在 lua 下使用它,所以可以按需定制,但也不局限于 lua 使用。这两天,我便构思了下面的东西:

March 02, 2014

谈谈陌陌争霸在数据库方面踩过的坑(排行榜篇)

为什么大部分网络服务都需要一个数据库在后台支撑整个系统?

这通常是因为大部分系统的一个运行周期都很短,对于传统的网站服务来说,从收到一个 HTTP 请求开始,到终端用户收到这个请求的结果为止,就是一个运行周期。而其间可能处理的数据集是很大的,通常没有时间(甚至没有空间)把所有数据都加载到内存,处理其中涉及的一小部分,然后保存在磁盘上再退出。

当数据量巨大时,任何对数据的操作的算法和数据结构都需要精心设计,这不是随便一个程序员就可以轻松完成的任务。尤其是数据量大到超过内存容量时,很多算法和数据结构对大部分非此领域的程序员来说都是陌生的。本着专业的事情交给专业的人来做的原则,一般系统都会把这部分工作交给独立的数据库来完成。

对数据的操作只有抽象的足够简单,系统才能健壮,这便有了 SQL 语言做一层抽象,让数据管理的工作可以独立出来。甚至于你想牺牲一部分的特性来提高性能,还可以选用近年来流行的各种 NOSQL 数据库。

可在 MMO 游戏服务器领域,事情发生了一点点变化。

数据和业务逻辑是密切相关的,改变非常频繁。MMO 服务器需要持续快速的响应用户的请求。我们几乎不可能把一切数据都放在独立的数据库中,比如玩家在虚拟世界中的位置,以及他所影响的其他玩家的列表;玩家战斗时的各种属性变化,还有和玩家互动的那些 NPC 的状态改变……

最大的矛盾是:MMO 游戏中数据集的改变不再是简单的 SQL 可以表达的东西,不可能交给数据库服务期内部完成。无论什么类型的数据库,都不是为这种应用设计的。如果你硬要套用其它领域的应用模式的话,游戏服务器只能频繁的把各种数据从数据库中读出来,按游戏逻辑做出改变,再写回去。数据库变成了一个很低效的数据中转中心,无论你是否使用内存数据库,都改变不了这个低效的本质。

我听过无数从别的领域转行到游戏领域做开发的程序员设计出来的糟糕系统。他们最终仅仅把数据库当成一个可靠的数据储存点和中转点,认为把所谓重要的数据写进数据库就万事大吉,然后再别扭的从另一个位置把数据从数据库读出来使用。系统中充满了对数据库的奇怪异步回调用来改善系统的反应速度,而系统却始终步履阑珊。能做对已经是极限了,更何况游戏系统不仅仅是输入输出正确就是正确,如果超过了应用的响应时间,一切都是不正确的。

October 10, 2013

D 语言的数组和字符串

这个国庆假期,我读完了《D程序设计语言》 一书。里面读到了很多有趣的东西,挑一点写出来和大家分享一下。

字符串,数组和关联数组(hash 表)是最重要的三种数据结构,我们几乎可以利用它们模拟出任何更复杂的结构。Lua 就是这么干的,只不过 Lua 把数组和关联数组合并成一个 table 类型了。D 在语言层面对这三种数据结构支持的很好,概念定义非常清晰。这一篇只谈数组和字符串,不涉及 hash 表的部分。


数组可以看成是存放同一类型数据的连续内存。

在 C 语言中,数组和指针虽然是不同的类型,但编译器生成的代码却是相同的,可以说实质上,数组即指针。但将数组隐含有长度信息,即内存的范围。有些数组是固定大小的,在编译器就知道其范围;有些数组需要动态扩展大小,其范围是运行期确定,并可以改变的。无论如何,对数组的随机访问,缺乏边界检查的代码都隐藏着风险。

D 语言是一门期望有高安全性的同时又重视运行性能的语言。它在平衡这个问题上的解决方案很有趣。程序员可以指定一段代码是安全的,还是系统级的,还是是接口安全的。根据不同的标注来插入边界检查代码。在 debug 版中,即使是系统级代码,也会插入类似 assert 的契约检查。

由于 D 语言以 GC 为内存管理核心(且要求所有数据都是位置无关,可移动的),所以管理数组切片 Slice 就变得很简单。不同的Slice 引用同一块内存,不用担心数据生命期问题。扩展数组也可以根据需要重新分配内存,或是在原地扩展。

提到数组扩展,不得不谈一下 D 语言中结构的 postblit 。D 语言中,所有的 class 都是引用语义的,而 struct 是值语义的。C++ 中花了很多年想解决的一个性能问题就是源于 vector 扩展时,数据如何从旧的位置移动新位置的问题。在 stl 的 sgi 实现中,为 POD 结构增加的特化模板来提高复制效率;在 C++11 中又从语言层面增加了右值引用来实现移动语义,来解决反复析构构造对象带来的性能浪费。

而 D 语言中没有那些晦涩的移动构造,拷贝构造概念;它只有 postblit 。也就是数据都应该默认按位复制(blit),然后在 blit 后,再用 postblit 方法去修改新的副本。这种不动源对象,而只在副本上修改的移动钩子技术概念更简单清晰。而且编译器可以自行推导什么时候调用 postblit 才是必要的。这个技术不仅仅用来解决数组的扩展问题,也可以很好的搞定 C++ 中返回值优化问题。

对于固定大小的数组,D (2.0) 是按值类型处理的(动态数组则是引用类型),不同长度的数组是不同的类型,但它们都可以隐式转换(映射)成动态数组。比较短的固定数组做值传递的时候更方便高效,也符合其它基础类型的特征。长数组可以通过 ref 修饰按引用传递。

September 17, 2013

一个简单的 C string 库

C 语言缺乏原生的 string 类型的支持,这使得字符串管理非常烦琐。我在 2006 年左右的一个项目中,我根据项目实际情况,简化了 C string 库,把大部分 string 都做了 string interning ,并直到进程退出再释放 string interning pool 。

但这种用法毕竟不够通用。

今天读到 facebook 开源的 libPhenom ,里面也实现了一个简单的 string 库。我有些想法。

libphenom 的 string 库核心想针对问题是尽量的减少堆上内存的动态分配。它把大部分临时字符串都放在栈上处理,也提供了用户自定义串空间的方法。我觉得这个方向是不错的,但是其实大可不必提供太多的弹性,只要尽量让临时字符串存在于栈上即可。而另一个很重要的功能,也就是 string interning 我认为更有实用性。

string interning 可以实现 symbol 类型,对于类似 json/xml 的解析来说非常有意义。可以节约许多内存,而且可以加快 symbol 的比较和 hash 速度。不过对所有字符串无差别的做 interning 有可能因为外部输入多变也被攻击。对 interning 的字符串做引用计数也会降低性能。

June 07, 2013

MongoDB 的 Lua Driver

最近听从同事建议想尝试一下 MongoDB 。

前年,图灵的同学送过我一本《MongoDB权威指南》 ,当时我花了两个晚上看完。我所有的认知就是这本书了。我们最近的合作项目 狂刃 也是用的 MongoDB ,最近封测阶段,关于数据库部分也出过许多问题。蜗牛同学在帮助成都的同学做调优,做了不少工作。总是能在办公室里听到关于 MongoDB 的话题。

我打算为 skynet 做一个 MongoDB 的 Driver 。

Skynet 默认是用 lua 做开发语言的。那么为什么不直接用 luamongo 呢?

因为 skynet 需要一个异步库,不希望一个 service 在做数据库操作的时候被阻塞住。那么,我们就不可能直接把 luamongo 作为库的形式提供给 lua 使用。

一个简单的方法是 skynet 目前对 redis 做的封装那样(当然,skynet 中的 redis 封装也是非阻塞的),提供一个独立的 service 去访问数据库,然后其它服务器向它发送异步请求。如果我直接使用 luamongo 就会出现一个问题:

我需要先把请求从 lua table 序列化,发送给和 mongoDB 交互的位置,反序列化后再把 lua table 打包成 bson 。获得 MongoDB 的反馈后,又需要逆向这个流程。这是非常低效的事情。如果我们可以直接让请求方生成 bson 对象,这样就可以直接把 bson 对象的指针发过到 交互模块就够了( skynet 是单进程模型,可以在服务内直接交换 C 指针)。这就需要我定制一套 lua moogodb 的 driver 了。

April 16, 2013

树结构的一点想法

数据结构中的树结构在抽象复杂事物时非常常见,在图形引擎中,多用于场景以及 sprite 的层级管理。在 GUI 相关的模块中也是必备的结构。其它领域,比如对程序源码本身的解释翻译,以及对数据文件的组织管理,都离不开树结构。

我觉得,这是因为一个对象,除了它自身的属性(例如大小、形状、颜色等)之外,还需要一些外部属性(例如位置、层次、方向等)需要逐级继承。每个对象都可以分解成更细的对象组合而构成、这些对象在组成新的对象后,它们的聚合体又体现出和个体的相似性(至少具有类似的外部属性)。这使得采用树状数据结构最容易描述它们。

我最近的一些工作代码做了很多这方面的工作,回想这些年里,我不只一次的思考类似的问题(参看 2009 年的一篇 blog),而每次最后解决问题的代码的都有些不同,编程风格也有一些变化。总结一下这段时间的思考,今天再写这么一篇 blog 。

树结构的基本操作无非是遍历整棵树、遍历一层分支、添加节点、移动节点、删除节点这些。但在大部分应用环境下,我们最多用到的只是遍历,而非控制树的结构本身。

March 19, 2013

Objective-C 的对象模型

最近稍微学习了一点 Objective-C ,做笔记和做编码练习都是巩固学习的好方法。整理记录脑子里的新知识有助于理清思路,发现知识盲点以及错误的理解。

Objective-C 和 C++ 同样从兼容 C 语言开始,以给 C 语言增加面向对象为初衷,他们的出现的时间都很类似(1983 年左右)。但面向对象编程的源头却不同:C++ 受 Simula 和 Ada 的影响比较多,而 Objective-C 的相关思想源至 Smalltalk ,最终的结果是他们在对象模型上有不小的差异。

以我这些天粗浅的了解,Objective-C 似乎比 C++ 更强调类型的动态性,而牺牲了一些执行性能。不过这些牺牲,由于模型清晰,可以在今天,由更先进的编译技术来弥补了。

我对 C++ 的认知比 Objective-C 要多的多,所以对 C++ 开发中会遇到的问题的了解也多的多。在学习 Objective-C 的过程中,我发现很多地方都可以填上曾经在 C++ 开发中遇到的问题。当然,Objective-C 一定也有它自己的坑,只是我才刚开始,没有踩到过罢了。


ObjC 的类方法调用的形式,更接近于向对象发送消息。语法写作:

March 11, 2013

最近一些心得

最近特别忙, 每天写程序的时间都不够。有些东西在做完之前不想公开谈,所以只把一些笔记发在公司内部的周报里了。等这段时间过去,再贴到这里来。

不过还是有一些泛泛的心得可以写写的。

前几天遇到一个优化的问题。我想采用定期计算路图的方式优化寻路的算法。而不用每次每个单位在想查找目标的时候都去做一次运算并记录下路径结果。一切都看起来很顺利,算法的正确性很快就被验证了。可是最后实际跑的时候,发现在生成路图的地方会稍微卡一下影响流畅性。

January 14, 2013

Pixel light 中的场景管理

这几天无意中发现一款开源的 3d engine ,名为 pixel light文档 虽然不多,但写的很漂亮。从源码仓库 clone 了一份,读了几天,感觉设计上有许多可圈可点的地方,颇为有趣。今天简略写一篇 blog 和大家分享。

ps. 在官方主页上,pixel light 是基于 OpenGL 的,但实际上,它将渲染层剥离的很好。如果你取的是源代码,而不是下载的 SDK 的话,会发现它也支持了 Direct3D 。另,从 2013 年开始,这个项目将 License 改为了 MIT ,而不是之前的 LGPL 。对于商业游戏开发来说,GPL 的确不是个很好的选择。

这款引擎开发历史并不短(从 2002 年开始),但公开时间较晚(2010 年),远不如 OGRE 等引擎有名。暂时我也没有看到有什么成熟的游戏项目正在使用。对于没有太多项目推动的引擎项目,可靠性和完备性是存疑的。不推荐马上在商业游戏项目中使用。但是,他的构架设计和源代码绝对有学习价值。

September 03, 2012

Skynet 设计综述

经过一个月, 我基本完成了 skynet 的 C 版本的编写。中间又反复重构了几个模块,精简下来的代码并不多:只有六千余行 C 代码,以及一千多 Lua 代码。虽然部分代码写的比较匆促,但我觉得还是基本符合我的质量要求的。Bug 虽不可避免,但这样小篇幅的项目,应该足够清晰方便修正了吧。

花在 Github 上的这个开源项目上的实际开发实现远小于一个月。我的大部分时间花了和过去大半年的 Erlang 框架的兼容,以及移植那些不兼容代码和重写曾经用 Erlang 写的服务模块上面了。这些和我们的实际游戏相关,所以就没有开源了。况且,把多出这个几倍的相关代码堆砌出来,未必能增加这个开源项目的正面意义。感兴趣的同学会迷失在那些并不重要,且有许多接口受限于历史的糟糕设计中。

在整合完我们自己项目的老代码后,确定移植无误,我又动手修改了 skynet 的部分底层设计。在保证安全迁移的基础上,做出了最大限度的改进,避免背上过多历史包袱。这些修改并不容易,但我觉得很有价值。是我最近一段时间仔细思考的结果。今天这一篇 blog ,我将最终定稿的版本设计思路记录下来,备日后查阅。

July 23, 2012

C 的 coroutine 库

今天实现了一个 C 用的 coroutine 库.

我相信这个东西已经被无数 C 程序员实现过了, 但是通过 google 找了许多, 或是接口不让我满意, 或是过于重量.

在 Windows 下, 我们可以通过 fiber 来实现 coroutine , 在 posix 下, 有更简单的选择就是 setcontext

我的需求是这样的:

March 31, 2012

开发笔记(16) : Timer 和异步事件

这几天,安排新来的王同学做数据持久化工作。一开始他是将 sharedb 里的数据序列化为文本储存的。这步工作做完后,开始动手把数据放到 Redis 数据库中。我们的系统主干由 Lua 构建,所以需要一个 Lua 的 Redis 库。google 来的那份,王同学不满意。三下五除二自己重写了一个。据说把代码量减少到了原来的三分之一(开源计划我正在督促)。唯一的问题是,如果直接采用系统的 socket 库,不能很好的嵌入我们的整个通讯框架。我们的 skynet 全部是通过异步 IO 自己调度的,如果这个数据服务单方面阻塞了进程,会使得别的进程获得不了时间片。

蜗牛同学打算改进 skynet 增加异步 IO 的支持。

我今天在考虑现有的 API 时候,对比原有的 timer 接口和打算新增加的异步 IO 接口,发现它们其实是同一类东西。即,都是一个异步事件。由客户准备好一类请求,绑定一个 session id 。当这个事件发生后,skynet 将这个 session id 推送回来,通知这个事件已经发生。

在用户编写的代码的执行序上,异步 IO 和 RPC 调用一样,虽然底层通过消息驱动回调机制转了一大圈,但主干上的逻辑执行次序是连续的。

受历史影响,我之前在封装 Timer 的时候,受到历史经验的影响,简单的做了个 lua 内 callback 的封装。今天仔细考虑后发现,我们整个系统不应该存在任何显式的回调机制。正确的接口应该保持和异步 IO 一致:

January 20, 2012

libuv 初窥

过年了,人都走光了,结果一个人活也干不了。所以我便想找点东西玩玩。

今天想试一下 libev 写点代码。原本在我那台 ubuntu 机器上一点问题都没有,可在 windows 机上用 mingw 编译出来的库一个 backend 都没有,基本不可用。然后网上就有同学推荐我试一下 libuv 。

libuv 是 node.js 作者做的一个封装库,在 unix 环境整合的 libev ,而在 windows 下用 IOCP 另实现了一套。看起来挺满足我的玩儿的需求的。所以就试了一下。

January 11, 2012

铁路订票系统的简单设计

其实铁路订票系统面临的技术难点无非就是春运期间可能发生的海量并发业务请求。这个加上一个排队系统就可以轻易解决的。

本来我在 weibo 上闲扯两句,这么简单的方案,本以为大家一看就明白的。没想到还是许多人有疑问。好吧,写篇 blog 来解释一下。

简单说,我们设置几个网关服务器,用动态 DNS 的方式,把并发的订票请求分摊开。类比现实的话,就是把人分流到不同的购票大厅去。每个购票大厅都可以买到所有车次的票。OK ,这一步的负载均衡怎么做我就不详细说了。

每个网关其实最重要的作用就是让订票的用户排队。其实整个系统也只用做排队,关于实际订票怎么操作,就算每个网关后坐一排售票员,在屏幕上看到有人来买票,输入到内部订票系统中出票,然后再把票号敲回去,这个系统都能无压力的正常工作。否则,以前春运是怎么把票卖出去的?

我们来说说排队系统是怎么做的:

January 09, 2012

开发笔记 (7) : 服务器底层框架及 RPC

很久没有写工作笔记了,如果不在这里写,我连写周报的习惯都没有。所以太长时间不写就会忘记到底做了些啥了。

这半个多月其实做了不少工作,回想起来又因为太琐碎记不太清。干脆最近这几天完成的这部分工作来写写吧。

我在 开发笔记 第四篇谈到了 agent 的处理流程。但实际操作下来还是觉得概念显得复杂。推而广之,对于不是 agent 的服务,我需要一个通用的消息处理框架。

对于每个服务器,可以看成是对一组约定的服务协议进行处理。对于协议分组,之前我有许多想法,可做下来又发现了若干问题。本来我希望定义出一个完整的 session 概念,同一个 session 下,可以分不同的步骤,每个步骤都有一个激活的协议组。协议组之间可以共享状态,同时限制并发。做下来发现,很难定义出完整的事务处理流程并描述清楚。可能需要设计一个 DSL 来解决这个问题更好一些。一开始我也是计划设置这个小语言的。可一是时间紧迫,二是经验不足,很难把 DSL 设计好。

而之前的若干项目证明,其实没有良好的事务描述机制,并不是不可用。实现一个简单的 RPC 机制,一问一答的服务提供方式也能解决问题。程序员只要用足够多经验,是可以用各种土法模拟长流程的事务处理流。只是没有严格约束,容易写出问题罢了。那么这个问题的最小化需求定义就是:可以响应发起请求人的请求,解析协议,匹配到对应的处理函数。所有请求都应该可以并发,这样就可以了。至于并发引起的问题,可以不放在这个层次解决。

我谨慎的选择了 RPC 这种工作方式。实现了一个简单的 RPC 调用。因为大多数服务用 Lua 来实现,利用 coroutine 可以工作的很好。不需要利用 callback 机制。在每条请求/回应的数据流上,都创建了独立的环境让工作串行进行。相比之前,我设计的方案是允许并发的 RPC 调用的。这个修改简化了需求定义,也简化的实现。

举例来说,如果 Client 发起登陆验证请求,那么由给这个 Client 服务的 Agent 首先获知 Client 的需求。然后它把这个请求经过加工,发送到认证服务器等待回应(代码上看起来就是一次函数调用),一直等到认证服务器响应发回结果,才继续跑下面的逻辑。所以处理 Client 登陆请求这单条处理流程上,所有的一切都仅限于串行工作。当然,Agent 同时还可以相应 Client 别的一些请求。

如果用 callback 机制来表达这种处理逻辑,那就是在发起一个 RPC 调用后,不能做任何其它事情,后续流程严格在 callback 函数中写。

每个 RPC 调用看起来是这样的:

January 07, 2012

关于分工合作

最近工作有点感触, 关于如何分工的。

我觉得所谓设计和实现是无论如何都很难分拆出去的。就是说你不实现你设想的结构,永远都很难知道哪里有问题;即使没有问题,换一个人来实现你想的东西,也无法把设计意图全部传达过去。如果可以做到,那么耗费的时间和精力足够你自己来实现了。

这也是为什么我之前说,软件项目需要很多人一起完成可能是一个骗局 。但毕竟,一个人精力有限,项目时间也有限。分工是无奈之举。可这件事情怎样做才对呢?

我最近有所体会的还是那些被嚼过很多年的老道理。就是模块划分清晰,强内聚,低耦合之类。想强调的是,模块的层次一定要适中,同一层次上规模不能太大,有严格输入、输出接口。

这些并不是为了方便测试,检验工作正确性,而是为了拆分工作。

December 20, 2011

Buddy memory allocation (伙伴内存分配器)

今天吃晚饭的时候想到,我需要一个定制的内存分配器。主要是为了解决 共享内存 中的字符串池的管理。

这个内存分配器需要是非入侵式的,即不在要分配的内存块中写 cookie 。

而我的需求中,需要被管理的内存块都是很规则的,成 2 的整数次幂的长度。buddy memory allocation 刚好适用。

算法很简单,就是每次把一个正内存块对半切分,一直切到需要的大小分配出去。回收的时候,如果跟它配对的块也是未被使用的,就合并成一个大的块。标准算法下,分配和释放的时间复杂度都是 O(log N) ,N 不会特别大。算法的优点是碎片率很小。而且很容易做成非入侵式的,不用在被管理的内存上保存 cookie 。只需要额外开辟一个二叉树记录内存使用状态即可。

我吃完饭简单 google 了一下,没有立刻找到满足我要求的现成代码。心里估算了一下,C 代码量应该在 200 行以下,我大概可以在 1 小时内写完。所以就毫不犹豫的实现了一份。

然后,自然是开源了。有兴趣的同学可以去 github 拿一份。这样就省得到再需要时再造轮子了。嘿嘿。

December 15, 2011

开发笔记 (6) : 结构化数据的共享存储

开始这个话题前,离上篇开发笔记已经有一周多了。我是打算一直把开发笔记写下去的,而开发过程中一定不会一帆风顺,各种技术的抉择,放弃,都可能有反复。公开记录这个历程,即是对思路的持久化,又是一种自我督促。不轻易陷入到技术细节中而丢失了产品开发进度。而且有一天,当我们的项目完成了后,我可以对所有人说,看,我们的东西就是这样一步步做出来的。每个点滴都凝聚了叫得上名字的开发人员这么多个月的心血。

技术方案的争议在我们几个人内部是很激烈的。让自己的想法说服每个人是很困难的。有下面这个话题,是源于我们未来的服务器的数据流到底是怎样的。

我希望数据和逻辑可以分离,有物理上独立的点可以存取数据。并且有单独的 agent 实体为每个外部连接服务。这使得进程间通讯的代价变得很频繁。对于一个及时战斗的游戏,我们又希望对象实体之间的交互速度足够快。所以对于这个看似挺漂亮的方案,可能面临实现出来性能不达要求的结果。这也是争议的焦点之一。

我个人比较有信心解决高性能的进程间数据共享问题。上一篇 谈的其实也是这个问题,只是这次更进一步。

核心问题在于,每个 PC (玩家) 以及有可能的话也包括 NPC 相互在不同的实体中(我没有有进程,因为不想被理解成 OS 的进程),他们在互动时,逻辑代码会读写别的对象的数据。最终有一个实体来保有和维护一个对象的所有数据,它提供一个 RPC 接口来操控数据固然是必须的。因为整个虚拟世界会搭建在多台物理机上,所以 RPC 是唯一的途径。这里可以理解成,每个实体是一个数据库,保存了实体的所有数据,开放一个 RPC 接口让外部来读写内部的这些数据。

但是,在高频的热点数据交互时,无论怎么优化协议和实现,可能都很难把性能提升到需要的水平。至少很难达到让这些数据都在一个进程中处理的性能。

这样,除了 RPC 接口,我希望再提供一个更直接的 api 采用共享状态的方式来操控数据。如果我们认为两个实体的数据交互很频繁,就可以想办法把这两个实体的运行流程迁移到同一台物理机上,让同时处理这两个对象的进程可以同时用共享内存的方式读写两者的数据,性能可以做到理论上的上限。

ok, 这就涉及到了,如何让一块带结构的数据被多个进程共享访问的问题。结构化是其中的难点。

方案如下:

December 01, 2011

Protocol Buffers for C

我一直不太满意 google protocol buffers 的默认设计。为每个 message type 生成一大坨 C++ 代码让我很难受。而且官方没有提供 C 版本,第三方的 C 版本 也不让我满意。

这种设计很难让人做动态语言的 binding ,而大多数动态语言往往又没有强类型检查,采用生成代码的方式并没有特别的好处,反而有很大的性能损失(和通常做一个 bingding 库的方式比较)。比如官方的 Python 库,完全可以在运行时,根据协议,把那些函数生成出来,而不必用离线的工具生成代码。

去年的时候我曾经写过一个 lua 版本的库 。为了独立于官方版本,我甚至还用 lpeg 写了一个 .proto 文件的解析器。用了大约不到 100 行 lua 代码就可以解析出 .proto 文件内的协议内容。可以让 lua 库直接加载文本的协议描述文件。(这个东西这次帮了我大忙)

这次,我重新做项目,又碰到 protobuf 协议解析问题,想从头好好解决一下。上个月一开始,我想用 luajit 好好编写一个纯 lua 版。猜想,利用 luajit 和 ffi 可以达到不错的性能。但是做完以后,发现和 C++ 版本依然有差距 (大约只能达到 C++ 版本的 25% ~ 33% 左右的速度) ,比我去年写的 C + Lua binding 的方式要差。但是,去年写的那一份 C 代码和 Lua 代码结合太多。所以我萌生了重新写一份 C 实现的想法。

做到一半的时候,有网友指出,有个 googler 最近也在做类似的工作。μpb 这个项目在这里 。这里他写了一大篇东西阐述为什么做这样一份东西,大体上和我的初衷一致。不过他的 api 设计的不太好,我觉得太难用。所以这个项目并不妨碍我完成我自己的这一份。

April 12, 2011

再谈 C 语言的模块化设计

去年谈过 C 语言对模块化支持的欠缺。我引入了一个 USING 方法来表达一个 C 语言编写的模块对其它模块的依赖关系。用它来正确的处理模块初始化。

现代语言为了可以接近玩乐高积木的那样直接组合现有的模块,都对模块化做了语言级别上的支持。我想这一点在软件工程界也是逐步认识到的。C 语言实在是太老了。而它的晚辈 Go 就提供了 import 和 package 两个新的关键字。这也是我最为认可的方式。之前提到的方案只能说是对其拙劣的模拟。确认语言级的支持,恐怕也只能做到这一步了。

在项目实践中,那个 USING 的方案我用了许多年,还算满意。之前有过更为复杂“精巧”的方法,都被淘汰掉了。为什么?因为每每引入新的概念,都增加了新成员的学习成本。因为几乎每个人都有 C 语言经验,但每个人的项目背景却不同。接受新东西是有成本的。任何不是语言层面上的“必须”,都有值得商榷的地方。总有细节遭到质疑。为什么不这样,或许会更好?这是每个程序员说出或埋在心里的问题。

那个 USING 的方案远不完美,它只是足够简洁,可以让程序员勉强接受而已。但其实还不够简洁。因为从逻辑表达上来说,它是多余的。一个模块使用了另一个模块,代码上已经是自明的。从 C 语言的惯例上来说,只要 #include 了一个相关的 .h 文件,就证明它需要使用关联的模块。光用宏的技巧很难只依靠一次 #include 就搞定正确的模块初始化次序。因为 C 语言并没有明显的模块概念。如果将每个子模块都编译为动态库可能能一定的解决问题(我曾经试过这种方案),但却会引出别的问题。细粒度的动态库局限性太大。

这两天我结合这半年学习 Go 语言的体验,又仔细考虑了一下这个问题。想到另一个解决方案。

March 31, 2011

废稿留档:Effective C++ 3rd 的评注版(序)

Effective C++ 3rd 的评注版要出版了。我在这本书上花了不少心血。编辑约我最后写一篇序。我新码了点文字,用了点以前 blog 上写的旧文

今天侠少同学说“现在全文看下来还是有些纠结,反对、支持、再反对,再支持,百转千回的小情绪,读者恐怕会犯晕”。嗯,的确很羞愧的。不应该在这本大牛的书前面发牢骚。打算晚上改稿子。旧稿就贴这里存档吧。


November 18, 2010

Go 语言初步

这几天认真玩起了 Go。所谓认真玩,就是拿 Go 写点程序,前后大约两千行吧。

据说 Go 的最佳开发平台是 Mac OS ,我没有。其次应该是 Linux 。Windows 版还没全部搞定,但是也可以用了。如果你用 google 搜索,很容易去到一个叫 go-windows 的开源项目上。千万别上当,这是个废弃的项目。如果你用这个,很多库都没有,而且语法也是老的。我在 Windows 下甚至不能正确链接自己写的多个 package 。活跃的 Windows 版是 gomingw ,对于 Windows 用户,装一个 mingw32 以后就可以开始玩了。

就三天来实战经历,我喜欢上这门新语言有如下原因:

mix-in 的接口风格。非常接近于我在用 C 时惯用的面向对象风格。有语法上的支持要舒服多了。以平坦的方式编写函数,没有层次。而后用 interface 把需要的功能聚合在一起。没有继承层次,只有组合功能。

强类型系统。使得犯错误的机会大大降低。正确通过编译,几乎就没有什么 bug 了。而编写程序又有点使用 lua 这种动态语言的感觉,总之,写起来很舒服。

内置的 string / slice 类型,以及 gc 。这是我觉得现代编程必须的东西。手工管理未必有更高的效率,但一定有更多的出错机会。至少,我一直主张有一个方便的 string 不变量的基本类型的(参见这一篇)。

defer 是个有趣使用的东西,用它来实现 RAII 比 C++ 利用栈上对象的析构函数的 trick 方案让人塌实多了。go 在语言设计上是很吝啬新的关键字的。但多出一个关键字 defer ,并用内建函数 panic / recover 来解决许多看似应该用 exception 解决的问题要漂亮的多。

zero 初始化。我一直觉得 C++ 的构造函数特别多余。按我用 C 的惯例,一切数据结构都应该用 0 初始化。所以 C 里有 calloc 这个函数。go 把这点贯彻了。不会再有未定义的数据。

包系统特别的好。而且严格定义了包的初始化过程,即 init 函数。在我自己的 C 语言构建的项目中,实现了几乎一样的机制,甚至也叫 init 。但是有语言层面的支持就是好。对,只有 init 没有 exit 。正合我意。

goroutine 是个相当有用的设计。8 年前,我给 C 实现了 coroutine 库,并用在项目里,并坚信,程序就应该这么写。但是没有语言级的支持,用起来还是很麻烦。goroutine 不仅简化了许多业务逻辑的编写,而且天生就是为并发编程而生的。select/chan 可能是唯一正确的并发编程的模型。Erlang 还是太小众了,而 Go 可以延用 Erlang 的模型,却有着纯正的 C 语言血统,我想会被更多人接受的。虽然 Go 依然可以用共享状态加锁的方案,但不推荐使用。chan 用习惯了,还是相当方便的。

{ 要不要独立占一行的信仰之争终于结束了。还记得前段时间有位同学来 email 指责我开源的代码没有章法。程序写的太乱。他的理由就是,我的 { 都没有独占一行。好了,争论可以结束了。在 Go 里,如果你把 { 从 if/for 语言的行末去掉,放在下一行。编译器是不会让你通过的。(除非你再加一个 ; )我很欣慰 ;)

我发现我花了四年时间锤炼自己用 C 语言构建系统的能力,试图找到一个规范,可以更好的编写软件。结果发现只是对 Go 的模仿。缺乏语言层面的支持,只能是一个拙劣的模仿。

October 26, 2010

Effective C++ 3rd 的一点评论

今天终于把作业作完了(可能还有地方要返工),Effective C++ 第 3 版读完了,写了几万字的评论。如我给编辑交稿的 email 里所写:

我觉得评注这个工作比翻译难做。作者细节上讲的非常清楚,大部分地方都不觉得有必要再加注解。我想跟这本书反复写了 10 年有关。所以很多页我都没留评注,真的不知道可以写啥。

编辑原想每页中英分列排版,我是不建议这样的。除了少部分评注,针对个别代码段,或关键词。大部分我的文字都是独立成段的。跟具体原文句子关系不大,只跟篇章段落主题有些许联系。

前几天跟孟岩兄 email 交流,我发了一些稿子给他。他觉得关于本书第一篇 Item 1 : View C++ as a federation of languages ,我的评注还是没有讲透。是的,许多观点还是很难表达清楚。

下面选一段贴出来吧。

October 19, 2010

Effective C++ 3rd Edition

最近一个多月的业余时间都耗在了《Effective C++ 3rd Edition》这本书上。读的很辛苦,不仅仅是因为这是本英文书。之前答应了博文的编辑帮这本书写评注,将来用于出版。对于要印成白纸黑字的文章,不得不谨慎一些。

我已经有 4 年没有大段时间写 C++ 代码了。中间偶尔有几天写过几千行,其余的 C++ 经验就来至于 google reader 上的阅读。为了读这本书,我又重温了《C++语言的设计和演化》的几个章节。不过整个阅读过程还是不太赏心悦目。

可能还是因为我对 C++ 偏见过多,有如前几年对其的推崇备至。总觉得书里讲的太细,太多观点本是好的,只是局限在了 C++ 语言中。明明是 C++ 的缺陷,却让人绞尽心力的回避那些问题,或是以 C++ 独特的方式回避。在别的语言中不该存在的问题,却成了 C++ 程序员必备的知识。人生苦短,何苦制造问题来解决之。

August 31, 2010

从数组里删除一个元素

去年介绍过我在项目中实现的一个动态数组模块的接口

实际上,我为它提供的接口要更多一些,比如删除一个元素。

  void array_erase(struct array *, seqi iter);

原来的语义就是删除 iter 引用的元素。但这里引出一个问题:删除后,iter 是否应该保持有效?

从语义上说,iter 应该在调用完毕后变成一个无效引用。但实际应用中,往往需要在迭代 array 的过程中,删除符合条件的元素。让迭代器失效的做法,用起来很不方便。

July 12, 2010

C 语言中统一的函数指针

有时候,我们需要把多个模块粘合在一起。而这些模块的接口参数上有少许的不同。在 C 语言中,参数(或是返回值)不同的函数指针属于不同的类型,如果混用,编译器会警告你类型错误。

在 C 语言中,函数定义是可以不写参数的。比如:

void foo();

这个函数定义表示了一个返回 void 的函数,参数未定。也就是说,它是个弱类型,诸如:

void foo(int);

void foo(void *);

这些类型都可以无害的转换成它。正如在 C 语言中,具体的指针类型如 int * ,char * 都可以转换为 void * 一样。

注1:如果要严格定义一个无参数的函数,应该写成 void foo(void);

注2:如果有部分参数固定,而其后的参数可变,则定义看起来是这样: void foo(int , ...); 这表示第一个参数为 int ,从第 2 个参数开始可变。

June 28, 2010

C 语言的前世今生

本篇是应《程序员》杂志约稿所写。原本要求是写篇谈 C 语言的短文。4000 字之内 。我刚列了个提纲就去了 三千多字。 -_-

现放在这里,接受大家的批评指正。勿转载。

June 11, 2010

有关 Forth

今天晚上继续读 《Masterminds of Programming》,忍不住又翻译了半章关于 Forth 之父的访谈。我以前读过几篇更早时期关于他的访谈,部分了解他的观点。小时候还特别迷 Forth 。这位神叨叨的老头很有意思。

没看过原来的译本,只是自己按自己的理解翻了第 4 章 Forth 的前一半。我也算对 Forth 很有爱的人吧,也还了解 Forth 里诸如 ITC (Indirected-threaded code) 这种术语到底指的什么,不过还是觉得翻译有点吃力。

对 Forth 同样有爱的同学们姑且看之吧。

May 25, 2010

setjmp 的正确使用

setjmp 是 C 语言解决 exception 的标准方案。我个人认为,setjmp/longjmp 这组 api 的名字没有取好,导致了许多误解。名字体现的是其行为:跳转,却没能反映其功能:exception 的抛出和捕获。

longjmp 从名字上看,叫做长距离跳转。实际上它能做的事情比名字上看起来的要少得多。跳转并非从静止状态的代码段的某个点跳转到另一个位置(类似在汇编层次的 jmp 指令做的那样),而是在运行态中向前跳转。C 语言的运行控制模型,是一个基于栈结构的指令执行序列。表示出来就是 call / return :调用一个函数,然后用 return 指令从一个函数返回。setjmp/longjmp 实际上是完成的另一种调用返回的模型。setjmp 相当于 call ,longjmp 则是 return 。

重要的区别在于:setjmp 不具备函数调用那样灵活的入口点定义;而 return 不具备 longjmp 那样可以灵活的选择返回点。其次,第一、setjmp 并不负责维护调用栈的数据结构,即,你不必保证运行过程中 setjmp 和 longjmp 层次上配对。如果需要这种层次,则需要程序员自己维护一个调用栈。这个调用栈往往是一个 jmp_buf 的序列;第二、它也不提供调用参数传递的功能,如果你需要,也得自己来实现。

May 07, 2010

给你的模块设防

我们设计任何一个模块,都应当对其实现细节尽可能的隐藏。只留下有限的入口和外部通讯。这些入口如何定义是重中之重。大多数情况下,我们都在模仿已有的系统来设计,所以对貌似理所当然的接口定义不以为然,以为天生就应该是那样,而把过多精力放在了如何做更好(更优化)的实现上。对接口设计方面缺乏深度的思考,使得在面对新领域时,或是随心所欲,或是不知所措。

即使是有成熟设计的模块,用户依然可能使用错误。模块的设计者不能要求模块的使用者对其内部实现了然于胸。不能指望自己能写出完善的文档去告诫使用者,当你怎样用的时候会用错。即使写出了完善的文档,也不能指望每个人都仔细的读过。就算读了,也有百密一疏的时候。越是专有的模块,越不能指望文档或是口述的教导,更不能指望程序员去精读源码。人生苦短,如无特别的理由,逐行去读同僚的代码,何不自己重写一遍?你设计的系统若用出了问题,与其怪别人用错,不如怪自己没设计好。MSDN 洋洋洒洒文字以 G 计算,也属无奈之举。依然有无数人犯下那些被人提及的错误。

现举一个一切 C 语言程序员都用过的模块的设计:内存管理模块。

标准 API 为三个:

malloc

free

realloc

大多数程序员都以为这理所当然。直到接触到 gc 的方式管理内存,方知另有一片天地。即使在 C 库中引为标准,也并不是所有内存管理器都承认这种简洁的。比如在 Windows 的 API 中,HeapAlloc 系列的内存管理模块的 API 就更复杂一些。

April 12, 2010

实现一个简单的虚拟文件系统

Windows 游戏软件在发布时,通常会把所有数据文件打包。这通常出于两个目的:一是保护数据文件不被最终用户直接查看,二是 Windows 的文件系统一度相对低效。尤其是在处理非常多小文件的时候,无论是安装、分发还是运行时处理都有性能问题。

而游戏软件通常会有大量的资源文件,对数据文件打包的需求更为强烈。一般游戏引擎都会支持至少一种资源打包的形式。

打包数据文件的概念和实现,我最早是对 Allegro 的源码阅读学习来的,算起来也是十多年前的故事了。之后一段时间,我从 Doom/Quake 里又看到了类似的东西。再之后,见过了星际争霸对数据包的处理。大体上,大家都支持一种用法:即可以让数据包和本地文件系统中的数据文件共存。非打包的数据在开发期用起来非常方便,打包的数据用于发行。

March 31, 2010

C 语言的数据序列化

数据结构的序列化是个很有用的东西。这几天在修改原来的资源管理模块,碰到从前做的几个数据文件解析的子模块,改得很烦,就重新思考序列化的方案了。

Java 和 .Net 等,由于有完整的数据元信息,语言便提供了完善的序列化解决方案。C++ 对此在语言设计上有所缺陷,所以并没有特别好的,被所有人接受的方案。

现存的 C++ serialization 方案多类似于 MFC 在二十年前的做法。而后,boost 提供了一个看起来更完备的方案( boost.serialization )。所谓更完备,我指的是非侵入。 boost 的解决方案用起来感觉更现代,看起来更漂亮。给人一种“不需要修改已有的 C++ 代码,就能把本不支持 serialize 的类加上这个特性”的心理快感。换句话说, 就是这件事情我能做的,至于真正做的事情会碰到什么,那就不得而知了。

好吧,老实说,我不喜欢用大量苦力(或是高智慧的结晶?)堆积起来的代码。不管是别人出的力,还是我自己出的。另外,我希望有一个 C 的解决方案,而不是 C++ 的。

所以从昨天开始,就抽了点时间来搞定这件事。

March 17, 2010

C++ 中的 protected

当我还在用 C++ 做主要开发语言的最后几年,我已经不大用 protected 了。从箱底翻出曾经钟爱的一本书:《C++语言的设计和演化》,中文版 235 页这样记录:

“ ... Mark Linton 顺便到我的办公室来了一下,提出了一个使人印象深刻的请求,要求提供第三个控制层次,以便能支持斯坦福大学正在开发的 Interviews 库中所使用的风格。我们一起揣测,创造出单词 protected 以表示类里的一些成员,...”

“... Mark 是 Interviews 的主要设计师。他的有说服力的争辩是基于实际经验和来自真实代码的实例。...”

“...大约五年之后,Mark 在 Interviews 里禁止了 protected 数据成员,因为它们已经变成许多程序错误的根源...”

我不喜欢 protected ,但是今天,我偶尔用一下 C++ 时,不再有那么多洁癖。反正很难用 C++ 做出稳定的设计,那么,爱怎么用就怎么用吧。关键是别用 C++ 做特别核心的东西就成了。

今天,碰到一个跟 protected 有关的问题,小郁闷了一下。觉得可以写写。这个倒是个基本问题,貌似以前很熟悉。毕竟很多年不碰了,对 C++ 语法有点生疏。

March 13, 2010

我所偏爱的 C 语言面向对象编程范式

面向对象编程不是银弹。大部分场合,我对面向对象的使用非常谨慎,能不用则不用。相关的讨论就不展开了。

但是,某些场合下,采用面向对象的确是比较好的方案。比如 UI 框架,又比如 3d 渲染引擎中的场景管理。C 语言对面向对象编程并没有原生支持,但没有原生支持并不等于不适合用 C 写面向对象程序。反而,我们对具体实现方式有更多的选择。

大部分用 C 写面向对象程序的程序员受 C++ 影响颇深。企图用宏模拟出一个常见 C++ 编译器已经实现的对象模型。于我愚见,这并不是一个好的方向。C++ 的对象模型,本质上是为了追求实现层的性能,并直接体现出来。就有如在 C++ 中被滥用的 inline ,的确有效,却破坏了分离原则。C++ 的继承是过紧的耦合。

我所理解的面向对象,是让不同的数据元有共同的操作方式,适合成组的处理。根据操作方式的不同,我们会对数据元做不同的分组。一个数据可能出现在这个组里,也可以出现在那个组里。这取决于你从不同的方面提取的共性。这些可供统一操作的共性称之为接口(Interface),接口在 C 语言中,表现为一组函数指针的集合。放在 C++ 中,即为虚表。

我所偏爱的面向对象实现方式(使用 C 语言)是这样的:

February 24, 2010

在 C++ 中引入 gc 后的对象初始化

这几天白天都在安排面试,其实还是有点累的。晚上就随便写点程序,好久没摸 C++ ,有点生疏。也算是娱乐一下吧。

主要工作其实是在 C 库的基础上做一个 C++ 的中间层。跟在 C 库的基础上做 lua 中间层差不太多。前几天加入了 gc 后,发现了一些有趣的用法。

比如对于构造对象。 C 的 api 中,如果创建一个对象失败,就会返回空指针。但是对于 C++ 就不一样了,new 是不应返回空指针的。书本上的推荐做法是在构造函数里抛异常。但是我又不太想进一步的引入异常机智,怎么办呢?

February 23, 2010

C++ 中的接口继承与实现继承

为这篇 blog 打腹稿的时候,觉得自己很贱,居然玩弄 C++ 起来了。还用了 template 这种很现代、很有品味的东西。写完后一定要检讨。

起因是昨天写的那篇关于 gc 的框架。里面用了虚继承和虚的析构函数。这会导致 ABI 不统一,就是这个原因,COM 就不用这些。

说起 COM ,我脑子里就浮现出各种条条框框。对用 COM 搭建起来的 Windows 这种巨无霸,那可真是高山仰止。套 dingdang 的 popo 签名:虽不能至,心向往之。

好吧,我琢磨了一下如何解决下面的问题,又不把虚继承啦,虚析构函数啦之类的暴露在接口中。

简单说,我有几个接口是一层层继承下来的,唤作 iA iB 。iA 是基类,iB 继承至 iA 。

然后,我写了一个 cA 类,实现了 iA 接口;接下来我希望再写一个 cB 类,实现 iB 接口。但是,iB 接口的基类 iA 部分,希望复用已经写好的 cA 类。我想这并不是一个过分的需求。正如当年手写 COM 组件时,我对手写那些 AddRef Release QueryInterface 深恶痛绝。

用虚继承可以简单的满足这个需求:

February 22, 2010

在 C++ 中实现一个轻量的标记清除 gc 系统

最近想把 engine 做一个简单 C++ 封装,结合 QT 使用。engine 本身是用纯 C 实现的,大部分应用基于 lua 开发。对对象生命期管理也依赖 lua 的 gc 系统。关于这部分的设计,可以参考我以前写的一篇 为 lua 封装 C 对象的生存期管理问题

当我们把中间层搬到 C++ 中时,遇到的问题之一就是,C++ 没有原生的 gc 支持。我也曾经写过一个 gc 库。但在特定应用下还不够简洁。这几天过年休息,仔细考虑了一下相关的需求,尝试实现了一个更简单的 gc 框架。不到 200 行代码吧,我直接列在这篇 blog 里。

这些尚是一些玩具代码,我花了一天时间来写。有许多考虑不周的地方,以及不完整的功能。但可以阐明一些基本思路。

January 28, 2010

古怪的 C++ 问题

我好多年没写 C++ 程序了,读 C++ 代码也是偶尔为之。

今天晚上就碰到这么一个诡异的问题,我觉得是我太久没摸 C++ 了,对那些奇怪的语法细则已经不那么熟悉了。有知道的同学给我解惑一下吧。

事情的起因是,我想安装一个 perl 模块唤作 Syntax::Highlight::Universal 。

本来用 CPAN 安装很方便的,直接 install 即可。

可是在我的机器上,make 死活通不过。我就仔细研究了一下编译出错信息。又读了一下源代码,自己感觉没错。纠结了半天,仔细模仿出错的地方写了一小段程序测试。

January 21, 2010

浅谈 C 语言中模块化设计的范式

今天继续谈模块化的问题。这个想慢慢写成个系列,但是不一定连续写。基本是想起来了,就整理点思路出来。主要还是为以后集中整理做点铺垫。

我们都知道,层次分明的代码最容易维护。你可以轻易的换掉某个层次上的某个模块,而不用担心对整个系统造成很大的副作用。

层次不清的设计中,最糟糕的一种是模块循环依赖。即,分不清两个模块谁在上,谁在下。这个时候,最容易牵扯不清,其结果往往是把两者看做一体去维护算了。这里面还涉及一些初始化次序等繁杂的细节。

其次,就是越层的模块联系。当模块 A 是模块 B 的上层,而模块 B 又是模块 C 的上层,这个时候,让模块 C 对模块 A 可见,在模块 A 中有对 C 导出接口的直接调用,对于清晰的设计是很忌讳的一件事。虽然,我们很难完全避免这个问题,去让 A 对 C 的调用完全通过 B 。但通常应尽力为之。(注:以后写书的话,我争取补充一些实际的例子来说明)不过,对语言不原生支持的数据类型,以及基础设施,但却有必要创造出来给系统用的。可以有些例外。比如内存管理,log 管理,字符串(C 语言用原始库函数管理比较麻烦)等等,我们可能以基础模块的形式提供。但却可能被不同层次的模块直接使用。但,上到一定层次后,还是需要去隐藏它们的。

下面来一点更实际的分析。

January 19, 2010

C 语言对模块化支持的欠缺

继续昨天的话题。随便列些以后成书可能会写的东西。既然书的主题是:怎样构建一个(稍具规模的)软件。且我选择用 C 为实现工具来做这件事情。就不得不谈语言还没有提供给我们的东西。

模块化是最高原则之一(在 《Unix 编程艺术》一书中, Unix 哲学第一条即:模块原则),我们就当考虑如何简洁明快的使用 C 语言实现模块化。

除开 C/C++ ,在其它现在流行的开发语言中,缺少标准化的模块管理机制是很难想象的。但这也是 C 语言本身的设计哲学决定的:把尽可能多的可能性留给程序员。根据实际的系统,实际的需要去定制自己需要的东西。

对于巨型的系统(比如 Windows 这样的操作系统),一般会考虑使用一种二进制级的模块化方案。由模块自己提供元信息,或是使用统一的管理方案(比如注册表)。稍小一点的系统(我们通常开发接触到的),则会考虑轻量一些的源码级方案。

January 18, 2010

好的设计

前几天说,想再写本书。许多朋友给了我支持。暂时我还写不了。因为:

  1. 工作真的很忙,很难脱开身。我觉得我在某种程度上陷进去了。需要花点时间整理规划一下。然后把工作的事情处理好。让它可以顺利做下去。不光是技术上要解决的问题,也不光是管理问题,也不光是团队合作的问题,也不光是项目开发运作的问题。反正很多很多,确实有很多麻烦。我要尽力做好。

  2. 觉得上一本没写好,是因为还是太仓促了。即使是已经写的那点东西,也积累不够。写书的经验也太少。我倒不怕有错误被人骂,是怕自己回头不满意。

  3. 如果再写,肯定只抓着很少的问题谈。但是具体写什么,还没全想好。积累是有了点,真能够拿出来写写的不多。毕竟,写书和写 blog 瞎扯还是不一样的。

孟岩建议我先在 blog 上列的大纲,然后随便写点。让同学们给意见,再逐步修改成书。我也有此想法,觉得不错。不过一开始,恐怕我连大纲都列不出来,就想到哪写到哪,随便写点东西吧。过段时间再把零碎想法串起来,作为正式列提纲的参考。

由于最近几年用的主要开发语言是 C 和 lua 。那么也打算以此为基础写。假定读者至少有不错的 C 语言基础了。我真正想谈的是,如何把一个软件很好的构建起来。到底需要做些什么。(从实现层面看)怎样才是好的软件。

那么有一个重点问题,也是老问题,怎样才是好的设计。

December 24, 2009

不要像小贝那样学习C++

小贝

今儿在 google reader 上看到有人推荐这篇文章,谈学计算机的问题。

上面的图是转过来的,《蜗居》第24集3:30秒截图 。这部片子同事前段 copy 给我,带在旅游的路上看的。我也就打发飞机上的时间看了一点。据说很火,但是跟我没什么共鸣,也就没啥欲望看完。

话说,《大规模C++程序设计》这本书,就胡乱翻过电子版的几页吧。算是本不错的书,可惜我对 C++ 失去兴趣已久,不太想读了。但就我读到的只言片语来说,这本书更多的是对 C++ 的友好批判。其实是很适合 C++ 中毒的程序员去读的。

正如引言中所述:”与主流观点相反,从根本上说,最普通形式的面向对象程序要比对应的面向过程的程序更难测试和校验。“

December 03, 2009

C++ 会议第一天

Lippman 大牛的第一场,关于大型可伸缩性的软件开发的, Chen Shuo 同学翻译的很不错 :D

找到电源,所以可以写写了。

果然是牛人啊,上来就讲形而上的东西。我听的有趣,就做了点笔记,但是记的不多。

我们从自然界去寻找灵感,然后在计算机领域去搞出来。以前的计算机是没有内存的,后来冯大侠说,计算机就像大脑,大脑是有记忆的,所以有了内存。

我们现在说大脑就像计算机,是本末倒置了。人们总是从自然界的角度来思考,然后解决软件里的问题。Lippman 牛的想法是,把软件比作生物,从 DNA ,细胞核开始向上一层层的。

系统的基础组织部分是 Data Structure 和 Data Stream ,这个就像细胞一样;在应用领域方面,Executive Function 和 Type Information 就好比生物的各个器官。

November 20, 2009

动态数组的 C 实现

上次谈到了一个常用的 ADT ,sequence 的 C 实现。通常,我们不会直接使用 sequence ,而是用它来实现满足最终需要的数据结构。比如消息队列,比如指令堆栈,等等。一个实现的优秀的 seq 的好处在于,即使你只用到其中一部分功能,也不会因为那些没用的部分损失太多的(时间和空间上的)性能。

今天我想谈另一个更为实用的 ADT ,动态数组。这个在传世神作《C 语言接口与实现》中也提到过,我不是想说其写的不对,或是讲述的不周全,实现的不漂亮。只是以我的观点来展开相关的问题。

为什么要有数组?C 语言内置了数组、在 C99 中更是允许在堆栈上声明非固定长度的数组。C++ 里以 STL 的形式提供了 vector 模块供程序员使用。

我们面临的问题,不是语言和库为我们提供了多少可能。而是我们无法确定,我们到底至少需要什么?

November 12, 2009

sequence 的 C 实现

这段时间一直在写代码,大约一周三四千行的样子。所以没有什么闲余时间写 blog 。可能再过段时间可以总结一些想法吧。

我这几年一直用 C 在做设计和编码(当然还写了许多 Lua 程序)。也一直在纠结,到底,我们在系统编程中,最少的需求是什么。C++ 给了我们太多,但是 C 又给的太少。如果常年用 C 写程序,那么必须多一点。

比如基础数据类型,在《C语言接口与实现》中叫作 ADT 的东西。给出了许多。我还是觉得多了点,其实用不了那么些。

其中 atom 是必须的,在我的系统中,给了个不恰当的命名,但是本质是一样的。以前写过一篇 blog 讨论过

因为 Lua 用的太多,感觉字典是个很有用的东西,所以我实现了一个基本的 hash map 。

然后,用的比较多的是变长数组,以及用于收发消息的队列。这个东西实在是太简单了,我一直没有单独实现成一个独立模块,都是随用随写。也不大容易写错。但是写了这么多年,我还是想把它抽象出来。和同事讨论的时候,Soloist 同学提醒我,其实我想要的 ADT 就是 sequence 。

一个可以方便的从两头插入,从两头删除,可变长,可以高效随机访问的 sequence 。在 《C语言接口与实现》里把这个东西简写为 seq ,在 Haskell 里也是。

为什么我一直从心里排斥把 seq 做成独立模块,我想是我的追求高效的坏习惯在作祟。虽然这个习惯很不好,但是我总觉得明明可以用一个原生数组来做这件事情,用个指针就可以遍历了,何必多几次函数调用,和数据访问的间接性呢。

固然,C++ 的 STL 提供了一个折中的方案,把代码都写到 .h 里(使用 template ),利用编译器去优化 inline 代码。但是却在源代码中暴露了数据结构的实现细节。今天的我看来,这是更不可以容忍的事情。(不同意这个观点的同学请原谅我的偏执)

从昨天开始,我又一次仔细考虑了这个问题,并花了今天一天的时间,实现了一个让我还算满意的 seq 模块。

October 16, 2009

神啊,C 终于开始支持 closure 了

不支持 closure 的语言用起来真是太难受了。

前段时间有同事在用 boost 的时候想用一个匿名的 struct 实现一个 functor 模拟出 closure 来用。可耻的失败鸟。迎接他的是一大坨的 template 编译错误。我这个久久不碰 C++ 的碰观者就有机会在一旁幸灾乐祸了。固然这是因为对 C++ 语言的犄角旮旯认识不足导致的,若是早几年,说不定我还拿这个作为招聘的高级笔试题呢。现在,我只会指责,语言怎么可以设计成这样。

给语言加新特性并不可怕。因为我们最终是要用语言解决问题的。

Apple 给 C/C++ 加的 Blocks 扩展就是这么一个好东西。

August 02, 2009

关于 getter 和 setter

网友 "sjinny" 在上篇评论里写:

云风对那种所有成员数据都写setter/getter的做法有什么看法吗……这两天试图精简三个太庞大的类,但是单单setter/getter就让接口数目变得非常多了……

我谈谈我的看法吧。

首先,几乎任何设计问题都没有标准答案。如果有,就不需要人来做这件事了。无论多复杂的事情,只要你能定义出精确的解决方案,总可以用机器帮你实现。

下面谈谈我的大体设计原则。记住、一切皆有例外,但这里少谈例外。因为这涉及更复杂的衡量标准。

May 10, 2009

树结构的管理

要写过多少代码才能得到哪怕一点真谛?

多少年过来,我在潜意识的去追求复杂的东西。比如我自幼好玩游戏,从小到大,一直觉得玩过的游戏过于简单(无论是电子游戏还是桌面游戏),始终追寻更复杂规则的游戏,供我沉浸进去。或许是因为,有了更高的理解和控制复杂度的能力,就可以更为轻松的驾御复杂性。

这很好的解释了 2000 年到 2004 年我对 C++ 的痴迷。还有对设计模式的迷恋。

Eric S. Raymond 说:尽量不要去想一种语言或操作系统最多能做多少事情,而是尽量去想这种语言或操作系统最少能做的事情——不是带着假想行动,而是从零开始。禅称为“初心”(beginner's mind)或者叫“虚心”(empty mind) 。

代码写多了,问题见过了,甚至是同一问题解决多了。模式这种东西自在心底,不必拿出来。时时的从零去想,总能重新明白一些道理。

为什么说语言重要也不重要,算法和数据结构重要也不重要。对要解决的问题的领域的理解很重要(即明白真正要做什么)。理解了,我们才可以用面向对象,用模式去套问题;可理解了,我们又不真的需要这些繁杂的抽象。

闲话放一边,今天想谈谈树结构的管理。

April 19, 2009

为什么说不要编写庞大的程序

《Unix 编程艺术》中总结的 Unix 哲学中有这么一条:除非确无它法,不要编写庞大的程序。并且在第 13 章 花了一章讨论复杂度的问题。(第 13 章 复杂度:尽可能简单,单别简单过了头)

下周一,是我们项目的一个进度线。所以,周末我安排了加班。当然,我最近两年,每个休息日都给自己安排的加班,无所谓周末。不过给团队安排加班还是比较稀少的事情。

由于种种原因,不是每个人都能够把自己的休息时间贡献出来的。作为团队负责人,我的原则是,生活大于工作。如果有生活上的事情,就可以拒绝加班。对于项目,也不应该把某件事情依赖到特别的某个人身上,虽然某些东西由特定的人去做(比如维护自己写的模块/程序)会效率高一些,但是其他人也应当可以顶替。

所以,偶尔维护一下不是自己写的代码,且能够在很短时间进入状态,就是团队每个人应该具有的能力。在这方面,我们的团队做的还不是很好,不是每个人都有这样的能力。但、这也并非个人能力单方面的因素。

March 28, 2009

安全的迭代一个集合

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

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

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

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

March 09, 2009

关于 manual gc 的代码分析

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

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

垃圾收集的那点事(A)

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

January 12, 2009

The New C Standard

周末开始读一本书,《The New C Standard》。尚未出版,但是电子版可以自由下载。

牛人写的计算机方面的书,我想有两个极端。要么像高爷爷的 TAOCP ,厚厚的几大本,还在待续;要么如 K&R 的 TCPL ,薄薄一本,躺在床上轻松读完。

之前,我从没想过,以 C 语言为主题的书,可以砖头样的一大本,1600+ 页。用 80 克纸双面打印,会厚达 9.2 厘米(作者语)。 不过看过副标题,稍微可以理解:An Economic and Cultural Commentary 。感情上升到经济和文化了。敢用这个词的人绝非泛泛之辈。

一不小心读到凌晨五点,居然 Introduction 的一半还没读完 :( ,也就是说,前 100 页都还没正式谈 C 语言呢。

由于是英文版,阅读速度受到了极大的限制。而行文中大量我不认识的单词和长句,迫使我不断的查字典。就这样还能坚持读下来,只能说,这是一本好书,有趣的书。

好吧,简单说,这是一本对 C 的标准及相关层面的一切注条评论的书。

对于每一个点,都在几个方面展开:将其和 C++ 、其它语言对比;描述一般的实现方法;对其做出评论;给出 Coding Guidelines (编码指引)。

下面,我试着将前面介绍部分选译几段,鉴于原文的行文与我来说有许多艰深之处,恐怕很难译的准确,姑且看之吧。

January 06, 2009

一个 C 接口设计的问题

C 语言在本质上,参数传递都是值传递。不像 Pascal 和 C++ 可以传引用。这一点,使得 C 语言可以保持简单的设计,但另一方面也颇为人诟病。

因为性能问题,指针不得不被引入。可以说,用 C 语言实现的软件,其实现的 Bug 90% 以上都来至于指针,应该是没有夸大了。当然设计引起的问题或许更为关键一些,那些于指针无关。

纠结于性能问题上,层次比较低。可 C 语言就是一个活跃在较低层次的语言,一旦你选择用它,就不得不关心性能问题。反过来,把 C 模仿成更高级的语言,倒是有点画蛇添足了。好了,让我们来看个实际的涉及参数传递的相关问题,用 C 语言该如何设计。

最近同事在做一个类似 Protocol Buffers 的东西。这个东西做好并不容易,设计上尤为困难。其中的设计难点:设计一个合适的 DSL (领域专用语言) 我们讨论过很久,也分析了好几天,但今天不打算谈了。拣个小东西说:当我们把一个二进制结构化数据块解析出来,传递到 C 语言中,让 C 语言可以方便的访问数据结构时,接口如何设计?

October 03, 2008

解决 RTorrent 部分中文文件名乱码

这两天在我的 LS Pro 上装 BT 软件。以前我在 freebsd 下都是装的 ctorrent ,这次想换个别的。看中了 RTorrent ,项目维护还比较勤,新版支持 DHT 。不过 debian 的源上比较老,官网上那个源我连不上。所以就下源代码自己编译了一个。

原来以为这种小东西没多少代码量的,本地编译就够了。可惜我轻视了 C++ 代码编译的龟速。在 LS Pro 上,居然一个短短的 .cc 文件就要编译 20 秒左右。有点后悔没有用交叉编译,不过忍了几小时也就过去了。

新版本支持 xmlrpc 的控制协议。我就可以装一个 web 界面管理了 :) 我选的是 rtgui 还不错。

本来以为一切都搞定可以庆祝了的。没想到试了一个种子,其中中文文件名出现乱码,连带的导致了 rtgui 工作不正常 :( 然后花了一整夜的时间来折腾这个,好不辛苦。

September 20, 2008

重构

随着 engine 开发进入尾声,最近几个月已经在修一些边角的东西,顺便给其他组的同事做介绍和教学。由于不在一起办公,折腾 VPN 和防火墙也折磨了好几天。

中秋假期前,我重新思考了去年设计好,但一直没精力去实现的东西:资源的多线程预读

由于资源管理模块当初设计的还是比较仓促,有些需求到了后期才逐步出现。比如,我们需要同时使用不同的资源加载模块,分别从本地文件系统于打包文件中读取。一开始,我认为,开发期不将资源文件打包是可以的。随着开发的进展,数据文件在数量级上增加,感觉将一些不太变化的文件打包还是有必要的。这就必须实现混合加载。

前期考虑到要做数据预读,我们将文件之间的依赖关系放到了文件系统内。而非自己定制的数据包文件系统和本地文件系统间有很大的不同。这使得混合加载实现比较困难。(具体原因是,我们的文件系统内采用的类似 linux ext2 的思路,每个文件有一个 inode 标识,并描述相互关系。但文件却不一定有文件名。这和本地文件系统相异,导致相互依赖关系难以描述。)

第二,虽然前期设计为多线程加载考虑。但由于中间变化很多,例如需要在加载过程中把部分数据上载到显存。最终,实现多线程安全变的很困难。(具体原因是,每种文件类似都有自解释的代码,我们的客户端主体 engine 代码是按单线程设计,实现资源加载的多线程安全必然对以后扩展资源文件类型的程序员做过多限制)

基于以上两点,我觉得花一番气力对整个资源管理模块做一次大的重构。

为了不影响项目组其他人员的工作,估算了工作量后,我决定自己在中秋节做这次重构工作。并在假期结束可以顺利归并到代码基的主干。

事情没有预期的顺利。

August 13, 2008

Lua 不是 C++

嗯,首先,此贴不是牢骚帖。

话题从最近私人的一点工作开始。应 dingdang 的建议,我最近在帮 大唐无双 做一些程序上的工作。接手做这件事情,是因为这个内部被我们称作 dt2 的游戏 engine 关系重大。公司有至少四个项目在使用(另外三个暂处于研发期,尚未公布)。

dt2 用了大量的 lua 代码构建系统,但从系统设计上,沿袭了老的大唐的许多代码。原来的大唐是用 C++ 构建的,为了利用上这些代码(虽然我觉得这种复用非常无意义,但是其中原因复杂,就不展开谈了),dt2 engine 的开发人员做了一套非常复杂的中间层,把 lua 和 C++ 几乎无缝的联系在了一起。

July 21, 2008

KISS

Keep it simple , stupid .

stupid 不是愚蠢的愚,而是大智若愚的愚。有时候,我们写程序做设计就是不够智慧,就只有点聪明。觉得自己可以把复杂的问题用巧妙的方法解决。这个巧妙的方法,保正了效率,节约的内存。真可谓聪明。

但聪明不是智慧,真正的智慧是看到将来。在不断的演化中它们还能不能保持这个巧妙。如果不那么巧妙,我们到底会损失些什么,我们真正需要什么,而失去的那些换来的到底是什么。

simple 也不是为了避免麻烦。保持 simple 比解决麻烦要麻烦的多。

June 24, 2008

摄象机接口的设计

最近在调整 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 则应该完全从实现域到问题域的一个变换,让开发者可以用最接近问题域的语言来表达问题。

June 15, 2008

对面向对象的一些思考

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

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

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

June 14, 2008

引用计数与垃圾收集之比较

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

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

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

June 10, 2008

给 C 实现一个垃圾收集器

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

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

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

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

March 22, 2008

感觉好多了

其实我并没有用 lua 亲手写过什么大规模的项目。超过 5 千行代码的项目几乎都是 C 或是 C++ 写的。这几天算是做了点复杂的玩意了。几经修改和删减,最后接近完工的这个东西统计下来不多不少 3000 行(误差在十位数)。其中用 C 编写了基础模块 900 多行(仅仅是 socket api 的封装和 byte 流的编码解码),剩下的都是用 lua 设计并实现的。

好吧,我承认 2000 多行代码也只是一个小东西。不过用 lua 实现的一个 wiki 系统,sputnik 还不到 2000 行呢。lua 有一种特质,用的久了就容易体会到。它和 python ruby 这些更为流行的动态语言是不同的。曾经,我把选择 lua 的理由,肤浅的停留在了更轻便更高效上,虽然这些也很重要,但抓住语言的特质才是更关键的。

January 05, 2008

C 语言(C99) 对 64 位整数类型的支持

前几天跟同事闲聊 64 位操作系统时,有人问起 64 位平台上,C 语言的数据类型如何确定的问题。以及跨平台(跨 16 位、32 位和 64 位平台)程序如何选用合适的数据类型。

我查了一下资料,记录如下:

char 通常被定义成 8 位宽。

int 通常被定义成 16 位或 32 位宽(或更高),它取决于平台。编译器将在这两者间选择最合适的字宽。

short 通常被定义成 16 位宽。

long 通常被定义成 32 位宽。

C99 为 C 语言扩展了新的整数类型 long long ,通常被定义成 64 位宽。(GNU C 亦支持)

但是 C 标准并没有定义具体的整数类型的宽度,只定义了 long long 的级别高于 long ,long 的级别高于 int ,int 的级别高于 short ,short 的级别高于 char 。(另外有 _Bool 永远是最低级别)。级别高的整数类型的宽度大于等于级别较低的整数类型。

char 的宽度用宏 CHAR_BIT 定义出来,通常为 8 ,而除了位域类型外,其它所有类型的位宽都必须是它的整数倍。

如果需要精确确定整数类型的宽度,在 C99 以及 GNU C 中,需要包含 stdint.h ,使用其中几种扩展的整数类型。

December 16, 2007

胡思乱想续

接着昨天的写。

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

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

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

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

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

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

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


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

December 15, 2007

胡思乱想

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

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

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

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

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

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

September 19, 2007

正确的迭代处理对象

昨天在写一个 AOI 模块,设计时又碰到一个对象迭代的老问题,必须谨慎对待,文以记之。

缘起:

当对象 A 进入 B 的 AOI 区域时,会触发一个 Enter 事件。这个事件处理是以回调函数的形式完成,如果回调函数中再次调用 AOI 模块,产生一次间接递归,就有可能破坏 AOI 模块内部的某些迭代过程。

更要命的是,如果回调函数内删除了一些相关对象,很有可能引起对已释放对象的访问错误。

这类问题在各种对象管理的程序框架中经常出现。除了上面提到的 AOI 模块,在 GUI 模块设计中也极其常见。下面谈谈我的解决方案吧。

September 09, 2007

C 的回归

周末出差,去另一个城市给公司的一个项目解决点问题。回程去机场的路上,我用手机上 google reader 打发时间。第一眼就看到孟岩大大新的一篇:Linux之父话糙理不糙 。主题是 C 与 C++ 的语言之争。转到刘江的 blog 下读完了 Linux之父炮轰C++:糟糕程序员的垃圾语言 大呼过瘾。立刻把链接短信发给了几个朋友。

语言之争永远是火药味十足的话题。尤其是 C 和 C++ 的目标市场又有很高的重合性,C++ 程序员往往对C++ 其有着宗教般的虔诚。我想,今天我在自己的 blog 上继续这个战争,一定会换来更多的骂名。只不过这次 Linus 几句话真是说到我心坎里去了,不喊出来会憋坏的 :D

July 24, 2007

C++ 0x 中的垃圾收集

g9 老大的 blog 里最近写了篇 关于C++ 0x 里垃圾收集器的讲座 。这是我看见的第一篇关于 C++ 0x 标准中GC 的中文文章。

最近两年我对 gc 很感兴趣 :D 已经在项目中用了两年。项目从 C++ 转到 C ,gc 模块的实现发生了变化,但是本质却没有变。我对 C++ 加入 gc 是非常欢迎的,这点在以前写的另一篇 blog 中已经表明过态度。

记得两年前,当有机会当面问 Bjarne Stroustrup 关于 C++ 发展的问题时,我毫不犹豫的讲出自己对 gc 的迫切期待,并希望能够以最小代价的把 gc 加入 C++ 。因为已经实现过一些 C++ 的 gc 模块,我有一些语言上的需求。当时描述了自己的想法,可惜英文实在是太差了,完全说不清楚 :( 因为没听明白我的意思,Bjarne Stroustrup 他老人家似乎也很无奈,最后只是建议中国的程序员应该参于到语言的标准化事务当中去,一直以来,C++ 标准委员会中似乎没有来至中国大陆的程序员。

既然 C++ 是你的工具,你就应该努力把自己对工具的改进需求说出来。

June 10, 2007

看到一句话,心有戚戚

语法层面的(nontrivial的)错误往往预示着语意层面的错误。例如,循环依赖导致的语法错误往往暗示抽象设计存在问题。

-- 转至 http://fanfou.com/statuses/uiT9IzmuonQ

我一直想好好写写循环依赖的问题,但不知如何下笔。只是在前段时间的 Blog 末尾提了一下。 (见 良好的模块设计 的最后两段。)

这些是我最近用 C 写了很多代码后悟到的。

May 25, 2007

模块的初始化

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

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

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

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

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

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

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

May 16, 2007

良好的模块设计

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

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

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

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

May 11, 2007

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

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

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

February 09, 2007

看着 C++ 远去

昨天试着维护几年前写的一个 C++ 库,只是增加一点东西。以那个时候我的眼光看,这个库设计的不算太差。这几天用的时候需要一些新功能,修改代码的话,有点担心引起不必要的麻烦。所以我决定从其中一个类继承下来,增加我要的东西。

大约花了半个多小时完成我需要的功能,由于 namespace 嵌套较多,修改编译错误又花掉了一些时间。当编译通过后,代码基本工作正常了。

January 17, 2007

从 Command 模式看 C++ 之缺陷

设计有 UI 的软件,Command 模式可以说是可能用到的设计模式中最常用的一种了。它隐藏了关于命令发起者的相关对象以及命令处理过程的细节。也就是建立一个第三方的对象,用来解耦发送者和接收者的联系。

Command 模式最常用的用途就是给软件做 undo/redo 的功能。只用维护一个链表放置命令序列,就可以方便的记住发出的命令。每个 Command 对象实现一个乒乓开关(或者实现一对 undo/redo ),在对象内部保留住相关对象,自己执行 undo 或 redo 操作即可。

January 12, 2007

C 语言已死?

今天俗一把,掺乎近期网上最热门的这个话题:C语言已经死了,5个需要忘却它的理由。大家驳来驳去 的。这的确是一个不值得一驳 的问题,我这里也没打算驳斥那些观点。只是写点别的:

January 05, 2007

C--

元旦这几天没啥心情做项目,老是胡思乱想。

有个问题我一直没弄清楚,那就是静态语言如何提供一套合理的 gc 机制。目前,给 C/C++ 硬加一套 gc 库,显然有超 C 语言的能力。这种库,也不是没有。A garbage collector for C and C++ 这儿就有一个。但是它的内存扫描,是基于一种对指针的猜测。这并非完美的解决方案。

D 语言 支持了 gc ,但跟我想象的不太一样。前段时间读了好多 D 语言的资料,还是不太了解它怎么实现 gc 的。

这几天想走另外一条路子:如果自己写一个 C 语言的前端,好象当年 C++ 干过的那样。该怎么实现最为合理呢?

December 11, 2006

为 lua 配一个合适的内存分配器

以前版本的 lua 缺省是调用的 crt 的内存分配函数来管理内存的。但是修改也很方便,内部留下了宏专门用来替换。现在的 5.1 版更为方便,可以直接把外部的内存分配器塞到虚拟机里去。

有过 C/C++ 项目经验的人都知道,一个合适的内存分配器可以极大的提高整个项目的运行效率。所以 sgi 的 stl 实现中,还特别利用 free list 技术实现了一个小内存管理器以提高效率。事实证明,对于大多数程序而言,效果是很明显的。VC 自带的 stl 版本没有专门为用户提供一个优秀的内存分配器,便成了许多人诟病的对象。

其实以我自己的观点,VC 的 stl (我用的 VC6 ,没有考察更新版本的情况)还是非常优秀的,一点都不比 sgi 的版本差。至于 allocator 这种东西,成熟的项目应该根据自己的情况来实现。即使提供给我一个足够优秀的也不能保证在我的项目中表现最佳,那么还不如不提供。基础而通用的东西,减无可减的设计才符合我的审美观。sgi 版 stl 里的 allocator 就是可以被减掉的。

好了,不扯远了。今天想谈的是,如何为 lua 定制一个合适的内存分配器。

August 31, 2006

玩了一下 Haskell

感觉 Haskell 很有趣,被它的 quicksort 的实现所吸引,花了一整天读官方的文档。感觉跟 lisp 很相象,但是比 lisp 更容易上手。

回忆当初玩 jam 的时候,jam 的语法也很有 functional programming 的味道。lua 也可以有类似的玩法:比如 http://lua-users.org/wiki/FunctionalTuples

June 14, 2006

看到一段关于 const 的讨论

摘录的一段:


My experience from other languages (C, C++, Objective C, Java, Smalltalk, etc) suggests that trying to add some notion of const to the language is detrimental. It's rarely of use to the compiler, adds little or no safety barrier for programmers, is confusing, and isn't always helpful documentation. I've seen grown men weep over C's const, and highly paid C++ professionals argue for hours over the meaning of const in C++.

The right place to annotate things with notions of constantness is the type hierarchy. See, for example, java.awt.Raster / java.awt.WritableRaster (from Java's 2D api), NSDictionary / NSMutableDictionary (from Objective-C's foundation classes).

drj


以为然也

May 30, 2006

对象和资源的管理

用了这么长时间的 C++ 架构软件,最头痛的莫过于管理内存中的对象和资源。而在管理对象方面,最难处理的就是删除对象的时机。恐怕很多人早就意识到这一点,所以才有了 gc 技术的蓬勃发展。

当一个对象被很多地方引用的时候,通常我们会给出引用记数,当记数减到 0 的时候就删除,这是个看似完美的解决方案。但是,有多少地方会记得解除引用呢?借助 C++ 的语法糖,可以自动的完成这些工作。长期的引用关系,可以在构造和析构的时候操作;短期的引用,比如就在一个函数内获得对象,操作完毕后马上解除引用。这个时候,可以通过返回几个 warpper 对象来完成。

May 27, 2006

C 有 C 的规则

最近在用 C 写程序,规模不小的程序,也谈不上太大。大约一万行之内的模块吧,关于 UI 的基础框架。我知道这个东西连用 C++ 都谈不上合适,更莫谈 C 了。可是我倔强的认为,应该用 C 把它写好。

很多人批评 C++ 没有拥有好的教育体系和方式,导致了很多 C++ 程序员在用 C 的方式写 C++ ,或是把 C++ 当成更好的 C 来用。可是受过 C++ (正确的?)教育熏陶过的程序员呢,当他拿起 C 的时候,是否把 C 当成蹩脚的 C++ 来用呢?

我希望我不是。

了解了更多的语言后,我深信,每种语言有它的游戏规则。C 有 C 的规则,C++ 有 C++ 的规则。用的越深入,越发觉得其间的差别。C++ 不是 C ,C 也不是 C++ 。它们的最大的共通点,是类似的语法,语法类似到可以用一套编译器编译。

March 10, 2006

Unicode vs Multibyte

我们的引擎的最初设计是 unicode 的,后来决定同时支持 unicode 和 multibyte 。所以我在 jamfile 里设置了一个叫做 unicode 的 feature 可以开关,这样我就可以得到两个版本。

但是,全部使用 unicode 又不太现实,有些系统提供的东西的接口就没有 unicode 版本,例如 fx 脚本。那么我们必须在 unicode 版本中又用回某些模块的 multibyte 版本。况且我们的引擎是跨平台的,不是所有的平台都像 Windows 这样对 unicode 支持的很好。管理两个版本本来就是一件非常麻烦的事情。

February 07, 2006

EPSILON is NOT 0.00001!

今天看到一篇 blog , 浮点数 和 EPSILON 。 这个问题我关注过好几次,最早是为了公司里台球的项目在公司内部 wiki 上写过。后来在留言本上也写过帖子。 http://www.codingnow.com/2004/board/view.php?paster=412&reply=0

想起来,去年 gdc2005 时完整的听过一个讲座,叫做 Numerical Robustness for Geometric Calculations 对这个问题谈的比较深入,google 了一把,把 PPT 找出来了 :) http://realtimecollisiondetection.net/pubs/ 有兴趣可以下载看看。

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 于我,可以说很有好感的,了解也逐渐增多。

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 的问题,特别做了些改进。

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++ 异常的实现的,我个人以前研究过一些,很有兴趣听听人家的理解,结果没有听到。据说后来那个会场最终吵了起来,很遗憾没有领略那个盛况 :)

September 26, 2005

关于 COM 的无责任评论

这是前段写在老的留言本上的帖子。<a href="http://www.codingnow.com/2004/board/view.php?paster=786&reply=0">http://www.codingnow.com/2004/board/view.php?paster=786&reply=0</a>

为什么有 COM ?我的理解是,MS 要给对象的二进制表达规范一种标准,好做到二进制模块的复用。到 COM 的诞生日为止,C++ 是最适合实现模块对象化的语言,直到现在 C++ 依旧是可以用面向对象的方式直接生成的本地码的最佳工具。可惜 C++ 的实现方案并没有标准,比如对象中数据的布局规则,函数调用的参数传递方式,返回值的处理方式,多继承的实现,等等。