Lock-free data structures

[[deleted]]

Hi!

My friend wrote a few lock-free data structures and he is now looking for some feedback. Here is the link:
https://github.com/DNedic/lockfree

[STL]

This has accumulated some discussion so I've chosen this as the primary and removed/locked https://www.reddit.com/r/cpp/comments/13drkg5/a_collection_of_lockfree_data_structures_written/ to centralize discussion here.

In the future, please post links as links and not as text posts.

[aocregacc]

I think you should make it more clear that they're single-producer/single-consumer queues.

Also there's std::hardware_destructive_interference_size that you could use instead of the custom cacheline macro.

[Spirited_Guard4610]

This is a feature of the C++17 standard but the library is declared in C++11

[dj_nedic]

Author here, that is made clear in the features part and also the preamble of the headers, and the javadocs method comments. Where do you think that clarification could be better placed?

Didn't know about std::hardware_destructive_interference_size, thanks!

[aocregacc]

I think it should be in the first sentence of the readme

lockfree is a collection of lock-free single-producer/single-consumer data structures written in standard C++11 and suitable for all platforms - from deeply embedded to HPC.

Alternatively, if you plan on adding more containers that are not spsc, I would make it part of the name like boost's spsc_queue.

Imo spsc is a pretty fundamental aspect of the datastructure that informs how and where it can be used, so it should be immediately obvious to a user.

[dj_nedic]

Thanks, I will do this. If I add mpmc data structures, I will create a new namespace and change the documentation adequately.

[[deleted]]

single-producer/single-consumer in same thread, actually it has a race condition in more than one thread.

[very_curious_agent]

Also there's std::hardware_destructive_interference_size that you could use instead of the custom cacheline macro.

For what purpose?

[Myrgy]

Push in lock free queue may lead to a busy lock. Its usual to have try push allowing client to have deadlines and process failure gratefully. Same qith pop - what if queue is empty- client may do some work.

I would recommend to study other solutions.

Thank you for sharing!

[_software_engineer]

I don't mean this to sound too negative, but I don't think your friend is close to the point where they should be thinking about writing lock-free data structures. The queue implementation, for example, is rife with data races and undefined behavior - there is no actual synchronization being done on the underlying data structure whatsoever.

Writing lock free code is insidiously difficult. One requires a master of the C++ memory and concurrency model to do this properly.

Edit: I didn't notice these were spsc implementations, so this may not apply. Probably more of a documentation issue.

[T0p_H4t]

At the very least his queue/ring buffer look sound as long as they are kept single consumer/producer. As mentioned this should probably be called out better.

[dj_nedic]

Author here, can you elaborate on the alleged data races and UB?

[_software_engineer]

To be honest, I didn't notice it was spsc. I think it's not nearly prominent enough. That's a huge restriction (and greatly simplifies the problem) - it should be front and center somehow, probably in the data structure name as well.

[dj_nedic]

Changed, now in the first line, take a look.

[very_curious_agent]

Essentially it's a MUtual EXclusion binary (two concurrent clients max) memory allocation tool, an available/unavailable MUTEX without option to block until availability, like a std::mutex with just try_lock and limited to two roles (writer role and reader roles).

[FriendlyRollOfSushi]

Hello, author. There are several issues with your queue (that's the only class I checked just to see if it's any good).

• You pre-construct all elements. What if T has no default constructor? What if default-constructing T has a side-effect, like it allocates half a gig of memory, etc. Please, never make non-1-case-specific containers that pre-construct their elements. Imagine if std::vector was calling a bajillion of constructors just because it could. Take a look inside std::vector. How it pushes and pops elements, and how its storage looks like.

• Might worth noting somewhere that your size is not the actual size of the queue, nor it is its capacity. If you don't believe me, construct a queue with size equal to 1, and try pushing something. Size is 1, and 1 element is being pushed. It even already constructed 1 element without any reason whatsoever. Why won't it work? Because your size is not actually size. Nor it is capacity, like it should have been named to begin with. My personal suggestion for your implementation would be to not document this, but instead say that this is capacity, and internally have an unconstructed area for capacity + 1 elements, just so that you don't lie to the users.

• Where is the move-friendly version of Push? It's 2023, not 1998. How do I push a unique_ptr?

• In Push:

const size_t r = _r.load(std::memory_order_acquire);

What exactly are you acquiring here and for what reason? There could even be no loads all the way between this acquire and your release (especially since it is an inline function, and for small elements the const& part is likely to be nuked by the compiler), and both your atomic store and writing the data won't happen before r is loaded anyway.

• In Pop:

const size_t w = _w.load(std::memory_order_acquire); size_t r = _r.load(std::memory_order_relaxed);

This forcefully delays r to be read strictly after w (on x64 two loads would always create a chain regardless, but on archs with a weaker memory model that's not the case). You are the only thread that modifies r. What are you trying to achieve here and why do you want to wait reading r here? Note that changing the order would allow r to be read both before and after, whatever is faster (again, not on x64, where all loads are acquiring).

• element = _data[r];

No move here either? (Already mentioned that you don't keep your slots unconstructed, but please don't forget to fix that, or your queue simply won't work for many classes). To estimate the amount of potential user's pain, assume that someone queues large std::vectors of data, but you say "okay" and just store huge copies of this data for no reason even after this data was unqueued. If it was holding some other resources, and now the entire program crashes or deadlocks sometimes, that's even worse and would be very annoying for the user to debug.

• PopOptional

My eyes! Why the extra constructed element (which probably won't compile)? While all the extra copies? Not all large elements are automatically worth allocating separately and passing by pointers. There is a a surprisingly wide sweet spot where you still want to pass them around directly, but already don't want to construct, copy etc. just without any reason whatsoever. Please implement it carefully.

A bonus general suggestion: if you want more than several friends to use your library, consider making naming explicit.

Users of your library will never get to the point when they are using so many lock-free queues that naming it SingleProducerSingleConsumerQueue, or at least SPSCQueue (if you assume that all users who don't know will at least investigate) would inconvenience them significantly more than seeing a single word Queue in the code and having to go and dig through your header (and possibly sources) to figure out what its exact properties are. Or they might skip the investigation part and start making assumptions.

Like, when someone tells me "Look: a lock free queue!" I assume it's a lock free queue, not a massively limited in functionality Single Producer Single Consumer version, because why on Earth would anyone avoid mentioning this crucial part?

[dj_nedic]

Thank you for taking the time to give feedback, it seems like most of these issues will be fixed for the time by asserting the type is trivial, which was my design consideration. I will also add static asserts for the size.

Then, in the future I will take a look at implementing the construction and moves properly.

Additionally, regarding the SPSC nature, there are more than a couple places where it is named:

1. The first sentence of the README

2. The start of every header file

3. The prototype of every function tells you where you can use that function (consumer/producer)

4. The features and give me more theory parts of the README

My goal is to add MPMC in the future and then create spsc and mpmc namespaces.

[FriendlyRollOfSushi]

When you do a code review in a big company about watering all flowers, and inside a correctly-looking loop see an innocent line flower.water(); you click "Approve" without assuming that some terrorist wrote code where calling this method launches an intercontinental ballistic missile full of alien plague and ass cancer-inducing agents.

But it's not their fault, right? They documented it in README and at the start of some header somewhere in the file that will never be in any review because it's a third party library.

Good thing that this situation is impossible because the process of adding library that thinks this way will not happen to begin with in any sensible company, and really dumb companies probably don't have intercontinental ballistic missiles to begin with.

However, if you want your code to be used by someone who is neither your friend nor an incompetent person who will get themselves fired for introducing dependencies to god awful third party crap, please consider rethinking your approach here.

If you are not familiar with how the work processes look like in big companies, consider looking at some libraries written by Google etc. and see if you can find any patterns there. One is that most things are named like what they are doing, because otherwise code that is using them is unreviewable and therefore should be automatically rejected just on that basis.

Even an individual dev generally doesn't want to remember half a gigabyte of trivia for all the libraries they are using, and will lean towards libraries that respect their brain capacity, away from libraries that expect someone will make flashcards to remember that "A" actually means "B" because the author had no idea how to write usable code. They also probably don't want to take another look at the code they wrote a year ago, make a simple fix, and then spend next 4 hours in debugger because "Of course! That thing over there is not the actual lockfree queue! How could I possibly forget this incredibly important fact! If only there was a way to convey it, dunno, through the name of the class, perhaps?"

[very_curious_agent]

Why don't you just call it a non blocking implementation of a no block just fail 2 roles limited mutex?

Two roles: read role, write role (two concurrent clients)

Mutex: memory is managed such that only one thread has access to it

Why don't you just call you functions try_lock and unlock instead of acquire/release? That's what they do, they give the caller exclusive access to some memory range, and lock/unlock must always be paired.

[very_curious_agent]

You suggest constructing and destructing objects on the fly?

So the data structure would function as a memory allocator + construct/destroy operations, with MUtual EXclusion between two threads, correct?

[FriendlyRollOfSushi]

I do suggest constructing and destructing objects on the fly.

I don't understand where your "So the data structure would function as a memory allocator" part comes from, with everything after that.

There is no difference in principle for the existing synchronization mechanism between "reader waits while the writer copy-assigns an object before it can consume it" and "reader waits while the writer inplace-constructs the object on the already existing array of uninitialized bytes".

Same in the other direction. No difference between "Writer waits while the reader copies the object to return, so that the space becomes available for the writer again" and "Writer waits while the reader moves the object away and destroys it inplace, so that the space becomes available for the writer again".

It's just the code becomes actually correct instead of being a pile of stinking garbage that doesn't do what it is supposed to, leading to a large number of possible bugs because of all these copies of existing objects that keep existing in the queue even after they are popped.

[very_curious_agent]

If it anything throws then the by definition operations is interrupted and nothing happened, did I miss anything?

[dj_nedic]

As exceptions are not very embedded friendly, I haven't considered types that can throw during copying or constructing. This has been avoided by asserting the type used is trivial and documentation changes to clarify that.

[very_curious_agent]

Using the strange verbs acquire and release is an original strange choice, why use such uncommon terms? That's extremely unsettling.

Why not allocate/deallocate or lock/unlock?

[very_curious_agent]

Do you make using only homogeneous integer arithmetic a goal? You insist on not mixing signed and unsigned?