# verlib

**Repository Path**: spearNeil/verlib

## Basic Information

- **Project Name**: verlib
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: MIT
- **Default Branch**: main
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2024-05-24
- **Last Updated**: 2024-05-24

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# VERLIB: Concurrent Versioned Pointers

VERLIB is a C++ library supporting multiversioned pointers and lock-free locks as described in the paper:

VERLIB: Concurrent Versioned Pointers
Guy Blelloch and Yuanhao Wei
ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP 2024)


## Setting up and compiling
```
    python3 run_tests.py  # run sanity checks
```
  - All the binaries are already pre-compiled, but you can re-compile by running ```make clean``` inside the build directory and then running ```bash compile_all.sh``` in the top level directory
  - Expected output for the sanity checks can be found in: run_tests_expected_output.txt

## Running experiments and generating graphs
  - To reproduce all the graphs in the paper, run ```bash generate_graphs_from_paper.sh```
    - this command will take ~4 hours to run
  - The output graphs will be stored in the ```build/benchmark/verlib/graphs/``` directory and can be viewed by copying the directory out of the container using ```docker cp```
  - You can rerun a specific graph by running the corresponding command from the 
    generate_graphs_from_paper.sh file. Each command generates a single figure.
  - You can also run custom experiments (and generate graphs for them) using the following scripts from the ```build/benchmark/verlib/``` directory: 

```
    python3 run_optimization_experiments.py -u [update percent] -ls [list size] -s [tree/hashtable size] -z [zipfian parameter] -mf [multi-find size] -p [threads] -f [graph file name] -r [repeats] -t [runtime]
    python3 run_scalability_experiments.py ... [same as above]
    python3 run_size_experiments.py ... [same as above]
    python3 run_timestamp_experiments.py ... [same as above]
    python3 run_update_experiments.py ... [same as above]
    python3 run_zipf_experiments.py ... [same as above]
```
  - You can generate graphs similar to Figure 9 using the following script from the ```rqsize_benchmark``` directory:

```
    python3 run_rqsize_experiments.py [data structure size] [num update threads] [num range query threads] [list of range query sizes] ../build/benchmark/verlib/graphs/[graph file name] [repeats] [runtime] [JVM memory size, 50G recommended but lower works as well]
```

  - See generate_graphs_from_paper.sh for examples of how to use the above scripts and to see which figure each script corresponds to.
  - Parameter description: 
    - -p: number of threads
    - -s: initial size of tree/hashtable data structures
    - -ls: initial size of list data structures
    - -mf: number of keys to look up in a multi-find operation
    - -z: Zipfian parameter, number between [0, 1)
    - -u: percentage of updates, number between 0 and 100
    - -f: graph file name
    - -r: number of times to repeat each experiment
    - -t: runtime for each experiment (measured in seconds)
    - In some scripts, the parameter that gets varied expects a list of numbers as input (e.g. [1,2,3,4] with no spaces).



## List of claims from the paper supported by the artifact
  - Given a machine with ~128 logical cores, the graphs generated should be very similar to the ones reported in our paper
  - For machines with different numbers of cores, we recommend using the following settings to reproduce the general shape of our graphs:
    - Let X be the number of logical cores on your machine
    - experiments with 127 threads should be run with X-1 threads
    - scalability experiments should be run with [1, X/2, X, 1.5\*X, 2.5\*X, 3\*X] threads