Convert Figma logo to code with AI

khizmax logolibcds

A C++ library of Concurrent Data Structures

2,546
358
2,546
51
View on GitHub

Top Related Projects

cameron314's avatar

concurrentqueue

9,815

A fast multi-producer, multi-consumer lock-free concurrent queue for C++11

facebook's avatar

folly

28,056

An open-source C++ library developed and used at Facebook.

rigtorp's avatar

MPMCQueue

1,174

A bounded multi-producer multi-consumer concurrent queue written in C++11

preshing's avatar

junction

1,399

Concurrent data structures in C++

Quick Overview

libcds is a C++ library of concurrent data structures and synchronization primitives. It provides a collection of lock-free and fine-grained lock-based containers and algorithms designed for concurrent programming in multi-threaded environments. The library aims to improve performance and scalability in multi-core systems.

Pros

  • Offers a wide range of concurrent data structures, including queues, stacks, maps, and sets
  • Implements both lock-free and fine-grained locking algorithms for better performance
  • Provides thorough documentation and examples for each data structure
  • Supports modern C++ standards (C++11 and later)

Cons

  • Steep learning curve for developers unfamiliar with concurrent programming concepts
  • May require careful consideration of memory management and ABA problem mitigation
  • Limited support for older C++ standards (pre-C++11)
  • Some data structures may have higher memory overhead compared to their non-concurrent counterparts

Code Examples

Example 1: Using a lock-free queue

#include <cds/container/msqueue.h>
#include <cds/gc/hp.h>

cds::Initialize();
{
    // Declare Hazard Pointer GC
    cds::gc::HP hpGC;

    // Declare a lock-free queue
    typedef cds::container::MSQueue<cds::gc::HP, int> Queue;
    Queue queue;

    // Enqueue and dequeue operations
    queue.enqueue(42);
    int value;
    if (queue.dequeue(value)) {
        std::cout << "Dequeued: " << value << std::endl;
    }
}
cds::Terminate();

Example 2: Using a lock-free map

#include <cds/container/feldman_hashmap_hp.h>
#include <cds/gc/hp.h>

cds::Initialize();
{
    // Declare Hazard Pointer GC
    cds::gc::HP hpGC;

    // Declare a lock-free map
    typedef cds::container::FeldmanHashMap<cds::gc::HP, int, std::string> Map;
    Map map;

    // Insert and find operations
    map.insert(1, "one");
    Map::guarded_ptr gp = map.get(1);
    if (gp) {
        std::cout << "Found: " << *gp << std::endl;
    }
}
cds::Terminate();

Example 3: Using a fine-grained lock-based set

#include <cds/container/striped_set/std_list.h>
#include <cds/container/striped_set.h>

cds::Initialize();
{
    // Declare a fine-grained lock-based set
    typedef cds::container::StripedSet<
        std::list<int>,
        cds::container::striped_set::make_traits<
            cds::opt::less< std::less<int> >
        >::type
    > StripedSet;
    StripedSet set;

    // Insert and erase operations
    set.insert(10);
    set.insert(20);
    set.erase(10);
}
cds::Terminate();

Getting Started

To use libcds in your project:

  1. Clone the repository: git clone https://github.com/khizmax/libcds.git
  2. Build the library: 
    cd libcds
mkdir build && cd build
cmake ..
make
sudo make install
  3. Include the necessary headers in your C++ file
  4. Link against the libcds library when compiling your project
  5. Initialize the library with cds::Initialize() at the beginning of your program
  6. Terminate the library with cds::Terminate() at the end of your program

Remember to compile your project with C++11 or later standard support (e.g., -std=c++11).

Competitor Comparisons

cameron314 logo

concurrentqueue

9,815

A fast multi-producer, multi-consumer lock-free concurrent queue for C++11

Pros of concurrentqueue

  • Simpler API, focusing solely on concurrent queues
  • Faster performance for single-producer/single-consumer scenarios
  • Header-only library, easier to integrate into projects

Cons of concurrentqueue

  • Limited to queue data structures only
  • Fewer features compared to libcds's comprehensive collection
  • Less flexibility for complex concurrent data structure needs

Code Comparison

concurrentqueue:

moodycamel::ConcurrentQueue<int> q;
q.enqueue(42);
int item;
bool success = q.try_dequeue(item);

libcds:

cds::container::MSQueue<cds::gc::HP, int> q;
q.push(42);
int item;
bool success = q.pop(item);

Summary

concurrentqueue is a specialized library focusing on high-performance concurrent queues, offering a simpler API and easier integration. It excels in specific use cases but lacks the broader range of data structures provided by libcds.

libcds offers a comprehensive collection of concurrent data structures, including queues, sets, and maps. It provides more flexibility for complex concurrent programming needs but may have a steeper learning curve and slightly lower performance in some scenarios.

Choose concurrentqueue for projects primarily needing efficient concurrent queues, and libcds for more diverse concurrent data structure requirements.

facebook logo

folly

28,056

An open-source C++ library developed and used at Facebook.

Pros of Folly

  • Broader scope with a comprehensive collection of C++ components
  • Backed by Facebook, with extensive real-world usage and testing
  • Active development and frequent updates

Cons of Folly

  • Larger codebase, potentially more complex to integrate
  • May include unnecessary components for specific use cases
  • Higher learning curve due to its extensive feature set

Code Comparison

libcds (lock-free queue):

cds::container::MSQueue<cds::gc::HP, int> queue;
queue.push(42);
int value;
if (queue.pop(value)) {
    // Use value
}

Folly (lock-free queue):

folly::MPMCQueue<int> queue(100);
queue.write(42);
int value;
if (queue.read(value)) {
    // Use value
}

Both libraries provide lock-free data structures, but Folly offers a wider range of utilities beyond concurrent containers. libcds focuses specifically on concurrent data structures, while Folly includes various components for different aspects of C++ development.

Folly is more suitable for large-scale projects requiring diverse C++ utilities, whereas libcds is ideal for projects primarily needing efficient concurrent data structures with a smaller footprint.

rigtorp logo

MPMCQueue

1,174

A bounded multi-producer multi-consumer concurrent queue written in C++11

Pros of MPMCQueue

  • Simpler and more focused implementation, specifically for multi-producer multi-consumer queues
  • Potentially lower memory footprint due to its specialized nature
  • Easier to integrate into existing projects due to its single-header design

Cons of MPMCQueue

  • Limited to MPMC queue functionality, while libcds offers a broader range of concurrent data structures
  • May lack some of the advanced features and optimizations present in libcds
  • Less actively maintained compared to libcds (fewer recent updates and contributions)

Code Comparison

MPMCQueue usage:

MPMCQueue<int> q(100);
q.push(42);
int value;
q.pop(value);

libcds usage (similar functionality):

cds::container::MSQueue<cds::gc::HP, int> q;
q.enqueue(42);
int value;
q.dequeue(value);

Both libraries provide thread-safe queue implementations, but libcds offers a wider variety of concurrent data structures and memory reclamation schemes. MPMCQueue focuses solely on providing an efficient MPMC queue implementation, which may be preferable for projects with specific requirements or those seeking a lightweight solution.

preshing logo

junction

1,399

Concurrent data structures in C++

Pros of Junction

  • Simpler API and easier to use for basic concurrent data structures
  • Better documentation and examples for getting started quickly
  • More focused on high-performance concurrent hash tables

Cons of Junction

  • Less comprehensive set of data structures compared to libcds
  • Not as actively maintained (last commit was in 2019)
  • Fewer advanced features and customization options

Code Comparison

Junction:

junction::ConcurrentMap_Linear<int, std::string> map;
map.assign(1, "one");
std::string value;
if (map.find(1, value)) {
    std::cout << value << std::endl;
}

libcds:

cds::container::FeldmanHashMap<cds::gc::HP, int, std::string> map;
map.insert(1, "one");
auto result = map.find(1);
if (result) {
    std::cout << result->second << std::endl;
}

Both libraries provide concurrent data structures, but libcds offers a wider range of options and more advanced features. Junction focuses on simplicity and ease of use, particularly for concurrent hash tables. libcds is more actively maintained and provides a broader set of concurrent data structures, making it suitable for more complex concurrent programming scenarios.

Convert Figma logo designs to code with AI

Visual Copilot

Introducing Visual Copilot: A new AI model to turn Figma designs to high quality code using your components.

Try Visual Copilot

README

!!! STOP WAR !!!

CDS C++ library

Codacy Badge GitHub version License Build Status Build status

The Concurrent Data Structures (CDS) library is a collection of concurrent containers that don't require external (manual) synchronization for shared access, and safe memory reclamation (SMR) algorithms like Hazard Pointer and user-space RCU that is used as an epoch-based SMR.

CDS is mostly header-only template library. Only SMR core implementation is segregated to .so/.dll file.

The library contains the implementations of the following containers:

  • lock-free stack with optional elimination support
  • several algo for lock-free queue, including classic Michael & Scott algorithm and its derivatives, the flat combining queue, the segmented queue.
  • several implementation of unordered set/map - lock-free and fine-grained lock-based
  • flat-combining technique
  • lock-free skip-list
  • lock-free FeldmanHashMap/Set Multi-Level Array Hash with thread-safe bidirectional iterator support
  • Bronson's et al algorithm for fine-grained lock-based AVL tree

Generally, each container has an intrusive and non-intrusive (STL-like) version belonging to cds::intrusive and cds::container namespace respectively.

Version 2.x of the library is written on C++11 and can be compiled by GCC 4.8+, clang 3.6+, Intel C++ 15+, and MS VC++ 14 (2015) and above

Download the latest release from http://sourceforge.net/projects/libcds/files/

See online doxygen-generated doc here: http://libcds.sourceforge.net/doc/cds-api/index.html

How to build

  • *nix: use CMake
  • Windows: use MS Visual C++ 2017 project

Some parts of libcds may depend on DCAS (double-width compare-and-swap) atomic primitive if the target architecture supports it. For x86, cmake build script enables -mcx16 compiler flag that switches DCAS support on. You may manually disable DCAS support with the following command line flags in GCC/clang (for MS VC++ compiler DCAS is not supported):

  • -DCDS_DISABLE_128BIT_ATOMIC - for 64bit build
  • -DCDS_DISABLE_64BIT_ATOMIC - for 32bit build

All your projects AND libcds MUST be compiled with the same flags - either with DCAS support or without it.

**Building libcds -use vcpkg

You can download and install libcds using the vcpkg dependency manager:

git clone https://github.com/Microsoft/vcpkg.git
cd vcpkg
./bootstrap-vcpkg.sh
./vcpkg integrate install
vcpkg install libcds

The libcds port in vcpkg is kept up to date by Microsoft team members and community contributors. If the version is out of date, please create an issue or pull request on the vcpkg repository.

Pull request requirements

  • Pull-request to master branch will be unconditionally rejected
  • integration branch is intended for pull-request. Usually, integration branch is the same as master
  • dev branch is intended for main developing. Usually, it contains unstable code

Project stats

References

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" pdf
  • FCStack - flat-combining wrapper for std::stack

Queue

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

Deque

  • flat-combining deque based on stl::deque

Map, set

  • MichaelHashMap: [2002] Maged Michael "High performance dynamic lock-free hash tables and list-based sets" pdf
  • SplitOrderedList: [2003] Ori Shalev, Nir Shavit "Split-Ordered Lists - Lock-free Resizable Hash Tables" pdf
  • 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"
  • FeldmanHashMap, FeldmanHashSet: [2013] Steven Feldman, Pierre LaBorde, Damian Dechev "Concurrent Multi-level Arrays: Wait-free Extensible Hash Maps". Supports thread-safe bidirectional iterators pdf

Ordered single-linked list

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

Priority queue

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

Tree

  • EllenBinTree: [2010] F.Ellen, P.Fatourou, E.Ruppert, F.van Breugel "Non-blocking Binary Search Tree" pdf
  • BronsonAVLTreeMap - lock-based fine-grained AVL-tree implementation: [2010] Nathan Bronson, Jared Casper, Hassan Chafi, Kunle Olukotun "A Practical Concurrent Binary Search Tree" pdf

SMR

  • Hazard Pointers
    • [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-free objects using atomic reads and writes" pdf
    • [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects" pdf
    • [2004] Andrei Alexandrescu, Maged Michael "Lock-free Data Structures with Hazard Pointers" pdf
  • User-space RCU
    • [2009] M.Desnoyers "Low-Impact Operating System Tracing" PhD Thesis, Chapter 6 "User-Level Implementations of Read-Copy Update" pdf
    • [2011] M.Desnoyers, P.McKenney, A.Stern, M.Dagenias, J.Walpole "User-Level Implementations of Read-Copy Update" pdf

Flat Combining technique

  • [2010] Hendler, Incze, Shavit and Tzafrir "Flat Combining and the Synchronization-Parallelism Tradeoff" pdf