Hacker News Reader

A good spinlock, as Linux uses internally for example, is much more complicated. But, if you know there are only two relevant threads, you can get decent performance with a simple spinlock.

However, do not use AtomicExchange in a loop like this. When you are waiting, you always want to wait with the target cache line in the shared state, and AtomicExchange will force it to be exclusive. Performance will go down the drain. Instead, do something like:

    if (value looks good)
      AtomicExchange;
      Loop again if you lost the race;
    else
      Loop again;

if you expect your lock to uncontended, forcing an exchange might be better. You can then switch to the test and test and set pattern of failure.

> That means the L1 (and probably L2) caches are flushed every time you read or write to them on ARM systems. (x86 has stricter guarantees and almost "natively" implements SeqCst, so you won't have as many flushes on x86). The cache must be flushed on EVERY operation declared SeqCst. Its absurdly slow, the absolute slowest memory model you can have.

SeqCst is definitely the slowest memory model to use, but the bit about flushing caches doesn't sound right. SeqCst on a processor with a relaxed memory consistency model usually 'just' requires core-local operations on the load/store buffers - usually draining the buffers (but that is not strictly necessary). It isn't necessary to flush caches to enforce consistency if the memory system has coherent caches.

Fences for sequential consistency are certainly heavy on ARM and it will show up as poor performance, I'd be very surprised if any aarch64 processor flushed any cache on LDAR/STLR.

I'd appreciate a correction if I've misunderstood or if there are modern ARM processors that do flush L1 on LDAR/STLR/DMB ISH.

You bring up some good points, and have forced me to consult documentation to double-check a lot of intricate details.

I'm using the following as a reference: https://static.docs.arm.com/100941/0100/armv8_a_memory_syste...

> Fences for sequential consistency are certainly heavy on ARM and it will show up as poor performance, I'd be very surprised if any aarch64 processor flushed any cache on LDAR/STAR.

I agree. But LDAR / STLA are weaker than full sequential consistency. They're only acquire/release consistency.

So its the DMB ISH that I'm curious about. If the memory is never flushed out of L1 cache, how can you possibly establish a total sequential ordering with other threads?

EDIT: I had a bad example here originally. Lets use the SeqCst example from here instead: https://en.cppreference.com/w/cpp/atomic/memory_order#Sequen...

    std::atomic<bool> x = {false};
    std::atomic<bool> y = {false};
    std::atomic<int> z = {0};
     
    void write_x()
    {
        x.store(true, std::memory_order_seq_cst);
    }
     
    void write_y()
    {
        y.store(true, std::memory_order_seq_cst);
    }
     
    void read_x_then_y()
    {
        while (!x.load(std::memory_order_seq_cst))
            ;
        if (y.load(std::memory_order_seq_cst)) {
            ++z;
        }
    }
     
    void read_y_then_x()
    {
        while (!y.load(std::memory_order_seq_cst))
            ;
        if (x.load(std::memory_order_seq_cst)) {
            ++z;
        }
    }
     
    int main()
    {
        std::thread a(write_x);
        std::thread b(write_y);
        std::thread c(read_x_then_y);
        std::thread d(read_y_then_x);
        a.join(); b.join(); c.join(); d.join();
        assert(z.load() != 0);  // will never happen
    }

Variable x is being written to by "write_x". While variable y is being written to by "write_y" thread. Assume they're on different cache-lines.

* Thread C may see "X=True THEN Thread C THEN Y=True" (Formally: Thread A happened before Thread C happened before Thread B). In this case, Z=0.

* Thread D may see instead "Y=True THEN Thread D THEN X=True" (Formally: Thread B happened before Thread D happened before Thread A). In this case, Z=0.

This apparent contradiction is possible in Acquire-Release consistency, but not possible in Sequential Consistency. LDRA and STLR provide only acquire-release consistency.

So now lets ask: how do you implement sequential consistency?

There's no way for Thread A or B to do things correctly from their side. Thread A independently writes "X" in its own leisure, not knowing that Thread "B" is writing a "related" variable somewhere else called Y. There is no opportunity for A or B to coordinate with each other: they have no idea the other thread exists.

---------

To solve this problem, I imagine that an MESI cache will simply invalidate the cache (which "forcibly ejects" the data out of the core running Thread A and Thread B). Whatever order Thread A and Thread B create (X then Y... or Y then X) will be resolved in L3 cache or DDR4 RAM.

Now... perhaps there's a modern optimization that doesn't require flushing the cache? But that's my mental model of sequential-consistency. Its slow, but that's the only way I'm aware of that establishes the strong SeqCst guarantee.

---------

However, you are right to challenge me, because I don't know. If it makes you feel better, I'll "retreat" to the more easily defended statement: "Load/Store Buffers of the CPU Core need to be flushed every time you SeqCst load/store on ARM systems" (which should effectively kill out-of-order execution in the core).

The question I have is how does L3 cache perceive a total-ordering without the L1 cache flushing? I guess you've given me the thought that its possible for it to happen, but I'm not seeing how it would be done.

There is no "cache flushing" when barriers or other instructions are used to ensure seqcst on any system I am aware of. Such a system would perform so slowly as to be practically unusable.

At most there is usually a local dispatch stall while store buffers (not caches) are flushed and pending loads complete. In some scenarios, like a cache-line crossing atomic operation on x86, you might need additional non-local work such as asserting a lock signal on an external bus. There might be some other work such as ensuring that all arrived invalidation requests have been processed.

Still, you are talking in the range of 10s or maybe low 100s of cycles. Nothing like a cache flush which would probably be an impact of 10,000s of cycles or more (depending on how large the caches are and where the data to reload them comes from).

> There is no "cache flushing" when barriers or other instructions are used to ensure seqcst on any system I am aware of.

Good to know. I've seen enough of your other posts to trust you at your word.

BTW: I'll have you know that AMD GPUs implement "__threadfence()" as "buffer_wbinvl1_vol", which is documented as:

> buffer_wbinvl1_vol -- Write back and invalidate the shader L1 only for linesthat are marked volatile. Returns ACK to shader.

So I'm not completely making things up here. But yes, I'm currently looking at some GPU assembly which formed the basis of my assumption. So you can mark at least ONE obscure architecture that pushes data out of the L1 cache on a fence / memory barrier!

GPU L1 caches are typically not coherent, so flushing them is necessary on GPU architectures.

Right, I could have been clearer that I was restricting my comments to general purpose CPUs.

Exactly.

I just wanted to add that #StoreLoad fences (i.e. mfence on x86 for example), as far as I know do not usually actually flush the store buffer per-se. They just stall the pipeline (technically they only need to stall any load) until all stores prior to the fence have been flushed out by the normal store buffer operations, i.e. the store buffer is always continuously flushing as fast as possible all the time.

You didn't imply otherwise, but I wanted to clarify that because I have seen comments elsewhere and in code claiming that a fence would make a prior store visible faster (i.e. the fence was added to improve latency instead of being required for correctness), which I do not think it is the case, at least at a microarchitectural level (things are more complex when a compiler is involved of course).

Yes, that's right. As far as I know, on modern Intel chips, atomic operations block both the store and load ports, but lets other ops through. I think allocation blocks when the first load/store arrives when the pipeline is in that state - so you can hide a lot of the cost of atomic operations by ensuring there is a long-as-possible series of non-load/store operations after them (of course, this is often not possible).

mfence used to work like that, but due to various bugs/errata was "upgraded" to now block execution of all subsequent instructions until it retires (like mfence) in addition to it's store draining effects. So mfence is actually a slightly stronger barrier than atomic operations (but the difference is only apparent with non-WB memory).

If you want to be totally pedantic, it may be the case that that mfence or another fencing atomic operation results in the stores being visible faster: because they block further memory access instructions, there can less competition for resources like fill buffers, so it is possible that the stores drain faster.

For example, Intel chips have a feature where cache lines targeted by stores other than the ones at the head of the store buffer can be fetched, so called "RFO prefetch" - this gives MLP in the store pipeline. However, this will be limited by the available fill buffers and perhaps also heuristics ramping back this feature when fill buffers are highly used even if some are available (since load latency is generally way more important than load latency).

So something like an mfence/atomic op blocks later competing requests and gives stores the quietest possible environment to drain. I don't think the effect is very big though, and you could achieve the same effect by for e.g., just putting a bunch of nops after the "key" store (although you wouldn't know how many to put).

Sorry that should say "(like lfence)" not "(like mfence)".

> As far as I know, on modern Intel chips, atomic operations block both the store and load ports, but lets other ops through. I think allocation blocks when the first load/store arrives when the pipeline is in that state.

That's great to know. I suspected that was the case and they had moved from the stall the pipeline approach, but I had never tested it.

As a minor note, LDAR and STLR are poorly named and are documented as providing multicopy atomicity in addition to acquire-release semantics and are the recommended way to implement C11 SeqCst.

Some of the below is almost certainly incorrect, apologies in advance.

Your example is more or less the Independent Read Independent Write (IRIW+syncs) litmus test. The short version is you don't need to flush any caches to get IRIW to always obey sequential consistency.

Originally, ARMv8 was non-multicopy atomic, but AFAIK there was never any non-multicopy atomic implementation, and a revised spec requires multicopy atomicity. This matters in terms of thinking about how sequential consistency for IRIW is implemented, but it works either way.

The core idea is that the DMB ISH ensures that the value that the first reads in threads c and d receive are visible to all threads. With multicopy atomicity this is free - e.g. if Thread C reads true from X, then all other threads will also read true.

(-> below indicates a sequenced before relationship)

So you get

Thread C: read X as true -> dmb ish -> read Y as false

Thread D: read Y as true -> dmb ish -> read X as false

However, you get some extra edges. If either thread reads X as false, then X as true is not visible to any thread. So you get

(Thread C reads y as false) -> (Thread D reads Y as true)

(Thread D reads x as false) -> (thread c reads x as true)

These are enough to produce a cycle that forbids the z=0 case.

Essentially, threads A and B have to make sure that once any thread sees its write, all threads see its write. (Or alternatively the dmb ish on thread C and D have to ensure that future memory accesses from that thread don't proceed until the prior read is consistent to all cores).

Thanks for the in-depth answer!

> Essentially, threads A and B have to make sure that once any thread sees its write, all threads see its write

Gotcha. So that's where cache snooping comes in and why that's sufficient to handle the case. I think I see it now. Again, thanks for breaking it down for me. So it appears the only thing necessary is for the DMB ISH to ensure that all cache-snoop messages are "processed" before proceeding.

> I don't really need to benchmark to see which one is faster.

I know that iterating an Array is radically faster than iterated a LinkedList. But I also know this because I’ve seen the difference first hand. Countless times over the years in fact. I even have a bit of a gut feeling for how much slower it can be.

This case I don’t have the same level of experience. I’m sitting in an airport on my tablet right now. So I can’t throw any quick benchmarks together.

Suffice to say I very much would like to see an actual for reals comparison. Because I haven’t dealt with this before and even if I’m convinced one way is faster seeing is believing! Performance benchmarks are almost always surprising.

Edit: from Reddit here is a different spsc-ringbuffer that may be more to your liking! https://github.com/polyfractal/bounded-spsc-queue

It needs to be slow, because each core will need to coordinate with all other contending cores.

No matter what, the system must ensure all cores in the system have a coherent view of the cache line in question. So there must be communication involved.

For example in MOESI protocol [0], it's not enough to have the cache line in exclusive state, you need to have it in owned state. So the core needs to broadcast to all other participating (contending) cores.

You can simply saturate CPU internal core to core ring buses. Even worse between CPU sockets (multiple separate physical chips), because there's rather limited capacity to carry the coherency traffic.

https://en.wikipedia.org/wiki/MOESI_protocol

If you have spare time, the Pikus talks at CPPCON talk about the performance hits associated with various primitives.

https://www.youtube.com/watch?v=9hJkWwHDDxs

This is the one you want, with benchmarks associated with everything. Of course, benchmark on your own system too, and learn hardware performance counters (!!). This sort of stuff gets into nanosecond-level measurements, so learning to use the hardware profiler of your CPU really, really helps to see these details.

Honestly, because of how intricate the L1 / L2 caches can be on a modern system... learning hardware performance counters while you're measuring benchmark code / benchmark tests like this is helpful.

> spinlock=false; // Don't even need an atomic here actually

No, you'll need a memory barrier there. On x86, sure you get away for free, because x86 memory model says stores are never reordered with other stores.

On practically all other systems you'll need equivalent of C++ atomic "memory_order::release" to prevent stores from being reordered with other stores.

Otherwise you're in for a surprise. Without a (half) barrier, it'll be buggy on ARM, POWER, MIPS, etc.

Edit: I see you added the barriers. Sneaky. :)

Yes, good point.

The obscure details are always hard to remember... that particular example is x86 specific.

I probably should edit in the memory barriers.

> Edit: I see you added the barriers. Sneaky. :)

You reminded me about them. Lol. Thanks for the reminder :-)

Hmm... are you sure your unlock barrier is in the right place? ;-)

Edit: I see you fixed that too.

Uhhh... now it is :-)

This stuff is always hard...

If you still wanted to fine tune it a bit further, you could have used a WeakAtomicExchange (?). Performs better on some systems, and a strong one is not required here.

On x86, it's of course same.

Ha! I think I'm finally correct against you :-)

"AtomicExchange" is just a swap. It is NOT a compare-and-swap, so there's no Weak vs Strong version. A pure-swap is probably faster to implement than a compare-and-swap in microcode, but I admit that I've never actually tested this theory.

Indeed, oops! Brains in pattern matching mode. :-)

Then again, I think XCHG (has implicit atomic LOCK, no need for LOCK prefix) is kinda x86 only thing.

> pure-swap is probably faster to implement than a compare-and-swap in microcode, but I admit that I've never actually tested this theory.

I don't think there's practical performance difference, because inter-core cache coherency traffic is going to dominate by far.

For others that are curious, there's an example of lock XCHG spin lock for amd64 here:

https://en.m.wikibooks.org/wiki/X86_Assembly/Data_Transfer

Ed: well technically x86 I guess - not sure if there's improvements to be made for amd64?

That example is based on "lock cmpxchg" (x86 compare-and-swap). Not on atomic swap, like what "xchg" based one [0] above does.

Someone else [1] also had a good point how "xchg" can cause more contention, because it generates stores. If loads were used for waiting instead, the cache line could have remained in much cheaper shared state on the waiting core.

But regardless benchmark on as many system types as you can get your hands on. No matter how well you know the architecture and you read on the internet, real software systems and CPUs are sometimes rather unpredictable beasts.

[0]: https://news.ycombinator.com/item?id=20098978

[1]: https://news.ycombinator.com/item?id=20099764

Hm, so the above:

while (AtomicExchange(spinlock, true) != false) hyperthread_yield(); // loop until you grab false.

Does do a cmp (the while construct) - but only the XCHG is atomic. While the other example does both CMP and XCHG as an atomic "unit"/op?

First of all, I think "AtomicExchange" will return previous value of "spinlock". First parameter ("spinlock" here) is actually a pointer to "spinlock", not the value itself. Second parameter is what should be swapped with the memory address.

So it atomically stores true to "spinlock" and returns whatever value it contained previously. While-loop is comparing against the previous value, what was swapped from memory.

Unless "spinlock" wasn't false in the first place, the loop can only terminate when the other thread eventually stores false to "spinlock". After that point, one of the waiting threads will suddenly swap that false into true and notice the previous value was false, meaning the lock was successfully acquired.

So until the other thread releases it by storing false to "spinlock", there'll be just endless swaps of true.

I wouldn't recommend using a spinlock like this, because it probably causes a lot of unnecessary and avoidable cache coherency traffic [0] between all of the contending CPU cores.

[0]: Unless, of course, CPUs contain some instruction stream pattern matching to detect this situation (swapping in same value the memory address contained before) and optimize the endless stores away. Wouldn't surprise me at all if such optimizations existed on modern x86 silicon...

Thank you. Still a little unclear on how the code maps to actual x86_64 assembler though. There's generally no "return" value - so I'm curious what the machine code would cmp on.

I suppose one puts the value to write in a registry, then if the XCHG succeed, the "return" value will be in the registry. And the only way to detect success is if the value has changed (which is OK, overwriting a value with the same value... Is a logical noop...).

I suppose I could try something like the above, or:

http://www.cplusplus.com/reference/atomic/atomic/exchange/

And look at the output...

See my quick completely untested idea above in thread how it'll probably be in x86[-64] assembler.

Note: moved this from thread leaf here, because it broke the page formatting.

Can't check any reference now, but I think the whole while loop is roughly:

  loop:
    mov eax, 1 ; "true"
    ; edi points to &spinlock
    xchg [edi], eax 
    ; eax is AtomicExchange retval
    test eax, eax
    jnz loop ; while(eax != false)
    ; we've acquired the lock

X86-64 version is same, except the address is probably in a 64-bit register, like RDI. Although this would also work in 64-bit mode, if the pointer just happens to be in the lower 4 GB.

Actually, the barriers matter also because evil compilers like to mess with reordering loads and stores.

If you write:

  a = 5;
  b = 4;

... without any barriers compiler can actually generate code that performs "b = 4" first. Even if the barriers get compiled into nothing, they can still affect the generated code load/store order.

I know you know this, but just to make sure even those people reading this later who think their software is only going to run on x86 ever need to watch out.

I think std::atomic / std::memory_order are pretty useful abstractions to get these things right.

> Well-written spinlocks are absurdly fast

They're fast if there's low contention. If you have high contention then they burn CPU cycles needlessly and can be significantly slower than something more clever like Windows' CriticalSection.