缓存行与空间局部性

缓存从不只取一个字节，它一次取一整条 64 字节的缓存行，所以紧挨着你刚读的那个值已经在里面了。本讲搭建一个缓存，说明按顺序读比每次跳过一整行便宜八倍，并把它用到一张价格表上。

不管要多少字节，从内存取一次的代价都一样，所以硬件一次就多要一些。内存被切成 64 字节的块，缓存总是整块地装入、整块地替换。想象一部把 64 字节运上缓存的电梯：反正电梯要上去，顺便带上邻居不花任何成本，下次你需要其中一个时它已经在楼上了。

每个字节都有一个地址，一个说明它在哪里的数。要找地址所在的行，用地址除以行大小并丢掉余数。下面的代码打印四个地址所在的行。

line_bytes = 64for address in (0, 63, 64, 130):    print(address, "is in line", address // line_bytes)

0 is in line 0
63 is in line 0
64 is in line 1
130 is in line 2

地址 0 和 63 同在第 0 行，只要装入其中一个，另一个就免费。地址 64 是第 1 行的开头，130 在第 2 行。本主题的一切都来自这个整数除法。

最简单的缓存是一张表，能容纳多少行就有多少个槽位。32 KB、64 字节行的缓存有 512 个槽位。内存里的每一行只允许放进一个槽位，用取余求出：行号对槽位数取模。这叫直接映射缓存。因为许多行共用一个槽位，槽位还要记一个标签，说明它此刻装的是哪一行。

1. 1
   求出行号用地址除以行大小。
2. 2
   求出槽位把行号对槽位数取模。
3. 3
   比较标签槽位里正是这一行，就是命中。
4. 4
   未命中就替换把这一行装进槽位，丢掉原来的那一行。

缓存就是这些。下面的类用十五行写成了一个完整可用的版本。我们读四个相邻的值，再读下一行，然后回到地址 0。

def line_of(address, line_bytes):    return address // line_bytesclass Cache:    def __init__(self, size_bytes, line_bytes):        self.line_bytes = line_bytes        self.n_lines = size_bytes // line_bytes        self.tags = [None] * self.n_lines        self.hits = 0        self.misses = 0    def access(self, address):        line = line_of(address, self.line_bytes)1        slot = line % self.n_lines        if self.tags[slot] == line:2            self.hits += 1            return True        self.misses += 1        self.tags[slot] = line        return Falsecache = Cache(size_bytes=512, line_bytes=64)reads = [0, 8, 16, 24, 64, 72, 0, 512, 0]print([cache.access(a) for a in reads])print(cache.hits, "hits and", cache.misses, "misses")

[False, True, True, True, False, True, True, False, False]
5 hits and 4 misses

1. 1槽位就是行号对槽位数取模。
2. 2命中意味着槽位里的标签正是这一行。

看这串标志：第一次读未命中并装入第 0 行，接下来三次读命中，因为都在第 0 行；64 未命中并装入第 1 行；72 命中；回到 0 又命中，因为第 0 行没被替换。接着地址 512 是第 8 行，它也映射到槽位 0（8 对 8 取模），于是把第 0 行替换掉，最后一次读地址 0 又未命中：一次冲突多花了一次缺失。

现在用这个缓存。一个 float64 占 8 字节，所以一行装得下 8 个。按顺序读一个数组，每一行的第一次读未命中，后面七次命中：八次里一次缺失。如果用步长来读，也就是每次读之间固定跳过若干个值，读到的就是不同的行。下面的代码测量步长为 1、2、4、8、16 个值时的缺失率。

def sequential_trace(n, elem_bytes):    return [i * elem_bytes for i in range(n)]def strided_trace(n, elem_bytes, stride):    return [i * stride * elem_bytes for i in range(n)]def miss_rate(trace, size_bytes=32768, line_bytes=64):    cache = Cache(size_bytes, line_bytes)    for address in trace:        cache.access(address)    return cache.misses / len(trace)n = 4096for stride in (1, 2, 4, 8, 16):    print("stride", stride, "values:", miss_rate(strided_trace(n, 8, stride)))

stride 1 values: 0.125
stride 2 values: 0.25
stride 4 values: 0.5
stride 8 values: 1.0
stride 16 values: 1.0

步长每翻一倍，缺失率也翻一倍，直到 1.0：步长 8 个值时跳 64 字节，正好一整行，每次读都打开一条新行，缓存什么也省不下。更大的步长不会更糟，只会一样。规律就是下面这个公式。

日线表每天有五个数：开、高、低、收、成交量。像大多数程序那样一行一行存，一天的五个数就并排放着。只读收盘价时，每次读之间要跳过四个值：步长 5，也就是 40 字节。把每一列单独存，收盘价就一个接一个：步长 1。数字一样，读取一样，只是布局不同。

closes = 1000as_column = miss_rate(sequential_trace(closes, 8))as_rows = miss_rate(strided_trace(closes, 8, 5))print("column layout:", as_column)print("row layout:   ", as_rows)

column layout: 0.125
row layout:    0.625

收盘价隔着读时，缺失的读取多了五倍。这不会改变程序的结果，只改变速度，而且分析器里任何一行算术都看不出来：多出来的时间都花在等内存上了。

实验按同样的顺序要求你实现刚读过的几个部分，最后对真实的 SPY 表做研究。

• 函数 · 问题依赖
• line_of(address, line_bytes)这个地址在哪一行？整数除法
• Cache(size_bytes, line_bytes).access(address)这次读取是否命中？line_of
• sequential_trace(n, elem_bytes)按顺序读会碰到哪些地址？简单算术
• strided_trace(n, elem_bytes, stride)跳着读会碰到哪些地址？简单算术
• miss_rate(trace, size_bytes, line_bytes)一条访问轨迹里有多少比例未命中？Cache
• study(bars)SPY 收盘价用行布局要多花多少？miss_ratestrided_trace

下一个主题：直接映射缓存有一个本讲提过的弱点，即共用槽位的行之间的冲突。在相联度与冲突缺失里，你给每个槽位多个位置，并看清为什么行间距为 4096 字节的表会毁掉一个缓存。