ki7chen / timer-benchmarks

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 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的顺序到期

algo		Start()	Cancel()	Tick()	FIFO	implemention file
binary heap	最小堆	O(log N)	O(log N)	O(1)	no	PriorityQueueTimer
4-ary heap	四叉堆	O(log N)	O(log N)	O(1)	no	QuatHeapTimer
redblack tree	红黑树	O(log N)	O(log N)	O(log N)	no	RBTreeTimer
hashed timing wheel	时间轮	O(1)	O(1)	O(1)	yes	HashedWheelTimer
hierarchical timing wheel	多级时间轮	O(1)	O(1)	O(1)	yes	HHWheelTimer

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

Benchmark	Time	CPU	Iterations
BM_PQTimerAdd	441 ns	433 ns	1947826
BM_QuadHeapTimerAdd	429 ns	427 ns	1866667
BM_RBTreeTimerAdd	1231 ns	1228 ns	1120000
BM_HashWheelTimerAdd	430 ns	436 ns	1792000
BM_HHWheelTimerAdd	669 ns	672 ns	1000000
BM_PQTimerCancel	668 ns	656 ns	1000000
BM_QuadHeapTimerCancel	351 ns	349 ns	2240000
BM_RBTreeTimerCancel	1685 ns	1692 ns	896000
BM_HashWheelTimerCancel	632 ns	641 ns	1000000
BM_HHWheelTimerCancel	942 ns	953 ns	1000000
BM_PQTimerTick	29.8 ns	29.8 ns	23578947
BM_QuadHeapTimerTick	30.3 ns	30.5 ns	23578947
BM_RBTreeTimerTick	30.2 ns	29.8 ns	23578947
BM_HashWheelTimerTick	31.2 ns	30.8 ns	21333333
BM_HHWheelTimerTick	30.5 ns	30.7 ns	22400000

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

timer-benchmarks's Issues

线程安全

现在实现的timer非线程安全吧

测试程序Bug:count为偶数时删除所有timer，为奇数时不删除timer

static void TestTimerQueue(TimerQueueBase* timer, int count)
{
    std::vector<TimerContext> ctxvec;
    ctxvec.resize(count);
    for (int i = 0; i < count; i++)
    {
        TimerContext* ctx = &ctxvec[i];
        ctx->queue = timer;
        ctx->interval = rand() % ScheduleRange;
        int id = timer->AddTimer(ctx->interval, std::bind(&onTimeout, ctx));
        ctx->id = id;
        //printf("schedule timer %d of interval %d\n", id, ctx->interval);
        //std::this_thread::sleep_for(std::chrono::milliseconds(ctx->interval/2));
    }
    for (int i = 0; i < count; i++)
    {
        if (count % 2 == 0)  //count偶数时删除所有timer，奇数时不删除timer. count是不是应该改为 i ？
        {
            timer->CancelTimer(i);
        }
    }
    printf("all timers scheduled, %d\n", count / 2);
    while (timer->Size() > 0)
    {
        timer->Update();
        std::this_thread::sleep_for(std::chrono::milliseconds(2));
    }
}

find 3 bug

1. 时间轮事件删除时立即从哈希中删除，在触发中延期统一删除可能使得hash map一直变大（我的测试10%影响，先大量加入然后大量删除的应用场景）

2. 时间轮事件执行中立即把taskl状态设置为false，因为callbak中可能删除当前执行的定时器，使得size计算不对变成负数（测试遇到了,size 变量可以删除用hash map计数）

3. cancel 时间轮的事件可多次执行。需设置task事件状态为fasle或从hash中删除

4. tick中执行了2次execute，可以减少一次调用（简单做在外部循环外调用一次，调用一次就行）。

5. cascade 重新添加事件要过滤已失效的

换 flat hash map 提升性能

下面测试替换我实现的hash map. 性能提升比较明显https://github.com/ktprime/emhash/blob/master/hash_table5.hpp

D:\timer-benchmarks-master\test\BenchTimer.cpp relative time/iter iters/s

PQTimerAdd 17.27ms 57.89
TreeTimerAdd 76.74% 22.51ms 44.42
WheelTimerAdd 113.68% 15.20ms 65.81

PQTimerDel 12.65ms 79.08
TreeTimerDel 113.87m% 11.11s 90.04m
WheelTimerDel 159.14% 7.95ms 125.85

PQTimerTick 3.67ms 272.61
TreeTimerTick 70.78% 5.18ms 192.94
WheelTimerTick 58.32% 6.29ms 158.98

PQTimerAdd 12.44ms 80.38
TreeTimerAdd 55.98% 22.22ms 45.00
WheelTimerAdd 119.79% 10.39ms 96.28

PQTimerDel 7.73ms 129.29
TreeTimerDel 68.57m% 11.28s 88.65m
WheelTimerDel 157.01% 4.93ms 203.01

PQTimerTick 2.17ms 461.49
TreeTimerTick 38.52% 5.63ms 177.75
WheelTimerTick 46.62% 4.65ms 215.16

新的定时器 时间轮 + 4-dray heap

在我的quic 网络库中，单个用户连接存在6-8个左右定时器(重传，延时发包，心跳，idle，ack, blackhole, send_flush ...)，统计显示95%以上的操作删除和插入，真正触发非常少(活跃的ack和重传)，每秒10w+次基本操作，需要超高性能的定时器毫秒精度设计方案。

上面各种方案或多或少存在应用场景限制，比如时间轮定时器存在如下缺陷
第一：存在空转现象，尤其是定时器不多，触发分布不均匀
第二：无法O(1)取到最小时间触发点 (比如网络库中 epoll 常用最小触发时间作为超时参数)
另外堆和红黑等实现中高频繁插入删除性能比较差 ，内存局部性性能不友好

我结合时间轮和4叉堆两种不同实现方案整合一直新的定时器， 基本能满足各种设计要求,
时间轮第一级(比如 256 毫秒内)用4叉堆实现。堆的大小至于太大，活跃的定时器基本都在堆中，
时间轮每256 ms更新一次堆中数据。

#pragma once

#include "util/heap_timer.h"
#include "util/wheel_timer.h"

// timer queue implemented with hashed hierarchical wheel + 4-dary heap.
// complexity:
//      AddTimer   CancelTimer   PerTick  GetMinTimer
//       O(1)       O(1)          O(1)            O(1)
//

class HWheelTimer : public TimerBase
{
public:
    HWheelTimer(int64_t now_time, uint32_t timer_size);

    timerId Schedule(int64_t deadline_ms, QTask* cb);
    bool Delay(int64_t deadline_ms, timerId timer_id);
    void Reset(int64_t deadline_ms, timerId timer_id, QTask* cb);

    bool Cancel(const timerId timer_id);
    bool Erase(const timerId timer_id);
    int Run(const int64_t now_ms);
    int64_t NearTime();
    int DumpTimer(char* buffer);

private:
    void tick();
    void add_wheel(TimerNode* node);
    bool cascade(int bucket);
    bool erase_node(TimerNode* node);
    bool erase_slot(WheelList& near, const TimerNode* node);

private:
    int64_t min_expire_;
    uint32_t addws_, addn1_, moves_, runs_, delays_;
#ifndef BIN_HEAP
    DaryHeap min_queue_;
#else
    BinHeap min_queue_;
#endif
    WheelList buckets_[WHEEL_BUCKETS][TVN_SIZE];
};