LPD-EPFL/ASCYLIB-Go

An attempt to rewrite ASCYLIB (https://github.com/LPD-EPFL/ASCYLIB) in Go

ASCYLIB-Go

ASCYLIB-Go is an endeavor to re-implement ASCYLIB + OPTIK (https://github.com/LPD-EPFL/ASCYLIB) in Go.

Only a few of the concurrent-search data-structures implemented in ASCYLIB have been translated. The philosophy of Go, namely "share memory by communicating; don't communicate by sharing memory", may frown upon such implentation.

ASCYLIB is a set of more than 50 concurrent-search data-structure implementations. OPTIK is a new design pattern for easily implementing fast and scalable concurrent data structures.

• Website : http://lpd.epfl.ch/site/ascylib - http://lpd.epfl.ch/site/optik
• Authors : Vasileios Trigonakis vasileios.trigonakis@epfl.ch, Tudor David tudor.david@epfl.ch
• Related Publications:
  • Optimistic Concurrency with OPTIK, Rachid Guerraoui, Vasileios Trigonakis (alphabetical order), PPoPP 2016 (to appear)
  • Asynchronized Concurrency: The Secret to Scaling Concurrent Search Data Structures, Tudor David, Rachid Guerraoui, Vasileios Trigonakis (alphabetical order), ASPLOS 2015

Algorithms

The following table contains the algorithms translated in ASCYLIB-Go:

#	Name	Type	Year	Reference
	Linked lists
1	Pugh's linked list	lock-based	1990	[P+90]
2	Lazy linked list	lock-based	2006	[HHL+06]
3	Harris linked list with ASCY	lock-free	2015	[DGT+15]
4	OPTIK fine-grained linked list	lock-based	2016	[GT+16]
	Hash Tables
5	Java's ConcurrentHashMap	lock-based	2003	[L+03]
6	Hash table using Java's CopyOnWrite array map	lock-based	2004	[ORACLE+04]
7	Hash table using global-lock OPTIK list	lock-based	2016	[GT+16]
	Skip Lists
8	Sequential skip list	sequential
9	Pugh skip list	lock-based	1990	[P+90]
10	Fraser skip list	lock-free	2003	[F+03]
11	Herlihy et al. skip list	lock-based	2007	[HLL+07]
12	OPTIK skip list using trylocks (default OPTIK skip list)	lock-based	2016	[GT+16]
	Queues
13	Michael and Scott (MS) lock-based queue	lock-based	1996	[MS+96]
14	Michael and Scott (MS) lock-free queue	lock-free	1996	[MS+96]
15	MS queue with OPTIK trylock-version	lock-based	2016	[GT+16]
16	MS queue with OPTIK trylock-version	lock-based	2016	[GT+16]
	Priority Queues
17	Lotan and Shavit priority queue	lock-free	2000	[LS+00]
	Stacks
18	Global-lock stack	lock-based
19	Treiber stack	lock-free	1986	[T+86]

References

• [DGT+15] T. David, R. Guerraoui, and V. Trigonakis. Asynchronized Concurrency: The Secret to Scaling Concurrent Search Data Structures. ASPLOS '15.
• [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.
• [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.
• [HLL+07] M. Herlihy, Y. Lev, V. Luchangco, and N. Shavit. A Simple Optimistic Skiplist Algorithm. SIROCCO '07.
• [L+03] D. Lea. Overview of Package util.concurrent Release 1.3.4. http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html,

• [LS+00] I. Lotan and N. Shavit. Skiplist-based concurrent priority queues. IPDPS '00.
• [MS+96] M. M. Michael and M. L. Scott. Simple, Fast, and Practical Non-blocking and Blocking Concurrent Queue Algorithms. PODC '96.
• [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.

Tests modules

There is a few test modules available. All of them execute a concurrent algorithm following variable parameters.

To get the accepted parameters, issue from src/:

make run NAME=<concurrent algorithm name> TEST=simple ARGS=-h

The default test module, 'simple', is the same as in ASCYLIB (https://github.com/LPD-EPFL/ASCYLIB/blob/master/src/tests/test_simple.c).

The 'ldi' test module performs simple latency measurements, for each operation (find, insert, remove).

The three other ones are to get metrics about the Go runtime while performing the same work as the 'simple' test module. You will need go tool {trace, pprof} version 1.6 or higher to build and use those metrics.

Compilation

Build a test binary

You will need make and go 1.6 or higher to build all test binaries.

To build a test binary (= test code + concurrent algorithm to test), in src/, run:

make build NAME=<concurrent algorithm name> [ TEST=<test module name> ]

The TEST parameter is optional (don't put brackets!). The 'simple' test module is selected by default.

Run a test binary

Still from src/, run:

make run NAME=<concurrent algorithm name> [ TEST=<test module name> ARGS=<arguments to pass>]

Or from bin/, run:

./<concurrent algorithm name>_<test module name>

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.).