False sharing and padding

Four threads each update their own counter, nothing is shared, and yet the loop runs 40 times slower than it should. The reason is that the four counters sit in one cache line and the cores fight over it. This lecture builds a small model of cache coherence, shows what false sharing costs on a loop driven by the dates of the SPY table, and fixes it with a few bytes of padding.

So far one program ran on one core. A real machine has several cores, and each has its own small, fast cache. This creates a problem: if core 0 and core 1 both hold a copy of a line and core 0 changes it, core 1 must not go on reading the old value. The hardware rule that prevents this is cache coherence. The simplest way to enforce it: before a core may write to a line, every other core's copy of that line is thrown out. That is an invalidation.

1. 1
   Look in your own cacheIf the line is not there, this access is a miss.
2. 2
   On a write, evict the othersEvery other core that holds the line loses its copy: one invalidation each.
3. 3
   Keep the lineAfterwards the line is in this core's cache, ready for its next access.

The class below keeps, for each core, the set of lines it holds. We replay three steps: core 0 writes byte 0, core 1 writes byte 8 (the same line), then core 0 writes byte 0 again.

class CoherentCaches:    def __init__(self, n_cores):        self.lines = [set() for _ in range(n_cores)]        self.misses = 0        self.invalidations = 0    def access(self, core, address, write):        line = address // LINE_BYTES        hit = line in self.lines[core]        if not hit:            self.misses += 1        if write:            for other, held in enumerate(self.lines):1                if other != core and line in held:                    held.discard(line)                    self.invalidations += 1        self.lines[core].add(line)        return hitcaches = CoherentCaches(2)print(caches.access(0, 0, True), caches.access(1, 8, True), caches.access(0, 0, True))print("misses:", caches.misses, "invalidations:", caches.invalidations)

False False False
misses: 3 invalidations: 2

1. 1A write removes the line from every other core that holds it and counts one invalidation per copy.

All three accesses miss. The write of core 1 invalidates the copy of core 0, and the next write of core 0 invalidates the copy of core 1 in turn. Core 0 and core 1 never wrote the same byte, only neighbouring ones, and still they take the line from each other on every write.

A common way to count events in parallel is to give each core its own counter, so that no core waits for another one. The counters are 8 bytes each. Put them one after another in an array and four of them fit into one 64-byte line. We build the writes of 50 rounds of updates, one write per core in each round, and replay them with the counters 8 bytes apart (packed) and 64 bytes apart (padded). The time is 1 ns for an access in the core's own cache and 60 ns for a miss that fetches the line from another core.

def counter_address(core, stride_bytes):    return core * stride_bytesdef update_trace(n_cores, n_updates, stride_bytes):    return [(core, "w", counter_address(core, stride_bytes)) for _ in range(n_updates) for core in range(n_cores)]def run_trace(trace, n_cores):    caches = CoherentCaches(n_cores)    for core, op, address in trace:        caches.access(core, address, op == "w")    return {"accesses": len(trace), "misses": caches.misses, "invalidations": caches.invalidations}def time_ns(stats):    return (stats["accesses"] - stats["misses"]) * HIT_NS + stats["misses"] * MISS_NSfor name, stride in (("packed", 8), ("padded", 64)):    stats = run_trace(update_trace(4, 50, stride), 4)    print(name, stats, time_ns(stats), "ns")

packed {'accesses': 200, 'misses': 200, 'invalidations': 199} 12000.0 ns
padded {'accesses': 200, 'misses': 4, 'invalidations': 0} 436.0 ns

Packed, all 200 writes miss and 199 of them invalidate the previous writer: 12,000 ns. Padded, each core keeps its counter in a line of its own: four cold misses at the start, then every write hits, and no invalidation: 436 ns. That is 27 times faster for exactly the same arithmetic, because the four cores no longer take the line from each other.

To give every counter a line of its own, the distance between two counters must be a multiple of the line size, so the item size is rounded up to the next multiple of 64. An 8-byte counter takes 64 bytes, which wastes 56. An item of 65 bytes takes 128. The function below does the rounding.

def padding_needed(item_bytes):    return math.ceil(item_bytes / LINE_BYTES) * LINE_BYTESprint([padding_needed(size) for size in (8, 63, 64, 65, 100)])

[64, 64, 64, 128, 128]

In the lab four cores each count the trading days they handle, and day number i of the SPY table goes to core weekday % 4. The first 1,000 days drive the writes in date order. Because the days follow the calendar, the same core rarely writes twice in a row and the line is taken away again and again. With the counters packed, 818 of the 1,000 writes miss and 817 invalidate another core; with them padded, only the four first writes miss.

The lab builds the coherence model, the traces of per-core counters with a given stride, the replay, the padding rule, the time model and the study on the SPY dates.

• Function · questionBuilds on
• CoherentCaches(n_cores).access(core, address, write)Hit or miss, and who loses a copy?Plain arithmetic
• counter_address(core, stride_bytes)Where does a core's counter live?Plain arithmetic
• update_trace(n_cores, n_updates, stride_bytes)Which writes do the cores make?counter_address
• run_trace(trace, n_cores)How many misses and invalidations?CoherentCaches
• padding_needed(item_bytes)How far apart must the items be?Plain arithmetic
• time_ns(stats)How long does the run take?Hit and miss costs
• study(bars)What does false sharing cost on the SPY dates?run_tracepadding_neededtime_ns

Next topic: false sharing is about cores that share a socket. On a machine with two sockets, memory itself is split: some of it is close to a core and some is far. In NUMA effects you place pages on nodes, count local and remote accesses and price the difference.