Compare-and-swap and memory ordering

What is the ABA problem, in one sentence I can say in a round?

A compare-and-swap checks that a value is the same as when you read it, not that nothing happened to it in between, so a pointer that went from A to B and back to A passes the check although the structure behind it changed. In a lock-free stack that means a thread swings the head to a next pointer it read before the node was popped, freed and reused, and the stack ends up holding a node that was removed. The usual fixes are a version tag beside the pointer that every successful swap bumps, or a reclamation scheme such as hazard pointers or epochs that never reuses a node another thread may still be looking at. In a language with a garbage collector the reuse cannot happen while you hold a reference, so the pointer form of the bug does not arise there.

Why does a compare-and-swap loop not need a lock?

Because the swap itself is the one step that cannot be split. The loop reads the current value, works out the new one, and asks the hardware to write it only if the value is still the one it read. If another thread got there first, the swap refuses and the loop reads again. Nobody waits for anybody: a thread that loses a race retries, and the thread that won has already finished. What you give up is a bound on retries under heavy contention, and the ability to update two words together without extra machinery.

Is acquire and release enough, or do I need sequential consistency?

Acquire and release are enough when one thread publishes data and another reads it: the writer stores the data, then stores a flag with release, and a reader that sees the flag with acquire is guaranteed to see the data. They are not enough when two threads each write one variable and then read the other’s, the pattern behind Dekker-style mutual exclusion. There both reads can return the old value unless the operations are sequentially consistent. If you cannot say which of the two patterns you have, use sequential consistency, which is the default in C++ and what Java volatile and Go’s sync/atomic give you.

Can I write a lock-free data structure in Python?

Not in the sense a systems round means. Python gives you no compare-and-swap on a shared word and no way to choose a memory ordering, so a round that asks for a lock-free queue or stack is taken in C++, Rust, Java or Go. What Python does give you is a lock and queue.Queue, and for Python code those are the right tools. The model on this page runs a lock-free stack and a store buffer so you can watch the mechanism, but the code you would write in the round is in another language.

What is false sharing, and how would I find it?

Two threads each write their own variable, but the two variables sit in the same cache line, so every write by one core takes the line away from the other and the threads slow each other down without sharing any data. It shows up as code that gets slower when you add threads although nothing is locked. On Linux, perf c2c reports cache lines that several cores keep writing. The fix is to put each hot variable on its own line, by padding or by alignment: C++17 names the distance std::hardware_destructive_interference_size.