Correctly implementing a spinlock in Modern C++
rigtorp.se
rigtorp.se
Technical discussions are more deterministic, I suppose, but at a high enough level of abstraction, it's all so much information management.
It can be between two to three orders of magnitude higher throughput. Equally important, lower latency.
(Throughput tends to be a consequence of low latency, but not always.)
I'm not saying this should be the norm, though. You probably don't need this design. But when you do, e.g. processing millions of stock market messages, there's no substitute.
EDIT: I love hearing about the designs and questions, but it was probably a mistake for me not to be explicit. Sorry! The thing I'm referring to is LMAX Disruptor pattern: https://lmax-exchange.github.io/disruptor/
I learned about it in 2011-ish, and it deeply changed my perspective on high speed designs.
It was truly a cool design, for its time.
I feel strongly like it's one of those designs you should study just to even be aware that such a thing exists. Otherwise I probably would've been like "Oh, a spinlock! Yes, always."
(It's the disruptor pattern: https://lmax-exchange.github.io/disruptor/)
Atomic increment is still fairly cheap/efficient and resolves many cases where you'd risk live lock by being wait-free in some aspects.
Certain devilish details I’m sure are exceptions to those scenarios, just sharing the ones I’ve come across.
As long as you aren't oversubscribing hardware threads, you'll be fine, but at the cost of pathological behavior once you add just a single additional thread.
Also don't use `sched_yield(2)` for spin locks, unless you're running priority-based RT Linux. A scheduler that is good for that scenario tends to be quite bad at most real-world scenarios that don't try to do their own spinlocks in userspace due to NIH syndrome.
(A+ and full marks on recognizing that that's a central problem.)
So from my experiments with this, in order to avoid a lock you need to have a ringbuffer of atomic pointers (or atomic values if you're literally just buffering ints or similar). You claim a slot which is a pointer, and then swap out the pointer to the stale value with the pointer to the updated value.
But this now requires a multithreaded lock free memory pool. Single threaded this is no problem, but multithreaded this is incredibly difficult without high latency.
From my own efforts, while it's possible to implement a lock free ring buffer + suitable memory allocator, you end up with high latency. This high latency can only be justified if the size of the data you're buffering is greater than a certain bound because you get increased bandwidth.
For data less than a certain bound, my experience is you get much lower latency and lower bandwidth (but still pretty good bandwidth) by tagging each element with a lock-bit.
I suspect we work in the same area (finance), so if you have insight into good lock free memory allocators or resources I'd be very happy to better inform myself.
As to your specific concern, I think you should be able to preallocate a large buffer of objects that you want to share. In other words, the allocations only need to happen infrequently.
The conversation going from "ringbuffer" to "multithreaded lock-free memory pool" is throwing up warning signals. It's true that you do need to be allocating memory, but the memory can be allocated by a thread (lock free), and then the slot is claimed and pointer written (still lock free). But there's nothing special about this process -- just allocate some memory, and stick it into the slot.
The ringbuffer is the thing that handles the coordination, enabling you to allocate memory on whatever thread you want.
Is there a reason more complexity is justified? (More complexity might entirely be justified, and I just haven't had that experience.)
If there is one thread A allocating memory to push a value onto the ring buffer, and another thread B popping a value off of the ring buffer, how does B free that memory back to the memory allocator without introducing a data race? Certainly there must be some kind of synchronization so that A can allocate memory and B can free that memory.
>The conversation going from "ringbuffer" to "multithreaded lock-free memory pool" is throwing up warning signals.
Yes, because in many cases when I see lock free data structures and get excited about it, what is really presented is a data structure that is putting all of the locking pressure on the memory allocator so that the system as a whole has no net gain.
And this comes down to the crux of the issue, you can write a lock free ring buffer if you stuff all your locking into your memory allocator and I suppose you could claim that the ring buffer is lock free... but the system of ring buffer + memory allocator is then no longer lock free.
That said I'm not saying that this is bad, being lock free doesn't mean good, fast whereas using a lock means slow, bad... it's just that there are a lot of subtle details that make a proper analysis of this much more difficult than it first appears and to the best of my knowledge there is no lock free ring buffer that gives a clear performance benefit.
But as I said, this is such a tricky subject with so many different possible configurations that I would love to see different approaches.
I'm tempted to say "No need to free it; next time A needs one, let it have that one that you were going to free."
In other words, claiming a slot also claims an already-allocated object.
You're right; this isn't a trivial design consideration. And I'm second-guessing myself as to whether my answer here is wrong. If you see a problem with it, definitely call it out.
(Cheers for the interesting conversation, by the way... Didn't expect it.)
You can read more about it here in Section 4.3 on page 6 where they have the following busy waiting:
long expectedSequence = claimedSequence – 1;
while (cursor != expectedSequence) {
// busy spin
}
cursor = claimedSequence
Some other details of the blocking are here:
http://mechanitis.blogspot.com/2011/07/dissecting-disruptor-...
B) Your ring buffer is your allocator: copy (or inplace-construct) your messages direcly in your ring buffer. This work very well for short messages like continuations.
B) each producer thread has a freed-memory lock free queue so that consumers can return memory. The producer can pop the whole queue in one go when it has exhausted its local cache, but pushing an object in the queue can be expensive if the producer was talking with multiple threads. If you want to get fancy you can have NxN spsc queues which works fine with the one thread per core model, but obviously won't scale to ten of thousands of threads.
Then you will need a lock. There's no way to atomically copy data in place without locking.
>each producer thread has a freed-memory lock free queue so that consumers can return memory.
Variations of this is how lock free allocators work and the latency penalty for this strategy is very significant, anywhere from 3-5x the latency penalty of a blocking allocator. Certainly lock free allocators have their use cases and if you have a system that needs bandwidth over latency you go for it, but the point is that unless you have hard real time needs for your system, then you're usually better off going for a blocking data structure.
This is similar to the disruptor model, except that write positions are not pointer sized but arbitrary sized. Similarly to the disruptor model, the mpsc case is technically not lock-free (not even obstruction-free), but writers and the consumer never need to block on an actual lock.
Every single lock-free allocator I've seen is intended to satisfy high throughput at the expense of incurring high latency, and mimalloc is no different in this respect. At any rate you don't normally use a general purpose memory allocator when you need a high performance data structure, instead opting for a data structure specific allocator/memory pool.
If you have multiple producers and consumers though, then yes. But it's very cool to me that you can do without the spinlock in any useful case.
The BlockingWaitStrategy was mutex based IIRC.
I did this in 2011 or so, so it's been a decade. But my feelings are, "I'm quite certain that if I were to re-read the paper from start to finish, I'd end up feeling convinced of the position I just tried to convince you of."
If that's not true, then I'm simply a fool, and will happily concede. :) But! For now, I have to go look at a house that we're thinking of renting.
Sometimes you don't have time to do things perfectly and might use a spinlock when initializing some cache on first use... Only light contention, not great not, not terrible :).
It keeps using exchange() which swaps the old value in memory for your value and give back the old value, but it sets std::memory_order_acquire with the author apparently thinking that since this wants to acquire a lock this is enough.
But it isn't. The exchange() call is two memory operations, it's a load and a store, and so what you wanted here was Acquire and Release semantics ie. memory_order::acq_rel
What has been written is effectively Relaxed semantics for the store, and C++ doesn't do a great job of explaining that to programmers.
I spent a whole lot of time staring at this, and I was eventually able to convince myself that you're correct, there isn't any way for this to actually go wrong.
In the case where you're storing a different value than was already there, you just took the lock and even in relaxed ordering that is in fact an atomic operation, nobody else has the lock. In every other case who cares if you release, you didn't change anything anyway. The unlock() will release, and so anybody who subsequently acquires the lock will see the changes made under the lock.
Even after convincing myself this analysis is correct, I'm still scared that it's wrong, anyway. After all my previous analysis was wrong :/
It's not actually clear to me right now what part of the memory model would prevent the release store of an earlier unlock from being moved past the acquire load of a later lock.
Except that you wouldn't move it past a single acquire load, you'd potentially move it past an infinite number of acquire loads, and maybe then you run into formal language about forward progress?
There are similarly fun questions around hoisting an acquire load out of an otherwise empty loop...
Are you talking about different locks? In that case, yes, reordering can happen.
If it's about the same lock, then this can't happen because it would change the semantics of the code (you can't aquire the lock without releasing it first).
There must be some formal semantics reason which forbids it, and I think the reason boils down to the lock not being a single acquire load but instead a loop of acquire loads.
Unlock followed by lock is a store that is followed by a potentially infinite loop. If you move the store past the loop, and the loop happens to be or becomes infinite, then the effect of the store will never become visible, and that is an incorrect program transform because it'd be as-if you simply erased the store.
So you can probably move the store past any finite number of loads, but not past a potentially infinite loop.
The compiler can move a release store of variable A past an aquire load of variable B because it violates neither constraints.
The opposite is not true: it can't move an aquire load of variable A past a release store of variable B because it violates both contraints.
For a lock, aquire/release semantics are sufficient because its only job is to protect some shared piece of data, it doesn't care about other locks.
> reordering would be bad even with different locks because it can introduce deadlocks, as somebody has pointed out.
Do you have an example of such a deadlock? Maybe it's best to work with some actual code.
Thread 1 does A.lock, A.unlock, B.lock, B.unlock
Thread 2 does B.lock, B.unlock, A.lock, A.unlock
That's fine, but swap the middle pair of unlock followed by lock on both threads and you have a standard deadlock based on different lock nestings.
And to reiterate from my previous comment, I do think that transform is or should be forbidden. That's not for synchronization reasons per se, but because the transform can change the set of externally visible side effects of the code. This argument requires that a store with release semantics is considered to be an externally visible side effect. That makes intuitive sense to me, though I don't remember what e.g. the C++ standard actually says about that.
> C++ committee member Tony Van Eerd commented on reddit that with std::memory_order_acquire and two locks a and b; calls to a.unlock(); b.lock() and lock() for different locks could be reordered to b.lock(); a.unlock(); and introduce a potential deadlock. I don’t think that’s true. Reading section 6.9.2.1 Data races (paragraph 9) of the C++ standard] no loads or stores can bed moved into or out from between a load-acquire and store-release pair.
I think my stack overflow link above gives a more satisfying explanation on why the example can't deadlock.
Basically a compiler can not optimize a non-deadlocking program into a potentially deadlocking one.
Looks like you've been on the right track with regard to possible infinite loops.
You can still get this deadlock if you actually write the code like that: lock1.lock(); lock2.unlock();
https://github.com/boostorg/sync/blob/dfdf317f63d26fb40c703b...
It has been written by an expert in lockfree programming (Tim Blechmann)
https://github.com/boostorg/sync/commit/1b5aaa4a0b7ef4fad2a4...
BTW, the spinlock implementation is not affected.
I'm currently playing with multithreading right now. I'm implementing snapshot isolation multiversion concurrency control.
In theory you can avoid locks (except for data structure locks) by creating a copy of the data you want to write and detect conflicts at read and commit time. Set the read timestamp of a piece of data to the transaction timestamp (timestamps are just monotonically increasing numbers) that reads it. If someone with a higher transaction timestamp comes along, they abort and restart because someone got in before them.
At the moment I have something that mostly works but occasionally executes a duplicate. I'm trying to eradicate the last source of bugs but as with anything parallel, it's complicated due to the interleavings.
My test case is to spin up 100 threads, with each thread trying to increment a number. The end numbers should be 101 and 102. If there was a data race, then the numbers will be lower.
https://github.com/samsquire/multiversion-concurrency-contro...
It's kinda made to handle investigating and preventing such rare race conditions.
What’s not clear to me is if TLA+ can properly model the memory model. If I recall correctly, it doesn’t. You’re just testing your logic. That does still leave for some heavy lifting to be done.
You cannot use that in non-preemptible context.
spinlocks in systems with preemption are only allowed if the scheduler knows about them, though. Otherwise a throughput-optimizing scheduler may cause hold times in the range of seconds, by keeping an aquiring thead active with the holding thread asleep. Such a scheduler wouldn't be suitable for interactive workloads, but for non-networked batch tasks it should be quite efficient (due to a combination of calling the scheduling logic less often (thus wasting less time on it), and less cache contention with the application.
In interrupt handlers and such you may need to use spin locks, as you can't sleep either way. The rule about preemption still applies though, and aside from fairness issues, will take care of preventing pathological hold times.
Some people empirically find it improves their applications' performances in some situations.
Some environments don't have a scheduler or a "user-space", and so this implementation can suffice, but the problem with this post is that all of the testing and benchmarking are done in user-space, and hence the metrics are not very meaningful.
But more importantly, even with kernel backed waiting (e.g. using futexes) some userspace spinning can be important for performance. And then pretty much all the concerns from the spinlock apply there as well.
I never thought whether it could lead to deadlocks or not and it is an interesting question. I assume there musy ve some formal proof against it but I would have to think about it (my first hunch is that if the reordering could cause a deadlock, then the cose wasn't safe in any case, like not acquiring locks in a consistent order).
You can use a model checker that understands C++11 memory model.