Drzewa binarne wyszukiwania: O(log n) i wydajność pamięci podręcznej

Binarne drzewa wyszukiwań w praktyce: dlaczego O(log n) nie zawsze oznacza szybkość

W świecie teoretycznej informatyki binarne drzewa wyszukiwań (BST) oraz ich samobalansujące warianty, takie jak drzewa czerwono-czarne, uchodzą za wzorzec efektywności dla dynamicznych struktur danych. Ich asymptotyczna złożoność O(log n) dla operacji wstawiania, wyszukiwania i usuwania wydaje się idealna. Jednak w praktyce, w warunkach nowoczesnej architektury procesorów z wielopoziomową pamięcią podręczną, wydajność BST może znacząco ustępować prostszym strukturom, nawet jeśli te mają podobną złożoność teoretyczną. Ten artykuł bada przyczyny tej rozbieżności i oferuje praktyczne rekomendacje dotyczące wyboru struktur danych.

Nieoczekiwany spadek wydajności kompilatora

Wyobraźmy sobie sytuację: kompilator poświęca 60% swojego czasu nie na parsowanie czy generowanie kodu, lecz na wyszukiwanie symboli w tabeli. Dla systemów wbudowanych z tysiącami symboli jest to niedopuszczalne. Tabela symboli, przechowująca nazwy zmiennych, funkcji i typów, została zaimplementowana w oparciu o drzewo czerwono-czarne — klasyczne, samobalansujące BST. Teoretycznie, O(log n) powinno było zapewnić wysoką szybkość.

Jednak profiler perf ukazał niepokojący obraz:

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

Prawie 2,8 miliona pudeł pamięci podręcznej (cache misses) na 8,5 miliona instrukcji — to jedno pudło na każde trzy instrukcje. Taki wskaźnik świadczy o poważnych problemach z dostępem do pamięci. W ramach eksperymentu drzewo czerwono-czarne zostało zastąpione posortowaną tablicą z wyszukiwaniem binarnym, która również ma teoretyczną złożoność O(log n). Wynik okazał się zdumiewający: kompilator przyspieszył 3-krotnie.

Jak dwie struktury danych o identycznej złożoności asymptotycznej mogą wykazywać tak różną wydajność? Odpowiedź tkwi w specyfice działania pamięci podręcznej.

Badanie przyczyn: pamięć podręczna i pudła

Szczegółowa analiza za pomocą perf potwierdziła przypuszczenia. Porównanie drzewa czerwono-czarnego i posortowanej tablicy ujawniło krytyczną różnicę w zachowaniu pamięci podręcznej:

# Wersja z drzewem czerwono-czarnym
$ 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

# Wersja z posortowaną tablicą
$ 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

Drzewo czerwono-czarne wykazywało 87,7% pudeł pamięci podręcznej, podczas gdy posortowana tablica — zaledwie 20,9%. Na systemach RISC-V każde pudło pamięci podręcznej może kosztować do 100 cykli CPU. Oznacza to, że drzewo czerwono-czarne przez większość czasu pozostawało w bezczynności, oczekując na dane z pamięci głównej, zamiast wykonywać obliczenia.

Teoria kontra praktyka: problem podążania za wskaźnikami

Podręczniki dotyczące struktur danych często wyróżniają BST za ich zrównoważoną wydajność dla różnych operacji. Gwarantują one O(log n) dla wstawiania, wyszukiwania i usuwania, a także utrzymują posortowany porządek elementów. Zbalansowane warianty, takie jak drzewa AVL czy drzewa czerwono-czarne, zapobiegają degradacji wydajności do O(n) w najgorszym przypadku, zapewniając logarytmiczną wysokość.

Jednak te teoretyczne zalety nie uwzględniają hierarchii pamięci współczesnych komputerów. Problem BST polega na podążaniu za wskaźnikami (pointer chasing). Każde przejście od węzła do jego elementu potomnego (lewego lub prawego) oznacza przejście po wskaźniku do dowolnego adresu w pamięci. To drastycznie obniża efektywność wykorzystania pamięci podręcznej.

Posortowana tablica: lokalność danych

Przy użyciu posortowanej tablicy elementy są rozmieszczone w pamięci sekwencyjnie. Na przykład:

Pamięć: [10][20][30][40][50][60][70][80]
          ↑   ↑   ↑   ↑   ↑   ↑   ↑   ↑
       0x1000 ...sekwencyjnie, wygodne dla pamięci podręcznej...

Gdy procesor odwołuje się do array[4], ładuje do linii pamięci podręcznej blok pamięci o rozmiarze, na przykład, 64 bajtów, który zawiera array[4] i kilka sąsiednich elementów (np. array[5], array[6]). Kolejne odwołania do tych sąsiednich elementów będą trafieniami w pamięci podręcznej (cache hit), co zajmuje zaledwie 1 cykl CPU.

Binarne drzewo wyszukiwań: rozproszenie danych

W BST każdy węzeł jest zazwyczaj alokowany dynamicznie (np. za pomocą malloc()) i może być umieszczony w dowolnym miejscu sterty. Prowadzi to do fragmentacji pamięci:

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

Podczas wyszukiwania w BST każde przejście po wskaźniku najprawdopodobniej będzie wymagało dostępu do zupełnie nowego obszaru pamięci, który nie znajduje się w bieżącej linii pamięci podręcznej. Prowadzi to do pudeł pamięci podręcznej (cache miss), co wiąże się z opóźnieniem rzędu setek cykli CPU, zanim dane zostaną załadowane z pamięci głównej.

Rozważmy wyszukiwanie wartości 70:

Posortowana tablica (wyszukiwanie binarne):

* Krok 1: Dostęp do środkowego elementu [40] @ 0x1020. PUDŁO PAMIĘCI PODRĘCZNEJ (100 cykli). Ładowana jest linia pamięci podręcznej zawierająca [30][40][50][60].

* Krok 2: Dostęp do [60] @ 0x1030. TRAFIENIE W PAMIĘCI PODRĘCZNEJ (1 cykl).

* Krok 3: Dostęp do [70] @ 0x1038. TRAFIENIE W PAMIĘCI PODRĘCZNEJ (1 cykl).

* Łącznie: ~102 cykle, 1 pudło pamięci podręcznej.

Binarne drzewo wyszukiwań:

* Krok 1: Dostęp do korzenia [40] @ 0x5000. PUDŁO PAMIĘCI PODRĘCZNEJ (100 cykli). Ładowana jest linia pamięci podręcznej pod adresem 0x5000.

* Krok 2: Przejście w prawo, dostęp do [60] @ 0x8000. PUDŁO PAMIĘCI PODRĘCZNEJ (100 cykli). Adres w innej linii pamięci podręcznej.

* Krok 3: Przejście w prawo, dostęp do [70] @ 0x9000. PUDŁO PAMIĘCI PODRĘCZNEJ (100 cykli). Kolejny nowy adres.

* Łącznie: ~300 cykli, 3 pudła pamięci podręcznej.

Oba algorytmy wykonują taką samą liczbę porównań logicznych, ale z powodu pudeł pamięci podręcznej BST okazuje się znacznie wolniejsze.

Porównanie wydajności i kodu

Dla przejrzystości przedstawiamy przykłady kodu do wyszukiwania oraz wyniki benchmarków.

Wyszukiwanie w BST:

// Węzeł drzewa binarnych wyszukiwań
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;
}

Wyszukiwanie w posortowanej tablicy:

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;
}

Testowanie 10 000 losowych operacji wyszukiwania na zbiorach danych o różnych rozmiarach wykazało:

Zbiór danych: 1000 elementów

* BST: 2400 cykli na operację wyszukiwania

* Posortowana tablica: 800 cykli na operację wyszukiwania

* Przyspieszenie: 3×

Zbiór danych: 10000 elementów

* BST: 3200 cykli na operację wyszukiwania

* Posortowana tablica: 1100 cykli na operację wyszukiwania

* Przyspieszenie: 2,9×

Statystyki perf dotyczące pudeł pamięci podręcznej:

BST: 8,5 pudła na operację wyszukiwania
Posortowana tablica: 2,1 pudła na operację wyszukiwania

Posortowana tablica konsekwentnie wykazuje 3-krotnie lepszą wydajność. Przyczyny tego to:

Sekwencyjny schemat pamięci: Elementy tablicy są przechowywane w ciągłym bloku, co jest idealne dla pamięci podręcznej.
Efektywne wykorzystanie linii pamięci podręcznej: Przy każdym pudle ładowana jest cała linia pamięci podręcznej (np. 64 bajty), zawierająca od razu kilka elementów tablicy, co minimalizuje liczbę przyszłych pudeł.
Sprzętowe wstępne pobieranie (prefetching): Nowoczesne procesory posiadają sprzętowe mechanizmy wstępnego pobierania, które rozpoznają sekwencyjne wzorce dostępu i z wyprzedzeniem ładują dane do pamięci podręcznej, jeszcze bardziej redukując opóźnienia.

BST są pozbawione tych zalet. Każde dereferencjonowanie wskaźnika podczas wyszukiwania może prowadzić do nowego pudła pamięci podręcznej.

Narzut pamięci i drzewa zbalansowane

Oprócz problemów z pamięcią podręczną, BST często mają większy narzut pamięci z powodu przechowywania wskaźników.

Węzeł BST (system 64-bitowy, z wyrównaniem):

```c

struct bst_node {

int key; // 4 bajty

void *value; // 8 bajtów

struct bst_node *left; // 8 bajtów

struct bst_node *right; // 8 bajtów

// Wypełniacz: 4 bajty

};

// Łącznie: 32 bajty na element

```

Element posortowanej tablicy (z wyrównaniem):

```c

struct array_entry {

int key; // 4 bajty

void *value; // 8 bajtów

// Wypełniacz: 4 bajty (dla wyrównania)

};

// Łącznie: 16 bajtów na element

```

Dla 1000 elementów BST wymaga 32 KB, podczas gdy tablica — 16 KB. Zwiększona objętość pamięci dla BST oznacza, że mniej węzłów może zmieścić się w pamięci podręcznej, co pogłębia problem pudeł.

Wielu deweloperów uważa, że drzewa zbalansowane (np. czerwono-czarne lub AVL) rozwiązują wszystkie problemy BST. Rzeczywiście, gwarantują one logarytmiczną wysokość drzewa, zapobiegając degradacji do listy połączonej w przypadku niekorzystnych danych wejściowych. Rotacje węzłów, używane do utrzymania balansu, są niskokosztowymi operacjami aktualizacji wskaźników. Jednak te mechanizmy nie rozwiązują fundamentalnego problemu pamięci podręcznej: węzły nadal pozostają rozrzucone po pamięci. Pudła pamięci podręcznej dla drzewa czerwono-czarnego w kompilatorze występowały niemal na każdym 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

Drzewa zbalansowane rozwiązują algorytmiczne problemy najgorszego przypadku, ale nie sprzętowe ograniczenia związane z hierarchią pamięci.

Kiedy zatem używać binarnych drzew wyszukiwań?

Mimo opisanych wad, BST nie są bezużyteczne. Istnieją scenariusze, w których ich użycie jest uzasadnione, a nawet preferowane.

Główna zaleta BST objawia się w sytuacjach z częstymi operacjami wstawiania i usuwania elementów. W posortowanej tablicy te operacje wymagają przesunięcia dużej liczby elementów, co prowadzi do złożoności O(n):

Wstawianie do posortowanej tablicy: O(n)
Usuwanie z posortowanej tablicy: O(n)

Dla BST wstawianie i usuwanie pozostają operacjami o złożoności O(log n), ponieważ wymagają jedynie aktualizacji kilku wskaźników i, być może, kilku rotacji w celu utrzymania balansu. Benchmark na 1000 losowych operacji wstawiania/usuwania pokazuje:

Posortowana tablica: 12000 cykli/operacja (z powodu przesunięcia)
Drzewo czerwono-czarne: 3500 cykli/operacja
Przyspieszenie dla BST: 3,4×

Zatem, jeśli Twoja struktura danych stale się zmienia (wiele wstawień i usunięć), a operacje wyszukiwania nie dominują pod względem częstotliwości, BST (zwłaszcza zbalansowane) mogą być lepszym wyborem, pomimo potencjalnych problemów z pamięcią podręczną. W przeciwnym razie, dla statycznych lub rzadko modyfikowanych zbiorów danych, gdzie przeważają operacje wyszukiwania, posortowane tablice lub inne struktury zoptymalizowane pod kątem pamięci podręcznej (np. drzewa B), często wykazują lepszą wydajność.

Co ważne

O(log n) nie gwarantuje szybkiej wydajności w praktyce: Asymptotyczna złożoność nie uwzględnia wpływu hierarchii pamięci i pamięci podręcznej.
Problem podążania za wskaźnikami: BST cierpią z powodu niskiej lokalności danych, co prowadzi do wielokrotnych pudeł pamięci podręcznej i wysokich opóźnień.
Zalety posortowanych tablic: Sekwencyjne rozmieszczenie elementów zapewnia wysoką lokalność danych, efektywne wykorzystanie linii pamięci podręcznej i działanie sprzętowego wstępnego pobierania.
Narzut pamięci: BST wymagają więcej pamięci z powodu przechowywania wskaźników, co dodatkowo obniża efektywność pamięci podręcznej.
Drzewa zbalansowane nie rozwiązują problemu pamięci podręcznej: Zapobiegają degradacji wysokości, ale nie poprawiają lokalności danych.
Używaj BST do częstych wstawień/usuęć: Jeśli operacje zmiany danych przeważają nad wyszukiwaniem, BST mogą być efektywniejsze niż posortowane tablice.

— Editorial Team