Předponové stromy ART: optimalizace paměti a cache

Optimalizace prefixových stromů: z 825 MB na 18 MB pro automatické dokončování

Prefixový strom pro vyhledávání 50 tisíc příkazů zabíral 825 MB paměti a pracoval osmkrát pomaleji než hashová tabulka (4,8 milionu cyklů proti 600 tisícům). Každý uzel měl 2064 bajtů s polem 256 ukazatelů, což způsobovalo mnohonásobné selhání mezipaměti při vyhledávání.

Benchmark perf stat ukázal 125 tisíc selhání mezipaměti proti 18 tisícům u hashové tabulky. Hledání řetězce délky 5 znaků generuje 5 selhání, protože každý uzel se nevejde do jedné řádky mezipaměti.

Struktura uzlu a spotřeba paměti

Běžná implementace uzlu:

typedef struct trie_node {
    struct trie_node *children[256];  // 2048 bajtů
    void *value;                      // 8 bajtů
    bool is_end;                      // 1 bajt
    // Celkem: 2064 bajty
} trie_node_t;

Pro datovou sadu 50 tisíc příkazů (průměrná délka 8 znaků) je potřeba přibližně 400 tisíc uzlů. Celkem 825 MB proti 1,2 MB u hashové tabulky – rozdíl 687×.

Základní stromy: komprese řetězců

Řešení – základní stromy (Patricia tries), kde řetězce jednotlivých uzlů jsou komprimovány do předpon. Uzel uchovává řetězec předpony místo samostatných znaků.

typedef struct radix_node {
    char *prefix;
    int prefix_len;
    struct radix_node *children[256];
    void *value;
} radix_node_t;

Algoritmus hledání:

void* radix_search(radix_node_t *node, const char *key) {
    while (node) {
        int i = 0;
        while (i < node->prefix_len && key[i] == node->prefix[i]) {
            i++;
        }
        if (i < node->prefix_len) return NULL;
        if (key[i] == '\0') return node->value;
        node = node->children[(unsigned char)key[i]];
        key += i + 1;
    }
    return NULL;
}

Výsledek: paměť klesla na 330 MB, cykly na 2,4 milionu, selhání mezipaměti na 6,8. Zrychlení o 2×.

Adaptivní základní stromy (ART)

Problém zůstal: pole 256 ukazatelů je prázdné v 98 %. Řešení – adaptivní uzly podle počtu dětí.

• Node4 (1–4 děti): 40 bajtů
• Node16 (5–16 dětí): 152 bajty
• Node48 (17–48 dětí): 640 bajtů
• Node256 (49+ dětí): 2048 bajtů

Strategie růstu: Node4 → Node16 → Node48 → Node256 při překročení limitu.

Průměrný uzel má 40–152 bajtů místo 2048. Úspora paměti 10–50×.

Benchmarky optimalizací

Srovnání při 1 milionu hledání 50 tisíc příkazů:

| Struktura | Paměť | Cykly | Selhání mezipaměti | Zrychlení |

|-----------|--------|-------|-------------------|-----------|

| Trie | 825 MB | 4 800 | 12,5 | 1× |

| Radix | 330 MB | 2 400 | 6,8 | 2× |

| ART | 18 MB | 1 200 | 3,2 | 4× |

| Hash | 1,2 MB | 600 | 1,8 | 8× |

ART je 45× kompaktnější než standardní trie, uzly Node4/Node16 se vejdou do 1–2 řádek mezipaměti.

Použití prefixových stromů

Použijte ART, pokud potřebujete operace s předponami:

• Automatické dokončování: procházení podstromu v čase O(k + m), kde m je počet shod. Hashová tabulka vyžaduje úplné procházení.
• IP směrování: nejdelší předpona odpovídající bitovému adresu.
• Kontrola pravopisu: vyhledávání podle editační vzdálenosti prostřednictvím předpon.
• Rozrýžené pole: jako v jádru Linux (mezipaměť stránek, IDR, XArray).

Vyhněte se pro přesné vyhledávání, malé datové sady (<1000 prvků) nebo řetězce bez společných předpon.

Základní stromy v jádru Linux

Jádro používá radix_tree_node s 64 sloty (6 bitů na úroveň). Pro 32bitový index – 6 úrovní, přibližně 6 selhání mezipaměti proti 32 u BST.

Výhody:

• Operace s rozsahy
• Předvídatelná složitost O(log₆₄ n)
• Efektivní pro rozrýžená data

Důležité informace

• Standardní trie spotřebují 687× více paměti kvůli polím 256 ukazatelů
• ART snižuje paměť na 18 MB a selhání mezipaměti na 3,2 díky adaptivním uzlům
• Používejte pro předponová vyhledávání; hashové tabulky vyhrávají při přesném vyhledávání
• Základní stromy komprimují řetězce a poskytují 2× zrychlení
• V jádru Linux – standard pro rozrýžená pole a rozdělování ID

— Editorial Team