Facebook mécht Implementatioun vun F14 Hash Dëscher op

Facebook Firma ugekënnegt iwwer Open Source Ëmsetzung vun Hash Dëscher F14, optimiséiert fir efficace Erënnerung Konsum. F14 gëtt an der Facebook Infrastruktur als Ersatz fir déi meescht Aarte vun Hash Dëscher benotzt a kann de Gedächtnisverbrauch reduzéieren ouni d'Performance ofzeginn. F14 bemierkbar besser wéi google :: sparse_hash_map Hash-Tabellen, déi bis elo als déi effizientst a punkto Erënnerungsverbrauch ugesi goufen. De Projet Code ass an C ++ geschriwwen an ass an der Bibliothéik abegraff Dommheeten.

F14 bezitt sech op Algorithmen mat engem Kollisiounsopléisungssystem baséiert op Duebelhashing mat 14 Sequenzen vun Echantillon (eng Kette vu 14 Plaze gëtt an enger Hash-Tablezelle gespäichert, an den Intervall tëscht Zellen gëtt mat Hëllef vun enger Hëllefs-Hash-Funktioun berechent). Fir Zellfilteroperatiounen ze beschleunegen, benotzt d'Implementatioun Vektorinstruktiounen SSE2 fir x86_64 Systemer an NEON fir Aarch64, déi d'Ausféierung vun Operatiounen paralleliséiere fir Slots mat Schlësselketten auszewielen an Schlësselen an der Kette auszeféieren. Blocks vu 14 Slots ginn gläichzäiteg veraarbecht, wat den optimale Gläichgewiicht tëscht der Effizienz vum Prozessor Cache an der Unzuel vun de Kollisiounen ass.

Eng speziell Feature vum F14 ass d'Fäegkeet fir verschidde Datelagerstrategien ze wielen:

• F14NodeMap - verbraucht déi mannst Erënnerung fir grouss a mëttelgrouss Schlësselen. Assuréiert datt Elementer indirekt mat engem Opruff zu Malloc op all Insertioun gespäichert ginn;
• F14ValueMap - stellt minimal Erënnerung Konsum fir kleng Schlësselen. Elementer ginn an den Zellen selwer (inline) gespäichert. Fir mëttel- a grouss Schlësselen, féiert dës Approche zu merkbar Erënnerung Overhead;
• F14VectorMap - Wierker méi séier fir grouss Dëscher a komplex Schlësselen, mee méi lues fir einfach Schlësselen a kleng Dëscher. D'Elementer ginn an eng kontinuéierlech populéiert Array gepackt a adresséiert vun engem 32-Bit Indexer;
• F14FastMap ass eng kombinéiert Strategie. Wann de Schlëssel manner wéi 24 Bytes ass, da gëtt F14ValueMap ausgewielt, a wa méi ass F14VectorMap ausgewielt.

Source: opennet.ru