3 ms·
> Is 3 atomics on the same cache line a legit problem? This is a commonly known problem called false sharing. https://en.wikipedia.org/wiki/False_sharing https
by dragontamer 7y ago
> Is 3 atomics on the same cache line a legit problem?
This is a commonly known problem called false sharing. https://en.wikipedia.org/wiki/False_sharing https://en.wikipedia.org/wiki/False_sharing
To be fair: I don't know how these particular atomics work, maybe they're all on their own cache lines, and 192 bytes are used up for those three atomics so that things are done properly (unlikely, but possible). But atomics in my experience usually assume the "external" programmer figures out the buffering issue to prevent false sharing.
2. These are atomics declared to be SeqCst memory ordering. 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.
3. Well-written spinlocks are absurdly fast. Benchmark them if you don't believe me. The assembly in x86 is
Lock:
while (AtomicExchange(spinlock, true) != false) hyperthread_yield(); // loop until you grab false.
acquire_barrier(); // Prevent reordering of memory
Unlock:
release_barrier(); // Prevent reordering of memory. NOP on x86 but important in ARM / POWER9
spinlock=false; // Don't even need an atomic here actually
Literally one assembly instruction to unlock, 3-assembly instructions to lock (the atomicexchange + loop) + hyperthread_yield if you wanna play nice with your siblings (reduces performance for you, but overall makes the whole system faster).
From a cache-perspective, the spinlock will play nice with L1 cache (if a thread unlocks, then locks again before a new thread comes in, it all stays local to L1 and no cross-thread communication occurs).
So pretty much every aspect of the hypothetical spinlock implementation is faster in my mind. I don't really need to benchmark to see which one is faster.
EDIT: At bare minimum: because the Spinlock will be properly written using Acquire / Release half-barriers, they will be ABSOLUTELY faster than SeqCst Atomics. You'll need to use Acquire/Release Atomics if you want to "keep up" with the Acquire/Release based Spinlocks.
- vardump 7y ago> 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. :)
- dragontamer 7y agoYes, 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 :-)
- vardump 7y agoHmm... are you sure your unlock barrier is in the right place? ;-) Edit: I see you fixed that too.
- dragontamer 7y agoUhhh... now it is :-) This stuff is always hard...
- vardump 7y agoIf 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.
- dragontamer 7y agoHa! 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.
- vardump 7y agoIndeed, 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.
- forrestthewoods 7y ago> 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 https://github.com/polyfractal/bounded-spsc-queue
- vardump 7y agoIt 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 https://en.wikipedia.org/wiki/MOESI_protocol
- dragontamer 7y agoIf 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 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.
- amluto 7y agoA 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;
- gpderetta 7y agoif 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.
- magicalhippo 7y ago> 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.
- tntn 7y ago> 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.
- dragontamer 7y agoYou 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_systems_100941_0100_en.pdf 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#Sequentially-consistent_ordering 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.