Sharded Counters, Padding, and False Sharing

Two threads, two counters, no sharing at all. Each thread increments its own variable, declared next to the other in the same struct. This should scale perfectly: no lock, no shared state, no reason for the threads to interact. It does not. The aggregate rate is a fraction of what one thread achieves alone, and the reason is that the two variables occupy the same 64-byte cache line.

The mechanism is a consequence of cache coherence protocols working at line granularity and of the line being the unit of ownership. There is no per-byte tracking. When a core writes to any part of a line, it must own the whole line, and any other core holding a copy must invalidate it. Two threads writing two distinct words that happen to share a line exchange ownership of that line on every write, which is the same traffic pattern as if they were writing the same word. The hardware cannot tell the difference and is not asked to.

Ownership, invalidation, and the cost of a transfer

Caches on modern shared-memory multiprocessors keep lines coherent through a protocol in which each line in each cache has a state: modified, exclusive, shared, or invalid. A write requires exclusive ownership. If the writer’s copy is shared or invalid, it must first obtain the line exclusively, which means telling other caches to invalidate their copies and waiting for them to acknowledge.

The wait is the expensive part. A line that is clean in another core’s cache can be transferred directly, without going to memory, but the transfer still traverses the interconnect and the latency is on the order of tens to a couple of hundred cycles depending on whether the cores are on the same socket. On a multi-socket machine, a line held by a core on the other socket costs on the order of hundreds of cycles, and the accounting is further complicated by the directory or snoop filter structures that track which sockets hold copies.

Ownership transfers do not stop after the first write. A core that owns a line exclusively may keep writing without traffic, and it will, until something forces it to give the line up. In the pathological pattern, each core performs a single write and then waits for a long time, so the line goes cold and is written back or downgraded before the other core writes; the transfer rate is then bounded by the write frequency rather than by any coherence inefficiency, and the structure is merely slow in a way that mimics real sharing. The damaging case is repeated writes from different cores within a short window, where each write finds the line invalidated by the previous one and must fetch it again. Thread A writes the line, taking it exclusive. Thread B writes, invalidating A’s copy and taking ownership. Thread A writes again, invalidating B’s. Each iteration transfers the line once, and each transfer stalls the writing core until the line arrives. Two cores that each increment a word a million times per second therefore generate two million line transfers per second, all of which are pure overhead: no data is shared, but the ownership is.

Placement of two counters	Approximate steady-state behaviour
Same cache line, both written hot	Line transfer on every write; near-zero scaling
Same line, one written, one read-only	Reader invalidated repeatedly; slow
Separate cache lines, plain stores	No transfers; scales with core count
Separate cache lines, atomic increments	One atomic per write, uncontended
One shared counter, atomic increments	One line transfer per write; serialized

The third and fifth rows are the ones to hold in mind. Padding the two counters apart removes the false sharing completely. Making them one shared counter reintroduces real sharing, which is a different problem with a similar cost.

Why the compiler and the layout fight back

The obvious fix is to insert padding between the counter and its neighbour so that they occupy different lines. This is correct in intent and surprisingly easy to get wrong in execution.

The first hazard is the cache line size itself. The common x86-64 cache line is 64 bytes, and the common requirement is that a variable be aligned to that boundary as well as spaced by that amount. Padding to 64 bytes without aligning does not help: a counter placed at offset 60 with 64 bytes of padding shares its line with whatever is at offset 0 and whatever is at offset 124. Alignment and spacing are separate requirements, and most languages express alignment explicitly because the default alignment of a counter is its own size.

The second hazard is that many CPUs fetch adjacent lines together. Some x86-64 implementations fetch 128 bytes into a cache in units of two lines, so two variables padded 64 bytes apart but aligned so that they are adjacent in a 128-byte window can still create contention on the fetch unit even when the coherence protocol never transfers a line. Vendor optimization manuals describe this as a documented effect and recommend spacing at 128 bytes when it is relevant. The safe choice is a compile-time constant for the spacing, not a hard-coded 64.

The third hazard is the compiler and the language runtime moving things. Fields of a struct are laid out in a defined order in C, but the linker can merge read-only data across translation units, and some linkers combine constant strings and zero-initialized globals in ways that place unrelated hot variables in the same line. Languages with garbage collectors move objects at will, and array elements are contiguous by definition, which makes an array of per-thread counters the most common accidental false-sharing structure there is.

#include <stdalign.h>
#include <stdatomic.h>

#define CACHELINE 128   /* pad to two lines: some cores fetch in pairs */

struct alignas(CACHELINE) padded_counter {
    _Atomic unsigned long long value;
    char pad[CACHELINE - sizeof(_Atomic unsigned long long)];
};

/* Array of counters, one per thread, each on its own line. */
static struct padded_counter counters[16];

static inline void record(int id) {
    atomic_fetch_add_explicit(&counters[id].value, 1, memory_order_relaxed);
}

The relaxed memory order is not an optimization detail to gloss over. The counter’s value is only observed at the end, through a sum, so there is no ordering relationship to establish with any other memory operation. Requiring sequential consistency here would add a fence that buys nothing.

Sharding a single logical counter

False sharing is a layout accident. The related problem, sharing by design, arises when many threads must increment one logical counter: requests served, bytes written, errors observed. A single atomic variable is correct and does not scale, because every increment takes exclusive ownership of one line and every other core’s copy must be invalidated. The line is a serialization point that costs a coherence transfer per operation.

Sharding replaces the single variable with one per thread or per core, each on its own line, each incremented locally with no coherence traffic in the steady state. The logical value is the sum of the shards, computed when someone reads it.

/* Contiguous shards: one field per line, each written only by one thread. */
struct shard_set {
    struct padded_counter shard[16];
};

static unsigned long long total(const struct shard_set *s) {
    unsigned long long sum = 0;
    for (int i = 0; i < 16; i++)
        sum += atomic_load_explicit(&s->shard[i].value, memory_order_relaxed);
    return sum;
}

The price paid for the scaling is paid at read time. A read must sum sixteen values from sixteen lines, which is sixteen cache misses on a cold read, and the sum is not a snapshot: a thread can increment shard 3 after the reader has already read shard 3, so the total includes increments that happened both before and after other shards were read. For a monotonic counter this means the read is not linearizable: no single instant corresponds to the value returned.

That non-linearity is normally acceptable for statistics and never acceptable for anything with a correctness condition attached. A rate limiter that checks a sharded counter will admit more work than its limit under contention, because each thread’s local shard is behind the true total. A quota enforced against a sharded value has the same problem. The technique applies to measurement, not to admission control.

A third kind of counter avoids both problems at a cost: a striped counter with a bounded number of stripes, where each increment picks a stripe by hash of the thread identifier and the read takes a lock. Correctness is preserved, scaling is nearly as good, and the reader pays for a lock. Choosing between the three is a matter of which operation must be exact.

How much sharding is worth it

Sharding is worthwhile in proportion to the write rate per counter and the number of writers. A counter incremented once per request in a process serving a thousand requests per second has no coherence problem at all: the line is touched a thousand times a second and the cost is invisible next to the work being done. A counter incremented in an inner loop over a million items, by sixteen threads, is a pure serialization point and costs the entire parallel speedup of the loop.

The useful diagnostic is the ratio of counter updates to units of useful work per thread. Above roughly one update per cache miss worth of work, the coherence traffic is comparable to the memory traffic of the real computation, and sharding or local batching pays. Below that, the complexity of sharding is not recoverable.

There is also an allocation cost that is easy to miss. Per-thread shards aligned to 128 bytes with sixteen threads occupy 2 kilobytes of memory, which is negligible, but the same structure in a per-connection or per-object record can multiply into megabytes and worsen locality for everything else in the same working set. The padding that removes false sharing between the shards can introduce a different kind of waste when the shards are embedded in a frequently iterated array.

The natural companion technique is to accumulate locally and publish rarely, which is the same argument as Batching and the Amortization of Per-Item Cost: the fewer times a shared location is written, the less the coherence protocol has to do. When the update cannot be reduced to a single word, the alternative to a lock is an optimistic read-modify-write loop, whose behaviour under contention is treated in Compare-and-Swap Retry Loops Under Contention.