En résumé : la mise en cache est un moyen facile d'améliorer les performances lorsque des calculs coûteux peuvent être réutilisés. Vous pouvez l'implémenter facilement en Python en utilisant les décorateurs @cache et @lru_cache.

Trouvez le code lié à cette Bits of ... sur GitHub.

Concept

La mise en cache est une technique simple pour accélérer votre code lorsque des calculs coûteux peuvent être réutilisés. Un cache est une couche de stockage de données éphémère à haute vitesse contenant un sous-ensemble de données pour un accès rapide. Au lieu de recalculer à plusieurs reprises les mêmes résultats coûteux, vous les stockez dans le cache. Lorsque vous en avez besoin ultérieurement, vous le lisez à partir du cache au lieu de le recalculer.

La bibliothèque standard de Python fournit des décorateurs pour mettre facilement en cache les fonctions : @cache et @lru_cache du module functools.

Taille du cache

Un cache vit généralement dans un stockage avec un accès considérablement rapide par rapport au temps de calcul des résultats. Il s'agira souvent de votre RAM, qui est limitée en taille. Compromis : plus votre cache est grand, plus vous pouvez économiser de calculs coûteux, mais plus il utilisera d'espace.

Politique d'éviction

La plupart du temps, vous voulez limiter la taille maximale de votre cache. Vous le faites via une politique d'éviction. Il s'agit d'une stratégie pour choisir quel élément supprimer du cache lorsqu'il atteint sa capacité. Une politique simple est la politique du dernier élément utilisé (LRU), qui supprime les entrées de cache les plus anciennes.

Fraîcheur du cache

Rappelez-vous que les éléments du cache ne sont pas recalculés. Si, pour une même entrée, la sortie de votre calcul changera à l'avenir (par exemple, une page Web avec un classement de jeu), vous devez supprimer les éléments obsolètes du cache.

En pratique

Ici, prenons comme exemple le calcul de la séquence de Fibonacci. Nous implémentons la définition récursive qui devient rapidement lente à mesure que le nombre d'entrée augmente.

Voici la récursion : f(n) = f(n-1) + f(n)

Si nous développons quelques termes pour n=10 :

Voici l'implémentation en Python :

# Fibonacci récursif sans cache
def recur_fibo_no_cache(n):
    if n <= 1:
        return n
    else:
        return recur_fibo_no_cache(n - 1) + recur_fibo_no_cache(n - 2)

Cette implémentation est récursive : la fonction s'appelle elle-même plusieurs fois pour résoudre le problème. Ce n'est pas l'implémentation la plus performante. La version itérative est à la fois plus efficace en termes de calcul et de mémoire. Cependant, c'est un bon exemple pour illustrer les avantages de la mise en cache.

Comme vous pouvez le constater, nous répétons les mêmes calculs à maintes reprises. Une manière facile d'accélérer ce code est d'utiliser un cache : nous ne calculerons jamais plus d'une fois pour une entrée donnée.

Dans l'exemple suivant, nous créons 2 fonctions mises en cache en utilisant les décorateurs functools. Ces fonctions appellent simplement l'implémentation récursive, mais elles utilisent un cache pour éviter le recalcul. D'abord, nous utilisons le décorateur @cache, qui utilise un cache non borné. Ensuite, nous utilisons le décorateur @lru_cache avec une taille maximale de 5. @lru_cache(maxsize=None) est équivalent à @cache.

# Fibonacci récursif avec cache (en utilisant le décorateur de cache functools)
@cache
def recur_fibo_cache(n):
    if n <= 1:
        return n
    else:
        return recur_fibo_cache(n - 1) + recur_fibo_cache(n - 2)


# Fibonacci récursif avec cache LRU (en utilisant le décorateur lru_cache functools)
@lru_cache(maxsize=5)
def recur_fibo_lru_cache(n):
    if n <= 1:
        return n
    else:
        return recur_fibo_lru_cache(n - 1) + recur_fibo_lru_cache(n - 2)

Comme toujours, mesurez le gain de performances pour valider la solution. Pas besoin d'ajouter de complexité si cela n'améliore pas les performances !

def exec_and_clear(f, arg):
    a = f(arg)
    f.cache_clear()
    return a

if __name__ == "__main__":
    N = 35
    TIMEIT_NUMBER = 10

    # Calcul du temps d'exécution sans cache, avec cache et avec LRU cache
    no_cache_timer = Timer(lambda: recur_fibo_no_cache(N))
    no_cache_time = no_cache_timer.timeit(number=TIMEIT_NUMBER) / TIMEIT_NUMBER
    print(f"Temps d'exécution sans cache : {no_cache_time:.2e}")

    cache_timer = Timer(lambda: exec_and_clear(recur_fibo_cache, N))
    cache_time = cache_timer.timeit(number=TIMEIT_NUMBER) / TIMEIT_NUMBER
    print(
        f"Temps d'exécution avec cache : {cache_time:.2e}",
    )

    lru_cache_timer = Timer(lambda: exec_and_clear(recur_fibo_lru_cache, N))
    lru_cache_time = lru_cache_timer.timeit(number=TIMEIT_NUMBER) / TIMEIT_NUMBER
    print(
        f"Temps d'exécution avec LRU cache : {lru_cache_time:.2e}",
    )

    print()

    # Calcul de l'accélération pour le cache et le LRU cache par rapport à l'absence de cache
    speedup = round(no_cache_time / cache_time)
    print(f"Accélération du cache par rapport à l'absence de cache : x{speedup:.2e}")

    speedup = round(no_cache_time / lru_cache_time)
    print(f"Accélération du LRU cache par rapport à l'absence de cache (taille max 2) : x{speedup:.2e}")

En utilisant le décorateur @cache, nous obtenons une accélération de x2.44e5 !

En utilisant le décorateur @lru_cache, nous obtenons une accélération de x2.28e5 !