Under heavy contention, a shared counter updated with an atomic fetch-and-add instruction often achieves much higher throughput than an equivalent compare-and-swap retry loop that computes the same result. Explain why.
answer
- fetch-and-add cannot fail: N ops for N updates
- CAS loop: losers retry, attempts grow with threads
- failed attempts still steal the cache line
- fetch-and-add is wait-free, CAS loop only lock-free
- loop is for conditional / packed / state-transition updates
basics
~20 sFetch-and-add cannot fail: every attempt completes, so N threads need N operations. A compare-and-swap loop discards work whenever another thread wins, so attempts grow superlinearly with contention, and each wasted attempt still costs an exclusive cache-line transfer. Fetch-and-add is also wait-free rather than merely lock-free.
solid answer
~60 sBoth take exclusive ownership of the cache line, so a single uncontended operation costs about the same. The difference is the **failure rate**. Fetch-and-add is unconditional: the hardware adds the delta to whatever is there and returns the previous value. There is no expected value, so there is nothing to be stale, and every operation succeeds first time. N increments cost N atomic operations regardless of how many threads are involved — and it is wait-free, giving each thread a bounded completion time. A compare-and-swap loop is conditional. Each thread reads, computes, and only wins if nobody intervened. With many threads on one line, most attempts fail; each failed attempt still pulled the line into exclusive state, burning interconnect bandwidth and evicting it from the winner. Wasted attempts scale up as contention rises, so throughput can flatten or fall as cores are added. The practical rule: if hardware offers a direct primitive for your operation — add, exchange, bitwise or — use it, and reserve the compare-and-swap loop for updates with no direct instruction, such as conditional or multi-field transitions.
code
text · 6 linesfetch-and-add: CAS loop:
fetch_add(c, 1) loop:
# always succeeds old = c.load()
# 1 atomic op if CAS(c, old, old+1): break
# under N-way contention,
# expect many failed roundsgo deeper
Know that fetch-and-add always succeeds while a compare-and-swap can fail and must be retried, so the loop does more work when threads collide.
Explain that failure rate rises with the number of contending threads, so attempts grow superlinearly while fetch-and-add stays one operation per update.
Bring in cache-line exclusivity: failed attempts still steal the line and slow the eventual winner, and name the wait-free versus lock-free distinction.
Treat a hot shared counter as a design smell — discuss per-thread or sharded accumulation, batching, and what retry-rate telemetry you would use to decide.
## Same cost per operation, very different number of operations On a cache-coherent machine, any atomic read-modify-write requires the executing core to hold the target cache line in an exclusive (or modified) state. That means the line must be invalidated in every other core's cache and transferred, which is a bus or interconnect round trip costing far more than an ordinary cache hit. Both fetch-and-add and compare-and-swap pay this. Where they diverge is how many such transfers are needed to accomplish K logical updates. **Fetch-and-add** is unconditional. It has no expected-value parameter, therefore no notion of staleness, therefore no failure. K increments require exactly K atomic operations, no matter how many threads issue them. Additionally, the primitive is *wait-free*: each thread finishes in a bounded number of steps regardless of what other threads do, so latency has a real upper bound rather than a probabilistic tail. **A compare-and-swap loop** is conditional. A thread reads value v, computes v+1, and installs it only if the location is still v. Under contention most attempts lose. Consider N threads all trying at once: one wins per round and the rest must re-read and retry, so a naive analysis gives on the order of N-squared attempts for N increments — and the constant is not small, because every failed attempt performed a full exclusive line acquisition and thereby slowed the winner too. Throughput can *decrease* as you add cores past a modest count. ## Why the loser's work is not merely wasted but harmful This is the part candidates miss. A failed compare-and-swap is not a free no-op. To attempt it, the core had to take the line exclusively, which invalidated it everywhere else — including in the cache of the thread that was about to succeed. The failed attempts actively increase the cost of the successful ones. That is the mechanism behind CAS storms: contention on a single line degrades everyone, and the degradation grows with the number of participants rather than staying constant. Some hardware makes this even more lopsided by implementing atomic addition *remotely* — performing the add at a shared cache or memory controller rather than migrating the line to the requesting core. Where that exists, contended fetch-and-add scales dramatically better than any load-compute-store protocol, because the line never ping-pongs at all. ## When the compare-and-swap loop is still the right tool The loop is not a mistake; it is the general mechanism. Use it when: - **The update is conditional.** Atomic maximum, saturating decrement ("decrement unless zero"), "take a permit if any remain" — none of these are expressible as an unconditional add. Reserving a slot with fetch-and-add and then correcting an overshoot is possible, but the transient over-count is visible to other threads and usually unacceptable. - **The update is a state transition.** Moving a state machine from PENDING to RUNNING only if it is still PENDING is precisely a compare-and-swap. - **The value is a packed structure.** Updating several fields packed into one word, or a pointer plus a version stamp, needs compare-and-swap. - **Contention is low.** With little contention, failures are rare and the loop is effectively a single operation; the difference is noise. Optimising this case is premature. ## Practical guidance First, prefer the most specific primitive the hardware and the platform give you for the operation you actually need: add, exchange, bitwise or/and. Second, if you must loop, make the body trivial and consider skipping the attempt when it would be a no-op (checking the current value first turns a write into a cheap shared read for the common case). Third, if contention remains the bottleneck, the answer is usually not micro-tuning the loop but removing the shared hot location — per-thread accumulation, striping, or batching updates and applying them periodically. Finally, measure. Retry rate is the diagnostic: instrument how many attempts per successful update the loop takes. A ratio near one means contention is not your problem and the loop is fine; a ratio in the tens means you are burning interconnect bandwidth and should change the design, not the backoff constant.
- Give an update that genuinely cannot be expressed as a fetch-and-add and therefore needs a compare-and-swap loop.A saturating decrement such as 'decrement only if the value is greater than zero', which is how you take a permit from a bounded pool. An unconditional fetch-and-add would drive the counter negative, and although you could add one back afterwards, the negative value is momentarily visible to other threads and can let them make wrong decisions. Atomic maximum and any conditional state transition have the same shape.
- You cannot change from a compare-and-swap loop to fetch-and-add. What else reduces contention cost?Add exponential backoff with jitter so losers stop hammering the line while a winner completes; check the current value with a cheap shared read and skip the attempt when it would be a no-op; batch many logical updates into one atomic operation; and above all reduce sharing by giving each thread or shard its own cell and combining only when a total is read. The structural fixes usually dominate the tuning ones.
A ticket dispenser versus a whiteboard tally. Everyone pulls a ticket in one motion and always gets one; with the whiteboard, several people read the total, and all but one have to erase their work and start again.
saying these in an interview costs you the question
- Believing a failed compare-and-swap is cheap because it does not write
- Assuming fetch-and-add and a compare-and-swap loop have the same cost profile under contention
- Claiming compare-and-swap loops always scale because they are lock-free
- Not knowing fetch-and-add is wait-free while a retry loop is not
- Reaching for backoff tuning before questioning whether the location should be shared at all