1 Concept

Compare-and-swap is an atomic primitive that operates on a single memory location. It checks whether the current value matches an expected value and, if so, replaces that value with a new one. Because the check and update occur as one indivisible step, other threads cannot observe an intermediate state.

The operation is central to many concurrent algorithms because it allows a thread to attempt an update without first taking a traditional lock. When the comparison fails, the calling code can decide whether to retry, back off, or follow a different path.

1.1 Basic operation

A typical compare-and-swap call takes three inputs: an address, an expected value, and a desired replacement value. If the value stored at the address equals the expected value, the memory location is updated to the replacement value. Otherwise, the location is left unchanged.

In practice, the primitive is often used in a loop. A thread reads the current value, computes a new value, and tries the atomic update. If another thread has changed the data in the meantime, the attempt fails and the process is repeated with the fresh state.

1.2 Atomicity

Atomicity means that the compare and the swap cannot be interleaved with other operations on the same memory location. This property is essential in concurrent programming, where several execution units may access shared data at nearly the same time.

The atomic guarantee helps prevent lost updates and other race conditions. It allows software to treat a memory change as a single event rather than as separate read and write steps.

1.3 Expected value and replacement value

The expected value represents the state a thread believes is currently present in memory. The replacement value is the new content that should be written if that belief is correct. This makes the primitive suitable for optimistic concurrency, where a thread proceeds on the assumption that interference is unlikely.

The expected value is often obtained from an earlier read. The replacement value may be a computed result, a pointer to a new node, or a modified status flag. The two values are central to expressing conditional updates without locks.

1.4 Success and failure outcomes

A successful compare-and-swap changes the memory location and usually returns a success indication. A failure leaves memory unchanged and reports that the current value did not match the expected one. Many APIs also return the observed value on failure so that the caller can retry with up-to-date information.

Success and failure are both useful. Success advances the algorithm, while failure provides a signal that the shared state has changed and that the thread may need to re-evaluate its plan.

2 Implementation

Compare-and-swap can be implemented directly in hardware or simulated with lower-level mechanisms when native support is unavailable. Hardware support is common in modern processors because it enables efficient synchronization and underpins many system-level concurrency techniques.

The exact behavior depends on the architecture, cache system, and memory model. Even when the logical operation is simple, its correct implementation involves careful coordination between processors and memory subsystems.

2.1 Hardware support

Native hardware support provides the strongest and most efficient form of compare-and-swap. In such systems, the processor performs the comparison and potential write using special instructions or tightly controlled memory transactions.

This support is especially valuable in multiprocessor machines, where multiple cores may attempt to modify the same data simultaneously. The hardware ensures that one update is seen as taking effect before another, preventing partial interference.

2.1.1 CPU instruction sets

Many instruction sets include a dedicated compare-and-swap or compare-and-exchange instruction. These instructions are typically designed for use with shared-memory synchronization and are often exposed to programmers through low-level compiler interfaces or atomic libraries.

Different architectures may vary in naming, operand order, and return conventions. Some provide a direct boolean result, while others return the original memory content so that software can determine whether the update succeeded.

2.1.2 Memory bus and cache coherence

On systems with shared caches and coherence protocols, compare-and-swap interacts with the mechanisms that keep copies of memory synchronized across cores. The processor generally needs exclusive access to the cache line containing the target location before it can complete the update.

Earlier designs sometimes relied on bus locking or similar serialization methods. Modern machines usually achieve atomicity through cache coherence and internal coordination within the memory subsystem, which reduces the performance cost of synchronized operations.

2.2 Software emulation

When hardware lacks direct support, compare-and-swap may be emulated using other atomic primitives or by disabling interrupts in limited environments. Such approaches are usually slower and may not scale as well as native instructions.

Emulation must still preserve the essential property that the compare and update occur without interference. In practice, this is often achieved by building the primitive on top of another instruction that already guarantees exclusivity.

2.3 Memory ordering considerations

Atomicity alone does not fully determine how surrounding memory operations are observed. Compare-and-swap is often paired with memory ordering rules that specify when other reads and writes become visible to different threads.

Depending on the language or platform, the operation may act as a full barrier, an acquire operation, a release operation, or a weaker form with explicit ordering choices. Correct concurrent code must account for these guarantees to ensure that data published before or after the atomic update is seen in the intended sequence.

3 Variants

Several related forms of the primitive exist. They differ in naming, width, and the type of conditional access they provide, but they share the same underlying idea of checking state before committing a change.

These variants arise from differences in programming interfaces, processor capabilities, and the needs of higher-level algorithms. Some are designed to reduce ambiguity, while others extend the basic operation to larger data items.

3.1 Compare-and-swap and compare-and-exchange

Compare-and-exchange is often used as an alternate name for compare-and-swap, especially in programming libraries. In many contexts, the two terms refer to the same operation or to nearly identical interfaces.

Some APIs distinguish them by return value. One form may report whether the exchange happened, while another may return the previous content of memory regardless of outcome. The distinction is mostly one of interface design rather than of core behavior.

3.2 Double-width compare-and-swap

Double-width compare-and-swap operates on two adjacent machine words as a single unit. It is useful when an algorithm needs to update a pointer and a version number together, or when two related values must change consistently.

This broader operation is harder to implement efficiently than the single-word form, but it can simplify some lock-free designs. By updating both parts at once, it reduces the risk of observing a mixed or partially updated state.

3.3 Conditional load and store

Some systems provide instructions that resemble compare-and-swap but separate the read and write aspects in different ways. Conditional load and store operations may load a value, verify a condition, or store only if a prior check remains valid.

These mechanisms can serve similar purposes in synchronization code. They are often used as building blocks for more elaborate atomic protocols when a direct compare-and-swap is unavailable or unsuitable.

4 Uses in concurrent programming

Compare-and-swap is widely used to coordinate access to shared data without conventional locking. It supports optimistic updates, where multiple threads may attempt progress independently and only retry when contention causes interference.

Its flexibility makes it useful in both low-level infrastructure and application code. Many lock-free structures and synchronization mechanisms depend on it directly or indirectly.

4.1 Lock-free data structures

Lock-free structures aim to guarantee that at least one thread can make progress even if others are delayed. Compare-and-swap is a natural fit because it can safely replace a shared pointer or counter only when the state still matches the thread’s expectation.

These data structures often use retry loops and carefully designed invariants. The atomic primitive helps preserve consistency while allowing concurrency.

4.1.1 Stacks

Lock-free stacks commonly use compare-and-swap to update the top pointer. A thread reads the current head, links a new node to that head, and then attempts to swing the top reference to the new node.

If another thread changes the stack in the meantime, the attempt fails and the operation is retried. This approach can provide good performance under light to moderate contention.

4.1.2 Queues

Queues may use compare-and-swap to adjust head and tail pointers or to insert new elements safely. More elaborate queue designs often require multiple atomic steps to preserve order and prevent corruption.

Because queues have both insertion and removal sides, they are a common setting for careful synchronization design. Compare-and-swap helps maintain correct transitions between queue states.

4.1.3 Linked lists and hash tables

In linked lists, compare-and-swap can be used to insert or remove nodes by updating next pointers only when the expected neighbor is still present. This enables concurrent structural changes without locking the entire list.

Hash tables may use the primitive to claim empty slots, publish new entries, or coordinate resizing metadata. The operation is especially helpful when changes to one bucket should not block access to unrelated buckets.

4.2 Synchronization primitives

Beyond data structures, compare-and-swap can form the basis for other synchronization tools. It is often used to implement compact and efficient waiting or ownership mechanisms.

These primitives may be simpler than full-featured locks in some cases, though they still require careful design to avoid excessive spinning or unfairness.

4.2.1 Spinlocks

A spinlock can be built by repeatedly attempting a compare-and-swap on a lock state variable. If the lock is free, the thread claims it; if not, the thread continues checking until it succeeds.

This technique is straightforward and can be effective when lock hold times are very short. However, it may waste CPU cycles if a thread waits for long periods.

4.2.2 Semaphores and mutexes

Semaphores and mutexes may use compare-and-swap in their fast paths, such as when acquiring an uncontended lock or adjusting a count. The primitive helps keep common operations efficient while allowing more complex slow paths for waiting threads.

In many implementations, compare-and-swap is not the entire synchronization mechanism but a key piece of it. It helps manage state transitions that would otherwise require heavier coordination.

4.3 Reference counting and object lifecycle

Reference counts can be incremented or decremented with atomic operations to track shared ownership safely. Compare-and-swap is useful when a count must change only if the current value remains within an expected range or when an object’s state must be checked before reuse.

This technique helps manage object lifetime in multithreaded programs. It reduces the risk that one thread will free or repurpose an object while another still relies on it.

5 Correctness issues

Although compare-and-swap is powerful, correct use can be subtle. Several known hazards arise when the surrounding algorithm assumes more than the primitive guarantees.

These issues do not reflect flaws in the operation itself. Rather, they show that a correct concurrent design must account for identity, ordering, progress, and visibility.

5.1 ABA problem

The ABA problem occurs when a memory location changes from value A to value B and then back to A. A thread that only checks whether the current value equals A may incorrectly conclude that nothing has changed, even though the state has been modified in between.

This can be dangerous in pointer-based structures, where the same address may reappear after an object has been removed and reused. Version counters, tagged pointers, or wider atomic operations are common ways to reduce the risk.

5.2 Spurious failure

Some compare-and-swap style operations may fail even when the expected value matches. This is known as spurious failure and is usually permitted by certain weak atomic interfaces as part of their design.

Spurious failure requires retry loops in code that uses such operations. Although it may seem inconvenient, the possibility can enable more efficient hardware or software implementations.

5.3 Livelock and starvation

A compare-and-swap loop can suffer from livelock when several threads repeatedly interfere with one another and none completes for a long period. Starvation can also occur if one thread consistently loses races to others.

These problems are most visible under heavy contention. Backoff strategies, randomized retries, or alternative synchronization methods may improve fairness and progress.

5.4 Memory consistency and visibility

Even when the atomic update itself is correct, other memory accesses around it may be observed in an unexpected order if the program ignores memory consistency rules. A thread may publish a pointer before the object it points to is fully initialized unless the code uses the proper ordering constraints.

Visibility issues are especially important in producer-consumer patterns and publication protocols. Correct use of compare-and-swap therefore depends on both atomicity and the surrounding memory model.

6 Performance characteristics

Compare-and-swap is often fast when contention is low, but performance can degrade as more threads compete for the same location. Its efficiency depends on the cost of retries, cache traffic, and the frequency of failed attempts.

In many systems, the primitive performs best when updates are relatively infrequent and reads dominate. It is not a universal substitute for locking, but it offers important advantages in the right setting.

6.1 Contention effects

Under contention, multiple processors may repeatedly invalidate one another’s cache lines while attempting the same update. This can increase latency and waste work, especially when many threads target a single shared variable.

Algorithms that use compare-and-swap often try to reduce contention by spreading updates across shards, batching work, or using local aggregation. Such techniques can improve throughput and lower retry rates.

6.2 Scalability

Compare-and-swap can scale well when threads mostly operate on separate data or when critical updates are brief. It is one reason many lock-free algorithms perform well on multiprocessor systems.

However, scalability is not automatic. A design that concentrates all activity on one atomic variable may become a bottleneck, even if the operation itself is efficient. Good structure and data partitioning remain important.

6.3 Comparison with locks

Compared with traditional locks, compare-and-swap can avoid blocking and reduce overhead in uncontended cases. It also supports non-blocking algorithms, which may continue making progress even if some threads are delayed.

Locks can still be preferable when the protected work is large, when fairness is important, or when the algorithm is difficult to express safely with atomic retries. The best choice depends on workload, contention, and implementation complexity.

7 Programming language support

Most modern languages provide some form of atomic compare-and-swap through libraries, standard types, or compiler features. These interfaces make the primitive accessible without requiring direct assembly language programming.

Language support typically includes both the atomic operation itself and rules for how it interacts with the language’s memory model. This combination is necessary for writing portable concurrent code.

7.1 Atomic libraries

Atomic libraries expose compare-and-swap through dedicated data types or functions. They commonly support integers, pointers, booleans, and sometimes user-defined structures if the platform can represent them atomically.

Such libraries often offer several operations beyond compare-and-swap, including loads, stores, exchanges, and fetch-based arithmetic. This gives programmers a consistent toolkit for synchronization.

7.2 Language memory models

A language memory model defines when atomic operations become visible and what ordering guarantees they provide. Compare-and-swap is usually tied to these rules so that developers can reason about correctness across different compilers and processors.

The memory model can affect both performance and safety. Choosing the weakest ordering that still preserves correctness often yields better efficiency.

7.3 Compiler intrinsics

Compiler intrinsics provide a direct bridge to machine-specific atomic instructions. They allow a program to use compare-and-swap in a way that the compiler can optimize while still generating correct low-level code.

Intrinsics are often used in systems programming, runtime libraries, and performance-critical software. They can also serve as a foundation for higher-level atomic abstractions.

Compare-and-swap belongs to a family of atomic read-modify-write operations. These related primitives solve similar coordination problems but differ in how they select, update, or verify memory.

Understanding the differences among them helps programmers choose the most suitable primitive for a given concurrent design.

8.1 Fetch-and-add

Fetch-and-add atomically increases a numeric value and returns the previous result. It is especially useful for counters, ticketing systems, and allocation of sequential identifiers.

Unlike compare-and-swap, it does not test against an expected state before writing. Its behavior is simpler, but it is less flexible for conditional updates.

8.2 Test-and-set

Test-and-set atomically sets a location and reports the previous value. It is often used in simple locking schemes and is closely associated with spin-based synchronization.

Compared with compare-and-swap, test-and-set provides less information about the current state and is therefore less expressive for many lock-free algorithms.

8.3 Load-linked/store-conditional

Load-linked/store-conditional is a paired mechanism in which a value is loaded with a reservation and later stored only if the reservation remains valid. It can provide functionality similar to compare-and-swap while fitting different processor designs.

This approach is often used to build atomic updates when the architecture prefers reservation-based synchronization. It is conceptually related, though not identical, to compare-and-swap.