The Cache-Sensitive Skip List (CSSL) is a cache-sensitive variant of the
conventional skip list that uses a different memory layout to take
maximal advantage of modern CPUs.
Please have a look at the paper
Cache-Sensitive Skip List: Efficient Range Queries on modern CPUs presented at ADMS-IMDM 2016 to get a
detailed description of the index structure.
CSSL uses Intel's AVX instructions (SIMD), so please make sure that your CPU supports them.
Setup is easy, just use the provided
Makefile and run the created executable
In the following example, range queries and lookups are executed on 16M
sparse integer keys.
- make clean all
- ./cssl 16000000 1
./cssl to see a description of needed parameters.
If you want to use a skip value greater than 5, please adjust the parameter MAX_SKIP in the file skiplist.h (line 4).