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操作的性能。
ObtainCMake first.
Linux or WSL
make build
or
cmake -Bbuilds -DCMAKE_BUILD_TYPE=Release
cmake --build builds --config Release
Visual C++ Compiler toolchain is necessary.
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