Skip to content

vigna/sux

Repository files navigation

Sux 1.0.3

Welcome to the C++ part of the Sux project.

Available classes

The classes we provide fall into three categories:

All classes are heavily asserted. For testing speed, remember to use -DNDEBUG.

Documentation can be generated by running doxygen.

All provided classes are templates, so you just have to copy the files in the sux directory somewhere in your include path.

Benchmarks

The commands make ranksel, make recsplit, make fenwick and make dynranksek will generate binaries in bin with which you can test the speed of RecSplit, rank/select static structures, compact Fenwick trees and dynamic rank/select structures. Note that you can set the make variable LEAF to change the leaf size of RecSplit, as in make recsplit LEAF=4, and the variable ALLOC_TYPE to the possible values of sux::util::AllocType to experiment, for example, with transparent huge pages on Linux.

For ranking and selection, we generate one binary for each type of structure, with some variation on parameters (see the makefile for more details). Beside the number of bits, you can provide one or two probabilities. Bits will be set to one with the given probability in the first half of the test array, and with the second probability in the second half (if no second probability is specified, it is assumed to be equal to the first one). This setup is necessary to show the slow behaviour of naive implementations on half-almost-empty-half-almost-full arrays.

For RecSplit, we provide dump/load binaries which dump on disk a minimal perfect hash function, and test it. The standard version uses a keys file for the keys, whereas the “128” version uses 128-bit random keys. We suggest the latter for benchmarking as in any case the first step in RecSplit construction is mapping to 128-bit hashes.

Licensing

Sux is licensed exactly like libstdc++ (GPLv3 + GCC Runtime Library Exception), which essentially means you can use it everywhere, exactly like libstdc++.

seba (mailto:sebastiano.vigna@unimi.it)