实现一个 timer
前段时间写过一篇 blog 谈到 用 timer 驱动游戏 的一个想法。当 timer 被大量使用之后，似乎自己实现一个 timer 比用系统提供的要放心一些。最近在重构以前的代码，顺便也重新实现了一下 timer 模块。
这次出于谨慎，查了一些资料，无意中搜到这样一篇文章：Linux内核的时钟中断机制 。真是一个不错的设计啊 :D 和我的 timer 实现的思路是一致的，但是在细节上要优秀。
linux 的这个实现方法的优点是把事件按回调时间距离现在的远近分成了多级。我早先的实现考虑到游戏通常不会设置很长远的事件，所以只分了两级。事实上，巧妙的安排每级的数组容量，利用取模操作，处理的速度非常的快，不会因为只分两级或是分成更多级别而受到影响。
昨天晚上重写了一遍 timer 模块，居然只用了 100 行代码就完成了，篇幅较上次写的大为缩短。
我的实现方法和那篇文章中所述 linux 的实现有所区别，这并不是因为我的算法更优秀，而只是因为要解决的问题更简单罢了：
我认为实际上 struct list_head vec[TVR_SIZE]; 这里这个数组只需要开 [TVR_SIZE-1] 大小就够了。因为每级的数组的第 0 项永远都会为空，其内容全部包含在近一级别的各个数组中。而全部 5 个数组正好覆盖 [0,0xffffffff] 。
cascade_timers 这个操作并不需要每次 run 的时候都做，而只需要在恰当的时刻一次做了即可。我们在 add_timer 时不需要理会相对时刻，而只需要处理绝对时刻的事件。
这样做存在两个潜在的问题，一是 run 的时候，速度有所波动，特定时刻需要处理额外的 cascade_timers 操作，比起每次每次都调用 cascade_timers 来说，这个时刻处理的数据量会增加。但我个人认为还不至于造成被人感觉的到的停顿感；二是采用绝对时刻的话，32bit 来表示时间值对于太长时间有可能溢出。好在游戏 client 程序不需要 7*24 小时工作，40 亿个 ticks 足够了。
另外，我认为 del_timer 的需求是完全多余的。如果真的有杀掉事先注册的事件的需求，我们完全可以由 timer 的参数来决定在它被触发的时候是否需要被 cancel 掉。而增加从外面主动杀掉的方法，只会增加接口的复杂性。取消这个设计后，代码会简洁很多。至少在内部实现上，不再需要双向链表。
最近一两年的开发经验让我感觉到，通常游戏中用到的 timer 回调函数往往只有唯一的一个，而仅靠参数就可以区分要做的事情。（这得益于脚本的嵌入，真正的回调函数并不需要是一个独立的 C 函数，而是一个脚本函数）
所以，我们并不需要在 timer 结构中纪录下 callback 函数指针，而只需要在 run 的时候统一传入一个即可。这样的设计比之 linux 的实现有更多的灵活性。如果真的需要支持不同的 C 函数回调，完全可以把函数指针填到参数中。因为大多数情况下，参数并不是一个数字，而是一个结构指针，如果让回调函数去负责回收内存，设计就略显丑陋了。
最终，我的 add_timer 原型只需要这样：void add_timer(void *arg, int time) 。而 run_timer_list 则需要多传递一个 callback function 。如果需要自定义的 c callback function ，可以扩展 arg 结构。例如：
Comments
把callback放到timer_arg比放在timer结构中的好处在哪里呢？
Posted by: totti | (17) June 13, 2011 09:32 PM
定时器里面管理内存分配？？为什么呢？请问云风如果我要删除，在这套代码里要怎么做？
Posted by: lin_style | (16) September 27, 2010 04:15 PM
为什么不用最小堆组织定时器事件列表？插入和删除都是log(n)复杂度，简单而且不需要再额外的维护...
Posted by: orz | (15) May 11, 2007 12:31 PM
建议云风再出一本书，名字我都想好了，就叫《造，并快乐着！》。。。。。。。。。。。。。。。。。。。。。。。。。。。。。纯属玩笑！
Posted by: crazymader | (14) May 5, 2007 04:24 PM
因为真正的 callback 函数指针可以写到参数中去。
正文最后的例子已经写明了。
Posted by: Cloud | (13) May 4, 2007 04:01 PM
为什么说“通常游戏中用到的 timer 回调函数往往只有唯一的一个，而仅靠参数就可以区分要做的事情。”呢？能详细解释一下吗？
Posted by: Anonymous | (12) May 4, 2007 03:46 PM
我想我们这里的开发环境能让所有真正热爱游戏和编程的人满意 :D
Posted by: Cloud | (11) May 3, 2007 02:12 AM
我有个疑问是，云风一会儿切到C了，一会儿切到C++了，一会儿搬出个bjam，一会儿又弄mingw了，一个正规的有点规模的公司能这么容易让下面的人随便切换程序语言和开发工具吗？
Posted by: missdeer | (10) May 3, 2007 01:45 AM
我的观点是：bug 出现的频率跟代码长短有一定的关系，但是这个影响因素是次要的；更主要的影响因素是程序员的程序生涯中写的代码总数。
说到底 bug 会不会出现，出现的多不多，因人而异。人才是主要因素。
好的程序员应该在不拷贝粘贴的前提下尽量多的写程序, 写不同的程序，写没实现过的程序。无论有没有人曾经做过类似的工作。提高自身的水平，才是提高项目质量的正途。
Posted by: Cloud | (9) May 3, 2007 01:33 AM
1. 相同接口的实现固然是找不到，相似接口的实现倒是有的。
2. 更可信的解释是为了自己实现更有控制感吧:-) 的确，很多时候，往往自己实现比重用现有的东西还快。
3. 说的没错啊。不过有一点小地方我不同意，一个相当规模的游戏程序，在需求不变的前提下，对于单个程序员来说，往往是可以写得更短的。短的代码理所当然出错更少，只不过，往往短的代码比长的代码花的时间更多。
Posted by: Atry | (8) May 3, 2007 12:14 AM
看了半天没看太明白说明了什么问题，是实现了一个timer wheel算法吗？游戏里面一般用不了几个定时器，直接用list也没什么问题。
提高开发效率的最好方法是永远只用最简单有效的方法实现当前的需求，直到确实出现需求变动或者性能瓶颈才进行重构。一个好的程序员应该尽可能的少写代码。
Posted by: analyst | (7) May 2, 2007 11:51 PM
如果用模板,函数指针都可以不用:)效率更高.
自己发明轮子是有必要的，尤其是在服务器端,STL和ACE的效率很多时候无法接受.
Posted by: sunway | (6) May 2, 2007 10:59 PM
1.我写的 timer 并非底层，它依赖底层的实现，并满足游戏逻辑实现的需求。而且并无完全相同接口的相同实现。
2.键盘上 26 个字母，一直存在那里，我们都需要重复的输入。写程序靠的是熟能生巧，程序员永远不会去用鼠标把单词拖到一起组成程序。任何代码只要写到跟 1+1=2 的地步，可以在不过大脑思考而靠条件反射就可以写出来的境界，就无所谓重不重写了。
3.一个相当规模的游戏程序，你复用也好，从零写也好。整个的代码行数还是同一数量级的。而一个好的程序员可以提升的工作效率却是超过一个数量级的。整个项目的完成周期跟代码是否更多的复用已有程序无关；而跟程序员的稳定性栖息相关。而程序员提高其稳定性，惟有不停的写程序。
Posted by: Cloud | (5) May 2, 2007 10:16 PM
非也，这个世界上千奇百怪的需求多了去了。前人没写过的程序在满大街都是。唯有底层构造是前人写过千百万遍，重写无益。
Posted by: Atry | (4) May 2, 2007 08:21 PM
云风这么做是为了跨平台?
Windows下的实现是基于什么的？kernel timer吗？
Posted by: madlax | (3) May 2, 2007 07:10 PM
非也，我没有发明什么。造个轮子而已，百把行代码。如果大家都写前人没写过的程序，这世界上就无甚程序可写了。
Posted by: Cloud | (2) May 2, 2007 03:59 PM
恭喜你，你又发明了一个轮子！
Posted by: Atry | (1) May 2, 2007 03:36 PM