Project

Profile

Help

Statistics
| Revision:
How to connect?

root

Name Size Revision Age Author Comment
  build 10 about 6 years Evgeny Kalishenko Merged with latest trunk version from the maste...
  cds 11 about 6 years Evgeny Kalishenko Build fix of Harris list: forgotten includes!
  doxygen 1 over 6 years Svyatoslav Vlasov origin version
  projects 10 about 6 years Evgeny Kalishenko Merged with latest trunk version from the maste...
  scripts 1 over 6 years Svyatoslav Vlasov origin version
  src 1 over 6 years Svyatoslav Vlasov origin version
  tests 10 about 6 years Evgeny Kalishenko Merged with latest trunk version from the maste...
.cproject 17.6 KB 11 about 6 years Evgeny Kalishenko Build fix of Harris list: forgotten includes!
.project 817 Bytes 9 about 6 years Evgeny Kalishenko Added eclipse project
brush_cds.pl 1.1 KB 1 over 6 years Svyatoslav Vlasov origin version
change.log 13.1 KB 10 about 6 years Evgeny Kalishenko Merged with latest trunk version from the maste...
libcds.v12.suo 33.5 KB 1 over 6 years Svyatoslav Vlasov origin version
license.txt 1.31 KB 1 over 6 years Svyatoslav Vlasov origin version
make_distrib.pl 4.25 KB 1 over 6 years Svyatoslav Vlasov origin version
make_docs.bat 155 Bytes 1 over 6 years Svyatoslav Vlasov origin version
readme 7.42 KB 1 over 6 years Svyatoslav Vlasov origin version

CDS (Concurrent Data Structures) C++ library

CDS library is (mostly) header-only template library. The shared library contains only garbage collector's core implementation.
CDS contains implementation of some well-known lock-free and fine-grained data structures:

Stack:
TreiberStack
[1986] R. K. Treiber. Systems programming: Coping with parallelism. Technical Report RJ 5118, IBM Almaden Research Center, April 1986.
Elimination back-off implementation is based on idea from
[2004] Danny Hendler, Nir Shavit, Lena Yerushalmi "A Scalable Lock-free Stack Algorithm"

Queue:
BasketQueue
[2007] Moshe Hoffman, Ori Shalev, Nir Shavit "The Baskets Queue"
MSQueue
[1998] Maged Michael, Michael Scott "Simple, fast, and practical non-blocking and blocking concurrent queue algorithms"
[2002] Maged M.Michael "Safe memory reclamation for dynamic lock-free objects using atomic reads and writes"
[2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects"
RWQueue
[1998] Maged Michael, Michael Scott "Simple, fast, and practical non-blocking and blocking concurrent queue algorithms"
MoirQueue
[2000] Simon Doherty, Lindsay Groves, Victor Luchangco, Mark Moir "Formal Verification of a practical lock-free queue algorithm"
OptimisticQueue
[2008] Edya Ladan-Mozes, Nir Shavit "An Optimistic Approach to Lock-Free FIFO Queues"
SegmentedQueue
[2010] Afek, Korland, Yanovsky "Quasi-Linearizability: relaxed consistency for improved concurrency"
TsigasCycleQueue
[2000] Philippas Tsigas, Yi Zhang "A Simple, Fast and Scalable Non-Blocking Concurrent FIFO Queue for Shared Memory Multiprocessor Systems"
VyukovMPMCCycleQueue
Dmitry Vyukov (see http://www.1024cores.net)

Deque:
MichaelDeque
[2003] Maged Michael "CAS-based Lock-free Algorithm for Shared Deque"

Map, set:
MichaelHashMap
[2002] Maged Michael "High performance dynamic lock-free hash tables and list-based sets"
SplitOrderedList
[2003] Ori Shalev, Nir Shavit "Split-Ordered Lists - Lock-free Resizable Hash Tables"
StripedMap, StripedSet
[2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming"
CuckooMap, CuckooSet
[2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming"
SkipListMap, SkipListSet
[2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming"

Ordered single-linked list (buckets for the map):
LazyList
[2005] Steve Heller, Maurice Herlihy, Victor Luchangco, Mark Moir, William N. Scherer III, and Nir Shavit "A Lazy Concurrent List-Based Set Algorithm"
MichaelList
[2002] Maged Michael "High performance dynamic lock-free hash tables and list-based sets"

Priority queue:
MSPriorityQueue
[1996] G.Hunt, M.Michael, S. Parthasarathy, M.Scott "An efficient algorithm for concurrent priority queue heaps"

Tree:
EllenBinTree
[2010] F.Ellen, P.Fatourou, E.Ruppert, F.van Breugel "Non-blocking Binary Search Tree"

Garbage collection:
Hazard Pointers
[2002] Maged M.Michael "Safe memory reclamation for dynamic lock-freeobjects using atomic reads and writes"
[2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects"
[2004] Andrei Alexandrescy, Maged Michael "Lock-free Data Structures with Hazard Pointers"
Hazard pointers with reference counting
[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
[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 ? 242, Springer-Verlag, 2005
Pass-the-Buck
[2002] M. Herlihy, V. Luchangco, and M. Moir. The repeat offender problem: A mechanism for supporting
dynamic-sized lockfree data structures. Technical Report TR-2002-112, Sun Microsystems Laboratories, 2002
[2002] M. Herlihy, V. Luchangco, P. Martin, and M. Moir. Dynamic-sized Lockfree Data Structures.
Technical Report TR-2002-110, Sun Microsystems Laboratories, 2002
[2005] M. Herlihy, V. Luchangco, P. Martin, and M. Moir. Nonblocking Memory Management Support
for Dynamic_Sized Data Structures. ACM Transactions on Computer Systems, Vol.23, No.2, May 2005
User-space RCU
[2009] M.Desnoyers "Low-Impact Operating System Tracing" PhD Thesis,
Chapter 6 "User-Level Implementations of Read-Copy Update"
[2011] M.Desnoyers, P.McKenney, A.Stern, M.Dagenias, J.Walpole "User-Level
Implementations of Read-Copy Update"

Memory allocation:
[2004] M.Michael "Scalable Lock-free Dynamic Memory Allocation"

Common approach:
[2010] Hendler, Incze, Shavit and Tzafrir "Flat Combining and
the Synchronization-Parallelism Tradeoff"

Supported platforms and compilers
---------------------------------

GCC: 4.3 and above
MS Visual C++: 9 (2008) and above
Clang: 3.0 and above

The library was tested on following server platforms:
GNU GCC 4.3.3:
x86 RedHat Linux 4.0, 5.0
amd64 (x86-64) RedHat Linux 4.0, 5.0
ia64 (itanium) RedHat Linux 4.0
ia64 (itanium) HP-UX 11.23 and HP-UX 11.31
sparc (ultrasparc-IV and Niagara) Sun Solaris 2.10

also tested by GCC 4.4+ on amd64 Ubuntu 12.04, amd64 FreeBSD 8.1, Mac OS X

Microsoft Visual C++ 2008 :
x86 Windows7
amd64 (x86-64) Windows7

Clang:
amd64 Linux Ubuntu 12.04

How to build
------------

The CDS library is depend on boost header-only libraries (tested with boost 1.47 and later).
The regression tests in tests directory also depends on boost_thread dynamic library.
You should build boost_thread library before building CDS test.

Windows
Use Visual C++ 2008 solution projects\Win\vc9\cds.sln.
The solution depends on BOOST_PATH environment variable that contains the path to boost root directory.
The CDS tests also depends on boost_thread library in %BOOST_PATH%\stage\lib or %BOOST_PATH%\bin.

Unix
GCC compiler supported (4.3 and above) and Clang 3.0 and above for Linux
Use script build/build.sh that builds release and debug libcds.so and tests executable. Please,
do not try to call 'make' directly, - build.sh script sets necessary vars for make.
See examples in build/sample directory.

build.sh main options:
-x compiler C++ compiler name (g++, gcc, clang; default g++)
-p arch Processor architecture. Possible values are: x86, amd64, x86_64, sparc, ia64
-o os_family OS family. Possible values are: linux, sunos, solaris, hpux
-b bits Bits to build (32 or 64)
-l options Extra linker options
-x options Extra compiler options
--with-boost path Path to boost root
--clean Clean all before building

For more options use build.sh -h

Warnings
GCC: compile CDS library and all projects that depends on libcds with -fno-strict-aliasing flag!

Test suite
----------
Note the duration of full test set is up to 24 hours (depending on your hardware and test configuration)