[libcds.git] / readme
1 CDS (Concurrent Data Structures) C++ library\r
2 \r
3 CDS library is (mostly) header-only template library. The shared library contains only garbage collector's core implementation.\r
4 Download the latest release from\r
5 \r
6 The library contains implementation of some well-known lock-free and fine-grained data structures:\r
7 \r
8 Stack:\r
9     TreiberStack\r
10         [1986] R. K. Treiber. Systems programming: Coping with parallelism. Technical Report RJ 5118, IBM Almaden Research Center, April 1986.\r
11     Elimination back-off implementation is based on idea from\r
12         [2004] Danny Hendler, Nir Shavit, Lena Yerushalmi "A Scalable Lock-free Stack Algorithm"\r
13         \r
14 Queue:\r
15     BasketQueue\r
16         [2007] Moshe Hoffman, Ori Shalev, Nir Shavit "The Baskets Queue"\r
17     MSQueue\r
18         [1998] Maged Michael, Michael Scott "Simple, fast, and practical non-blocking and blocking concurrent queue algorithms"\r
19         [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-free objects using atomic reads and writes"\r
20         [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects"\r
21     RWQueue\r
22         [1998] Maged Michael, Michael Scott "Simple, fast, and practical non-blocking and blocking concurrent queue algorithms"\r
23     MoirQueue\r
24         [2000] Simon Doherty, Lindsay Groves, Victor Luchangco, Mark Moir "Formal Verification of a practical lock-free queue algorithm"\r
25     OptimisticQueue\r
26         [2008] Edya Ladan-Mozes, Nir Shavit "An Optimistic Approach to Lock-Free FIFO Queues"\r
27     SegmentedQueue\r
28         [2010] Afek, Korland, Yanovsky "Quasi-Linearizability: relaxed consistency for improved concurrency"\r
29     TsigasCycleQueue\r
30         [2000] Philippas Tsigas, Yi Zhang "A Simple, Fast and Scalable Non-Blocking Concurrent FIFO Queue for Shared Memory Multiprocessor Systems"\r
31     VyukovMPMCCycleQueue\r
32         Dmitry Vyukov (see\r
33 \r
34 Deque:\r
35     MichaelDeque\r
36         [2003] Maged Michael "CAS-based Lock-free Algorithm for Shared Deque"\r
37 \r
38 Map, set:\r
39     MichaelHashMap\r
40         [2002] Maged Michael "High performance dynamic lock-free hash tables and list-based sets"\r
41     SplitOrderedList\r
42         [2003] Ori Shalev, Nir Shavit "Split-Ordered Lists - Lock-free Resizable Hash Tables"\r
43     StripedMap, StripedSet\r
44         [2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming"\r
45     CuckooMap, CuckooSet\r
46         [2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming"\r
47     SkipListMap, SkipListSet\r
48         [2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming"\r
49         \r
50 Ordered single-linked list (buckets for the map):\r
51     LazyList\r
52         [2005] Steve Heller, Maurice Herlihy, Victor Luchangco, Mark Moir, William N. Scherer III, and Nir Shavit "A Lazy Concurrent List-Based Set Algorithm"\r
53     MichaelList\r
54         [2002] Maged Michael "High performance dynamic lock-free hash tables and list-based sets"\r
55 \r
56 Priority queue:\r
57     MSPriorityQueue\r
58         [1996] G.Hunt, M.Michael, S. Parthasarathy, M.Scott "An efficient algorithm for concurrent priority queue heaps"\r
59 \r
60 Tree:\r
61     EllenBinTree\r
62         [2010] F.Ellen, P.Fatourou, E.Ruppert, F.van Breugel "Non-blocking Binary Search Tree"\r
63 \r
64 Garbage collection:\r
65     Hazard Pointers\r
66         [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-freeobjects using atomic reads and writes"\r
67         [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects"\r
68         [2004] Andrei Alexandrescy, Maged Michael "Lock-free Data Structures with Hazard Pointers"\r
69     Hazard pointers with reference counting\r
70         [2006] A.Gidenstam "Algorithms for synchronization and consistency in concurrent system services", Chapter 5 "Lock-Free Memory Reclamation" Thesis for the degree of Doctor     of Philosophy \r
71         [2005] Anders Gidenstam, Marina Papatriantafilou and Philippas Tsigas "Allocating memory in a lock-free manner", Proceedings of the 13th Annual European Symposium on Algorithms (ESA 2005), Lecture Notes in Computer Science Vol. 3669, pages 229 \96 242, Springer-Verlag, 2005\r
72     Pass-the-Buck\r
73         [2002] M. Herlihy, V. Luchangco, and M. Moir. The repeat offender problem: A mechanism for supporting\r
74                dynamic-sized lockfree data structures. Technical Report TR-2002-112, Sun Microsystems Laboratories, 2002\r
75         [2002] M. Herlihy, V. Luchangco, P. Martin, and M. Moir. Dynamic-sized Lockfree Data Structures. \r
76                Technical Report TR-2002-110, Sun Microsystems Laboratories, 2002\r
77         [2005] M. Herlihy, V. Luchangco, P. Martin, and M. Moir. Nonblocking Memory Management Support\r
78                for Dynamic_Sized Data Structures. ACM Transactions on Computer Systems, Vol.23, No.2, May 2005\r
79     User-space RCU\r
80         [2009] M.Desnoyers "Low-Impact Operating System Tracing" PhD Thesis,\r
81                Chapter 6 "User-Level Implementations of Read-Copy Update"\r
82         [2011] M.Desnoyers, P.McKenney, A.Stern, M.Dagenias, J.Walpole "User-Level\r
83                Implementations of Read-Copy Update"\r
84 \r
85 Memory allocation:\r
86     [2004] M.Michael "Scalable Lock-free Dynamic Memory Allocation"\r
87 \r
88 Common approach:\r
89     [2010] Hendler, Incze, Shavit and Tzafrir "Flat Combining and \r
90            the Synchronization-Parallelism Tradeoff"\r
91     \r
92 Supported compilers\r
93 ---------------------------------\r
94 \r
95 GCC: 4.8 and above\r
96 MS Visual C++: 12 (2013) and above\r
97 Clang: 3.3 and above\r
98 \r
99 How to build\r
100 ------------\r
101 \r
102 The CDS library is depend on boost header-only libraries (tested with boost 1.47 and later). \r
103 The regression tests in tests directory also depends on boost_thread dynamic library. \r
104 You should build boost_thread library before building CDS test.\r
105 \r
106 Windows\r
107     Use Visual C++ 2013 solution projects\Win\vc12\cds.sln.\r
108     The solution depends on BOOST_PATH environment variable that contains the path to boost root directory. \r
109     The CDS tests also depends on boost_thread library in %BOOST_PATH%\stage\lib or %BOOST_PATH%\bin.\r
110 \r
111 Unix \r
112     GCC compiler supported (4.8 and above) and Clang 3.3 and above for Linux\r
113     Use script build/ that builds release and debug and tests executable. Please,\r
114     do not try to call 'make' directly, - script sets necessary vars for make.\r
115     See examples in build/sample directory.\r
116 \r
117 main options:\r
118     -x compiler     C++ compiler name (g++, gcc, clang; default g++)\r
119     -p arch         Processor architecture. Possible values are:  x86, amd64, x86_64, sparc, ia64\r
120     -o os_family    OS family. Possible values are: linux, sunos, solaris, hpux\r
121     -b bits         Bits to build (32 or 64)\r
122     -l options      Extra linker options\r
123     -x options      Extra compiler options\r
124     --with-boost path   Path to boost root\r
125     --clean         Clean all before building\r
126 \r
127     For more options use -h\r
128 \r
129 Warnings\r
130     GCC: compile CDS library and all projects that depends on libcds with -fno-strict-aliasing flag!\r
131     \r
132 Test suite\r
133 ----------\r
134     Note the duration of full test set is up to 24 hours (depending on your hardware and test configuration)\r