rigtorp / awesome-lockfree

A collection of resources on wait-free and lock-free programming

Awesome Lock-Free

A collection of resources on wait-free and lock-free programming.

🔥 🔥 🔥 Even better resource from MattPD: C++ links: atomics, lock free, memory model.

Libraries

• Boost.Lockfree - Boost lock-free data structures.
• ConcurrencyKit - Concurrency primitives.
• crossbeam - Rust library for concurrent programming.
• Folly - Facebook Open-source Library (has good implementation of MPMC queue).
• Junction - Concurrent data structures in C++.
• MPMCQueue - A bounded multi-producer multi-consumer lock-free queue written in C++11.
• SPSCQueue - A bounded single-producer single-consumer wait-free and lock-free queue written in C++11.
• Seqlock - Implementation of Seqlock in C++.
• Userspace RCU - liburcu is a userspace RCU (read-copy-update) library.
• libcds - A C++ library of Concurrent Data Structures.
• liblfds - portable, license-free, lock-free data structure library written in C.
• xenium - A C++ library providing various concurrent data structures and reclamation schemes.

Websites

• 1024cores - Dmitry Vyukov's website on lock-free programming.
• LMAX Disruptor
• Wikipedia: Non-blocking algorithm
• Wikipedia: Read-copy-update
• Wikipedia: Seqlock

Blogs

• Concurrency Freaks - A web site dedicated to Concurrent algorithms and patterns.
• Dan Luu - Lots of info on modern computer architecture.
• Locking in Webkit
• Mechanical Sympathy
• Paul E. McKenney
• Preshing on Programming
• Sutter's Mill - Herb Sutter on software development.
• Paul Khuong

Books

• Paul E. McKenney. Is Parallel Programming Hard, And, If So, What Can You Do About It?
• Maurice Herlihy and Nir Shavit. The Art of Multiprocessor Programming

Papers

• A Tutorial Introduction to the ARM and POWER Relaxed Memory Models
• Paul E. McKenney. Memory Barriers: a Hardware View for Software Hackers.
• Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms - The Michael - Scott Queue
• Ulrich Drepper. What Every Programmer Should Know About Memory
• x86-TSO: A Rigorous and Usable Programmer’s Model for x86 Multiprocessors

Talks

• CppCon 2014: Herb Sutter "Lock-Free Programming (or, Juggling Razor Blades), Part I"
• CppCon 2014: Herb Sutter "Lock-Free Programming (or, Juggling Razor Blades), Part II"
• CppCon 2015: Fedor Pikus PART 1 “Live Lock-Free or Deadlock (Practical Lock-free Programming)"
• CppCon 2015: Fedor Pikus PART 2 "Live Lock-Free or Deadlock (Practical Lock-free Programming)"
• CppCon 2015: Michael Wong “C++11/14/17 atomics and memory model..."
• CppCon 2015: Paul E. McKenney “C++ Atomics..."
• CppCon 2014: Tony Van Eerd "Lock-free by Example"
• CppCon 2016: Fedor Pikus "The Speed of Concurrency: is lock-free faster?"
• CppCon 2016: Hans Boehm “Using weakly ordered C++ atomics correctly"
• CppCon 2017: Fedor Pikus “C++ atomics, from basic to advanced. What do they really do?”
• CppCon 2017: Fedor Pikus “Read, Copy, Update, then what? RCU for non-kernel programmers”
• CppCon 2017: P. McKenney, M. Michael & M. Wong “Is Parallel Programming still hard? PART 1 of 2”
• CppCon 2017: P. McKenney, M. Michael & M. Wong “Is Parallel Programming still hard? PART 2 of 2”
• CppCon 2018: “The Landscape and Exciting New Future of Safe Reclamation for High Performance”
• C++ and Beyond 2012: Herb Sutter - atomic<> Weapons, 1 of 2
• C++ and Beyond 2012: Herb Sutter - atomic<> Weapons, 2 of 2
• "Aeron: Open-source high-performance messaging" by Martin Thompson
• Adventures with Concurrent Programming in Java: A Quest for Predictable Latency - Martin Thompson
• Understanding the Disruptor, a Beginner's Guide to Hardcore Concurrency -Trisha Gee & Mike Barker

About

This list was compiled by Erik Rigtorp <[email protected]>.

awesome-lockfree's Issues

Suggestion

What about the http://liblfds.org/ ?

Add crossbream-rs to list

The list is appealing for concurrency hobbyists. However, it does not have my favourite crossbeam, which is a Rust library for concurrency lovers. This article should give an overview of current status.

In brief, crossbeam already provides:

• MsQueue: lock-free Michael-Scott queue
• TreiberStack: lock-free stack
• lock-free skiplist

Xenium

Hi,

I am working on a C++ library called "Xenium" that provides various concurrent data structures and memory reclamation schemes: https://github.com/mpoeter/xenium
Maybe you can take a look at it and add it to your list. 🙂

Cheers,
Manuel

Broken link

The link for "Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms" is broken. The working one is: https://www.cs.rochester.edu/u/scott/papers/1996_PODC_queues.pdf

Intel oneTBB?

Hi, thanks for keeping the list, a nice collection! I do not know if Intel's oneTBB, neé TBB, belongs in. Its not a “lock-free” library, rather a “don't think about locks and build robust high-throughput HPC software that scales” library. At the core, it uses both locking and lock-free algorithms, and takes care about task affinity, data cache locality, per-thread memory allocation to reduce allocation contention, and other crazy stuff. But most of this stuff is deep at the core; it focuses on high-level design blocks (hence the name). xPxC queues and other concurrent containers are probably among the lowest level algorithms which it surfaces. Up to you.