TL; DR - это оптимизация, которая не имеет большого эффекта при небольших размерах lru_cache, но (см. Ответ Раймонда) имеет больший эффект, когда ваш размер 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
Случайные пики, вероятно, вызваны паузами G C или системными прерываниями.
В В этот момент я понял, что мой код всегда генерирует пропуски кэша и никогда не приводит к попаданию в кеш. Что произойдет, если мы запустим одно и то же, но всегда попадем в кеш?
Я заменил внутренний l oop на:
# 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 кеш size:
Время, конечно, уменьшается по мере увеличения размера нашего кэша, поскольку мы не тратим столько времени на выполнение вычислений. Интересно, что, похоже, наблюдается спад с 15 до 16, 17 и с 31 до 32, 33. Давайте увеличим старшие числа:
Мало того, что мы теряем этот паттерн в старших числах, мы на самом деле видим, что производительность уменьшается для некоторых из двух степеней (от 511 до 512, 513).
Редактировать: примечание о степени двойки было добавлено в 2012 , но алгоритм для functools.lru_cache выглядит так же при этом коммите , так что, к сожалению, опровергает мою теорию, что алгоритм изменился и документы устарели.
Редактировать: Убрал мои гипотезы. Первоначальный автор ответил выше - проблема с моим кодом заключается в том, что я работал с «маленькими» кэшами - это означает, что изменение размера O (n) на участках было не очень дорогим. Было бы здорово поэкспериментировать с очень большими lru_caches и множеством промахов в кеше, чтобы посмотреть, сможем ли мы получить эффект.