本文共 1499 字，大约阅读时间需要 4 分钟。
:
游戏中定时器的设计:
ACE有一个非常优美的定时器队列模型，他提供了4种定时器Queue让大家使用：ACE_Timer_Heap，ACE_Timer_Wheel，ACE_High_Res_Timer，ACE_Timer_Hash。在《C++ Network Programming Volume 2 - Systematic Reuse with ACE and Frameworks》中间有相应的说明，其中按照说明最诱人的的是：
ACE_Timer_Hash, which uses a hash table to manage the queue. Like the timing wheel implementation, the average-case time required to schedule, cancel, and expire timers is O(1) and its worst-case is O(n).
但是遗憾的是，ACE_Timer_Hash其实是性能最差的。几乎不值得使用。我曾经也被诱惑过，但是在测试中间发现，文档中所述根本不属实，在一个大规模定时器的程序中，我使用ACE_Timer_Hash发现性能非常不理想，检查后发现ACE的源代码如下：
template <class TYPE, class FUNCTOR, class ACE_LOCK, class BUCKET> int
ACE_Timer_Hash_T<TYPE, FUNCTOR, ACE_LOCK, BUCKET>::expire (const ACE_Time_Value &cur_time)
{
// table_size_为Hash的桶尺寸，如果要避免冲突，桶的数量应该尽量大，
//每个桶可以理解为一个Hash开链的链表
// Go through the table and expire anything that can be expired
//遍历所有的桶
for (size_t i = 0;
i < this->table_size_;
++i)
{
//在每个桶中检查是否有要进行超时处理的元素
while (!this->table_[i]->is_empty ()
&& this->table_[i]->earliest_time () <= cur_time)
{
…………
简单说明一下上面的代码，ACE_Timer_Hash_T采用开链的Hash方式，每个桶就是一个链表，在超时检查时所有的桶中是由有要进行超时处理的元素。所以在超时处理中ACE采用了遍历所有元素的方法。但悖论是如果你希望Hash的冲突不大，你就必须将桶的个数调整的尽量多。我在测试中将上述的程序的Time_Queue替换为标准的的ACE_Timer_Heap，发现性能提高数百倍。
冷静下来思考一下，这也是正常的。对于一个Hash的实现，保证查询的速度，也就是通过定时器ID进行操作的速度是足够快的。但是实际上对于定时器操作，最大的成本应该是寻找要超时的定时器，对于Hash这种数据结构，只能采用迭代遍历的方式……， 所以采用Hash的低效是正常的。而原文应该改为schedule, cancel,的最好时间复杂度是O(1)，最差是O(n),而expire的时间复杂度始终是O(n)。
这个问题在ACE自己的文档中间也有较为正确的描述。
这个问题至少倒5.6.1的版本还是存在的。我个人估计也不会得到解决。Hash的特性摆在那儿呢，除非ACE采用更加复杂的数据结构。
转载地址：http://gezvb.baihongyu.com/