13 ms·
Correctly implementing a spinlock in Modern C++
- AnanasAttack 5y agoCorrectly using a spinlock: Never when preemption is enabled
- notacoward 5y agoTherefore, also never when hold times and/or contention are non-trivial (i.e. obviating the PAUSE addition).
- namibj 5y agoThat one isn't actually as strict. Just because you used a spinlock doesn't mean you cause pathological degradation. 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.
- rigtorp 5y agoYes that's right!
- raphlinus 5y agoThe debate about whether further reordering is possible is an interesting one. I think it's evidence that it's basically not possible for humans to reason about the memory model. The best way to resolve it is to use an automated checking tool based on a formal model. Good choices are CDSChecker[1] or the newer CppMem[2]. [1]: http://plrg.ics.uci.edu/software_page/42-2/ http://plrg.ics.uci.edu/software_page/42-2/ [2]: http://svr-pes20-cppmem.cl.cam.ac.uk/cppmem/help.html http://svr-pes20-cppmem.cl.cam.ac.uk/cppmem/help.html
- RcouF1uZ4gsC 5y agoI think it may become even easier with C++20 and the addition of wait/notify to std::atomic https://en.cppreference.com/w/cpp/atomic/atomic/wait https://en.cppreference.com/w/cpp/atomic/atomic/wait
- Kranar 5y agoThat is a great way to implement a lock, but it won't be a spin lock (which is a good thing by the way). The wait function is a blocking call.
- sillysaurusx 5y agoOne neat thing is, you don't actually need a spinlock if you're using a ringbuffer. You can use atomic increment on a counter to claim a slot, then write to that slot. 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/ https://lmax-exchange.github.io/disruptor/ I learned about it in 2011-ish, and it deeply changed my perspective on high speed designs.
- ampdepolymerase 5y agoLong live the LMAX?
- sillysaurusx 5y agoAll hail! 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/ https://lmax-exchange.github.io/disruptor/)
- emerged 5y agoI spent several years developing lockfree algorithms and very often CAS loops are the empirically fastest solution. But as often, you can perform as good or better with atomic increments. The devil is in the details of what sort of tasks you’re managing and on which specific hardware.
- namibj 5y agoThe problem is that CAS loops in locking scenarios aren't an option if you're subject to preemption. Yes, true lock-free datastructures are allowed, but for many there are situations where you could practically encounter live locks (i.e., they aren't just a theoretical possibility for the access algorithm). Atomic increment is still fairly cheap/efficient and resolves many cases where you'd risk live lock by being wait-free in some aspects.
- gentleman11 5y agoWhat is your favourite resource for studying multithreaded programming?
- brtv 5y agoI quite liked the book "C++ Concurrency in Action: Practical Multithreading". It has been a few years since I've read it, but it gave me a better understanding of both C++ and concurrency in general.
- malkia 5y agoSpinlocks are great way of telling the kernel that you believe in small governments, and no regulations. I mean really, why should the kernel meddle in your user business?
- duped 5y agoBecause we live in a society and not every program can live it's life without affecting others
- BobbyJo 5y agoFavor local variables over global variables where able.
- duped 5y agoRAM is a global variable
- BobbyJo 5y agoI never leave L1.
- DSingularity 5y agoI never leave the trace cache. FEEB.
- gumby 5y agoI did once write a small program for the PDP-10 that ran entirely in the registers (which happened also to be addressable as the first 18 words of memory)
- tomcam 5y agoWhat did it do?
- samsquire 5y agoMultithreading sure is complicated. 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-control https://github.com/samsquire/multiversion-concurrency-contro...
- namibj 5y agoHave you heard of TLA+? If not, I suggest checking it out. It's kinda made to handle investigating and preventing such rare race conditions.
- im_down_w_otp 5y agoThat assumes that the problem is in their model, not their implementation.
- vlovich123 5y agoIn something like described, it sounds like the design part is where they’re at. If they were optimizing a working algorithm (eg selecting the best memory ordering for some operation), then I’d say they’re in the implementation phase. 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.
- 5y ago
- inshadows 5y agoIsn't it nonsense to do this in user-space? Your thread can get preempted at any moment.
- dataflow 5y agoCan happen at any moment != will happen most of the time
- inshadows 5y agoPreemption sure is non-deterministic from POV of the thread. But what's the point of it anyway? It's not like you handle HW interrupts in user-space and need to wait for some value in memory mapped register.
- Kranar 5y agoIt absolutely is, which is why the benchmarks posted should not be taken seriously. 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.
- tialaramex 5y agoIt's a micro-benchmark. "Everybody" can write a faster lock that wins on a micro-benchmark they built, and I guess if your goal is to feel smug then you're all done. If you actually have a performance problem, you need to benchmark the entire system that isn't performing as well as you'd like, then try to distil a small element you can optimise, micro-benchmark that, improve it using your micro-benchmark to measure progress, then apply the improvement to the large system, and then finally benchmark the larger system again to discover if the changes paid off. This will be much more time-consuming, but if you don't do this work then you're probably just masturbating. The larger system might be Twitter, or Hacker News, or Binding of Isaac, or a SatNav, but the performance of those larger things is what matters, if you micro-optimise your spinlock to be 5% better but now Hacker News falls over with half as many simultaneous users, you made it worse not better.
- jeffbee 5y agoFor a real battle-tested combination of spinlock and futex, see https://github.com/abseil/abseil-cpp/blob/master/absl/synchronization/mutex.cc https://github.com/abseil/abseil-cpp/blob/master/absl/synchr...
- fisf 5y agoJust pointing out: while this implementation is absolutely non- trivial to study, everytime I take a look at the abseil source, I am delighted with the quality of inline comments.
- rigtorp 5y agoWell isn't that just a normal lock/mutex of the "lightweight" type (only enter kernel on contention)? You cannot use that in non-preemptible context.
- tialaramex 5y agoNotice that this code probably has a bug. [Edited to add: spacechild1 says it doesn't, and I now believe them] 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.
- deleted 5y ago[deleted]
- spacechild1 5y agoNope, std::memory_order_acquire is perfectly fine here. Just because an atomic operation involves a store doesn't necessarily mean you always need/want to synchronize with that store. In this case, we only need to make sure that subsequent code is not reordered before the atomic load, hence the aquire semantics.
- tialaramex 5y agoThanks, I guess? 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 :/
- atq2119 5y agoThis stuff is so subtle. 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...
- amelius 5y agoHow would you test this?
- rigtorp 5y agoDeploy to production :). You can use a model checker that understands C++11 memory model.
- gpderetta 5y agoRegarding moving loads and stores into acq/rel critical sections, this is possible, well studied and documented; it is known roach motel reordering since the Java MM standardisation, and generally considered safe. 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).
- MichaEiler 5y agoI'm surprised nobody has mentioned Linus's rant about spinlocks in userspace: https://www.realworldtech.com/forum/?threadid=189711&curpostid=189752 https://www.realworldtech.com/forum/?threadid=189711&curpost...
- thunkshift1 5y agoThere should be site like linus-rants.com
- rigtorp 5y agoHis rant only applies to preemptible threads. If you don't have preemptible threads spinlocks works great. The linux kernel uses them in non-preemptible contexts.