[Python] Python LRU Cache 성능 최적화

 

DP유형의 알고리즘 문제를 풀다 모범 답안으로 @lru_cache 데코레이터를 쓴 파이썬 함수가 있어 궁금해서 찾아봤다. 라떼는 이런거 없었는데....

LRU Cache란 무엇인가?

LRU(Least Recently Used) Cache는 가장 최근에 사용되지 않은 항목을 제거하는 캐싱 전략이다. 메모리가 제한된 환경에서 효율적인 데이터 관리를 위해 사용되며, 프로그램의 성능을 크게 향상시킬 수 있다.

 

LRU Cache의 핵심 개념

• 캐시 히트(Cache Hit): 요청된 데이터가 캐시에 있는 경우
• 캐시 미스(Cache Miss): 요청된 데이터가 캐시에 없어서 새로 계산해야 하는 경우
• 용량 제한: 메모리 사용량 제어를 위한 최대 항목 수 설정
• 교체 정책: 캐시가 가득 찼을 때 어떤 항목을 제거할지 결정

Python @lru_cache 데코레이터 사용법 (python 3.2 이상)

기본 사용법

from functools import lru_cache

@lru_cache(maxsize=128)
def expensive_function(n):
    print(f"Computing for {n}")
    result = sum(i**2 for i in range(n)) # 복잡한 연산
    return result


print(expensive_function(100))  # 계산 실행
print(expensive_function(100))  # 캐시에서 반환 (빠름)
print(expensive_function(200))  # 새로운 계산 실행

 

캐시 정보 확인 및 관리

@lru_cache(maxsize=100)
def fibonacci(n):
    if n < 2:
        return n
    return fibonacci(n-1) + fibonacci(n-2) # 재귀함수에서도 사용 가능 (Memoization)

# 캐시 통계 확인
print(fibonacci.cache_info())  # CacheInfo(hits=0, misses=0, maxsize=100, currsize=0)

fibonacci(50)
print(fibonacci.cache_info())  # 히트/미스 정보 확인

# 캐시 초기화
fibonacci.cache_clear()

LRU Cache 내부 구현 원리

Python의 LRU Cache의 구현을 위해서는 HashMap과 Double Linked-List 구조로 이루어지고 동작 과정은 아래와같다.thread saftey 하기 때문에 멀티쓰레드 환경에서도 사용 가능하다.

1. 함수 호출 시 키 생성

• _make_key(args, kwds, typed)로 인자와 키워드를 튜플로 묶어 캐시 키를 만듦.
• 단일 값이 int, str이면 그대로 키로 사용하고, 아니면 _HashedSeq로 래핑.

2. 캐시 조회/추가

• 캐시에서 키를 조회.
  • 있으면: 연결 리스트에서 해당 노드를 가장 최근 위치로 이동시키고, 저장된 결과 반환(hits 증가).
  • 없으면: 실제 함수 실행, 결과를 캐시에 저장(misses 증가).
    • 캐시가 가득 차 있으면 가장 오래된 노드(루트의 NEXT)를 삭제하고 새 노드를 삽입.
    • 캐시가 가득 차 있지 않으면 새 노드를 루트의 PREV 위치에 삽입.

3. 연결 리스트 관리

• 캐시의 순서를 관리하기 위해 이중 연결 리스트(원형)를 사용.
• 최근 사용한 노드는 리스트의 뒤(root[PREV])로 보내고, 오래된 노드는 앞(root[NEXT])로 이동.

lru_cahce 실제 구현된 Python 함수

def lru_cache(maxsize=128, typed=False):
    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

def _lru_cache_wrapper(user_function, maxsize, typed, _CacheInfo):
    # cache: 실제 저장소
    # root: 이중 연결 리스트의 루트
    # wrapper: 함수 호출 시 캐시 처리 담당

 

마무리

lru_cache를 쓰면 hash이기 때문에 DP문제에 대해 time-complexity O(1)으로 해결 가능하고, 알고리즘 문제 뿐만 아니라, 실제 비즈니스 어플리케이션에서도 캐시가 필요할 때 사용할 수 있어서 참고하면 좋을 것 같다.

 

참고.

https://docs.python.org/3/library/functools.html#functools.lru_cache

functools — Higher-order functions and operations on callable objects

https://github.com/python/cpython/blob/3.13/Lib/functools.py

cpython/Lib/functools.py at 3.13 · python/cpython