timer-benchmark

测试不同的数据结构（最小堆、四叉堆、红黑树、时间轮）实现的定时器的性能差异。

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 timer
int Start(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.

Big(O) complexity of algorithm

FIFO means whether same deadline timers expire in FIFO order.

FIFO的意思是相同到期时间的定时器是否按FIFO的顺序到期

How To Build

Obtain CMake

Obtain CMake first.

• sudo apt install cmake on Ubuntu or Debian
• sudo yum install cmake on Redhat or CentOS
• choco install cmake on Windows use choco

run shell command

• mkdir cmake-build; cd cmake-build && cmake -DCMAKE_BUILD_TYPE=Release .. && cmake --build .

Benchmarks

Benchmark result

Win10 x64 6-core 3.93MHz CPU

Conclusion

• 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顺序触发;

Reference

• Hashed and Hierarchical Timing Wheels
• Hashed and Hierarchical Timing Wheels
• Netty HashedWheelTimer
• Apache Kafka, Purgatory, and Hierarchical Timing Wheels