为什么当 maxsize 是 2 的幂时 python lru_cache 性能最好？

Question

文档是这样说的：

如果 maxsize 设置为 None，则禁用 LRU 功能，缓存可以无限制地增长。当 maxsize 是 2 的幂时，LRU 功能表现最佳。

有人会碰巧知道这个“二的幂”从何而来？我猜它必须对实现做些什么。

Answer 1

TL;DR - 这是一种优化，在 lru_cache 大小较小时没有太大效果，但是（请参阅 Raymond 的回复）随着 lru_cache 大小变大，效果会更大。

这引起了我的兴趣，我决定看看这是否属实。

首先，我去阅读了 LRU 缓存的源代码。cpython 的实现在这里： https: //github.com/python/cpython/blob/master/Lib/functools.py#L723，我没有看到任何基于它可以更好地运行的东西两个人的权力。

因此，我编写了一个简短的 python 程序来创建各种大小的 LRU 缓存，然后多次使用这些缓存。这是代码：

from functools import lru_cache
from collections import defaultdict
from statistics import mean
import time

def run_test(i):
    # We create a new decorated perform_calc
    @lru_cache(maxsize=i)
    def perform_calc(input):
        return input * 3.1415

    # let's run the test 5 times (so that we exercise the caching)
    for j in range(5):
        # Calculate the value for a range larger than our largest cache
        for k in range(2000):
            perform_calc(k)

for t in range(10):
    print (t)
    values = defaultdict(list)
    for i in range(1,1025):
        start = time.perf_counter()
        run_test(i)
        t = time.perf_counter() - start
        values[i].append(t)

for k,v in values.items():
    print(f"{k}\t{mean(v)}")

我在 macbook pro 上用 python 3.7.7 在轻负载下运行了这个。

结果如下：

https://docs.google.com/spreadsheets/d/1LqZHbpEL_l704w-PjZvjJ7nzDI1lx8k39GRdm3YGS6c/preview?usp=sharing

随机峰值可能是由于 GC 暂停或系统中断造成的。

此时我意识到我的代码总是生成缓存未命中，并且从不生成缓存命中。如果我们运行同样的事情，但总是命中缓存，会发生什么？

我将内循环替换为：

    # let's run the test 5 times (so that we exercise the caching)
    for j in range(5):
        # Only ever create cache hits
        for k in range(i):
            perform_calc(k)

此数据位于与上面相同的电子表格中的第二个选项卡中。

让我们来看看：

嗯，但我们并不真正关心这些数字中的大部分。另外，我们为每个测试做的工作量并不相同，因此时间安排似乎没有用。

如果我们只运行 2^n 2^n + 1 和 2^n - 1 会怎么样。由于这会加快速度，因此我们将对其进行 100 多次测试的平均，而不是仅仅 10 次。

我们还将生成一个大型随机列表来运行，因为这样我们就会期望有一些缓存命中和缓存未命中。

from functools import lru_cache
from collections import defaultdict
from statistics import mean
import time
import random

rands = list(range(128)) + list(range(128)) + list(range(128)) + list(range(128)) + list(range(128)) + list(range(128)) + list(range(128)) + list(range(128))
random.shuffle(rands)

def run_test(i):
    # We create a new decorated perform_calc
    @lru_cache(maxsize=i)
    def perform_calc(input):
        return input * 3.1415

    # let's run the test 5 times (so that we exercise the caching)
    for j in range(5):
        for k in rands:
            perform_calc(k)

for t in range(100):
    print (t)
    values = defaultdict(list)
    # Interesting numbers, and how many random elements to generate
    for i in [15, 16, 17, 31, 32, 33, 63, 64, 65, 127, 128, 129, 255, 256, 257, 511, 512, 513, 1023, 1024, 1025]:
        start = time.perf_counter()
        run_test(i)
        t = time.perf_counter() - start
        values[i].append(t)

for k,v in values.items():
    print(f"{k}\t{mean(v)}")

此数据位于上面电子表格的第三个选项卡中。

下面是每个元素的平均时间/lru 缓存大小的图表：

当然，随着缓存大小变大，时间会减少，因为我们不会花费太多时间来执行计算。有趣的是，似乎确实从 15 下降到了 16、17，从 31 下降到了 32、33。让我们放大看更高的数字：

我们不仅在较高的数字中失去了这种模式，而且实际上我们发现某些 2 的幂（511 到 512、513）的性能有所下降。

编辑：关于二的幂的注释是在 2012 年添加的，但是 functools.lru_cache 的算法在该提交中看起来是相同的，因此不幸的是，这反驳了我的理论，即算法已更改且文档已过时。

编辑：删除了我的假设。原作者在上面回复了 - 我的代码的问题是我正在使用“小”缓存 - 这意味着字典上的 O(n) 调整大小并不是很昂贵。尝试使用非常大的 lru_cache 和大量缓存未命中来看看是否可以出现效果会很酷。

Answer 2

尺寸效应出现的地方

该lru_cache（）的代码行使其底层辞典非典型的方式。在保持总大小不变的同时，缓存未命中删除最旧的项目并插入新项目。

二次幂的建议是这种删除和插入模式如何与底层字典实现交互的产物。

字典的工作原理

• 表大小是 2 的幂。
• 删除的键被替换为虚拟条目。
• 新密钥有时可以重用虚拟插槽，有时不能。
• 使用不同的键重复删除和插入将用虚拟条目填充表。
• 当表已满三分之二时，将运行 O(N) 调整大小操作。
• 由于活动条目的数量保持不变，调整大小操作实际上不会改变表的大小。
• 调整大小的唯一效果是清除累积的虚拟条目。

性能影响

带有2**n条目的 dict为虚拟条目提供了最多的可用空间，因此 O(n) 调整大小的发生频率较低。

此外，稀疏字典的哈希冲突比大多数完整字典少。冲突会降低字典性能。

重要的时候

该lru_cache（）只更新词典时，有一个高速缓存未命中。此外，当出现未命中时，会调用包装函数。因此，调整大小的效果仅在未命中率很高且包装函数非常便宜的情况下才重要。

比给maxsize一个 2 的幂更重要的是使用最大的合理maxsize。更大的缓存有更多的缓存命中——这就是大胜利的来源。

模拟

一旦lru_cache()已满并且发生了第一次调整大小，字典就会进入稳定状态并且永远不会变大。在这里，我们模拟在添加新的虚拟条目并定期调整大小将它们清除时接下来会发生什么。

steady_state_dict_size = 2 ** 7     # always a power of two

def simulate_lru_cache(lru_maxsize, events=1_000_000):
    'Count resize operations as dummy keys are added'
    resize_point = steady_state_dict_size * 2 // 3
    assert lru_maxsize < resize_point
    dummies = 0
    resizes = 0
    for i in range(events):
        dummies += 1
        filled = lru_maxsize + dummies
        if filled >= resize_point:
           dummies = 0
           resizes += 1
    work = resizes * lru_maxsize    # resizing is O(n)
    work_per_event = work / events
    print(lru_maxsize, '-->', resizes, work_per_event)

以下是输出的摘录：

for maxsize in range(42, 85):
    simulate_lru_cache(maxsize)

42 --> 23255 0.97671
43 --> 23809 1.023787
44 --> 24390 1.07316
45 --> 25000 1.125
46 --> 25641 1.179486
  ...
80 --> 200000 16.0
81 --> 250000 20.25
82 --> 333333 27.333306
83 --> 500000 41.5
84 --> 1000000 84.0

这表明当maxsize尽可能远离resize_point时，缓存所做的工作明显减少。

历史

当字典随着调整大小而增长时，Python3.2 中的影响很小4 x active_entries。

效果成为灾难性当增长速度降低到2 x active entries。

后来达成了妥协，将增长率设置为3 x used。通过默认情况下为我们提供更大的稳态大小，这显着缓解了这个问题。

2 的幂maxsize仍然是最佳设置，对于给定的稳态字典大小提供最少的工作，但它不再像在 Python3.2 中那样重要。

希望这有助于澄清您的理解。:-)