Skip to content
This repository has been archived by the owner on Nov 15, 2022. It is now read-only.
/ skipper Public archive

Various skip list implementations

License

Notifications You must be signed in to change notification settings

TmLev/skipper

Repository files navigation

Skipper

skipper Build Status

What is it?

Skipper is a C++17 header-only library with various implementations of skip list data structure.

How to use?

Benchmarks

For measuring performance Google Benchmark library was used. Source code of benchmarks can be found here.

3 experiments with different setups (described below) have been conducted. Every benchmark ran on several number of threads (from 1 to 16). Performance was measured on Intel Core i7-8565U x86-64 with 8 hyper-threading cores with 1.8 CHz base frequency and 4.6 max turbo frequency. RAM is 32 GB DDR4.

Contains

This benchmark tests Contains() method. As a setup 10^6 random numbers from R = (-10^4; 10^4) are inserted.

Contains benchmark graph

Insert

Here Insert() method performance is measured. For setup 10^3 random numbers from R = (-10^3; 10^3) are inserted.

Insert benchmark graph

One Insert & Many Contains

Here both methods are tested. 10^4 random numbers from R = (-10^4; 10^4) are inserted for a setup. During benchmarks itself one thread inserts random numbers from R the endless loop, while other threads are checking for contains random numbers from R.

One Insert & Many Contains benchmark graph

How to contribute?

Feel free to open an issue if something is wrong. For pull requests please follow these instructions.