This is an experiment aimed at building a tool that when given a list of ints will build a shared library with a function is_in_set(int) that tests whether a given int is a member of that list.

After correctness, the performance of is_in_set is the most important thing, while keeping within reasonable bounds the size of the shared library, the amount of memory it uses when dl_open'd, and the time it takes to generate a new one.

Developed on x86-64 Linux, but should work on other platforms and OSs. Notably, a previous version was made to work on winNT.

To test:

    make tester_pgo

and then

    make compare size=1000

or

    make benchmark_data.txt seq='\`seq 100 100 1000\`'

One can try

    make compare size=1000 CC=clang

to use clang. Help on using PGO with clang is appreciated.

    make compare size=1000 CC=icc

uses the Intel compiler.

Some of the implementations are silly. If you only want to run the interesting ones, do

    make compare IMPLS_BENCH="skiplist hopscotch" size=1000

The data structure used in "skiplist" is my own invention, in the sense that I came up with it by myself without seeing it a textbook, class, paper, other people's code, etc.
I have not performed any search to see if I am the first to implement it or whether someone has patented it.
It can be significantly faster than binary search while taking the same amount of space for the data.
Performance depends on compiler and processor, obviously. Notably, I am currently generating different variants of the code for gcc, clang and icc.

The "hash" implementation is compact in size for data and code, and fast. Hopscotch is less compact but faster.

Both hash and hopscotch use my own code to generate a fast and good hash function (given that all the keys are known in advance). That code can be slow in pathological cases.

Makefile has some processor-specific flags and readonly_set_cfg.h has a #define for the length of a cacheline (for skiplist). Adjust accordingly.