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