C++ implementation of LLX/SCX

Code (scx_provider.h)

A full implementation of LLX/SCX can be found in this bitbucket repo located at common/scx_provider.h. Rough usage instructions appear at the top of this header.

Example of its usage in a data structure

A fast data structure (a relaxed (a,b)-tree) that uses it can be found in ds/brown_ext_abtree_lf.

Running the example data structure in a microbenchmark

A microbenchmark appears in microbench/. Compile with make -j n, where n is the number of threads on your system.

Run with, e.g., "LD_PRELOAD=../lib/libjemalloc-5.0.1-25.so bin/brown_ext_abtree_lf.ubench_rdebra -i 10 -d 10 -rq 0 -rqsize 100 -k 1000000 -nrq 0 -nwork 36 -t 1000 -nprefill 36". (Parameters: -nwork is the number of threads, -k is the size of the key range, -i and -d are % insertions/deletions, -t is millis to run, -nprefill is the number of threads that will perform prefilling on the data structure. Just ignore -rq, -rqsize and -nrq. You can optionally pin threads to logical processors, in a specific order, by specifying, e.g., "-pin 0-17,72-89,18-35,90-107,36-53,108-125,54-71,126-143".)

Note that we use LD_PRELOAD to load jemalloc, since otherwise allocation isn't scalable. I've included the .so file for linux/x64. (On other systems, you should build jemalloc or use whatever scalable allocator you like.)

Memory reclamation is done with DEBRA, an efficient EBR algorithm. A few variants of DEBRA, as well as a no-reclamation variant, may also be compiled, depending on the contents of the Makefile (binaries: *.ubench_rdebra,*.ubench_rdebracap, *.ubench_rnone). Several other data structures are likely also compiled. Ignore macrobench.

Adding LLX/SCX (scx_provider.h) to your own project

The easiest way to use LLX/SCX in your own project is to copy the common folder into your project, and add it and its subfolders to your include path, then follow the usage instructions in scx_provider.h, or follow the example in ds/brown_ext_abtree_lf/*.h.

If you want to import only the minimal required code into your project, I believe you can copy just: common/plaf.h, common/scx_provider.h, common/descriptors/descriptors.h and common/descriptors/descriptors_impl.h (fixing includes / include paths as necessary to allow the headers to find each other).

Making things faster

Disable asserts by compiling with -DNDEBUG.