You Can Do Any Kind of Atomic Read-Modify-Write Operation | Hacker News Reader

You Can Do Any Kind of Atomic Read-Modify-Write Operation

preshing.com

18 pointssigna119 comments

When spinning on an atomic operation, you should add some kind of yield operation. The "pause" instruction in x86 at least. On newer CPUs a "monitor" and "mwait" can work a little better (but may not be available in user space). Do not use thread_yield or other kernel calls, because at that point you're better off using a mutex.

When spinning on atomics, the interconnect between cores needs to do a lot of work synchronizing the memory. When adding a pause or monitor instruction, the core will give an opportunity for the other hyperthread in the same core to execute, reducing the amount of churn on the interconnect.

Counterintuitively, adding a "pause" in the spin loop will make the program faster by yielding the CPU core for a few nanoseconds.

That's interesting. Any references about this? What about ARM CPUs?

See Intel Programmer's manual (vol 3a iirc) about pause, monitor and mwait. Not sure about ARM, that architecture has different rules of cache coherence and no hyperthreading and you need to add explicit memory barriers.

It looks like the examples are broken.

  uint32_t fetch_multiply(std::atomic<uint32_t>& shared, uint32_t multiplier)
  {
      uint32_t oldValue = shared.load();
      while (!shared.compare_exchange_weak(oldValue, oldValue * multiplier))
      {
      }
      return oldValue;
  }

If shared.compare_exchange_weak() fails because of a concurrent writer, then the while loop will never exit (unless another writer sets the value of shared to oldValue).

What the author wants is something like this:

  uint32_t fetch_multiply(std::atomic<uint32_t>& shared, uint32_t multiplier)
  {
      while(1) {
          uint32_t oldValue = shared.load();
          if(shared.compare_exchange_weak(oldValue, oldValue * multiplier)) {
              return oldValue;
          }
      }
  }

The other examples have the same problem.

Other articles in the blog had subtly incorrect or at least suspicious examples too. They probably work with the toy examples but may fail under real world timings.

This is an issue with multi threaded programming. Only way to test is to run stress testing, with various simulated payloads, for minutes at a time, preferably on different cpu architectures.

I'm pretty sure that example is actually fine - if there's a concurrent writer, the modified value will be loaded into oldValue. Repeating shared.load is unnecessary since that operation occurs as part of compare_exchange_weak.

Thanks, my mistake.

I've been bit by this before. I sometimes wish you had to mark "reference-of" just like you have to mark "address-of" with &.

It's obvious that blah(&foo) might modify foo, without needing to examine the signature of blah().

The tradeoff is a bit of code clutter when you add a symbol (something like shared.compare_exchange_weak(%oldValue, oldValue * multiplier)), and a violation of DRY, since the information provided by this symbol would be redundant.

Here's just to back up atomic_cheese's answer with some references:

Atomically, compares the contents of the memory pointed to by object or by this for equality with that in expected, and if true, replaces the contents of the memory pointed to by object or by this with that in desired, and if false, updates the contents of the memory in expected with the contents of the memory pointed to by object or by this.

http://open-std.org/JTC1/SC22/WG21/docs/papers/2011/n3242.pd...

Atomically compares the object representation of this with the object representation of expected, as if by std::memcmp, and if those are bitwise-equal, replaces the former with desired (performs read-modify-write operation). Otherwise, loads the actual value stored in this into expected (performs load operation). Copying is performed as if by std::memcpy.

http://en.cppreference.com/w/cpp/atomic/atomic/compare_excha...

I remember how I was surprised to find that you can implement compare-and-swap purely in software (with some caveats :) but still, IMO, preserving the idea). See, e.g. Peterson's algorithm. It does have a lock, but only for finite (and brief, if you will) moment, and, wrapped as procedure, is externally lock-free.

You still rely on ability to locally order operations in time (i.e., you have to be sure that you - the CPU - reads from that memory cell strictly after it completed writing into this one) - so there are restrictions for modern CPUs. You might have issues if you want to synchronize many threads/processes - as the locking delay may become too long. But still.

Reply on news.ycombinator.com