heiqiyihu123/timer-benchmarks

Benchmark of different timer implementations(min-heap, red-black tree, timing wheel)

timerqueue-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
int Start(interval, expiry_action)

// use `tiemr_id` to locate a timer and stop it
void Stop(timer_id)

// per-tick bookking routine
int Tick(now)

use min-heap, quaternary heap or 4-ary heap, balanced binary search tree or red-black tree, hashed timing wheel and Hierarchical timing wheel to model different time module

分别使用最小堆、四叉堆、红黑树、时间轮、层级时间轮实现定时器，测试插入、删除、Tick操作的性能。

How To Build

Obtain CMake

ObtainCMake first.

Linux or WSL

• make build

or

• cmake -Bbuilds -DCMAKE_BUILD_TYPE=Release
• cmake --build builds --config Release

Windows

Visual C++ Compiler toolchain is necessary.

Benchmarks

Big(O) complexity of algorithm

  algo                    | Start()    | Stop() | Tick()   | implemention file
------------------------------------------------------------------------------------
binary heap               | O(log N) | O(log N) | O(1)     | src/PriorityQueueTimer.h
4-ary heap                | O(log N) | O(log N) | O(1)     | src/QuatHeapTimer.h
redblack tree             | O(log N) | O(log N) | O(log N) | src/RBTreeTimer.h
hashed timing wheel       | O(1)     | O(1)     | O(1)     | src/HashedWheelTimer.h
hierarchical timing wheel | O(1)     | O(1)     | O(1)     | src/HHWheelTimer.h

Benchmark result

Conclusion

Reference

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