Исходный код Python 3.9 для кэша LRU: https://github.com/python/cpython/blob/3.9/Lib/functools.py#L429
Пример кода Фибоначчи
@lru_cache(maxsize=2)
def fib(n):
if n == 0:
return 0
if n == 1:
return 1
return fib(n - 1) + fib(n - 2)
Декоратор LRU Cache проверяет некоторые базовые случаи, а затем оборачивает пользовательскую функцию оболочкой _lru_cache_wrapper. Внутри обертки происходит логика добавления элемента в кеш, логика LRU, т.е. добавление нового элемента в циклическую очередь, удаление элемента из циклической очереди.
def lru_cache(maxsize=128, typed=False):
...
if isinstance(maxsize, int):
# Negative maxsize is treated as 0
if maxsize < 0:
maxsize = 0
elif callable(maxsize) and isinstance(typed, bool):
# The user_function was passed in directly via the maxsize argument
user_function, maxsize = maxsize, 128
wrapper = _lru_cache_wrapper(user_function, maxsize, typed, _CacheInfo)
wrapper.cache_parameters = lambda : {'maxsize': maxsize, 'typed': typed}
return update_wrapper(wrapper, user_function)
elif maxsize is not None:
raise TypeError(
'Expected first argument to be an integer, a callable, or None')
def decorating_function(user_function):
wrapper = _lru_cache_wrapper(user_function, maxsize, typed, _CacheInfo)
wrapper.cache_parameters = lambda : {'maxsize': maxsize, 'typed': typed}
return update_wrapper(wrapper, user_function)
return decorating_function
lru_cache нормализует maxsize(when negative), добавляет детали CacheInfo и, наконец, добавляет оболочку и обновляет документы декоратора и другие детали.
lru_cache_wrapper
Оболочка Lru Cache имеет несколько переменных бухгалтерского учета.
sentinel = object() # unique object used to signal cache misses
make_key = _make_key # build a key from the function arguments
PREV, NEXT, KEY, RESULT = 0, 1, 2, 3 # names for the link fields
cache = {}
hits = misses = 0
full = False
cache_get = cache.get # bound method to lookup a key or return None
cache_len = cache.__len__ # get cache size without calling len()
lock = RLock() # because linkedlist updates aren't threadsafe
root = [] # root of the circular doubly linked list
root[:] = [root, root, None, None] # initialize by pointing to self
Оболочка получает блокировку перед выполнением любой операции.
Несколько важных переменных - корневой список содержит все элементы, соответствующие значению maxsize. Важно помнить, что корень ссылается на себя (root[:] = [root, root, None, None]) в предыдущей (0) и следующей позиции (1)
Три проверки высокого уровня
В первом случае, когда maxsize равно 0, это означает отсутствие функциональности кэширования, оболочка оборачивает пользовательскую функцию без какой-либо возможности кэширования. Оболочка увеличивает счетчик промахов кеша и возвращает результат.
def wrapper(*args, **kwds):
# No caching -- just a statistics update
nonlocal misses
misses += 1
result = user_function(*args, **kwds)
return result
Второй случай. когда maxsize равно None. В разделе нет ограничения на количество элементов, которые нужно хранить в кеше. Таким образом, оболочка проверяет наличие ключа в кеше (словаре). Когда ключ присутствует, оболочка возвращает значение и обновляет информацию о попадании в кэш. А когда ключ отсутствует, оболочка вызывает пользовательскую функцию с аргументами, переданными пользователем, обновляет кеш, обновляет информацию о промахе кеша и возвращает результат.
def wrapper(*args, **kwds):
# Simple caching without ordering or size limit
nonlocal hits, misses
key = make_key(args, kwds, typed)
result = cache_get(key, sentinel)
if result is not sentinel:
hits += 1
return result
misses += 1
result = user_function(*args, **kwds)
cache[key] = result
return result
Третий случай, когда maxsize является значением по умолчанию (128) или переданным пользователем целочисленным значением. Вот фактическая реализация кэша LRU. Весь код в обертке потокобезопасным способом. Перед выполнением любой операции прочитайте/запишите/удалите из кеша оболочка получает RLock.
LRU-кэш
Значение в кеше хранится в виде списка из четырех элементов (помните корень). Первый элемент — это ссылка на предыдущий элемент, второй элемент — это ссылка на следующий элемент, третий элемент — это ключ для вызова конкретной функции, четвертый элемент — это результат. Вот фактическое значение аргумента функции Фибоначчи 1 [[[...], [...], 1, 1], [[...], [...], 1, 1], None, None] . [...] означает ссылку на себя (список).
Первая проверка — на попадание в кеш. Если да, значение в кеше представляет собой список из четырех значений.
nonlocal root, hits, misses, full
key = make_key(args, kwds, typed)
with lock:
link = cache_get(key)
if link is not None:
# Move the link to the front of the circular queue
print(f'Cache hit for {key}, {root}')
link_prev, link_next, _key, result = link
link_prev[NEXT] = link_next
link_next[PREV] = link_prev
last = root[PREV]
last[NEXT] = root[PREV] = link
link[PREV] = last
link[NEXT] = root
hits += 1
return result
Когда элемент уже находится в кеше, нет необходимости проверять, заполнена ли циклическая очередь или извлекать элемент из кеша. Скорее измените позиции элементов в круговой очереди. Поскольку недавно использованный элемент всегда находится вверху, код перемещается к недавнему значению в начало очереди, а предыдущий верхний элемент становится следующим за текущим элементом last[NEXT] = root[PREV] = link, link[PREV] = last и link[NEXT] = root. NEXT и PREV инициализируются вверху, что указывает на соответствующие позиции в списке PREV, NEXT, KEY, RESULT = 0, 1, 2, 3 # names for the link fields. Наконец, увеличьте информацию о попадании в кэш и верните результат.
Когда это кеш-промах, обновите информацию о промахах, и код проверит три случая. Все три операции происходят после получения RLock. Три случая в исходном коде в следующем порядке - после получения ключ блокировки найден в кеше, кеш заполнен, и кеш может принимать новые элементы. Для демонстрации давайте проследим порядок, когда кеш не заполнен, кеш заполнен, а ключ доступен в кеше после получения блокировки.
Когда кеш не заполнен
...
else:
# Put result in a new link at the front of the queue.
last = root[PREV]
link = [last, root, key, result]
last[NEXT] = root[PREV] = cache[key] = link
# Use the cache_len bound method instead of the len() function
# which could potentially be wrapped in an lru_cache itself.
full = (cache_len() >= maxsize)
Если кэш не заполнен, подготовьте последние result(link = [last, root, key, result]), чтобы они содержали предыдущую ссылку корня, корень, ключ и вычисленный результат.
Затем укажите недавний результат (ссылку) на вершину циклической очереди (root[PREV] = link), предыдущий элемент root рядом, чтобы указать на недавний результат (last[NEXT]=link), и добавьте последний результат в кеш (cache[key] = link).
Наконец, проверьте, заполнен ли кеш (cache_len() >= maxsize and cache_len = cache.__len__ is declared in the top) и установите статус на полный.
Для примера fib, когда функция получает первое значение 1, корень пуст, а корневое значение равно [[...], [...], None, None], а после добавления результата в циклическую очередь корневое значение равно [[[...], [...], 1, 1], [[...], [...], 1, 1], None, None]. И предыдущий, и следующий указывают на результат ключа 1. А для следующего значения 0 после вставки корневое значение равно
[[[[...], [...], 1, 1], [...], 0, 0], [[...], [[...], [...], 0, 0], 1, 1], None, None]. Предыдущий [[[[...], [...], None, None], [...], 1, 1], [[...], [[...], [...], 1, 1], None, None], 0, 0], следующий [[[[...], [...], 0, 0], [...], None, None], [[...], [[...], [...], None, None], 0, 0], 1, 1]
Когда кэш заполнен
...
elif full:
# Use the old root to store the new key and result.
oldroot = root
oldroot[KEY] = key
oldroot[RESULT] = result
# Empty the oldest link and make it the new root.
# Keep a reference to the old key and old result to
# prevent their ref counts from going to zero during the
# update. That will prevent potentially arbitrary object
# clean-up code (i.e. __del__) from running while we're
# still adjusting the links.
root = oldroot[NEXT]
oldkey = root[KEY]
oldresult = root[RESULT]
root[KEY] = root[RESULT] = None
# Now update the cache dictionary.
del cache[oldkey]
# Save the potentially reentrant cache[key] assignment
# for last, after the root and links have been put in
# a consistent state.
cache[key] = oldroot
- Когда кеш заполнен, используйте корень как oldroot(
oldroot=root) и обновите ключ и результат.
- Затем сделайте следующий элемент oldroot новым корнем (
root=oldroot[NEXT]), скопируйте новый корневой ключ и результат (oldkey = root[KEY] and oldresult = root[RESULT]).
- Установите для нового корневого ключа и результата значение None(
root[KEY] = root[RESULT] = None).
- Удалите элемент старого ключа из кеша (
del cache[oldkey]) и добавьте вычисленный результат в кеш (cache[key] = oldroot).
- Для примера Фибоначчи, когда кеш заполнен и ключ равен
2, корневое значение равно [[[[...], [...], 1, 1], [...], 0, 0], [[...], [[...], [...], 0, 0], 1, 1], None, None], а новый корень в конце блока равен [[[[...], [...], 0, 0], [...], 2, 1], [[...], [[...], [...], 2, 1], 0, 0], None, None]. Как видите, ключ 1 удален и заменен ключом 2.
Когда ключ появляется в кеше после получения блокировки.
if key in cache:
# Getting here means that this same key was added to the
# cache while the lock was released. Since the link
# update is already done, we need only return the
# computed result and update the count of misses.
pass
Когда ключ появляется в кэше, после получения блокировки другой поток может поставить значение в очередь. Так что делать особо нечего, обертка возвращает результат.
Наконец, код возвращает результат. Перед выполнением части промаха кеша кеш обновления кода пропускает информацию и вызывает функцию make_key.
Примечание. Мне не удалось заставить работать отступ вложенного списка, поэтому ответ может выглядеть немного хуже при форматировании.
person
Kracekumar
schedule
09.07.2020
