LIFO Cache : essence, algorithme de pile et fonctionnement

Qu'est-ce que le LIFO Cache ?

LIFO Cache (Last In First Out Cache) est un cache de taille fixe implémenté sur une pile. Lorsqu'un nouvel élément est ajouté à un cache plein, l'élément le plus récent (le sommet) est supprimé et le nouvel élément prend sa place. Le nom « Last In First Out » signifie que l'élément entré en dernier dans le cache sera supprimé en premier.

Cette politique diffère radicalement de LRU et FIFO. Alors que LRU tente de conserver les données les plus pertinentes (par temps du dernier accès) et que FIFO préserve l'« âge » des données, LIFO sacrifie délibérément les données récentes. Cela peut sembler contre-intuitif pour la mise en cache, mais pour certains scénarios, LIFO s'avère être la solution optimale.

Une implémentation classique de LIFO Cache utilise une pile basée sur un tableau ou une liste chaînée. Un tableau fournit un stockage compact et une localité de cache, mais nécessite une pré-allocation de mémoire pour maxSize. Une liste chaînée est plus flexible, mais chaque élément nécessite de la mémoire supplémentaire pour les pointeurs (8–16 octets par élément).

Opérations de Base du LIFO Cache

L'opération push(value) ajoute un élément au sommet de la pile. Si la taille atteint maxSize, le sommet est supprimé avant l'insertion. L'opération pop() supprime et retourne l'élément supérieur — utile pour les scénarios d'« annulation de la dernière action ». L'opération peek() retourne l'élément supérieur sans le supprimer — pour visualiser le dernier état sauvegardé sans modifier la pile.

Comment fonctionne le LIFO Cache

Le principe de fonctionnement du LIFO Cache est extrêmement simple : toutes les opérations sont effectuées sur une extrémité de la structure — le sommet de la pile. Lorsqu'un nouvel élément est ajouté, il est placé au sommet. Si la pile est pleine, l'élément du sommet est retiré et le nouveau prend sa place. La suppression n'affecte toujours qu'un seul élément — le sommet — donc l'algorithme ne nécessite ni itération ni recherche.

Cette propriété fait du LIFO Cache le plus rapide parmi toutes les politiques de suppression : toutes les opérations s'exécutent en O(1) sans aucune structure de données supplémentaire. Pas besoin de table de hachage pour les recherches, pas de liste doublement chaînée pour le réordonnancement — juste un simple pointeur vers le sommet de la pile. La consommation mémoire est minimale : seulement le stockage des éléments eux-mêmes.

Cependant, la simplicité a un inconvénient : le LIFO Cache ne prend pas en compte la fréquence ou le temps du dernier accès aux données. Si une application demande d'abord les données A, B, C puis à nouveau A, C (le dernier ajouté) sera supprimé lorsque le cache sera plein, même si A n'est plus pertinent. Pour les scénarios de cache généraux, cela fait de LIFO le pire choix, car les données récentes sont souvent les plus précieuses.

Taille de la Pile et Gestion de la Mémoire

Pour un LIFO Cache basé sur un tableau, la taille est définie à la création et ne change pas dynamiquement. Si la pile est pleine et qu'un push se produit, l'élément du sommet est écrasé. Pour une implémentation avec liste chaînée, la mémoire est allouée par élément selon les besoins, mais lorsque la limite est atteinte, l'ancien nœud est détaché et peut être collecté par le ramasse-miettes. Dans les applications mobiles, il est recommandé d'utiliser un tableau pour LIFO Cache, car il ne crée pas de charge supplémentaire sur le GC.

LIFO vs LRU et FIFO : Comparaison des Stratégies

Le choix de la stratégie de suppression affecte directement l'efficacité du cache. LIFO, LRU et FIFO représentent différentes approches de la même question : quel élément supprimer lorsque le cache est plein. Chaque approche est optimale pour sa propre classe de tâches.

LRU offre généralement le meilleur taux de succès mais nécessite plus de mémoire et est plus complexe à implémenter. FIFO est un compromis entre performance et taux de succès, utile pour les données en streaming. LIFO est le plus simple mais avec un faible taux de succès : il ne doit être utilisé que lorsque la sémantique « dernier entré, premier sorti » correspond à la logique métier (navigation, opérations d'annulation).

Où le LIFO Cache est utilisé

Malgré son adéquation limitée pour le cache général, le LIFO Cache trouve son utilisation dans des scénarios spécifiques où l'ordre de traitement des données est inverse à l'ordre d'arrivée. Examinons les principaux cas.

Piles de Navigation

Dans les applications mobiles, une pile de navigation est utilisée : lorsqu'un nouvel écran est ouvert, il est placé au sommet de la pile ; lorsque le bouton « Retour » est enfoncé, il est supprimé. Si la profondeur de la pile est limitée (par exemple, maximum 10 écrans), LIFO Cache supprimera automatiquement l'écran le plus récent lorsque la limite est dépassée. Cela permet de contrôler la consommation mémoire de la pile de navigation sans perdre les écrans ouverts précédemment.

Piles Annuler/Rétablir

Le mécanisme d'annulation (Undo) est un exemple classique de LIFO. Chaque action de l'utilisateur est sauvegardée dans une pile. Lorsqu'Undo est appelé, la dernière action est annulée et déplacée vers la pile Rétablir. La limitation de la taille des piles via LIFO Cache garantit que lorsque la limite est dépassée, les actions les plus anciennes (au bas de la pile) restent tandis que les plus récentes sont supprimées — ce qui est logique car l'utilisateur annule généralement les actions récentes tandis que les anciennes ne sont plus pertinentes.

Mise en Tampon des Calculs Temporaires

Dans les calculs récursifs avec retour en arrière (backtracking), les résultats des étapes intermédiaires sont sauvegardés dans l'ordre LIFO. Lorsque le tampon déborde, le dernier résultat est abandonné — ce qui est acceptable car l'algorithme peut le recalculer si nécessaire. Cette approche est utilisée dans les analyseurs syntaxiques, les compilateurs et les algorithmes de parcours de graphes avec limites de profondeur.

Exemples de Code LIFO Cache

Examinons une implémentation de LIFO Cache en Kotlin utilisant un tableau de taille fixe. Un tableau offre les meilleures performances et la consommation mémoire minimale pour les appareils mobiles.

class LifoCache<V>(
    private val maxSize: Int
) {
    private val array = arrayOfNulls<V>(maxSize)
    private var top = -1

    fun push(value: V) {
        if (top == maxSize - 1) {
            top--  // discard oldest when full
        }
        array[++top] = value
    }

    fun pop(): V? {
        if (top == -1) return null
        val result = array[top]
        array[top--] = null
        return result
    }

    fun peek(): V? {
        return array[top]
    }
}

L'indice top pointe vers le sommet de la pile. push incrémente top et écrit la valeur ; si le tableau est plein (top == maxSize - 1), top est décrémenté avant l'écriture — le sommet de la pile est écrasé, ce qui implémente la suppression LIFO. La méthode pop retourne l'élément et décrémente top, tandis que peek lit simplement l'élément supérieur sans modifier la pile.

Exemple : Pile de Navigation avec LIFO Cache

Considérez l'utilisation de LIFO Cache pour limiter la profondeur de navigation dans Jetpack Compose. Lorsqu'un nouvel écran est ouvert, il est ajouté à la pile, et lorsque la limite est dépassée, l'écran le plus récent est supprimé.

class NavigationStack(maxDepth: Int = 10) {
    private val cache = LifoCache<Screen>(maxDepth)

    fun navigateTo(screen: Screen) {
        cache.push(screen)
    }

    fun goBack(): Screen? {
        return cache.pop()
    }

    fun currentScreen(): Screen? {
        return cache.peek()
    }
}

Dans cet exemple, NavigationStack utilise LIFO Cache pour stocker l'historique des écrans. Lorsque navigateTo est appelé, l'écran est ajouté à la pile ; lorsque goBack est appelé, le dernier est supprimé. Si l'utilisateur a ouvert 11 écrans avec une limite de 10, le plus récent (11e) supprimera le précédent (10e) — le premier écran reste dans la pile, ce qui correspond aux attentes de l'utilisateur lors de la navigation arrière. Cette stratégie est plus efficace que LRU pour la navigation : supprimer les écrans ouverts depuis longtemps (« accueil », « profil ») entraînerait un comportement inattendu.