Optimierung von Präfixbäumen: Von 825 MB auf 18 MB für Autovervollständigung
Ein Trie zur Suche nach 50.000 Befehlen verbrauchte 825 MB Speicher und war achtmal langsamer als eine Hash-Tabelle (4,8 Mio. Zyklen gegenüber 600 K). Jeder Knoten hatte eine Größe von 2.064 Byte mit einem 256-Pointer-Array, was häufige Cache-Misses bei der Suche verursachte.
Der perf stat-Benchmark zeigte 125 K Cache-Misses gegenüber nur 18 K bei der Hash-Tabelle. Die Suche nach einem 5-Zeichen-String löste fünf Cache-Misses aus, da jeder Knoten nicht in einer einzigen Cache-Line Platz fand.
Knotenstruktur und Speicherverbrauch
Standardimplementierung eines Knotens:
typedef struct trie_node {
struct trie_node *children[256]; // 2048 Bytes
void *value; // 8 Bytes
bool is_end; // 1 Byte
// Gesamt: 2064 Bytes
} trie_node_t;Für eine Datenmenge von 50.000 Befehlen (durchschnittliche Länge 8 Zeichen) waren etwa 400.000 Knoten nötig – 825 MB gegenüber nur 1,2 MB bei der Hash-Tabelle, eine Differenz von 687-fach.
Komprimierte Bäume: Kettenkompression
Lösung: Komprimierte Bäume (Patricia-Bäume), bei denen Ketten aus Einzelkinder-Knoten zu Präfixen zusammengefasst werden. Knoten speichern statt einzelner Zeichen nun Präfix-Strings.
typedef struct radix_node {
char *prefix;
int prefix_len;
struct radix_node *children[256];
void *value;
} radix_node_t;Suchalgorithmus:
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;
}Ergebnis: Speicherplatz sank auf 330 MB, Zyklen auf 2,4 Mio. und Cache-Misses auf 6,8 – eine Verdoppelung der Geschwindigkeit.
Adaptive Radix-Bäume (ART)
Das Problem blieb: 98 % der 256-Pointer-Arrays waren leer. Lösung: adaptive Knoten basierend auf der Anzahl der Kinder.
- Node4 (1–4 Kinder): 40 Bytes
- Node16 (5–16 Kinder): 152 Bytes
- Node48 (17–48 Kinder): 640 Bytes
- Node256 (49+ Kinder): 2048 Bytes
Wachstumsstrategie: Node4 → Node16 → Node48 → Node256, sobald die Grenzen überschritten sind.
Durchschnittliche Knotengröße: 40–152 Bytes gegenüber 2048 – Speicherersparnis von 10 bis 50-fach.
Benchmark-Ergebnisse
Vergleich bei 1 Mio. Suchen über 50.000 Befehle:
| Struktur | Speicher | Zyklen | Cache-Misses | Geschwindigkeitszuwachs |
|----------|----------|--------|--------------|------------------------|
| 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 ist 45-fach kompakter als der Standard-Trie; Node4/Node16-Knoten passen in 1–2 Cache-Lines.
Einsatzgebiete für Präfixbäume
Verwenden Sie ART, wenn Sie Präfixoperationen benötigen:
- Autovervollständigung: Durchlaufen des Unterbaums in O(k + m), wobei m die Anzahl der Treffer ist. Hash-Tabellen erfordern einen vollständigen Durchlauf.
- IP-Routing: Längster Präfix-Abgleich anhand der Bitfolge.
- Rechtschreibprüfung: Suche mittels Edit-Distanz über Präfixe.
- Spärliche Arrays: Wie im Linux-Kernel verwendet (Seiten-Cache, IDR, XArray).
Vermeiden Sie sie für exakte Suchen, kleine Datensätze (<1.000 Elemente) oder Zeichenketten ohne gemeinsame Präfixe.
Komprimierte Bäume im Linux-Kernel
Der Kernel nutzt radix_tree_node mit 64 Slots (6 Bits pro Ebene). Bei einem 32-Bit-Index ergeben sich 6 Ebenen – etwa 6 Cache-Misses gegenüber 32 bei einem BST.
Vorteile:
- Unterstützung von Bereichsoperationen
- Vorhersehbare O(log₆₄ n)-Komplexität
- Effizient für spärliche Daten
Wichtige Erkenntnisse
- Standard-Tries verbrauchen 687-fach mehr Speicher aufgrund der 256-Pointer-Arrays
- ART reduziert Speicher auf 18 MB und Cache-Misses auf 3,2 durch adaptive Knoten
- Für Präfixabfragen nutzen; Hash-Tabellen schlagen bei exakten Suchen
- Komprimierte Bäume komprimieren Ketten und liefern eine Verdopplung der Geschwindigkeit
- Der Linux-Kernel nutzt sie für spärliche Arrays und ID-Zuweisung
— Editorial Team
Noch keine Kommentare.