Binární vyhledávací stromy: O(log n) a výkon cache

Binární vyhledávací stromy v praxi: Proč O(log n) ne vždy znamená rychlost

Ve světě teoretické informatiky jsou binární vyhledávací stromy (BST) a jejich samovyvažující se varianty, jako jsou červeno-černé stromy, považovány za etalon efektivity pro dynamické datové struktury. Jejich asymptotická složitost O(log n) pro operace vkládání, vyhledávání a mazání vypadá ideálně. Avšak v praxi, v podmínkách moderní architektury procesorů s víceúrovňovou cache pamětí, může výkon BST výrazně zaostávat za jednoduššími strukturami, i když ty mají podobnou teoretickou složitost. Tento článek zkoumá příčiny tohoto rozporu a nabízí praktická doporučení pro výběr datových struktur.

Neočekávaný pokles výkonu kompilátoru

Představte si situaci: kompilátor tráví 60 % svého času ne parsováním nebo generováním kódu, ale vyhledáváním symbolů v tabulce. Pro vestavěné systémy s tisíci symboly je to nepřijatelné. Tabulka symbolů, která ukládá názvy proměnných, funkcí a typů, byla implementována na základě červeno-černého stromu – klasického samovyvažujícího se BST. Teoreticky by O(log n) mělo zajistit vysokou rychlost.

Avšak profiler perf ukázal znepokojivý obrázek:

$ perf stat -e cache-misses,instructions ./compiler test.c
  Performance counter stats:
    2,847,234 cache-misses
    8,500,000 instructions

Téměř 2,8 milionu cache missů na 8,5 milionu instrukcí – to je jeden cache miss na každé tři instrukce. Takový ukazatel naznačuje vážné problémy s přístupem k paměti. V rámci experimentu byl červeno-černý strom nahrazen seřazeným polem s binárním vyhledáváním, které má také teoretickou složitost O(log n). Výsledek byl ohromující: kompilátor se zrychlil 3krát.

Jak mohou dvě datové struktury se stejnou asymptotickou složitostí vykazovat tak odlišný výkon? Odpověď spočívá ve specifikách fungování cache paměti.

Vyšetřování příčin: Cache paměť a missy

Detailní analýza pomocí perf potvrdila domněnky. Srovnání červeno-černého stromu a seřazeného pole odhalilo kritický rozdíl v chování cache:

# Verze s červeno-černým stromem
$ perf stat -e cache-references,cache-misses,cycles ./compiler_rbtree test.c
  Performance counter stats:
    3,247,832  cache-references
    2,847,234  cache-misses  (87.7% miss rate)
   24,000,000  cycles

# Verze se seřazeným polem
$ perf stat -e cache-references,cache-misses,cycles ./compiler_array test.c
  Performance counter stats:
    1,123,456  cache-references
      234,567  cache-misses  (20.9% miss rate)
    8,000,000  cycles

Červeno-černý strom vykazoval 87,7 % cache missů, zatímco seřazené pole – pouze 20,9 %. Na systémech RISC-V může každý cache miss stát až 100 CPU cyklů. To znamená, že červeno-černý strom většinu času nečinně čekal na data z hlavní paměti, místo aby prováděl výpočty.

Teorie vs. praxe: Problém sledování ukazatelů

Učebnice datových struktur často vyzdvihují BST pro jejich vyvážený výkon pro různé operace. Zaručují O(log n) pro vkládání, vyhledávání a mazání a také udržují seřazené pořadí prvků. Vyvážené varianty, jako jsou AVL stromy nebo červeno-černé stromy, zabraňují degradaci výkonu na O(n) v nejhorším případě, zajišťujíce logaritmickou výšku.

Tyto teoretické výhody však neberou v úvahu hierarchii paměti moderních počítačů. Problém BST spočívá ve sledování ukazatelů (pointer chasing). Každý přechod z uzlu na jeho potomka (levého nebo pravého) znamená přechod po ukazateli na libovolnou adresu v paměti. To drasticky snižuje efektivitu využití cache.

Seřazené pole: Lokalita dat

Při použití seřazeného pole jsou prvky v paměti umístěny sekvenčně. Například:

Paměť: [10][20][30][40][50][60][70][80]
          ↑   ↑   ↑   ↑   ↑   ↑   ↑   ↑
       0x1000 ...sekvenčně, vhodné pro cache...

Když procesor přistupuje k array[4], načte do cache linky blok paměti o velikosti, například 64 bajtů, který zahrnuje array[4] a několik sousedních prvků (například array[5], array[6]). Následné přístupy k těmto sousedním prvkům budou cache hity, což zabere pouze 1 CPU cyklus.

Binární vyhledávací strom: Roztříštěnost dat

V BST je každý uzel zpravidla alokován dynamicky (například pomocí malloc()) a může být umístěn na libovolném místě haldy. To vede k fragmentaci paměti:

       40 (@ 0x5000)
      /  \
    20    60 (@ 0x2000, @ 0x8000)
   /  \   /  \
  10  30 50  70 (@ 0x1000, @ 0x3000, @ 0x6000, @ 0x9000)

Při vyhledávání v BST bude každý přechod po ukazateli s největší pravděpodobností vyžadovat přístup k zcela nové oblasti paměti, která se nenachází v aktuální cache lince. To vede k cache missům, což způsobuje zpoždění stovek CPU cyklů, dokud data nejsou načtena z hlavní paměti.

Zvažme vyhledávání hodnoty 70:

Seřazené pole (binární vyhledávání):

* Krok 1: Přístup ke střednímu prvku [40] @ 0x1020. CACHE MISS (100 cyklů). Načte se cache linka obsahující [30][40][50][60].

* Krok 2: Přístup k [60] @ 0x1030. CACHE HIT (1 cyklus).

* Krok 3: Přístup k [70] @ 0x1038. CACHE HIT (1 cyklus).

* Celkem: ~102 cyklů, 1 cache miss.

Binární vyhledávací strom:

* Krok 1: Přístup ke kořenu [40] @ 0x5000. CACHE MISS (100 cyklů). Načte se cache linka na 0x5000.

* Krok 2: Přechod doprava, přístup k [60] @ 0x8000. CACHE MISS (100 cyklů). Adresa v jiné cache lince.

* Krok 3: Přechod doprava, přístup k [70] @ 0x9000. CACHE MISS (100 cyklů). Další nová adresa.

* Celkem: ~300 cyklů, 3 cache missy.

Oba algoritmy provádějí stejný počet logických porovnání, ale kvůli cache missům je BST výrazně pomalejší.

Srovnání výkonu a kódu

Pro názornost uvádíme příklady kódu pro vyhledávání a výsledky benchmarků.

Vyhledávání v BST:

// Uzel binárního vyhledávacího stromu
typedef struct bst_node {
    int key;
    void *value;
    struct bst_node *left;
    struct bst_node *right;
} bst_node_t;

void* bst_search(bst_node_t *root, int key) {
    while (root) {
        if (key == root->key) return root->value;
        root = (key < root->key) ? root->left : root->right;
    }
    return NULL;
}

Vyhledávání v seřazeném poli:

typedef struct {
    int key;
    void *value;
} array_entry_t;

void* array_search(array_entry_t *arr, int n, int key) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid].key == key) return arr[mid].value;
        if (key < arr[mid].key) right = mid - 1;
        else left = mid + 1;
    }
    return NULL;
}

Testování 10 000 náhodných vyhledávacích operací na datových sadách různých velikostí ukázalo:

Datová sada: 1000 prvků

* BST: 2400 cyklů na vyhledávací operaci

* Seřazené pole: 800 cyklů na vyhledávací operaci

* Zrychlení: 30×

Datová sada: 10000 prvků

* BST: 3200 cyklů na vyhledávací operaci

* Seřazené pole: 1100 cyklů na vyhledávací operaci

* Zrychlení: 2,9×

Statistiky perf pro cache missy:

BST: 8,5 missů na vyhledávací operaci
Seřazené pole: 2,1 missů na vyhledávací operaci

Seřazené pole stabilně vykazuje 3krát lepší výkon. Důvody jsou:

Sekvenční uspořádání paměti: Prvky pole jsou uloženy v souvislém bloku, což je ideální pro cache.
Efektivní využití cache linek: Při každém missu se načte celá cache linka (například 64 bajtů), obsahující hned několik prvků pole, což minimalizuje počet budoucích missů.
Hardwarový prefetching: Moderní procesory mají hardwarové prefetchery, které rozpoznávají sekvenční vzory přístupu a předběžně načítají data do cache, čímž dále snižují latence.

BST tato výhody postrádají. Každé dereferencování ukazatele při vyhledávání může vést k novému cache missu.

Paměťová režie a vyvážené stromy

Kromě problémů s cache mají BST často větší paměťovou režii kvůli ukládání ukazatelů.

Uzel BST (64bitový systém, se zarovnáním):

```c

struct bst_node {

int key; // 4 bajty

void *value; // 8 bajtů

struct bst_node *left; // 8 bajtů

struct bst_node *right; // 8 bajtů

// Výplň: 4 bajty

};

// Celkem: 32 bajtů na prvek

```

Prvek seřazeného pole (se zarovnáním):

```c

struct array_entry {

int key; // 4 bajty

void *value; // 8 bajtů

// Výplň: 4 bajty (pro zarovnání)

};

// Celkem: 16 bajtů na prvek

```

Pro 1000 prvků vyžaduje BST 32 KB, zatímco pole – 16 KB. Zvětšený objem paměti pro BST znamená, že se do cache vejde méně uzlů, což zhoršuje problém s missy.

Mnoho vývojářů se domnívá, že vyvážené stromy (například červeno-černé nebo AVL) řeší všechny problémy BST. Skutečně zaručují logaritmickou výšku stromu, čímž zabraňují degradaci na spojový seznam při nepříznivých vstupních datech. Rotace uzlů, používané k udržení rovnováhy, jsou nízkonákladové operace pro aktualizaci ukazatelů. Tyto mechanismy však neřeší fundamentální problém cache: uzly zůstávají roztroušené po paměti. Cache missy pro červeno-černý strom v kompilátoru byly téměř na každém kroku:

$ perf stat -e cache-misses,L1-dcache-load-misses ./compiler_rbtree test.c
  Performance counter stats:
    2,847,234 cache-misses
    2,654,123 L1-dcache-load-misses

Vyvážené stromy řeší algoritmické problémy nejhoršího případu, ale ne hardwarová omezení související s hierarchií paměti.

Kdy tedy použít binární vyhledávací stromy?

Navzdory popsaným nedostatkům nejsou BST zbytečné. Existují scénáře, kde je jejich použití opodstatněné a dokonce preferované.

Hlavní výhoda BST se projevuje v situacích s častými operacemi vkládání a mazání prvků. V seřazeném poli tyto operace vyžadují posun velkého množství prvků, což vede ke složitosti O(n):

Vkládání do seřazeného pole: O(n)
Mazání ze seřazeného pole: O(n)

Pro BST zůstávají vkládání a mazání operacemi se složitostí O(log n), protože vyžadují pouze aktualizaci několika ukazatelů a případně několik rotací pro udržení rovnováhy. Benchmark na 1000 náhodných operací vkládání/mazání ukazuje:

Seřazené pole: 12000 cyklů/operace (kvůli posunu)
Červeno-černý strom: 3500 cyklů/operace
Zrychlení pro BST: 3,4×

Pokud se tedy vaše datová struktura neustále mění (mnoho vkládání a mazání) a vyhledávací operace nedominují frekvencí, mohou být BST (zejména vyvážené) lepší volbou, navzdory potenciálním problémům s cache. V opačném případě, pro statické nebo zřídka se měnící datové sady, kde převažují vyhledávací operace, seřazená pole nebo jiné struktury optimalizované pro cache (například B-stromy) často vykazují lepší výkon.

Co je důležité

O(log n) negarantuje rychlý výkon v praxi: Asymptotická složitost nebere v úvahu vliv hierarchie paměti a cache.
Problém sledování ukazatelů: BST trpí nízkou lokalitou dat, což vede k mnoha cache missům a vysokým latencím.
Výhody seřazených polí: Sekvenční uspořádání prvků zajišťuje vysokou lokalitu dat, efektivní využití cache linek a práci hardwarového prefetcheru.
Paměťová režie: BST vyžadují více paměti kvůli ukládání ukazatelů, což dále snižuje efektivitu cache.
Vyvážené stromy neřeší problém cache: Zabraňují degradaci výšky, ale nezlepšují lokalitu dat.
Používejte BST pro časté vkládání/mazání: Pokud operace změny dat převažují nad vyhledáváním, mohou být BST efektivnější než seřazená pole.

— Editorial Team