Structuri de date: nivel expert — memorii, cache, și optimizare la limită

Structurile de date determină performanța oricărui sistem. La nivel expert, nu mai alegem între array și listă — ci între layout-uri de memorie, pattern-uri de cache, alocatoare personalizate, și structuri concepute pentru arhitecturi moderne: NUMA, cache coherence, SIMD, și page-level optimizations.

Avansat 40 min 06 July 2026
structuri de date cache memorie layout NUMA SIMD alocatoare lock-free cache coherence

Paradigma: structura de date = performanță

La nivel entry-level, alegi structura după complexitățile asimptotice. La nivel mid, după pattern-urile de acces. La nivel expert, proiectezi structura pentru un hardware specific: dimensiunea cache line-ului, numărul de canale de memorie, topologia NUMA, și latentele fiecărui nivel de memorie.

Regula de aur a ingineriei de performanță: O structură de date nu e O(log n) — e O(costul real al acceselor la memorie). Iar costul real e dominat de cache misses, NUMA hops, și TLB misses.

Nivelul 1 — Fundamente hardware ignorate de 90% din programatori

Cache lines și false sharing

Un cache line e unitatea minimă de transfer între RAM și cache — de obicei 64 de octeți. Când accesezi un singur octet, CPU-ul încarcă 64 de octeți.

False sharing: Două thread-uri modifică variabile diferite care se află în același cache line. Deși nu e o cursă de date (datele sunt distincte), protocolul de cache coherence (MESI/MOESI) invalidează linia la fiecare scriere, forțând reîncărcări inutile. Rezultat: performanță cu 10-100x mai slabă decât ar fi fără false sharing.

Soluție: Padding la 64 de octeți:

struct DataPadded {
    value: AtomicU64,
    _padding: [u8; 56], // umple cache line-ul
}

Prefetching hardware și software

CPU-ul încearcă să ghicească ce date vei accesa (prefetching hardware). Pattern-urile liniare sunt prezise perfect. Pattern-urile stocastice (linked list, arbori) nu sunt prezise deloc.

Prefetching software: Instrucțiuni explicite (_mm_prefetch în C++, echivalent în Rust prin inline assembly) care spun CPU-ului să aducă datele în cache înainte de a fi necesare.

TLB (Translation Lookaside Buffer)

TLB e cache-ul pentru traducerea adreselor virtuale în fizice. Un TLB miss costă 50-200 de cicli. TLB-ul are de obicei 64-1024 de entry-uri. Dacă structura ta de date e răspândită pe multe pagini de memorie (4KB), vei avea TLB misses frecvente.

Soluție: Folosește pagini mari (2MB, 1GB) — reduce numărul de intrări TLB necesare cu un factor de 500x.

Nivelul 2 — Layout-uri avansate de memorie

AOS vs SOA vs AOSOA

| Layout | Acces | Cache friendly | |---|---|---| | AOS (Array of Structs) | Obiecte compacte | Da, dacă accesezi toate câmpurile | | SOA (Struct of Arrays) | Câmpuri separate | Da, dacă accesezi un singur câmp | | AOSOA (Array of Structs of Arrays) | Hbrid | Optimizat pentru SIMD |

AOSOA — cel mai avansat: Grupează câte N elemente într-un bloc (de obicei 4, 8, sau 16 — cât încape într-un registru SIMD), și în fiecare bloc pune câmpurile sub formă de array-uri mici. Ideal pentru procesoare vectoriale.

Arena allocators și pool allocators

Alocarea din heap (malloc) e lentă și fragmentează memoria. Structurile de date performante nu alocă element cu element — ci folosesc arena allocators:

struct Arena {
    buffer: Vec<u8>,
    cursor: usize,
}

impl Arena {
    fn alloc<T>(&mut self, val: T) -> &mut T {
        let ptr = &self.buffer[self.cursor] as *const u8 as *mut T;
        unsafe { ptr.write(val); }
        self.cursor += size_of::<T>();
        &mut *ptr
    }
}

Avantaje: Alocare O(1), zero fragmentare, cache-friendly (elementele sunt contigue în memorie). Dezavantaj: Nu poți elibera individual — doar tot arena-ul odată.

Intrusive data structures

În loc să stochezi pointeri la noduri, nodul însuși conține link-urile. Folosit extensiv în kernel-ul Linux.

struct ListNode {
    prev: Option<&'static ListNode>,
    next: Option<&'static ListNode>,
    data: [u8; 64],
}
// Lista operează pe nodurile existente — nu alocă nimic.

Avantaje: Zero alocări, cache-friendly, pot fi rearanjate în memorie. Folosit în: Linux kernel, Redis, filer de jocuri.

Nivelul 3 — Structuri de date pentru concurență

Lock-free și wait-free

Structurile lock-free folosesc operații atomice (CAS — Compare-And-Swap, FAA — Fetch-And-Add) pentru a permite accesul concurent fără locks.

Exemplu — lock-free stack (Treiber stack):

struct TreiberStack<T> {
    head: AtomicPtr<Node<T>>,
}

fn push(&self, val: T) {
    let node = Box::into_raw(Box::new(Node { data: val, next: self.head.load(Ordering::Relaxed) }));
    while self.head.compare_exchange_weak(
        node.next, node, Ordering::Release, Ordering::Relaxed
    ).is_err() { /* retry */ }
}

Problema ABA: Un pointer e citit, apoi nodul e eliberat și re-alocat cu aceeași adresă. CAS-ul vede aceeași valoare și crede că nimic nu s-a schimbat. Soluție: tag-uri (aba counter) asociate pointerului.

Hazard pointers și EBR (Epoch-Based Reclamation)

În structurile lock-free, nu poți elibera un nod imediat — alt thread poate avea un pointer la el. Două soluții clasice:

  • Hazard pointers: Fiecare thread marchează pointerii pe care îi folosește. Înainte de a elibera, verifici dacă niciun thread nu folosește acel nod.
  • EBR (Epoch-Based Reclamation): Împărțim timpul în epoci. Un nod e eliberat doar după ce toate thread-urile au părăsit epoca în care nodul a fost marcat pentru ștergere.

NUMA-aware data structures

În sistemele NUMA (Non-Uniform Memory Access), fiecare procesor are propria memorie locală. Accesul la memoria altui procesor e de 2-3x mai lent.

Principii:

  • Fiecare thread alocă din memoria locală (prefer party)
  • Structurile partajate sunt plasate în pagini interleaved (round-robin pe noduri)
  • Pentru cozi producător-consumator: producătorul scrie în memoria locală, consumatorul citește

Exemplu — coadă NUMA-aware: Fiecare pereche (producător, consumator) are un buffer circular local. Datele sunt mutate între buffere doar când e necesar, minimizând accesul la memoria distantă.

Nivelul 4 — Structuri de date ultra-specializate

Radix Tree (Patricia Trie) — nivel kernel

Un radix tree comprimă nodurile cu un singur copil. Linux îl folosește pentru page cache (radix tree per fișier). Cheia e offset-ul în fișier (64 biți), valoarea e pointer la pagina fizică.

Optimizări:

  • Nodurile interne conțin pointeri la subarbori + un bitmap de prezență
  • Căutarea e O(k) unde k = numărul de biți ai cheii (practic O(1) — 48 de biți, 6 niveluri)
  • Cache-friendly — nodurile sunt mici și contigue

B-Tree optimizat pentru SSD

B-Tree-urile clasice sunt optimizate pentru HDD (caută să minimizeze seek-urile). Pentru SSD, optimizarea e pentru scriere secvențială.

LSM-Tree (Log-Structured Merge-Tree):

  1. Scrierile merg într-un memtable în RAM (sortat)
  2. Când memtable-ul e plin, e flush-at pe disc ca SSTable (Sorted String Table)
  3. SSTable-urile sunt îmbinate periodic (compaction)
  4. Citirile verifică mai întâi memtable-ul, apoi SSTable-urile în ordine inversă

Folosit în: LevelDB, RocksDB, Cassandra, BigTable, SQLite (WAL mode).

De ce e mai rapid: Scrierile sunt secvențiale, nu random. Compaction-ul e background.

Bloom Filter — analiză probabilistică

Un Bloom Filter e un bitmap de m biți cu k funcții hash care testează apartenența cu fals-pozitive.

Probabilitatea de fals-pozitiv:

P = (1 - (1 - 1/m)^(k·n))^k ≈ (1 - e^(-k·n/m))^k

Pentru P = 1%, optimul e k = ln(2) · m/n ≈ 9.6 funcții hash.

Variante:

  • Counting Bloom Filter — suportă ștergeri (fiecare poziție e un counter, nu un bit)
  • Cuckoo Filter — mai eficient decât Bloom, suportă ștergeri
  • Quotient Filter — mai rapid, mai compact

Skip List — analiză probabilistică avansată

Înălțimea maximă: Cu probabilitatea p = 1/2, înălțimea e < log_(1/p)(n) cu probabilitate mare.

Memoria: Așteptat: n / (1-p) ≈ 2·n pointeri.

Folosit în: Redis (sorted sets), LevelDB (memtable).

De ce Redis folosește Skip List și nu AVL? Pentru că Skip List suportă range queries eficient și e mai simplu de implementat concurent.

Nivelul 5 — Proiectarea unui allocator personalizat

Un allocator personalizat poate îmbunătăți performanța cu 2-10x comparativ cu malloc general.

Principii

  1. Diminuează fragementarea externă — alocă blocuri de dimensiuni fixe (slab allocator)
  2. Diminuează fragementarea internă — alege cea mai potrivită dimensiune de bloc
  3. Cache locality — elementele alocate împreună sunt plasate în aceleași pagini
  4. Thread-local — fiecare thread are propriul pool, evitând lock-urile

Slab Allocator (folosit de Linux kernel)

struct Slab {
    objects: Vec<u8>,
    free_list: Vec<usize>,  // indici la obiecte libere
    object_size: usize,
    object_count: usize,
}

fn alloc(&mut self) -> &mut [u8] {
    let idx = self.free_list.pop().expect("SLAB full");
    &mut self.objects[idx * self.object_size..(idx+1) * self.object_size]
}

Avantaj: O(1) alloc/dealloc, zero fragmentare. Folosit în: Linux slab allocator, jemalloc, tcmalloc.

Lock-free memory pool

struct Pool {
    slots: Vec<AtomicPtr<Slot>>,
    next_free: AtomicUsize,
}

fn alloc(&self) -> *mut Slot {
    loop {
        let idx = self.next_free.load(Ordering::Acquire);
        if idx >= self.slots.len() { return null; }
        let slot = self.slots[idx].load(Ordering::Relaxed);
        if self.next_free.compare_exchange_weak(idx, idx+1, Ordering::Release, Ordering::Relaxed).is_ok() {
            return slot;
        }
    }
}

Nivelul 6 — Structuri de date experimentale și de frontieră

HAMT (Hash Array Mapped Trie)

Folosit de Clojure, Scala, Rust (im::HashMap) pentru structuri de date persistente (imutabile).

Cum funcționează: Cheia e hash-uită, apoi hash-ul e împărțit în câte 5 biți. Fiecare nivel e un array de 32 de elemente (2^5). Doar nodurile care au elemente sunt alocate (bitmap indexing).

Operații: O(log_32(n)) ≈ O(1) pentru n < 2^32. Memorie: Partajare structurală — copierea unui map de 1M chei costă O(log n) memorie nouă.

Cache-Oblivious Data Structures

Proiectate să fie eficiente pe orice nivel de cache, fără a cunoaște dimensiunea cache-ului.

Principiu: Folosesc recursivitatea pe divizare de matrice/array (cache-oblivious algorithms + layout) pentru a asigura că subproblemele încap în cache la un nivel suficient.

Exemplu — Van Emde Boas layout pentru arbori:

  1. Împarte arborele la jumătatea înălțimii
  2. Plasează subarborii recursiv, contiguu în memorie
  3. Oricare subarbore de dimensiune ≤ cache e plasat într-un bloc contiguu

Rezultat: Complexitate de cache O(log_B N) în loc de O(log_2 N · B) pentru un arbore binar standard.

Z-order (Morton order) Curves

În loc să stochezi o matrice pe rânduri (row-major) sau coloane (column-major), Z-order curve intercalează biții indecșilor. Rezultat: două celule apropiate în spațiul 2D sunt apropiate și în memorie.

Aplicații: Baze de date spațiale, compresie de imagini, ray tracing, simulări fizice.

Cod pentru intercalarea biților (magic bits):

fn morton_encode(x: u32, y: u32) -> u64 {
    // Spread biții lui x și y, apoi intercalează
    fn spread(v: u32) -> u64 {
        let v = v as u64;
        let v = (v | (v << 16)) & 0x0000FFFF0000FFFF;
        let v = (v | (v << 8))  & 0x00FF00FF00FF00FF;
        let v = (v | (v << 4))  & 0x0F0F0F0F0F0F0F0F;
        let v = (v | (v << 2))  & 0x3333333333333333;
        let v = (v | (v << 1))  & 0x5555555555555555;
        v
    }
    spread(x) | (spread(y) << 1)
}

Concluzii practice — ghid de decizie expert

| Ai nevoie de | Folosește | Evită | |---|---|---| | Maximă viteză, date imutabile | HAMT / RRB Vector | HashMap cu multe copii | | Concurență intensă | Lock-free queue + EBR | Mutex pe fiecare acces | | Cache locality maximă | Arena allocator + SOA | malloc per element | | Date pe disc/SSD | LSM-Tree | B-Tree clasic | | Set membership, zero false-negative | Cuckoo Filter | Bloom Filter | | Range queries + sorted sets | Skip List (Redis-style) | AVL (range query scump) | | Alocare zero runtime | Intrusive list + slab allocator | Vec + Box | | Thread safety + NUMA | NUMA-aware pool + per-thread arena | Global lock-free (ABA issues) |

Vezi și

  • Big O
  • Ce sunt algoritmii?
  • Algoritmi de sortare avansați
  • Memory Wall
  • Data-Oriented Design (DOD)

Elemente consecutive în memorie, acces indexat O(1).

| Operație | Cost | Descriere | |---|---|---| | Acces | O(1) | Prin index | | Inserare la final | O(1)* | Redimensionare rară | | Inserare în față | O(n) | Mută toate elementele | | Căutare | O(n) | Liniară |

*Amortizat O(1) cu redimensionare dinamică.

Listă înlănțuită (Linked List)

Elemente legate prin pointeri, structură flexibilă.

Avantaj: Inserare/ștergere O(1) la început. Dezavantaj: Acces O(n), memorie suplimentară per element.

| Tip | Memorie | Acces | |---|---|---| | Simplu înlănțuită | 1 pointer/element | O(n) | | Dublu înlănțuită | 2 pointeri/element | O(n) |

Stivă (Stack)

LIFO — Last In, First Out. Operații: push (O(1)), pop (O(1)), top (O(1)).

Folosită pentru: evaluare expresii, undo/redo, DFS, stiva de apeluri.

Coadă (Queue)

FIFO — First In, First Out. Operații: enqueue (O(1)), dequeue (O(1)).

Folosită pentru: BFS, buffer, scheduling, printer queue.

Tabelă Hash (HashMap)

Stochează perechi cheie-valoare. Acces O(1) în medie.

Coliziuni: Lanțuri separate (linked list), adresare deschisă (probing). Factor de umplere: Load factor = n/m. La > 0.75, redimensionare. Funcția hash: Distribuie uniform cheile.

Caz rău: O(n) — toate cheile în aceeași găleată.

Modul Expert

1. Arbori Binari de Căutare (BST)

Proprietate: stânga < rădăcină < dreapta. Operații: O(h), unde h = înălțimea.

Caz rău: h = n (arbore degenerează în listă) → O(n). Caz bun: h = log n (arbore echilibrat).

AVL (Adelson-Velsky și Landis, 1962)

Primul arbore binar de căutare auto-echilibrat. Înălțimea maximă: 1.44·log₂(n).

Regula: Diferența de înălțime între subarborii stânga și dreapta ≤ 1 (factor de echilibru).

Rotații: Stânga, dreapta, stânga-dreapta, dreapta-stânga — 4 cazuri.

Cost: O(log n) pentru inserare, ștergere, căutare. Dar rotațiile frecvente au cost constant.

Red-Black Tree (1972)

Alternativă la AVL cu rotații mai puține.

Proprietăți:

  1. Fiecare nod e roșu sau negru
  2. Rădăcina e neagră
  3. Frunzele (nil) sunt negre
  4. Un nod roșu nu poate avea copil roșu
  5. Orice drum de la rădăcină la frunză are același număr de noduri negre

Avantaj: Doar O(1) rotații amortizate la inserare. Folosit în Java TreeMap, C++ map.

B-Tree

Arbore cu mai multe chei per nod (degree = t). Toate frunzele la aceeași adâncime.

Proprietăți:

  • Fiecare nod (exceptând rădăcina) are t-1 ≤ chei ≤ 2t-1
  • Toate frunzele la aceeași adâncime
  • Înălțime: O(log_t n)

Folosit în: baze de date (MySQL InnoDB), sisteme de fișiere.

2. Heap-uri

Un heap e un arbore binar unde fiecare părinte e mai mare (max-heap) sau mai mic (min-heap) decât copiii.

| Operație | Cost | |---|---| | Inserare | O(log n) | | Extragere max/min | O(log n) | | Construire | O(n) | | Heapify | O(log n) |

Binomial Heap

Colecție de arbori binomiali. Suportă uniunea (merge) în O(log n).

Fibonacci Heap

Inserare O(1), scădere cheie O(1) amortizat. Extragere minim O(log n) amortizat.

Folosit în: algoritmii lui Dijkstra și Prim cu performanțe mai bune pe grafuri mari.

3. Tabele Hash avansate

Cuckoo Hashing

Folosește două funcții hash. La coliziune, evacuăm elementul existent în cealaltă tabelă. În caz extrem, reconstruim tabelele.

Căutare: O(1) garantat (worst-case, nu doar medie). Inserare: O(1) amortizat.

Consistent Hashing

Folosit în sisteme distribuite (Cassandra, Redis Cluster, CDN-uri).

Fiecare nod e mapat pe un cerc hash. Datele sunt stocate la primul nod în sensul acelor de ceas. La adăugarea/eliminarea unui nod, doar O(1/k) din date se mută.

Bloom Filter

Structură probabilistică pentru testarea apartenenței. Poate da fals-pozitive, dar nu fals-negative.

Cost: O(k) pentru inserare și test, unde k = numărul de funcții hash. Aplicații: cache-uri (evită miss-uri costisitoare), verificare parole, blockchain.

4. Disjoint Set Union (DSU / Union-Find)

Esențial pentru probleme de conexitate în grafuri.

Operații:

  • MakeSet(x) — creează o mulțime cu elementul x
  • Find(x) — găsește reprezentantul mulțimii lui x
  • Union(x, y) — unește mulțimile lui x și y

Optimizări:

  • Union by rank: atașăm arborele mai mic la cel mai mare
  • Path compression: aplatizăm drumul în Find

Complexitate: O(α(n)) per operație, unde α e funcția inversă a lui Ackermann — efectiv constant pentru orice valoare practică.

5. Tries (Arbori de prefixe)

Stochează șiruri de caractere pe muchii, nu în noduri. Căutare O(|șir|), indiferent de numărul de elemente.

Trie clasic

Fiecare nod are 26 de copii (pentru litere mici). Memorie O(alfabet · cuvinte · lungime).

Radix Tree (Patricia Trie)

Comprimă nodurile cu un singur copil. Memorie mai eficientă.

Folosit în: auto-completare, verificare ortografică, routere IP, sisteme de fișiere.

6. Analiză comparativă avansată

| Structură | Acces | Căutare | Inserare | Ștergere | Memorie | |---|---|---|---|---|---| | Array sortat | O(1) | O(log n) | O(n) | O(n) | n | | Hash Table | O(1)* | O(1)* | O(1)* | O(1)* | ~1.3n | | AVL Tree | O(log n) | O(log n) | O(log n) | O(log n) | 3n | | Red-Black | O(log n) | O(log n) | O(log n) | O(log n) | 2n | | B-Tree | O(log n) | O(log t·log_t n) | O(log t·log_t n) | O(log t·log_t n) | ~n | | Skip List | O(log n)* | O(log n)* | O(log n)* | O(log n)* | ~2n | | Trie (șiruri) | O(|s|) | O(|s|) | O(|s|) | O(|s|) | mare |

*Aproximativ / amortizat.

Reguli practice

  • Acces rapid după index: Array
  • Inserări frecvente la început: Listă înlănțuită
  • Căutare rapidă după cheie: Hash Table
  • Date ordonate + căutare: AVL / Red-Black Tree
  • Coadă de prioritate: Heap
  • Conexitate în grafuri: Union-Find
  • Prefixe șiruri: Trie
  • Sisteme distribuite: Consistent Hashing

Vezi și

  • Big O
  • Ce sunt algoritmii?
  • Algoritmi de sortare avansați
  • P vs NP