/ASCYLIB-Cpp

Porting ASCYLIB to C++

Primary LanguageC++

ASCYLIB(Cpp) + OPTIK

ASCYLIB (with OPTIK) is a concurrent data-structure library. The original C version (found at https://github.com/LPD-EPFL/ASCYLIB) contains over 40 implementations of linked lists, hash tables, skip lists, binary search trees (BSTs), queues, priority queues, and stacks, containing sequential, lock-based, and lock-free implementations for each data structure.

This C++ port, in its current state, contains 27 of those concurrent data structures.

ASCYLIB works on x86, SPARC, and Tilera architectures and contains tests to evaluate the throughput, latency, latency distribution, and energy efficiency of the included data structures.

OPTIK is a new design pattern for easily implementing fast and scalable concurrent data structures. We have merged several concurrent data structures developed with OPTIK in ASCYLIB. More details can be found here: http://lpd.epfl.ch/site/optik.

Algorithms

The following table contains the algorithms (and various implementations of some algorithms) included in ASCYLIB (respecting the original ASCYLIB numbering):

# Name Progress Year Referece
Array Maps
3 OPTIK global-lock array map lock-based 2016 [GT+16]
Linked lists
4 Sequential linked list sequential
5 Hand-over-hand locking linked list lock-based [HS+12]
6 Pugh's linked list lock-based 1990 [P+90]
7 Harris linked list lock-free 2001 [H+01]
9 Lazy linked list lock-based 2006 [HHL+06]
10 Harris linked list with ASCY lock-free 2015 [DGT+15]
12 OPTIK global-lock linked list lock-based 2016 [GT+16]
13 OPTIK fine-grained linked list lock-based 2016 [GT+16]
Hash Tables
18 Hash table using Pugh's list lock-based 1990 [P+90]
19 Hash table using Harris' list lock-free 2001 [H+01]
20 Java's ConcurrentHashMap lock-based 2003 [L+03]
21 Hash table using Java's CopyOnWrite array map lock-based 2004 [ORACLE+04]
26 Hash table using fine-grained OPTIK list lock-based 2016 [GT+16]
27 Hash table using global-lock OPTIK list lock-based 2016 [GT+16]
28 Hash table using OPTIK array map lock-based 2016 [GT+16]
Skip Lists
29 Sequential skip list sequential
31 Fraser skip list lock-free 2003 [F+03]
32 Herlihy et al. skip list lock-based 2007 [HLL+07]
33 Fraser skip list with Herlihy's optimization lock-free 2011 [HLS+11]
35 OPTIK skip list using trylocks (default OPTIK skip list) lock-based 2016 [GT+16]
Queues
45 Michael and Scott (MS) lock-based queue lock-based 1996 [MS+96]
46 Michael and Scott (MS) lock-free queue lock-free 1996 [MS+96]
47 Michael and Scott (MS) hybrid queue lock-based 1996 [MS+96]
Stacks
56 Global-lock stack lock-based
57 Treiber stack lock-free 1986 [T+86]

References

  • [AKL+15] D. Alistarh, J. Kopinsky, J. Li, N. Shavit. The SprayList: A Scalable Relaxed Priority Queue. PPoPP '15.
  • [BCH+10] N. G. Bronson, J. Casper, H. Chafi, and K. Olukotun. A Practical Concurrent Binary Search Tree. PPoPP '10.
  • [DGT+15] T. David, R. Guerraoui, and V. Trigonakis. Asynchronized Concurrency: The Secret to Scaling Concurrent Search Data Structures. ASPLOS '15.
  • [DMS+12] M. Desnoyers, P. E. McKenney, A. S. Stern, M. R. Dagenais, and J. Walpole. User-level implementations of read-copy update. PDS '12.
  • [DVY+14] D. Drachsler, M. Vechev, and E. Yahav. Practical Concurrent Binary Search Trees via Logical Ordering. PPoPP '14.
  • [EFR+10] F. Ellen, P. Fatourou, E. Ruppert, and F. van Breugel. Non-blocking Binary Search Trees. PODC '10.
  • [F+03] K. Fraser. Practical Lock-Freedom. PhD thesis, University of Cambridge, 2004.
  • [GT+16] R. Guerraoui, and V. Trigonakis. Optimistic Concurrency with OPTIK. PPoPP '16.
  • [H+01] T. Harris. A Pragmatic Implementation of Non-blocking Linked Lists. DISC '01.
  • [HHL+06] S. Heller, M. Herlihy, V. Luchangco, M. Moir, W. N. Scherer, and N. Shavit. A Lazy Concurrent List-Based Set Algorithm. OPODIS '05.
  • [HS+12] M. Herlihy and N. Shavit. The Art of Multiprocessor Programming, Revised First Edition.
  • [LS+00] I. Lotan and N. Shavit. Skiplist-based concurrent priority queues. IPDPS '00.
  • [M+02] M. M. Michael. High Performance Dynamic Lock-free Hash tables and List-based Sets. SPAA '02.
  • [MS+96] M. M. Michael and M. L. Scott. Simple, Fast, and Practical Non-blocking and Blocking Concurrent Queue Algorithms. PODC '96.
  • [NM+14] A. Natarajan and N. Mittal. Fast Concurrent Lock-free Binary Search Trees. PPoPP '14.
  • [ORACLE+04] Oracle. Java CopyOnWriteArrayList. http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/CopyOnWriteArrayList.html.
  • [P+90] W. Pugh. Concurrent Maintenance of Skip Lists. Technical report, 1990.
  • [T+86] R. Treiber. Systems Programming: Coping with Parallelism. Technical report, 1986.

Compilation

ASCYLIB requires the ssmem memory allocator (https://github.com/LPD-EPFL/ssmem). We have already compiled and included ssmem in external/lib for x86_64, SPARC, and the Tilera architectures. Still, if you would like to create your own build of ssmem, take the following steps. Clone ssmem, do make libssmem.a and then copy libssmem.a in ASCYLIB/external/lib and smmem.h in ASCYLIB-Cpp/external/include.

Additionally, the sspfd profiler library is required (https://github.com/trigonak/sspfd). We have already compiled and included sspfd in external/lib for x86_64, SPARC, and the Tilera architectures. Still, if you would like to create your own build of sspfd, take the following steps. Clone sspfd, do make and then copy libsspfd.a in ASCYLIB-Cpp/external/lib and sspfd.h in ASCYLIB-Cpp/external/include.

Finally, to measure power on new Intel processors (e.g., Intel Ivy Bridge), the raplread library is required (https://github.com/LPD-EPFL/raplread). We have already compiled and included raplread in external/lib. Still, if you would like to create your own build of raplread, take the following steps. Clone raplread, do make and then copy libraplread.a in ASCYLIB-Cpp/external/lib and sspfd.h in ASCYLIB-Cpp/external/include.

To build all data structures, you can execute make. This target builds all lock-free, lock-based, and sequential data structures.

ASCYLIB includes a default configuration that uses g++ and tries to infer the number of cores and the frequency of the target/build platform. If this configuration is incorrect, you can always create a manual configurations in common/Makefile.common and include/utils.h (look in these files for examples). If you do not care about pinning threads to cores, these settings do not matter. You can compile with make SET_CPU=0 ... to disable thread pinning.

ASCYLIB accepts various compilation parameters. Please refer to the COMPILE file.

Adding an algorithm

To add an algorithm, preferably implement (inherit from) one of the interfaces/abstract classes relevant to the data structure you are implementing (src/search.h or src/stack_queue.h). We also recommend you add it to:

  1. The relevant test file (src/test_search.cc or src/test_stackqueue.cc). This means adding the algorithm to:
  • The head of the file, including the relevant source header (algorithm.h)
  • The algorithms enum near the head of the file.
  • The parse_algorithm function starting around line 123, which will parse the algorithm quick name from the command line option (-a).
  • The list of algorithms in the help description, around line 550.
  • The actual initialization of the appropriate data structure, starting around line 655.

  1. The Makefile at the root of the project, either under SEARCH_ALGORITHMS or STACKQUEUE_ALGORITHMS. Add the name of the .h file without the extension, as it will be added later. This ensures that a modification of your file causes recompilation of the test file.

  2. Don't forget to include any aux files (extra classes, or other types of data nodes) you may create to this file as well, to also ensure that the test files are recompiled if they change.

Tests

This version of ASCYLIB, unlike the C implementation, has 2 single test files.

One is for search data structures, and one is for stack/queue data structures. You can find & execute either one in the bin directory. Run ./bin/test_search -h or ./bin/test_stackqueue -h for help on the parameters (selecting the algorithm, workload, etc.)

Scripts

ASCYLIB includes tons of usefull scripts (in the scripts folders). Some particularly useful ones are:

  • scalability.sh and scalability_rep.sh: run the given list of executable on the given (list of) number of threads, with the given parameters, and report throughput and scalability over single-threaded execution.
  • scripts in apslos/ directory: they were used to create the plots for the ASPLOS '15 paper. In particular, apslos/run_scy.sh accepts configuration files (see asplos/config) so it can be configured to execute almost any per-data-structure scenario.
  • scripts in ppopp/ directory: they were used to create the plots for the PPoPP '16 paper. In particular, ppopp/run_and_plot.sh can run and plot graphs for all the tests in the paper.

Bear in mind that these scripts were written for the C version. Some of them have been adapted (scalability_rep_simple.sh and also several of the run_**.sh files inside the ppopp directory. This should be helpful to illustrate how the change is made to run the C++ test files instead of the C ones.

Thanks

Some of the initial implementations used in ASCYLIB were taken from Synchrobench (https://github.com/gramoli/synchrobench - V. Gramoli. More than You Ever Wanted to Know about Synchronization. PPoPP 2015.).