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 Tick(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

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

TODO:

Conclusion

TODO:

Reference

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