Мемоизация: когда кэш результатов функции оправдан

Прямой ответ

Мемоизация — сохранение результата функции в словаре по её аргументам, чтобы при повторном вызове с теми же аргументами не выполнять вычисление заново.

В Python это одна строка:

from functools import cache, lru_cache

@cache                      # неограниченный кэш (Python 3.9+)
def fib(n: int) -> int:
    return n if n < 2 else fib(n - 1) + fib(n - 2)

@lru_cache(maxsize=1024)    # кэш с ограничением и вытеснением LRU
def parse_template(name: str) -> Template:
    return load_template(name)

lru_cache поддерживает интроспекцию и управление:

parse_template.cache_info()   # CacheInfo(hits=912, misses=48, maxsize=1024, currsize=48)
parse_template.cache_clear()  # сброс

Условия, при которых мемоизация применима:

1. Функция чистая. Результат зависит только от аргументов и не имеет побочных эффектов. Функция, читающая базу или текущее время, не подходит: кэш вернёт устаревшее значение.
2. Аргументы хешируемы. Списки, словари и изменяемые объекты не могут быть ключами кэша; нужны кортежи, строки, числа.
3. Вычисление дороже поиска. Если тело функции — одна арифметическая операция, кэш замедлит вызов, а не ускорит.
4. Повторные вызовы действительно есть. Доля попаданий измеряется через cache_info(); при низкой доле кэш только расходует память.

Практическая оценка выигрыша:

before = time.perf_counter()
results = [heavy(x) for x in workload]
after = time.perf_counter()
print(heavy.cache_info())   # hits / misses показывает реальную долю повторных вызовов

Типичные задачи, где мемоизация даёт заметный эффект: рекурсивные вычисления с перекрывающимися подзадачами, разбор и компиляция шаблонов и регулярных выражений, нормализация данных, вычисление производных значений в цикле.

Практика: ограничения и подводные камни

1. Кэш хранит ссылки. Результат и аргументы удерживаются в памяти, поэтому объект не освобождается сборщиком мусора. Неограниченный @cache на функции с уникальными аргументами — это утечка памяти; подробнее о том, почему сборщик здесь не поможет, в статье про сборку мусора.

@lru_cache(maxsize=None)          # опасно: рост без границы
def get_user(user_id: int) -> User: ...

@lru_cache(maxsize=4096)          # ограниченный объём
def get_user(user_id: int) -> User: ...

2. Кэш не знает об изменении источника. Если данные в базе обновились, мемоизированная функция вернёт прежнее значение. Для таких случаев нужен срок жизни записи, а lru_cache его не предоставляет — требуется собственная реализация или внешнее хранилище.

3. Мемоизация метода удерживает self. Ключ кэша включает экземпляр, поэтому все объекты, у которых вызывали метод, остаются живы. Это частая причина неожиданного роста памяти в долгоживущих процессах.

4. Потокобезопасность частична. Словарь кэша защищён от повреждения, но сама функция может выполняться параллельно несколькими потоками при одновременном промахе. Если вычисление дорогое или имеет побочные эффекты, нужна дополнительная блокировка.

5. Инвалидация — ручная. cache_clear() сбрасывает весь кэш целиком; выборочного удаления по ключу стандартная реализация не даёт.

6. Процессный кэш не разделяется между воркерами. Каждый процесс prefork-сервера имеет свой кэш, поэтому доля попаданий ниже, чем ожидается, а общий расход памяти — выше. Для разделяемого кэша используют внешнее хранилище — см. стратегии кэширования.

Рекомендации:

1. Всегда задавайте maxsize. Исключение — вычисления с заведомо небольшим числом комбинаций, например парсинг фиксированного набора констант.
2. Измеряйте долю попаданий. cache_info() показывает, работает ли кэш. Доля ниже 20–30 % обычно означает, что выгода не покрывает расход памяти.
3. Не кэшируйте то, что меняется. Функции, зависящие от внешних данных, требуют TTL; стандартный lru_cache для этого не предназначен.
4. Нормализуйте аргументы. f(1, 2) и f(1.0, 2) дают разные ключи, если типы различаются; приведение типов до вызова повышает долю попаданий.
5. Различайте уровни кэширования. Мемоизация в процессе, кэш в Redis и кэш на уровне HTTP решают разные задачи; о внешнем кэше — в статье про структуры Redis.

Практический сценарий: рост памяти из-за мемоизации метода

Контекст: долгоживущий воркер обрабатывал задачи и потреблял 2,8 ГБ памяти. Профиль показывал большое число живых объектов домена.

1. Диагностика. Проверка кэша показала 1,1 млн записей при maxsize=None. Функция была объявлена как метод класса и мемоизирована декоратором.
2. Причина. Ключ кэша включал self, поэтому каждый обработанный объект задачи оставался в памяти навсегда. Доля попаданий при этом составляла 6 %: задачи почти не повторялись.
3. Вывод. Кэш не давал выгоды, но удерживал объекты. Это была не утечка в строгом смысле: объекты оставались достижимы из кэша.
4. Действия. (а) Декоратор убрали с метода и перенесли на модульную функцию, принимающую только идентификатор; (б) задали maxsize=2048; (в) добавили метрику на cache_info(), чтобы видеть долю попаданий; (г) проверили, что для повторяющихся вычислений остались только функции с высокой долей попаданий.
5. Результат. Потребление памяти стабилизировалось на 620 МБ; время обработки не изменилось, потому что кэш и ранее почти не попадал.

Вывод: мемоизация — не универсальное ускорение. Без измерения доли попаданий она легко превращается в механизм удержания памяти, особенно когда применяется к методам и неограниченному набору аргументов.

FAQ

Чем @cache отличается от @lru_cache? @cache — это lru_cache(maxsize=None), то есть кэш без ограничения и без вытеснения. Он быстрее из-за отсутствия логики вытеснения, но растёт неограниченно. Для большинства задач безопаснее задавать размер явно.

Можно ли мемоизировать асинхронную функцию? Стандартные декораторы для этого не подходят: они кэшируют объект корутины, а не результат. Нужна отдельная реализация, сохраняющая результат после завершения ожидания, или кэширование на уровне вызывающего кода.

Что делать, если аргументы неизменяемы по смыслу, но не хешируемы? Преобразовать их к хешируемому представлению: список — к кортежу, словарь — к кортежу отсортированных пар, объект — к его идентификатору или набору значимых полей.

Когда лучше внешний кэш вместо мемоизации? Когда результат нужен нескольким процессам, когда требуется срок жизни записи или когда объём кэша превышает разумный размер памяти процесса.

Источники: Python docs (functools, weakref), Wikipedia (memoization) — ссылки в шапке.