LIFO Cache: lényeg, veremalgoritmus és hogyan működik

Mi az a LIFO Cache?

LIFO Cache (Last In First Out Cache) — egy korlátozott méretű gyorsítótár, amely verem alapján van megvalósítva. Amikor egy új elemet adunk a teli gyorsítótárhoz, a legfrissebb (legfelső) elem eltávolításra kerül, és az új elem foglalja el a helyét. A «Last In First Out» név azt jelenti, hogy az az elem, amely utoljára került a gyorsítótárba, elsőként kerül eltávolításra.

Ez a politika gyökeresen eltér az LRU-tól és a FIFO-tól. Míg az LRU megpróbálja megtartani a legaktuálisabb adatokat (az utolsó hozzáférés ideje alapján), és a FIFO megőrzi az adatok «életkorát», addig a LIFO tudatosan feláldozza a friss adatokat. Ez ésszerűtlennek tűnhet a gyorsítótárazáshoz, de bizonyos forgatókönyvekben a LIFO optimális megoldásnak bizonyul.

A LIFO Cache klasszikus megvalósítása tömbön vagy láncolt listán alapuló vermet használ. A tömb kompakt tárolást és gyorsítótár-lokalitást biztosít, de előzetes memóriafoglalást igényel a maxSize számára. A láncolt lista rugalmasabb, de minden elem többletmemóriát igényel a mutatók számára (elemenként 8–16 bájt).

A LIFO Cache alapműveletei

A push(value) művelet hozzáad egy elemet a verem tetejéhez. Ha a méret elérte a maxSize értéket, a beszúrás előtt a tető eltávolításra kerül. A pop() művelet eltávolítja és visszaadja a legfelső elemet — hasznos a «legutóbbi művelet visszavonása» forgatókönyvekhez. A peek() művelet visszaadja a legfelső elemet eltávolítás nélkül — az utoljára elmentett állapot megtekintéséhez anélkül, hogy megváltoztatná a vermet.

Hogyan működik a LIFO Cache

A LIFO Cache működési elve rendkívül egyszerű: minden művelet a szerkezet egyik végén — a verem tetején — történik. Amikor egy új elemet adunk hozzá, az a tetőre kerül. Ha a verem tele van, a legfelső elem kiszorításra (eltávolításra) kerül, és az új elem foglalja el a helyét. Kiszorítás mindig csak egy elemet érint — a tetőt, így az algoritmus nem igényel bejárást vagy keresést.

Ez a tulajdonság teszi a LIFO Cache-t a leggyorsabbá az összes kiszorítási politika közül: minden művelet O(1) időben történik, mindenféle további adatszerkezet nélkül. Nincs szükség hash táblára a kereséshez, nincs szükség kétszeresen láncolt listára a átrendezéshez — elég egy egyszerű mutató a verem tetejére. Memória minimálisan fogy: csak maguknak az elemeknek a tárolásához.

Az egyszerűségnek azonban van egy hátránya is: a LIFO Cache nem veszi figyelembe az adatokhoz való hozzáférés gyakoriságát vagy idejét. Ha az alkalmazás először A, B, C adatokat kér, majd újra A-t — túlcsorduláskor a C (utoljára hozzáadott) kerül eltávolításra, még akkor is, ha A már nem aktuális. Az általános gyorsítótárazási forgatókönyvekhez ez teszi a LIFO-t a legrosszabb választássá, mivel a friss adatok gyakran a legértékesebbek.

Veremméret és memóriakezelés

A tömb alapú LIFO Cache esetében a méret a létrehozzáskor kerül beállításra, és nem változik dinamikusan. Ha a verem tele van és push történik — a legfelső elem felülírásra kerül. A láncolt listán alapuló megvalósításnál a memória minden elemhez szükség szerint kerül lefoglalásra, de a korlát elérése után a régi csomópont leválasztásra kerül, és a szemétgyűjtő összegyűjtheti. Mobilalkalmazásokban ajánlott a tömb használata a LIFO Cache-hez, mivel ez nem terheli többletterheléssel a GC-t.

LIFO vs LRU és FIFO: stratégiák összehasonlítása

A kiszorítási stratégia választása közvetlenül befolyásolja a gyorsítótárazás hatékonyságát. A LIFO, LRU és FIFO különböző megközelítéseket képviselnek ugyanarra a kérdésre: melyik elemet távolítsuk el túlcsorduláskor? Mindegyik megközelítés optimális a saját feladatköréhez.

LRU általában a legjobb hit-ratio-t adja, de több memóriát és bonyolultabb megvalósítást igényel. FIFO — kompromisszum a teljesítmény és a hit-ratio között, hasznos adatfolyamokhoz. LIFO — a legegyszerűbb, de alacsony hit-ratio-val: csak akkor szabad alkalmazni, ha a «utolsó be – első ki» szemantika megfelel az üzleti logikának (navigáció, műveletek visszavonása).

Hol alkalmazzák a LIFO Cache-t

Az általános gyorsítótárazásra való korlátozott alkalmassága ellenére a LIFO Cache konkrét forgatókönyvekben talál alkalmazást, ahol az adatfeldolgozás sorrendje fordított az érkezés sorrendjéhez képest. Tekintsük át a fő eseteket.

Navigációs vermek

A mobilalkalmazásokban navigációs vermet használnak: új képernyő megnyitásakor az a verem tetejére kerül, a «Vissza» gomb megnyomásakor — eltávolításra kerül. Ha a verem mélysége korlátozott (például maximum 10 képernyő), a LIFO Cache automatikusan eltávolítja a legújabb képernyőt a korlát túllépésekor. Ez lehetővé teszi a navigációs verem memóriafogyasztásának szabályozását a korábban megnyitott képernyők elvesztése nélkül.

Undo/Redo vermek

A műveletek visszavonásának mechanizmusa (Undo) — a LIFO klasszikus példája. Minden felhasználói művelet elmentődik a verembe. Az Undo meghívásakor az utolsó művelet visszavonásra kerül és átkerül a Redo verembe. A vermek méretének korlátozása LIFO Cache segítségével garantálja, hogy a korlát túllépésekor a legrégebbi műveletek (a verem alján) megmaradjanak, és a legújabbak eldobásra kerüljenek — ami logikus, mivel a felhasználó általában a közelmúltbeli műveleteket vonja vissza, és a régek már nem aktuálisak.

Ideiglenes számítások pufferelése

Rekurzív számításoknál visszalépéssel (backtracking) a köztes lépések eredményei LIFO sorrendben kerülnek elmentésre. Amikor a puffer túlcsordul, az utolsó eredmény eldobásra kerül — ez elfogadható, mivel az algoritmus szükség esetén újraszámolhatja. Ezt a megközelítést elemzőkben, fordítóprogramokban és gráfbejárási algoritmusokban használják mélységkorlátozással.

LIFO Cache kódpéldák

Tekintsük át a LIFO Cache megvalósítását Kotlinban fix méretű tömb használatával. A tömb biztosítja a legjobb teljesítményt és minimális memóriafogyasztást a mobil eszközök számára.

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--  // a legrégebbi eldobása, ha tele
        }
        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]
    }
}

A top index a verem tetejére mutat. A push növeli a top értékét és írja az értéket; ha a tömb tele van (top == maxSize - 1), az írás előtt a top csökken — a verem teteje felülírásra kerül, ami megvalósítja a LIFO kiszorítást. A pop metódus visszaadja az elemet és csökkenti a top értékét, míg a peek egyszerűen beolvassa a legfelső elemet a verem megváltoztatása nélkül.

Példa: navigációs verem LIFO Cache-szel

Tekintsük át a LIFO Cache használatát a navigációs mélység korlátozására Jetpack Compose-ban. Új képernyő megnyitásakor az hozzáadódik a veremhez, és a korlát túllépésekor a legújabb képernyő kerül kiszorításra.

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()
    }
}

Ebben a példában a NavigationStack LIFO Cache-t használ a képernyő-előzmények tárolására. A navigateTo meghívásakor a képernyő hozzáadódik a veremhez, a goBack esetén — az utolsó eltávolításra kerül. Ha a felhasználó 11 képernyőt nyitott meg 10-es korláttal, a legújabb (11.) kiszorítja az előzőt (10.) — az első képernyő a veremben marad, ami megfelel a felhasználó elvárásainak a visszatéréskor. Ez a stratégia hatékonyabb, mint az LRU a navigációhoz: a régen megnyitott képernyők («kezdőlap», «profil») eltávolítása váratlan viselkedéshez vezetne.