测试不同的数据结构（最小堆、四叉堆、红黑树、时间轮）实现的定时器的性能差异。
as Hashed and Hierarchical Timing Wheels implies
a timer module has 3 component routines:
// start a timer that will expire after `interval` unit of time// return an unique id of the pending timerintStart(interval, expiry_action)
// cancel a timer identified by `timer_id`
void Cancel(timer_id)
// per-tick bookking routine// in single-thread timer scheduler implementions, this routine will run timeout actions
int Update(now)use min-heap, quaternary heap( 4-ary heap ), balanced binary search tree( red-black tree ), hashed timing wheel and Hierarchical timing wheel to implement different time scheduler.
FIFO means whether same deadline timers expire in FIFO order.
FIFO的意思是相同到期时间的定时器是否按FIFO的顺序到期
| algo | Start() | Cancel() | Tick() | FIFO | implementation file | |
|---|---|---|---|---|---|---|
| binary heap | 最小堆 | O(log N) | O(log N) | O(1) | no | PriorityQueueTimer |
| 4-ary heap | 四叉堆 | O(log N) | O(log N) | O(1) | no | QuatHeapTimer |
| redblack tree | 红黑树 | O(log N) | O(log N) | O(log N) | no | RBTreeTimer |
| hashed timing wheel | 时间轮 | O(1) | O(1) | O(1) | yes | HashedWheelTimer |
| hierarchical timing wheel | 多级时间轮 | O(1) | O(1) | O(1) | yes | HHWheelTimer |
Obtain CMake first.
apt/yum/brew install cmakeon Linux/MacOSchoco install cmakeon Windows use choco
run shell command
mkdir cmake-build; cd cmake-build && cmake -DCMAKE_BUILD_TYPE=Release .. && cmake --build .
Win10 x64 6-core 3.93MHz CPU
| Benchmark | Time | CPU | Iterations |
|---|---|---|---|
| BM_PQTimerAdd | 441 ns | 433 ns | 1947826 |
| BM_QuadHeapTimerAdd | 429 ns | 427 ns | 1866667 |
| BM_RBTreeTimerAdd | 1231 ns | 1228 ns | 1120000 |
| BM_HashWheelTimerAdd | 430 ns | 436 ns | 1792000 |
| BM_HHWheelTimerAdd | 669 ns | 672 ns | 1000000 |
| BM_PQTimerCancel | 668 ns | 656 ns | 1000000 |
| BM_QuadHeapTimerCancel | 351 ns | 349 ns | 2240000 |
| BM_RBTreeTimerCancel | 1685 ns | 1692 ns | 896000 |
| BM_HashWheelTimerCancel | 632 ns | 641 ns | 1000000 |
| BM_HHWheelTimerCancel | 942 ns | 953 ns | 1000000 |
| BM_PQTimerTick | 29.8 ns | 29.8 ns | 23578947 |
| BM_QuadHeapTimerTick | 30.3 ns | 30.5 ns | 23578947 |
| BM_RBTreeTimerTick | 30.2 ns | 29.8 ns | 23578947 |
| BM_HashWheelTimerTick | 31.2 ns | 30.8 ns | 21333333 |
| BM_HHWheelTimerTick | 30.5 ns | 30.7 ns | 22400000 |
- rbtree timer Add/Cancel has not so good performance compare to other implementations;
- 红黑树的插入和删除相比其它实现，表现都弱了一些；
- binary min heap is a good choice, easy to implement and have a good performance, but without FIFO expiration order(heap sort is unstable);
- 最小堆是一个不错的选择，代码实现简单性能也不俗，但不支持相同超时的定时器按FIFO顺序触发;