Facebook uzņēmums par atvērtā koda hash tabulu ieviešanu , optimizēts efektīvam atmiņas patēriņam. F14 tiek izmantots Facebook infrastruktūrā kā aizstājējs lielākajai daļai jaucējtabulu veidu, un tas var samazināt atmiņas patēriņu, nezaudējot veiktspēju. F14 manāmi pārspēj google::sparse_hash_map hash tabulas, kas līdz šim tika uzskatītas par visefektīvākajām atmiņas patēriņa ziņā. Projekta kods ir rakstīts C++ valodā un ir iekļauts bibliotēkā .
F14 attiecas uz algoritmiem ar sadursmes izšķiršanas sistēmu, kuras pamatā ir dubultā jaukšana ar 14 (14 slotu ķēde tiek glabāta vienā jaukšanas tabulas šūnā, un intervāls starp šūnām tiek aprēķināts, izmantojot jaucējfunkciju). Lai paātrinātu šūnu filtrēšanas darbības, ieviešana izmanto vektora instrukcijas SSE2 x86_64 sistēmām un NEON Aarch64, kas ļauj paralēli veikt darbības, lai atlasītu slotus ar atslēgu ķēdēm un izsijātu atslēgas ķēdē. Vienlaicīgi tiek apstrādāti 14 slotu bloki, kas ir optimālais līdzsvars starp procesora kešatmiņas izmantošanas efektivitāti un sadursmju skaitu.
F14 īpaša iezīme ir iespēja izvēlēties dažādas datu uzglabāšanas stratēģijas:
- F14NodeMap - patērē vismazāk atmiņas lieliem un vidējiem taustiņiem. Nodrošina, ka elementi tiek glabāti netieši ar malloc izsaukumu katrā ievietojumā;
- F14ValueMap - nodrošina minimālu atmiņas patēriņu maziem taustiņiem. Elementi tiek glabāti pašās šūnās (inline). Vidējiem un lieliem taustiņiem šī pieeja rada ievērojamas atmiņas izmaksas;
- F14VectorMap - darbojas ātrāk lielām tabulām un sarežģītām atslēgām, bet lēnāk ar vienkāršiem taustiņiem un mazām tabulām. Elementi tiek iesaiņoti nepārtraukti aizpildītā masīvā un adresēti ar 32 bitu indeksa rādītāju;
- F14FastMap ir kombinēta stratēģija. Ja atslēga ir mazāka par 24 baitiem, tiek atlasīts F14ValueMap, un, ja vairāk, tiek atlasīts F14VectorMap.
Avots: opennet.ru