Facebook iepenet ymplemintaasje fan F14-hash-tabellen

Facebook bedriuw oankundige oer iepen boarne ymplemintaasje fan hash tabellen F14, optimalisearre foar effisjint ûnthâld konsumpsje. F14 wurdt brûkt yn 'e Facebook-ynfrastruktuer as ferfanging foar de measte soarten hash-tabellen en kin ûnthâldferbrûk ferminderje sûnder prestaasjes op te offerjen. F14 docht merkber better as google :: sparse_hash_map hash tabellen, dy't oant no ta binne beskôge as de meast effisjint yn termen fan ûnthâld konsumpsje. De projektkoade is skreaun yn C ++ en is opnommen yn 'e bibleteek Folly.

F14 ferwiist nei algoritmen mei in botsingsresolúsjesysteem basearre op dûbele hashing mei 14 sekwinsjes fan samples (in keatling fan 14 slots wurdt opslein yn ien hash tabel sel, en it ynterval tusken sellen wurdt berekkene mei help fan in auxiliary hash funksje). Foar in flugger sel filter operaasjes, de ymplemintaasje brûkt vector ynstruksjes SSE2 foar x86_64 systemen en NEON foar Aarch64, dy't tastean parallelizing de útfiering fan operaasjes foar in selektearje slots mei kaai keatlingen en sifting út kaaien binnen de keatling. Blokken fan 14 slots wurde tagelyk ferwurke, dat is it optimale lykwicht tusken de effisjinsje fan it brûken fan de prosessor-cache en it oantal botsingen.

In spesjale eigenskip fan F14 is de mooglikheid om ferskate strategyen foar gegevensopslach te selektearjen:

• F14NodeMap - konsumearret it minste ûnthâld foar grutte en middelgrutte kaaien. Soarget derfoar dat eleminten wurde opslein yndirekt mei in oprop oan malloc op eltse ynfoegje;
• F14ValueMap - jout minimale ûnthâld konsumpsje foar lytse kaaien. Eleminten wurde opslein yn 'e sellen sels (ynline). Foar middelgrutte en grutte kaaien liedt dizze oanpak ta merkbere ûnthâld overhead;
• F14VectorMap - wurket flugger foar grutte tabellen en komplekse kaaien, mar stadiger foar ienfâldige kaaien en lytse tabellen. De eleminten wurde ynpakt yn in kontinu befolke array en oanpakt troch in 32-bit yndeks pointer;
• F14FastMap is in kombinearre strategy. As de kaai is minder as 24 bytes, dan is F14ValueMap selektearre, en as mear, F14VectorMap is selektearre.

Boarne: opennet.ru