1
Vývoj / Re:C, zápis do pole čísel a zápis mimo cache L1/L2
« kdy: 16. 01. 2020, 01:43:18 »
Máš v zásadě dvě možnosti. Jedna už padla někde na začátku - seřadit čísla i databázi a zvýšit tak šanci na cache-hit. Nemusí být nutně řazeno lexikograficky, může být podle hash apod - takže řazení může být konstantní operace (resp zařazení - v podstatě radix sort).
Druhá možnost, je klasická hash tabulka, ale trochu chytřeji orientovaná. Hash nesmí být per entry, ale musí být součástí indexu a měl by být taky dostatečně velký. Část hash (nebo případně agregovaný přes shift + xor + mask) se použije jako index do indexovací tabulky, najde se seznam teoretických záznamů v indexu, ale ještě u těch pointerů je uložený kompletnější hash, který eliminuje false hit. Až když větší hash odpovídá, jde se teprve na skutečnou entry, která může obsahovat zbytek hash (i index může obsahovat třeba jen 4-6 byte hash kvůli minimalizaci paměti) a samozřejmě kompletní data pro klíč a hodnotu. Použil jsem podobné řešení kdysi na persistentní mapovanou DB (takže o to horší, že data vlastně nebyly ani v RAM) a ten krok s umístěním hash do indexu zvedl performance o řády (klíčem bylo mít dost RAM aspoň na udržení indexu). Tady bude pořád limit cache a paměťová náročnost je samozřejmě daná počtem záznamů v databází, nikoli počtem look-ups.
Druhá možnost, je klasická hash tabulka, ale trochu chytřeji orientovaná. Hash nesmí být per entry, ale musí být součástí indexu a měl by být taky dostatečně velký. Část hash (nebo případně agregovaný přes shift + xor + mask) se použije jako index do indexovací tabulky, najde se seznam teoretických záznamů v indexu, ale ještě u těch pointerů je uložený kompletnější hash, který eliminuje false hit. Až když větší hash odpovídá, jde se teprve na skutečnou entry, která může obsahovat zbytek hash (i index může obsahovat třeba jen 4-6 byte hash kvůli minimalizaci paměti) a samozřejmě kompletní data pro klíč a hodnotu. Použil jsem podobné řešení kdysi na persistentní mapovanou DB (takže o to horší, že data vlastně nebyly ani v RAM) a ten krok s umístěním hash do indexu zvedl performance o řády (klíčem bylo mít dost RAM aspoň na udržení indexu). Tady bude pořád limit cache a paměťová náročnost je samozřejmě daná počtem záznamů v databází, nikoli počtem look-ups.