Vérifier l’éviction et la capacité d’un cache LRU iOS

Après plusieurs chargements de pages successives dans une liste, des données tout juste consultées sont déjà évincées alors que le cache est encore loin de la capacité prévue. Avant d’ajouter de la mémoire, vérifiez la logique : bien souvent, les lectures ne mettent pas à jour l’ordre d’accès, ou les mises à jour d’une même clé laissent des doublons. Sur un Mac cloud, isoler cette logique dans un package Swift autonome permet de reproduire le problème avec quelques séquences d’opérations déterministes, sans interface, sans réseau et sans simulateur.

Définir d’abord les cinq règles du contrat de cache

Nous allons vérifier un cache LRU dont la capacité est limitée par le nombre d’entrées : les entrées les moins récemment utilisées sont évincées en premier. L’expiration et la persistance sur disque ne font pas partie du périmètre. Commençons par fixer cinq règles :

• Une lecture qui trouve la clé la marque comme la plus récemment utilisée.
• Une lecture qui ne trouve pas la clé ne modifie pas l’ordre existant.
• L’écriture sur une clé existante met à jour sa valeur et sa position dans l’ordre d’accès, sans augmenter le nombre d’entrées.
• Si l’écriture d’une nouvelle clé dépasse la capacité, la clé la moins récemment utilisée est évincée.
• Une capacité nulle ne permet de conserver aucune donnée ; une capacité négative constitue une erreur d’appel.

Ces règles doivent être validées par l’équipe, et non déduites des détails de l’implémentation. Par exemple, certains besoins métier imposent qu’une lecture ne prolonge pas la présence d’une entrée dans le cache. Cette politique d’accès diffère de celle définie ici : les mêmes résultats attendus ne sont donc pas directement réutilisables.

Le taux de succès est un indicateur d’exécution ; l’ordre d’éviction relève du contrat fonctionnel. Un taux de succès apparemment normal peut masquer des clés en double et des évictions incorrectes.

Implémenter un modèle observable dans un répertoire indépendant

Une fois la chaîne d’outils complète installée sur le nœud, exécutez les commandes suivantes dans un répertoire de travail indépendant. Aucun droit administrateur ni lancement d’interface graphique n’est nécessaire.

mkdir LRUContract
cd LRUContract
swift package init --type library

Remplacez le contenu de Sources/LRUContract/LRUContract.swift par l’implémentation ci-dessous. Le tableau d’ordre va de l’entrée la plus ancienne à la plus récente pour faciliter les assertions ; cette implémentation ne vise pas les performances sur des caches de grande capacité.

public final class LRU<Key: Hashable, Value> {
    private let capacity: Int
    private var values: [Key: Value] = [:]
    public private(set) var oldestFirst: [Key] = []

    public init(capacity: Int) {
        precondition(capacity >= 0)
        self.capacity = capacity
    }

    public var count: Int { values.count }

    public func get(_ key: Key) -> Value? {
        guard let value = values[key] else { return nil }
        touch(key)
        return value
    }

    public func put(_ key: Key, _ value: Value) {
        guard capacity > 0 else { return }
        values.updateValue(value, forKey: key)
        touch(key)
        if values.count > capacity {
            let victim = oldestFirst.removeFirst()
            values.removeValue(forKey: victim)
        }
    }

    private func touch(_ key: Key) {
        oldestFirst.removeAll { $0 == key }
        oldestFirst.append(key)
    }
}

touch supprime d’abord l’ancienne position de la clé, puis l’ajoute à la fin : une même clé ne peut donc pas occuper deux positions. L’écriture passe ici par updateValue pour éviter de mêler à la logique de mise à jour la sémantique de suppression propre à l’affectation via l’indice d’un dictionnaire. Si l’implémentation de production utilise plutôt un dictionnaire associé à une liste doublement chaînée, vous pouvez conserver ces tests. En revanche, ne présentez pas cette version à base de tableau comme une implémentation en temps constant.

Distinguer les erreurs de lecture et de mise à jour avec des séquences courtes

Supprimez les exemples de tests générés automatiquement dans le répertoire des tests, puis enregistrez le contenu suivant dans Tests/LRUContractTests/LRUContractTests.swift. L’utilisation explicite de XCTest évite de dépendre du framework de test choisi par le modèle d’initialisation.

import XCTest
@testable import LRUContract

final class LRUContractTests: XCTestCase {
    func testReadPromotesAndMissDoesNot() {
        let cache = LRU<String, Int>(capacity: 2)
        cache.put("a", 1)
        cache.put("b", 2)
        XCTAssertNil(cache.get("missing"))
        XCTAssertEqual(cache.oldestFirst, ["a", "b"])
        XCTAssertEqual(cache.get("a"), 1)
        XCTAssertEqual(cache.oldestFirst, ["b", "a"])
        cache.put("c", 3)
        XCTAssertNil(cache.get("b"))
        XCTAssertEqual(cache.oldestFirst, ["a", "c"])
        XCTAssertEqual(cache.count, 2)
    }

    func testUpdateDoesNotConsumeAnotherSlot() {
        let cache = LRU<String, Int>(capacity: 2)
        cache.put("a", 1)
        cache.put("b", 2)
        cache.put("a", 9)
        XCTAssertEqual(cache.count, 2)
        XCTAssertEqual(cache.oldestFirst, ["b", "a"])
        cache.put("c", 3)
        XCTAssertNil(cache.get("b"))
        XCTAssertEqual(cache.get("a"), 9)
    }

    func testZeroCapacityStoresNothing() {
        let cache = LRU<String, Int>(capacity: 0)
        cache.put("a", 1)
        XCTAssertEqual(cache.count, 0)
        XCTAssertTrue(cache.oldestFirst.isEmpty)
        XCTAssertNil(cache.get("a"))
    }
}

Lancez swift test. Un échec du premier test signale généralement un problème de promotion à la lecture ou un effet de bord lors d’une lecture sans résultat. Si le deuxième échoue, examinez en priorité les mises à jour d’une même clé. Le troisième empêche qu’une capacité nulle conserve malgré tout une entrée. Ne vérifiez pas uniquement le nombre final d’entrées : il peut être correct alors que les clés conservées sont entièrement erronées.

Une vérification peut elle-même modifier l’ordre

get n’est pas une interface d’observation sans effet de bord. L’appeler pour vérifier une valeur modifie le choix de la prochaine entrée à évincer. C’est pourquoi l’exemple ci-dessus vérifie d’abord l’ordre, puis lit la valeur. Dans vos tests, évitez de parcourir toutes les clés en appelant get : le test modifierait lui-même l’état qu’il cherche à examiner.

Passer de trois cas de test à la validation de séquences

Lors du raccordement au cache réel, ajoutez quatre types de séquences : une capacité de un, des écrasements successifs de la même clé, des lectures successives sans résultat et une réinsertion après éviction. À chaque étape, vérifiez que le nombre d’entrées ne dépasse pas la capacité, que l’ordre ne contient aucune clé en double et que sa longueur correspond au nombre réel d’entrées.

Pour aller plus loin, vous pouvez générer des opérations pseudo-aléatoires avec une graine fixe, mais conservez aussi la liste complète des opérations. Chaque trace d’échec doit au minimum contenir le numéro de l’opération, la clé, la valeur écrite et l’ordre avant et après l’exécution. Vous pourrez ainsi rejouer la séquence même après une évolution de l’implémentation.

Si la version de production utilise une liste chaînée, prenez le modèle simple à base de tableau comme référence : exécutez la même séquence sur les deux et comparez les résultats. Ne recopiez pas l’implémentation de production pour en faire la « réponse de référence » : un même défaut pourrait alors passer inaperçu des deux côtés.

Respecter les limites du modèle lors de l’intégration au projet iOS

Cet exemple ne comporte aucun mécanisme de synchronisation. Même avec seulement deux tâches de téléchargement asynchrones, vous ne pouvez pas le partager directement. Si vous utilisez un actor ou un point d’accès unique sérialisé, la promotion à la lecture, l’écriture et l’éviction doivent toutes être protégées. Verrouiller uniquement les écritures ne suffit pas à préserver l’ordre.

Limiter le nombre d’entrées ne revient pas non plus à limiter le nombre d’octets. Dix miniatures et dix images originales n’ont pas le même coût mémoire. Si vous passez à une limite fondée sur le coût, vous devrez définir séparément les règles de coût total, de remplacement du coût lors de la mise à jour d’une même clé et de rejet d’une entrée trop volumineuse. Les tests de nombre d’entrées existants ne prouvent pas le respect d’un budget mémoire.

Enfin, adaptez le cache réellement utilisé par l’application au même contrat, plutôt que de limiter les tests au modèle pédagogique. Une fois les tests de l’algorithme seul réussis, ajoutez quelques tests d’intégration pour vérifier que les écritures à la fin des téléchargements et les lectures depuis l’interface passent bien par la même instance. Conserver les séquences qui échouent permet de mieux résoudre les problèmes qu’augmenter aveuglément la capacité du cache.

Questions fréquentes