from Hacker News

Correctly implementing a spinlock in Modern C++

by symisc_devel on 6/25/21, 10:58 PM with 97 comments

• by malkia on 6/26/21, 1:35 AM

  Spinlocks 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?

• by sillysaurusx on 6/26/21, 1:22 AM

  One 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/

  I learned about it in 2011-ish, and it deeply changed my perspective on high speed designs.

• by tialaramex on 6/26/21, 7:53 AM

  Notice 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.

• by raphlinus on 6/26/21, 1:07 AM

  The 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/

  [2]: http://svr-pes20-cppmem.cl.cam.ac.uk/cppmem/help.html

• by samsquire on 6/26/21, 2:04 AM

  Multithreading 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-contro...

• by jeffbee on 6/26/21, 4:10 AM

  For a real battle-tested combination of spinlock and futex, see https://github.com/abseil/abseil-cpp/blob/master/absl/synchr...

• by AnanasAttack on 6/26/21, 12:53 AM

  Correctly using a spinlock: Never when preemption is enabled

• by inshadows on 6/26/21, 3:32 AM

  Isn't it nonsense to do this in user-space? Your thread can get preempted at any moment.

• by RcouF1uZ4gsC on 6/26/21, 1:20 AM

  I 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

• by gpderetta on 6/26/21, 9:22 AM

  Regarding 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).

• by gentleman11 on 6/26/21, 1:31 AM

  What is your favourite resource for studying multithreaded programming?

• by MichaEiler on 6/26/21, 11:52 AM

  I'm surprised nobody has mentioned Linus's rant about spinlocks in userspace: https://www.realworldtech.com/forum/?threadid=189711&curpost...

• by amelius on 6/26/21, 8:58 AM

  How would you test this?