Hash tabulky a konflikty cache: benchmarky

Hash tabulky: Jak se vyhnout chybám cache v reálných projektech

Hash tabulky slibují vyhledávání v O(1), ale v praxi často prohrávají s lineárním procházením pole kvůli konfliktům cache. Při optimalizaci kompilátoru tabulka symbolů s 500 prvky a 1024 koši generovala 1,2 milionu chyb cache na 5 milionů instrukcí. Nahrazení polem zrychlilo provedení 3násobně. Problém je v přístupových vzorcích, které vyvolávají vyhození linií cache.

Základní implementace a kolize

Jednoduchá hash tabulka s přímým mapováním se neshoduje kvůli kolizím. Zde je základní kód:

typedef struct {
    char *key;
    int value;
} entry_t;

#define TABLE_SIZE 1024

entry_t *table[TABLE_SIZE];

int hash(const char *key) {
    unsigned int h = 0;
    while (*key) {
        h = h * 31 + *key++;
    }
    return h % TABLE_SIZE;
}

Vložení a vyhledávání vyžadují alokaci paměti a porovnávání řetězců, ale bez řešení kolizí je tabulka k ničemu.

Strategie řešení kolizí

Kolize nastane, když různé klíče hashují na stejný index. Dva přístupy:

Spojování do řetězce

Spojový seznam v koši zvyšuje rozptyl paměti:

typedef struct entry {
    char *key;
    int value;
    struct entry *next;
} entry_t;

void insert(const char *key, int value) {
    int index = hash(key);
    entry_t *entry = malloc(sizeof(entry_t));
    entry->key = strdup(key);
    entry->value = value;
    entry->next = table[index];
    table[index] = entry;
}

Vyhledávání jde po pointech, každý krok je potenciální chyba cache.

Otevřené adresování

Lineární sondování po poli zachovává lokalitu:

typedef struct {
    char *key;
    int value;
    int occupied;
} entry_t;

entry_t table[TABLE_SIZE];

void insert(const char *key, int value) {
    int index = hash(key);
    while (table[index].occupied) {
        index = (index + 1) % TABLE_SIZE;
    }
    table[index].key = strdup(key);
    table[index].value = value;
    table[index].occupied = 1;
}

Sekvenční přístup minimalizuje chyby: první načtení linky cache pokrývá 7–8 prvků.

| Strategie | Chyby cache na vyhledávání | Lokalita |

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

| Řetězec | 3–10 na řetězec délky 3 | Špatná |

| Sondování | 1–2 | Dobrá |

Analýza chyb cache

V řetězci každý uzel vyžaduje samostatné načtení: koš (1 chyba), prvek (2–3), next (1). Celkem až 10 chyb.

Sondování načte celou linku cache, následné sondy trefují cache. Rozdíl 3–5násobný v chybách.

Benchmark na 1000 vložení, 10 000 vyhledávání (load factor 0.5, 2048 košů):

• Řetězec: vložení 450k cyklů, vyhledávání 2.1M cyklů, 45k chyb
• Sondování: vložení 180k cyklů, vyhledávání 650k cyklů, 12k chyb

Sondování je rychlejší 3,2násobně.

Kvalita hash funkcí

Špatný hash (key[0] % size) shlukuje klíče podle prvního znaku, průměrný řetězec 38,5.

FNV-1a distribuuje rovnoměrně:

uint32_t fnv1a_hash(const char *key) {
    uint32_t hash = 2166136261u;
    while (*key) {
        hash ^= (uint8_t)*key++;
        hash *= 16777619u;
    }
    return hash;
}

Specializované hashe:

• Pro int: return key;
• Pro pointery: (uintptr_t >> 3) * 2654435761u

Benchmark: FNV-1a dává řetězce délky 0.98 vs 38.5 u špatného hashu.

Řízení zatížení a resize

Load factor = prvků / košů.

• Řetězec: >1.0 přípustné, ale degraduje
• Sondování: <0.7–0.8

Při 0.9: 10.5 sond v průměru, při 0.95 – 20.5.

Resize při překročení 0.7 (zdvojnásobení velikosti, O(n) amortizovaně O(1)):

void insert(const char *key, int value) {
    if (count >= table_size * 0.7) {
        resize_table();
    }
    // vložení
}

Optimalizovaná struktura pro cache

• Otevřené adresování + velikost 2^n (hash & mask místo %).
• Hustá balení:

typedef struct {
    uint32_t hash;
    uint32_t key;
    uint32_t value;
} entry_t;  // 12 bajtů, 5 v linku

• Oddělení klíčů/hodnot pro velké payload.
• SIMD sondování (AVX2 kontroluje 8 prvků najednou).

Hashování Robin Hood

Varianta sondování: při vložení "oloupit" prvky s menší vzdáleností sondy.

Příklad: key4 (hash=1) vytlačí key2 (dist=1 > 0), vyvažuje délky řetězců. Snižuje varianci sond na minimum.

Co je důležité

• Otevřené adresování s lineárním sondováním je 3–5x efektivnější než řetězce z hlediska cache.
• Kvalitní hash (FNV-1a) snižuje kolize 40násobně.
• Load factor <0.7 + resize zdvojením zajišťují amortizované O(1).
• Husté balení a velikost 2^n minimalizují chyby.
• Robin Hood hashování optimalizuje rozptyl sondování.

— Editorial Team