Questions tagged [lock-free]

An umbrella term for methods and algorithms to synchronize multithreaded environments or other forms of distributed system without using locks.

46
votes
5answers
14k views

Thread-Safe and Lock-Free - Queue Implementation

I was trying to create a lock-free queue implementation in Java, mainly for personal learning. The queue should be a general one, allowing any number of readers and/or writers concurrently. Would you ...
17
votes
2answers
2k views

O(1) lock free container

This is a lock-free Container class. By Container I mean it will hold objects for iteration at a later time. To achieve \$O(1)\$ ...
15
votes
3answers
2k views

Testing a lock-free job queue

I've created a lock-free job queue and with the tests I've written, which is also very fast. That makes me doubt my benchmark procedure, so I'm hoping the collective knowledge will shed some light on ...
15
votes
1answer
5k views

Lock-free multiple-consumer multiple-producer queue

The code below implements an intrusive lock-free queue that supports multiple concurrent producers and consumers. Some features: Producers and consumers work on separate ends of the queue most of ...
15
votes
2answers
1k views

Lock-free cache oblivious n-body algorithm

I'm currently looking at, from a rather high level, the parallelization of the gravity calculation in an N-body simulation for approximating a solution to the N-body problem. The simple form of the ...
12
votes
3answers
1k views

Lock-free thread-safe Fibonacci number generator

Here is my implementation of a lock-free thread-safe Fibonacci number generator. Is it correct? The idea is to use an immutable holder for previous and current numbers (since it's hard to change two ...
11
votes
1answer
4k views

Play some sine waves with SDL2

Runs smoothly, however valgrind is showing "possibly lost: 544 bytes in 2 blocks". This is my first time doing a lot of things here so I might be making multiple mistakes. Please let me know if ...
11
votes
2answers
1k views

Implementation of a lock-free fixed-sized allocator

This question now has a follow-up: Implementation of a lock-free fixed-sized allocator - follow-up - with commented code I've tried implementing a lock-free fixed-size allocator while trying to ...
11
votes
1answer
13k views

Thread-safe lock-free counter

I was using such code: ...
11
votes
1answer
2k views

Lock-free atomic shared pointer in C++14

I'm trying to write a lock-free implementation for atomic shared pointer. Basically, there are two class templates shared_ptr and ...
9
votes
3answers
1k views

Naive lock free work stealing queue

Recently, I read a article about work stealing queue Job System 2.0: Lock-Free Work Stealing – Part 3: Going lock-free, and this is my c++11 naive implementation based on my understand of c++11 ...
8
votes
3answers
215 views

C++ lock free, single producer, single consumer queue

Assumptions for use: push() will only ever be called by a single thread. pop() will only ever be called by a single thread. Requirements: push() needs to be as fast as possible. Requirements are ...
8
votes
1answer
413 views

Searching in a lock-free ordered single-linked list

The code below represents a lock-free ordered single-linked list, and is a modification of the algorithm proposed in this doc. How can I improve speed of searching (lookingup) in the list maintaining ...
8
votes
2answers
182 views

Creating a lock-free memory pool using C++11 features

I have created a thread-safe and lock-free memory pool program using C++11 features. A couple of notable features: g_memStack is a stack that contains the memory ...
8
votes
1answer
2k views

Lock-free multi-producer multi-consumer queue

I'm looking for some feedback on my lock-free queue, based on Disruptor, mainly for any potential concurrency issues, such as where I need additional fences. It looks correct to me, and I can't seem ...
8
votes
1answer
790 views

Low-lock Multi-threading Implementation

I'm designing in my spare time a game engine (for fun, not so much for profit, haha). I wanted to design the 'core pipeline' as efficiently as possible. Having a quad-core CPU, I decided to take ...
7
votes
1answer
2k views

Lock-free zero-copy triple buffer

In a producer-consumer scenario sometimes we have to deal with the producer being much faster than consumer. The data loss is unavoidable, and we are OK with it, as long as the consumer always has the ...
7
votes
1answer
2k views

Lockless Queue Multiple-Reader Singler-Writer in C++

I wrote a lockless queue for sending small objects from a single thread to a random worker thread. Assumptions: x86/x86_64 compiled with GCC one thread may Write(), multiple threads may Read() ...
6
votes
4answers
2k views

Singleton SpinLock: Making Random Thread-Safe

Is this a valid and safe use of .NET's System.Threading.SpinLock? Why am I doing this? Random's public methods are not ...
6
votes
3answers
1k views

Lock-free SPMC queue

Here is my lock-free queue implementation for single producer with some preallocated memory. T is a simple type with no need for move operations. I don't use ...
6
votes
1answer
491 views

Lock-free, multiple consumer, multiple producer queue

I'm implementing a lock-free, multiple consumer, multiple producer FIFO queue/pipe as an exercise in thinking about atomicity in operations. My main concern is correctness of operation, my second ...
6
votes
1answer
775 views

C++11 lock free collection similar to std::forward_list - follow-up

This question has been superseded by C++11 lock free collection similar to std::forward_list - follow-up 2 Thread safe and lock free collections are very hard to write, so I'd appreciate any feedback,...
6
votes
1answer
1k views

Multiple-producer, single-consumer lock-free circular queue

I'm working on a firmware on a bare-metal ARM single core processor (Cortex M4), with no RTOS. I need to add a multiple-producer, single-consumer, lockless fixed-size circular (ring) buffer to the ...
6
votes
1answer
286 views

Snowflake Id implementation

For some time now I have maintained (and written) IdGen. It's inspired by Twitter's Snowflake project and it's intended use is to generate (roughly) incremental id's in a distributed scenario with ...
6
votes
1answer
1k views

Lock-free bounded stack in C++11

Here is a classical attempt to implement a lock-free stack (based on this article). I rewrote it in C++11 and also tried to add memory orders which I would like to confirm to be correct. ...
5
votes
2answers
264 views

A simple lock-free queue for work stealing

I am currently reading the book C++ Concurrency in Action by Anthony Williams. In chapter 9, he implemented a lock-based work stealing queue and mentioned it is possible to implement a lock-free queue ...
5
votes
1answer
3k views

Lockless multi user, multi consumer FIFO queue using C++11

One of the features that is missing from C++11 are lockless queues. Therefore I have decided to write one myself. A few remarks: I know the code isn't technically lockless. However the lock is only ...
5
votes
1answer
3k views

Single consumer and single producer lock-free circular buffer

I'm pretty new to multithreading. The code below is a simple implementation of a single consumer/single producer circular buffer that does not use any locking, that I wrote for fun. The question is,...
5
votes
2answers
3k views

Lock-free multiple producer single consumer message queue

For a while now I've been after a lock-free, simple and scalable implementation of a multiple producer, single consumer queue for delegates in C#. I think I finally have it. I've run basic tests on it ...
5
votes
1answer
296 views

Single producer single consumer wait-free object container

I have a fast producer thread and a slow consumer thread. The consumer processes as many objects as it can and simply ignores the rest in order to not slow down the producer. Therefore, I used a one-...
5
votes
1answer
667 views

Non blocking single producer/consumer queue with C++11 atomics

I've recently got interested in lockless programming, mainly lockless queues for job repartitions, so here I undertook a challenge of creating lockless queue for single producer and consumer. This is ...
5
votes
1answer
331 views

Lockless, blocking, non synchronized multiple producers and consumers ring buffer

My program is structured like this: there are M producer threads, each of which computes a section of an object O with index <...
5
votes
1answer
1k views

Lockfree ThreadPool implementation

How could this template class ThreadPool be improved? I use Boost queue to keep std::function's numbers from ...
5
votes
1answer
4k views

Lock-free ringbuffer with multiple readers in C++11

Basic Info I needed a lock-free ringbuffer with multiple readers (but one writer). However, I did not want the writer to check all readers every time in order to prevent an overrun. Thus, I decided ...
5
votes
1answer
470 views

lock-free job queue without size restriction (multiple read/write)

I've since come up with an improved version, which isn't technically lock-free, but might be as close as you can get (nearly) lock-free job queue of dynamic size (multiple read/write) code below is ...
5
votes
1answer
789 views

CountdownLatch Thread-Safety Check

I've written this class as an exercise for a synchronization construct to be used across multiple threads. The intent is to have worker threads Increment() it, do ...
5
votes
0answers
105 views

Yet another multi-producer single consumer queue in C++17

Here's an implementation of a multi-producer single consumer queue that I wanted to use with tasks such as logging from multiple points in a program to a single sink. The implementation is inspired ...
5
votes
0answers
2k views

Disruptor pattern in a lock-free producer-consumer queue

I'm implementing a quick-and-dirty lock-free MPMC queue in C++, based on the v3 Disruptor algorithm. The implementation is pretty simple: Data to be shared between threads is stored in a ring buffer. ...
4
votes
2answers
2k views

Thread-safe lock free FIFO queue

A few years ago there was a need to add a FIFO queue between 2 threads into my project. At that time I've got some interesting idea how to do that without any atomics and locks. (There was a ...
4
votes
2answers
4k views

ArrayBlockingQueue: concurrent put and take

I have implemented an ArrayBlockingQueue (put and take) on the lines of LinkedBlockingQueue i.e using two locks so that my take ...
4
votes
1answer
137 views

Lock-free bounded stack atomics

I was thinking about using very basic bounded (preallocated) stack to keep track of my threads IDs in correct LIFO order. I was wondering if my implementation is thread safe: ...
4
votes
1answer
1k views

Lock-free FIFO queue implementation

...
4
votes
1answer
2k views

Lock-free list in C++

I tried to write a lock-free list in C++. Unfortunately, the performance compared to an std::list secured with a simple mutex is bad. What do you think? Are there ...
4
votes
3answers
481 views

Lock-free MultiConsumer/MultiProducer queue

I've written a simple lock-free multi-consumer/-producer FIFO queue. It's supposed to work like this: At any time many consumers may read from it At any time multiple producers can write to it, added ...
4
votes
1answer
390 views

Multi producer/consumers lockfree stack

Can you please take a look at the following x86-64 C++ code which should implement a multi consumer/produce lockfree stack? Do you think I have missed anything? ...
4
votes
1answer
2k views

Lock-free queue with doubly linked list correctness

I need a lock-free queue which is implemented by doubly linked list. Is my code correct? Are there any errors? Are there any improvements to be made? linkedlist.h ...
4
votes
2answers
4k views

Block a thread - spin-lock replacement

I have implemented several lock-free algorithms to maximise throughput but have always baulked when performing a spin-lock. I can usually convince myself that this is the only way but it still nags at ...
4
votes
0answers
182 views

An in-memory copy of the GDAX order book for an arbitrary cryptocurrency, updated in real time

GDAX is the cryptocurrency exchange owned and operated by Coinbase. This code is intended to be the basis for an order-book-strategy trading bot. I'd love feedback on my use of data structures, my ...
3
votes
2answers
282 views

Multi producer/consumers lockfree list

As per a similar question, following a lockfree list implementation. Note that this list has a pre-defined maximum set of elements which can be inserted (N argument ...
3
votes
2answers
326 views

Customized lock-free RingBuffer

I have implemented my own lock-free ringbuffer for multiple producers multiple consumers using vector. Can you guys help me review to see if there are any problems and ways to improve? Explanation: ...