伪共享与填充

四个线程各自更新自己的计数器，什么都没有共享，循环却比应有的速度慢了 40 倍。原因是四个计数器挤在同一条缓存行里，各个核心为它争抢不休。本讲搭一个缓存一致性的小模型，说明在一个由 SPY 表日期驱动的循环里伪共享要付出多少代价，并用几个字节的填充把它解决。

到目前为止，一个程序只在一个核心上运行。真实的机器有多个核心，每个核心都有自己小而快的缓存。这就带来一个问题：如果核心 0 和核心 1 都持有某条缓存行的副本，而核心 0 修改了它，核心 1 就不能继续读旧值。防止这种情况的硬件规则叫缓存一致性。最简单的实现办法是：在一个核心写某条缓存行之前，把其他所有核心里这条行的副本都丢掉。这就是一次失效。

1. 1
   先看自己的缓存行不在，这次访问就是缺失。
2. 2
   写入时，把其他副本清掉其他每个持有这条行的核心都失去副本：每个算一次失效。
3. 3
   留下这条行之后这条行就在本核心的缓存里，等待它的下一次访问。

下面的类为每个核心记录它持有的行的集合。我们重放三步：核心 0 写字节 0，核心 1 写字节 8（同一条行），然后核心 0 再写字节 0。

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. 1写入会把这条行从其他所有持有它的核心中移除，每个副本计一次失效。

三次访问都是缺失。核心 1 的写入使核心 0 的副本失效，核心 0 接着的那次写入又使核心 1 的副本失效。核心 0 和核心 1 从没写过同一个字节，写的只是相邻的字节，可它们每次写入都要把这条行从对方手里夺走。

并行统计事件的常见做法是给每个核心各自一个计数器，这样没有核心需要等别的核心。每个计数器 8 字节。把它们一个接一个放进数组，四个就挤进一条 64 字节的缓存行。我们构造 50 轮更新的写入序列，每轮每个核心写一次，并分别在计数器相隔 8 字节（紧凑）和 64 字节（带填充）时重放。时间按核心自己缓存里的访问 1 ns、从别的核心取行的缺失 60 ns 来算。

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

紧凑摆放时，200 次写入全部缺失，其中 199 次使上一个写入者的副本失效：12,000 ns。加了填充后，每个核心的计数器各占一条缓存行：开头 4 次冷缺失，之后每次写入都命中，没有失效：436 ns。算术完全一样，却快了 27 倍，因为四个核心不再互相抢这条行。

要让每个计数器独占一条缓存行，两个计数器之间的距离必须是行大小的倍数，所以元素大小要向上取整到下一个 64 的倍数。8 字节的计数器占 64 字节，浪费 56 字节；65 字节的元素占 128 字节。下面的函数完成这个取整。

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]

实验里四个核心各自统计自己负责的交易日，SPY 表的第 i 天交给核心“星期几 % 4”。前 1,000 天按日期顺序驱动这些写入。因为日期按日历推进，同一个核心很少连续写两次，缓存行于是被一次又一次地抢走。计数器紧凑摆放时，1,000 次写入中有 818 次缺失、817 次使另一个核心的副本失效；加了填充后，只有最初 4 次写入缺失。

实验搭建一致性模型、按给定步长生成每核计数器的轨迹、重放、填充规则、时间模型，以及对 SPY 日期的研究。

• 函数 · 问题依赖
• CoherentCaches(n_cores).access(core, address, write)命中还是缺失，谁会丢掉副本？简单算术
• counter_address(core, stride_bytes)一个核心的计数器在哪里？简单算术
• update_trace(n_cores, n_updates, stride_bytes)各个核心会做哪些写入？counter_address
• run_trace(trace, n_cores)缺失与失效各多少次？CoherentCaches
• padding_needed(item_bytes)元素之间要隔多远？简单算术
• time_ns(stats)这次运行要多久？命中与缺失的代价
• study(bars)在 SPY 日期上伪共享代价多大？run_tracepadding_neededtime_ns

下一个主题：伪共享说的是共用一个插槽的核心。在有两个插槽的机器上，内存本身也被分开了：一部分离某个核心近，另一部分离得远。在 NUMA 效应里，你要把页放到各个节点上，数出本地与远端访问，并估算两者的差价。