Giter Site home page Giter Site logo

heiqiyihu123 / timer-benchmarks Goto Github PK

View Code? Open in Web Editor NEW

This project forked from qi7chen/timer-benchmarks

0.0 0.0 0.0 1.75 MB

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

License: Apache License 2.0

C++ 83.80% C 1.99% Shell 0.80% Python 10.33% CMake 2.11% Starlark 0.83% Makefile 0.01% HTML 0.06% SCSS 0.07%

timer-benchmarks's Introduction

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

timer-benchmarks's People

Contributors

qchencd avatar qi7chen avatar tinkerlin avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.