Facebook jiftaħ l-implimentazzjoni tat-tabelli tal-hash F14

kumpanija Facebook ħabbar dwar l-implimentazzjoni ta 'sors miftuħ ta' tabelli hash F14, ottimizzat għal konsum effiċjenti tal-memorja. F14 jintuża fl-infrastruttura ta 'Facebook bħala sostitut għall-biċċa l-kbira tat-tipi ta' tabelli hash u jista 'jnaqqas il-konsum tal-memorja mingħajr ma tiġi sagrifikata l-prestazzjoni. F14 notevolment taqbeż it-tabelli tal-hash ta' google::sparse_hash_map, li s'issa tqiesu l-aktar effiċjenti f'termini ta' konsum tal-memorja. Il-kodiċi tal-proġett huwa miktub f'C++ u huwa inkluż fil-librerija Sħubija.

F14 jirreferi għal algoritmi b'sistema ta' riżoluzzjoni tal-ħabtiet ibbażata fuq hashing doppju b'14 sekwenzi ta' kampjuni (katina ta '14-il slot hija maħżuna f'ċellula waħda tal-hash table, u l-intervall bejn iċ-ċelloli huwa kkalkulat bl-użu ta' funzjoni hash awżiljarja). Biex tħaffef l-operazzjonijiet ta 'filtrazzjoni taċ-ċelluli, l-implimentazzjoni tuża struzzjonijiet tal-vettur SSE2 għal sistemi x86_64 u NEON għal Aarch64, li jippermettu l-parallelizzazzjoni tal-eżekuzzjoni ta' operazzjonijiet għall-għażla ta 'slots bi ktajjen taċ-ċwievet u tgħarbil iċ-ċwievet fi ħdan il-katina. Blokki ta '14-il slot huma pproċessati kull darba, li huwa l-aħjar bilanċ bejn l-effiċjenza tal-użu tal-cache tal-proċessur u n-numru ta' ħabtiet.

Karatteristika speċjali ta 'F14 hija l-abbiltà li tagħżel strateġiji differenti ta' ħażna ta 'dejta:

• F14NodeMap - jikkonsma l-inqas memorja għal ċwievet kbar u ta 'daqs medju. Jiżgura li l-elementi jinħażnu indirettament b'sejħa għal malloc fuq kull inserzjoni;
• F14ValueMap - jipprovdi konsum minimu ta 'memorja għal ċwievet żgħar. L-elementi huma maħżuna fiċ-ċelloli nfushom (inline). Għal ċwievet medji u kbar, dan l-approċċ iwassal għal overhead notevoli tal-memorja;
• F14VectorMap - jaħdem aktar malajr għal tabelli kbar u ċwievet kumplessi, iżda aktar bil-mod għal ċwievet sempliċi u tabelli żgħar. L-elementi huma ppakkjati f'firxa mimlija kontinwament u indirizzati b'indikatur ta' indiċi ta' 32 bit;
• F14FastMap hija strateġija magħquda. Jekk iċ-ċavetta hija inqas minn 24 bytes, allura jintgħażel F14ValueMap, u jekk aktar, jintgħażel F14VectorMap.

Sors: opennet.ru