Questions tagged [lock-free]
An umbrella term for methods and algorithms to synchronize multithreaded environments or other forms of distributed system without using locks.
102 questions
11
votes
4
answers
1k
views
C++ lock free single linked list dedicated to word frequency
I'm building this code for my students, so I'd like any comments about modern C++ and whether it is pedagogic. And of course if you find any logic error.
Basic exercise is to count word frequency in a ...
- 243
4
votes
1
answer
110
views
Lock-free queues and stacks
I am currently working on implementing lock-free stacks and queues. So far, they seem to function properly in test programs, but I am unsure if there are any underlying issues or areas for improvement(...
- 141
1
vote
0
answers
64
views
Lock free Leaky Bucket Rate Limiter
I want to validate my solution for a lock-free leaky bucket rate limiter. Given a queuing capacity and rate limit per second, it should queue requests till capacity is reached and it should allow only ...
5
votes
4
answers
677
views
Single Consumer Single Producer Wait-Free Zero-Copy Circular Message Queue
The title describes pretty well what the algorithm is for. It will be used for a realtime inter-process communication library that only uses shared memory for exchanging data. For realtime systems, it'...
- 199
9
votes
4
answers
2k
views
Lock-free ring buffer
I implemented lock-free ring buffer from scratch. As I am a beginner in atomic features in C++, I wanted to hear your feedback and possible ordering issues if there are.
...
- 161
4
votes
2
answers
330
views
SPSC templatized lock free queue implementation and benchmarking
I have tried implemented a fast lock free Single producer single consumer queue in C++ for practicing concurrency and low level design concepts. I also benchmarked the code on x86_64 2.3GHz Intel ...
- 83
3
votes
1
answer
166
views
Multi producer/consumer lock-free queue
I would be grateful if you could review my code for a multi producer/consumer lock-free queue in C++.
I am mainly after performance improvements, but all input is welcome.
...
- 33
5
votes
3
answers
569
views
C11 zero copy lock-free triple buffer
The code is for a single producer, single consumer scenario, where the consumer only cares about the latest information shared by the producer.
This is just a simple proof of concept created for linux....
- 199
1
vote
1
answer
190
views
Implementation of a lock free queue using CompareAndSwap in Go
Here is my implementation of a lock free queue using CompareAndSwap operation.
...
1
vote
1
answer
263
views
Lock-free implementation of getAndUpdate() using atomic CAS (Compare-And-Swap) operation
We have the following class written in Kotlin Native with the new Memory Manager (which doesn't require to freeze objects):
...
- 111
3
votes
2
answers
433
views
Concurrent Handle Table
I'm writing a data structure to solve a problem related to servicing hardware interrupts. I have to translate a 64-bit pointer to a 16-bit handle and back again. Unfortunately the hardware completions ...
- 181
1
vote
1
answer
345
views
Design a thread-safe Hit Counter
I have designed a Hit Counter which can conveniently be used to design a Rate Limiter
Original question: https://leetcode.com/problems/design-hit-counter/
To make it thread safe, I used lock statement....
- 146
3
votes
1
answer
305
views
Lock-free, thread-safe trie container
This is a Trie data structure for mapping strings to integers or pointers in O(n) time. Based on the idea that we never delete anything from the container, we can perform concurrent read/write ...
- 421
22
votes
3
answers
7k
views
C++ lock-free, MPMC Ring buffer in C++20
I have some performance critical inter-thread messaging code in C++. Multiple producers, one or more consumers.
Profiling dozens of iterations of this messaging code over several years of development, ...
- 364
7
votes
1
answer
1k
views
Lock-free triple buffer
I have a single producer and single consumer, and the producer never stops, but the consumer might not keep up. There's no need to consume every item, as long as we always access the most-recently ...
- 88.4k
5
votes
1
answer
995
views
A concurrent lock-free Linked Queue implementation
Recently I've been learning about concurrency/parallelism and I decided to implement the Michael&Scott lock-free Linked queue (PDF) as practice.
I'm not entirely sure how to test this data ...
- 148
2
votes
0
answers
675
views
Lock free ring buffer
I am hoping that someone can take a look at my implementation of a lock-free ring buffer and critique the implementation. I'm hoping that the focus can be of the correctness of the atomic operations ...
- 21
2
votes
1
answer
440
views
2
votes
2
answers
359
views
Lock-free multi producer logging/profiling, multi file descriptors
I am developing (for fun) a Utilities & Logging library
Can someone please help me to improve:
Github link
Pros
Thread-safe, no mutex. Use lock-free ring buffer (the idea is inherited from ...
- 121
3
votes
0
answers
91
views
implementing a mutex with capacity
Not sure this is the right place, but I'll have a try.
I'm trying to implement a mutex with capacity, which can be achieved easily with buffered channel like this:
...
- 31
2
votes
0
answers
174
views
Lock-free state machine
I've written a lock-free state machine in go and I would love to receive some feedback on it.
Writing this library my main concerns are keeping it lock-free and very light-weight (no bells and ...
- 309
6
votes
1
answer
605
views
Simple lock-free queue - multiple producers, single consumer
I have a simple lock-free queue, which supports multiple producers, but only one consumer. It is based on a constant-sized ring buffer and stores only pointers to a class and not actual instances. ...
- 69
4
votes
0
answers
114
views
C++14 AtomicRoundRobinPool for sharing a pool of keys
The idea here is that we have some resource that is relatively very expensive to generate, but once we have a bunch of them in a pool, we can keep reusing them instead of generating new ones. "HTTP ...
- 19.7k
1
vote
1
answer
260
views
A minimalistic kind of read-copy-update class
This is a very simple read-copy-update (RCU)-inspired synchronization class:
...
- 119
2
votes
0
answers
115
views
Lock-free pooled queue
I am attempting to create a lock free pool of resources and I need the ability to access any one that is not already accessed and then return it back when I do not need it. This will happen very very ...
9
votes
2
answers
6k
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 ...
10
votes
3
answers
6k
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 ...
- 103
8
votes
2
answers
2k
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 ...
- 83
1
vote
1
answer
330
views
Passing objects atomically across threads without locks or data races for audio synchronization
I am learning about one of the hardest parts of Audio development: the synchronization between the audio thread and the GUI thread. Per the discussion here https://forum.juce.com/t/timur-doumler-...
- 13
5
votes
0
answers
960
views
A multithreaded, growable vector with immutable elements, which has wait-free reads
Disclaimer for future readers: We experimented around with a similar approach at HASH. The linked Pull Request is working.
I wrote a small vector with a few lines of unsafe Rust.
The idea is to have ...
- 231
6
votes
1
answer
1k
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-...
- 161
10
votes
1
answer
2k
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 ...
- 195
3
votes
2
answers
724
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:
...
- 133
5
votes
2
answers
1k
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 ...
- 51
0
votes
1
answer
816
views
Lock free consumer producer using memory barrier [closed]
I am looking for "complete" producer-consumer sample using C++11 memory barrier.
(I have derived following example from Jeff's article and added a line to make it complete.)
...
8
votes
1
answer
4k
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 ...
- 1,398
4
votes
0
answers
299
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 ...
- 363
4
votes
1
answer
225
views
Lock-free Immutable ConcurrentQueue
Similar to the code review I posted last week for an agent-based immutable replacement for ConcurrentDictionary, I have also created an agent-based immutable ...
- 551
2
votes
0
answers
231
views
Lock-free statically allocated async-interrupt-safe multi-consumer double buffer
I have a single threaded embedded system with nested interrupts.
A writer interrupt will periodically update some global data structure with data.
Reader interrupts / calls from main thread will read ...
- 121
11
votes
1
answer
4k
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 ...
- 828
3
votes
0
answers
121
views
shared_mutex prototype implementation
Anyone feels to review a prototype C++11 shared_mutex implementation?
Not recursive, not protected and potentially dangerous if used incorrectly, but allegedly fast in case of many R/O less R/W ...
- 240
5
votes
1
answer
1k
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 ...
- 121
4
votes
2
answers
5k
views
C++ minimal threadsafe array based on std::deque
Here is a minimal example of a threadsafe array I want to build on for a timeseries application, with the following characteristics:
Ever-growing, and the already contained elements remain constant
(...
- 548
2
votes
1
answer
486
views
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, especially regarding bugs. The code below is a self contained hpp, followed by some tests.
This question ...
- 461
17
votes
2
answers
6k
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 ...
- 58.7k
9
votes
3
answers
2k
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 ...
- 203
4
votes
1
answer
3k
views
4
votes
0
answers
85
views
Fast lock implementation using pipes only
For fun I wanted to create a lock implementation that was about as fast as one using futexes but that used used pipes instead and that queues waiters in user space instead of in-kernel. For the queue ...
user12742
0
votes
2
answers
4k
views
Concurrent Stack with blocking and non-blocking methods
I wrote it this just for learning. Is there holes at this code?
...
- 593
2
votes
2
answers
368
views
Thread-efficient nonce generations
I need to create unique nonces for cryptographic purposes in a library that I am writing. If the nonces ever fail to be unique, the consequences may be up to and including remote execution of ...
- 325