timer-benchmarks
timer-benchmarks copied to clipboard
Published
20 hours ago •
ki7chen
ki7chen
Benchmark of different timer implementations(min-heap, red-black tree, timing wheel) 不同数据结构实现的定时器测试
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
| algo | Start() | Cancel() | Tick() | implemention file |
|---|---|---|---|---|
| binary heap | O(log N) | O(log N) | O(1) | PriorityQueueTimer |
| 4-ary heap | O(log N) | O(log N) | O(1) | QuatHeapTimer |
| redblack tree | O(log N) | O(log N) | O(log N) | RBTreeTimer |
| hashed timing wheel | O(1) | O(1) | O(1) | HashedWheelTimer |
| hierarchical timing wheel | O(1) | O(1) | O(1) | HHWheelTimer |
How To Build
Obtain CMake
Obtain CMake first.
-
sudo apt install cmakeon ubuntu or debian -
sudo yum install cmakeon redhat or centos -
choco install cmakeon 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:
ki7chen