勤能补拙,Expter

成都游戏Coder,记录游戏开发过程的笔记和心得!

一个高效的定时器分析及设计

       对于一个游戏而言,定时器是必须的,而它一般作为一个游戏基本公共组件,而定时器在游戏逻辑中运用是非常明显的(比如吃药回血,每几秒回血多少),而对于游戏逻辑而言需要开发一个高效率高精度(毫秒级别)的定时器。

    
一:分析Ace库定时器实现方式

   1.Ace种定时器实现有4种,这里不具体介绍实现细节,主要介绍实现数据结构,性能。
       具体的4种定时器都是从ACE_Timer_Queue_T继承,每种定时器用不同的数据结构来实现具体Timer的算法。
      1)ACE_Timer_Heap定时器,根据触发时间建立一个优先级队列(一个最小堆数据结构)来维护所有的定时器,代价就是删除和插入过程为O(logn),代价比较高。
      2)ACE_Timer_List定时器,根据触发时间建立一个有序的双向链表,代价就是插入定时器代价较高。
      3)ACE_Timer_Hash定时器,采用开链的Hash方式每一个桶为一个单链表,在检查所有桶超时的时候会遍历链表所有的元素。为了提高效率这里所用的Hash桶应该足够 大,而对于定时器一般是频繁的超时响应定时器,已经插入和删除,响应会采用迭代的方式。所以效率并不是那么高效。
      4)ACE_Timer_Wheel定时器,采用的一种时间轮的方式,具体实现就好象一个轮子上面有很多插槽,每一个插槽下面包括一个有序双向链表,在Ace中把轮子叫做Wheel,插槽叫做Spoke,每一个定时器被Hash到Spoke中,而Spoke也可以理解为timer的分辨率,而Spoke的计算公式为 :( 触发时间 >> 分辨率的位数)&(spoke大小-1).然后在根据触发时间把定时器插入到每一个Spoke的有序双向链表中, 与Ace_timer_Hash的实现类似,只是这里用户可以指定Spoke大小。这里代价就是插入的时候可能最坏为O(n).
    
      我们公司现在CTimer就是采用Ace的ACE_Timer_Wheel原理设计的
      这里有一个图更能直观的描述这种思想:
    
           实现方式为Vector,list组合。


 二: 本文介绍一种采用linux中断处理的定时器设计方式  
     此定时器的查找,删除,插入都是O(1)
     1) 介绍设计原理
     定时器是基于时间的中断函数,即是根据触发时间来超时响应。所以只要我们设计一个基于时间的Hash算法。只要我们能我们把一个函数触发时间全部Hash到此Hash算法的桶中,就实现了查找,插入,删除O(1)的操作了,其实不然基于时间的hash算法好像挺复杂,而且桶的数量太大,内存消耗太多,所以把一个时间直接Hash代价太大。是否有一种其他的方式呢,linux中断处理采用一种类似水表计算水量的方式,方式就是生活中的水表,第一个指针转一圈后一个转一格,假设每一个圈都是10个刻度,第一个圈能表示10,那么第二圈没一个刻度表示第一个圈的1圈,就能表示10*10, 二个圈一共就能表示10*10 + 10。 以此类推,5个圈就能表示10^5+10^4+10^3+10^2+10...

      一个32bits的整数,如果精确到1毫秒,则2^32位可以表示49.3天,而一般服务器应该不会直接运行49.3天,这里我们采用5个轮子(即圈), 轮子大小分别为256,64,64,64,64 ,轮子依次类推表示范围在0~256, 256~256*64, 256*64~256*64^2, 256*64^2~256*64^3, 256*64^3~256*64^4, 假设这里精度为n毫秒,第一个轮子表示n*256秒时间内触发函数,第二个轮子的第二个插孔则表示n*256*2时间范围内的,

    2)一些定义:
           A. 轮子,这里采用的轮子与上面介绍的Ace轮子大概一样,一个循环列队,每一个插槽你们有一个双向链表,注意这里链表不需要排序,所以在插入的是O(1)的操作。轮子为5个。

    3)  操作:
           A. Hash算法:这里Hash算法根据他的多少时间后触发,直接Hash得到轮子以及插槽,然后插入到某个插槽双向的链表中。
           B.定时器触发: 定时器触发只会触发第一个轮子超时的所有定时器,因为后面4个轮子定时器表示都在前1轮子触发完了才会触发,所以这里让后面4个轮子维护表示将要发生的定时。这里会根据当第一个轮子转第几圈后,第二个轮子会把第几插槽的所有定时器全部插入到第一个轮子中,依次类推,第二个轮子转一个第三个轮子某个插槽又会插入到第二个轮子中。。。
           
   4)注意的地方:
          A.将一个定时器插入到它应该所处的定时器轮子插槽中。
          B.定时器的迁移,也即将一个定时器从它原来所处的轮子插槽迁移到另一个轮子插槽中。
          C.超时响应执行当前已经到期的定时器。

三:编码实现
         1) 常量定义
                   
/// define m
#define lnum        5
#define sbits        6
#define ebits        8
#define sbitsize    ( 1 << sbits )
#define ebitsize    ( 1 << ebits )
#define sMask        ( sbitsize- 1)
#define eMask        ( ebitsize -1)

         2) 数据结构
                 
 1/// 定时器指针结点
 2struct ListNode
 3{
 4    ListNode *next,*prev;
 5}
;
 6
 7///
 8/// 定时器类型
 9/// 

10enum eTimerType
11{
12    eTimer1 = 10,
13    eTimer2 ,
14    eTimer3 
15}
;
16
17/// 
18/// 定时器结点,tlist表示结点的指针,expires循环周期时间
19/// etime 触发周期时间,pFun触发函数.
20/// 

21struct timernode
22{
23    ListNode    tlist;
24    ulong       expires;
25    ulong       etime;
26    void        *pFun;
27    eTimerType  eType;
28}
;
  3) 轮子类
                     
 1///              
 2/// 一个轮子,一个循环队列
 3/// 
 4/// 

 5class CLinkList
 6{
 7
 8public:
 9
10    CLinkList(void);
11
12    CLinkList( int size );
13    
14    ~CLinkList(void);
15    
16    /// 
17    /// 初始化
18    /// 

19    void  init();
20
21    /// 
22    /// 让指针指向自己
23    /// 

24    void  init_list_self( int  index);
25
26    /// 
27    /// 把news插入到prev,next之间
28    /// 

29    void  insert_listnode(ListNode *news , ListNode* prev , ListNode* next);
30
31    /// 
32    /// 插入到链表头
33    /// 

34    void  insert_head( ListNode* news , ListNode* head );
35
36    ///
37    /// 插入到链表尾
38    /// 

39    void  insert_tail( ListNode* news , ListNode* head );
40
41    /// 
42    /// 删除节点
43    /// 

44    void  list_del( ListNode* list);
45
46    /// 
47    /// 得到改轮子转到第几个插槽
48    ///

49    int        GetIndex( ) const return m_index ;}
50
51    ///
52    /// 更新轮子的插槽
53    ///

54    void       SetIndex(int idx) { m_index = idx  ;}
55
56    /// 
57    /// 得到轮子插槽的指针 
58    ///

59    ListNode*  GetNode(int index) const;
60
61private:
62    ///
63    /// 轮子的插槽数组
64    /// 

65    ListNode *m_List;  
66    
67    ///
68    /// 轮子当前转到的索引
69    /// 

70    int          m_index; 
71
72    ///
73    /// 轮子大小
74    ///

75    int       m_Size;
76
77}
;

         4)定时器管理类
                
定时器管理类


四: 测试
         通过本文的介绍可以理解次定时器的的查找,删除,插入都是O(1)的复杂度。

  
/// 游戏事件基类
class   CGameEvent
{
public:
    
virtual  long  TimeOut( eTimerType type) = 0;
}
;

测试例子:
 1long  Sum1= 0 ;
 2long  Sum2= 0 ;
 3long  Sum3= 0 ;
 4long  Sum = 0;
 5
 6class  CTimerTest : public   CGameEvent
 7{
 8public:
 9    long TimeOut( eTimerType type)
10    {
11        switch ( type)
12        {
13        case eTimer1:
14            std::cout <<"Sum1 = "<< Sum1 ++ << std::endl;
15            break;
16        case eTimer2:
17            std::cout <<"Sum2 = "<< Sum2 ++ << std::endl;
18            break;
19        case eTimer3:
20            std::cout <<"Sum3 = "<< Sum3 ++ << std::endl;
21            break;
22        default:
23            std::cout <<"Sum  = "<< Sum ++ << std::endl;
24            break;
25        }

26        return 0;
27    }

28}
;
29
30int _tmain(int argc, _TCHAR* argv[])
31{
32    CTimer  mytimer( 40 );
33    
34    long    n;
35    std::cin >> n;
36    CTimerTest test;
37    for ( int i = 0 ; i < n ; i++ )
38    {
39        timernode* tim = new timernode ;
40        tim->expires  = 0;
41        tim->etime    = GetCurrSystemTime() + (rand() % 1000 ) * 6;
42        tim->pFun     =&test;
43        tim->eType    =(eTimerType)( i%3 + 10 );
44
45        mytimer.add_timer( tim );
46    }

47
48    for ( ;; )
49    {
50        if ( (Sum1 + Sum2 + Sum3) == n )
51            break;
52
53        /// 运行所有的定时器
54        mytimer.Expires( GetCurrSystemTime() );
55    }

56
57    std::cout << " sum1 = " << Sum1 
58              << " sum2 = " << Sum2 
59              << " sum3 = " << Sum3 
60              << " sum  = " << Sum ;
61    return 0;
62}

63

上面的具体代码:http://code.google.com/p/tpgame/source/browse/#svn/trunk/CTimer/CTimer


最近2篇学习笔记将介绍:
1.参考多种内存管理模型的自己写的内存管理模块。
2.最近学习的Ai算法总汇。

posted on 2010-03-05 16:28 expter 阅读(8923) 评论(12)  编辑 收藏 引用 所属分类: 工作笔记算法与数据结构

评论

# re: 一种高效的定时器设计 2010-03-05 21:42 expter

整了半天,格式有点问题,现在看了下还是有点问题。。  回复  更多评论   

# re: 一个高效的定时器分析及设计 2010-03-07 22:59 何清龙

没关系。
因为有问题,才会需要C++程序员。哈哈  回复  更多评论   

# re: 一个高效的定时器分析及设计 2010-03-07 23:08 hr

我们公司有游戏职位,是否有兴趣。
已经联系你了:)  回复  更多评论   

# re: 一个高效的定时器分析及设计 2010-03-08 10:01 何清龙

想过了,我技术还不够,时间也不充裕。谢谢好意。  回复  更多评论   

# re: 一个高效的定时器分析及设计 2010-03-08 16:00 expter

@何清龙
你在说什么哦。。。  回复  更多评论   

# re: 一个高效的定时器分析及设计 2010-03-23 18:33 guest

>>这里会根据当第一个轮子转第几圈后,第二个轮子会把第几插槽的所有定时器全部插入到第一个轮子中

有个疑问。。假设第二个轮子的第几插槽上的定时器有100个,要对这100个定时器全部hash一遍,才插入到第一个轮子对应的插槽吧?

这样貌似的消耗还是有点大  回复  更多评论   

# re: 一个高效的定时器分析及设计 2010-03-23 22:17 expter

@guest
不会的,而且定时器的代价主要在遍历响应超时定时器结点。
而且插入式线性的,我做过测试对于100W个定时器插入时间不到1S。。。  回复  更多评论   

# re: 一个高效的定时器分析及设计 2010-03-24 00:00 guest

@expter
想了一下,第2轮子要等第一个轮子转动一圈之后才会转动一次,总体来说还是接近O(1)。。。

借鉴楼主的思路了:)  回复  更多评论   

# re: 一个高效的定时器分析及设计 2012-04-01 16:51 酱油男

就像钟表的时分秒针一样会遇到0点问题,三针重合会遍历处理所有链表。  回复  更多评论   

# re: 一个高效的定时器分析及设计 2013-07-24 08:33 =XTK

很好的设计,如果我想中途中止这个定时器,那还没有这个接口..不过我准备自己加上,准备用人你的这份设计啦..很好很强大..  回复  更多评论   

# re: 一个高效的定时器分析及设计 2014-01-03 16:38 simaocat

你好,请问主函数中CTimer mytimer( 40 );这个40代表什么意思呢,为什么算expires时间的时候要除以这个40, 其单位是秒还是毫秒  回复  更多评论   

# re: 一个高效的定时器分析及设计 2015-05-28 20:16 aaa

http://code.google.com/p/tpgame/source/browse/#svn/trunk/CTimer/CTimer
这个网址打不开啊!  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理