Facebook hap zbatimin e tabelave hash F14

Kompania Facebook i shpallur në lidhje me zbatimin me kod të hapur të tabelave hash F14, i optimizuar për konsum efikas të memories. F14 përdoret në infrastrukturën e Facebook si një zëvendësim për shumicën e llojeve të tabelave hash dhe mund të zvogëlojë konsumin e kujtesës pa sakrifikuar performancën. F14 dukshëm tejkalon tabelat hash google::sparse_hash_map, të cilat deri më tani janë konsideruar si më efikaset për sa i përket konsumit të memories. Kodi i projektit është i shkruar në C++ dhe është i përfshirë në bibliotekë marrëzi.

F14 i referohet algoritmeve me një sistem rezolucioni të përplasjes bazuar në hashimin e dyfishtë me 14 sekuencat e mostrave (një zinxhir prej 14 lojëra elektronike ruhet në një qelizë të tabelës hash dhe intervali midis qelizave llogaritet duke përdorur një funksion ndihmës hash). Për të përshpejtuar operacionet e filtrimit të qelizave, zbatimi përdor udhëzimet vektoriale SSE2 për sistemet x86_64 dhe NEON për Aarch64, të cilat lejojnë paralelizimin e ekzekutimit të operacioneve për zgjedhjen e lojërave elektronike me zinxhirë çelësash dhe shoshitjen e çelësave brenda zinxhirit. Blloqet me 14 slota përpunohen në të njëjtën kohë, që është ekuilibri optimal midis efikasitetit të përdorimit të cache-it të procesorit dhe numrit të përplasjeve.

Një veçori e veçantë e F14 është aftësia për të zgjedhur strategji të ndryshme të ruajtjes së të dhënave:

• F14NodeMap - konsumon më pak memorie për çelësat e mëdhenj dhe të mesëm. Siguron që elementët të ruhen në mënyrë indirekte me një thirrje në malloc në çdo futje;
• F14ValueMap - siguron konsum minimal të memories për çelësat e vegjël. Elementet ruhen në vetë qelizat (në linjë). Për çelësat e mesëm dhe të mëdhenj, kjo qasje çon në ngarkesë të dukshme të memories;
• F14VectorMap - funksionon më shpejt për tabela të mëdha dhe çelësa komplekse, por më ngadalë për çelësa të thjeshtë dhe tavolina të vogla. Elementet janë të paketuara në një grup të populluar vazhdimisht dhe adresohen nga një tregues indeksi 32-bit;
• F14FastMap është një strategji e kombinuar. Nëse çelësi është më pak se 24 bajt, atëherë zgjidhet F14ValueMap dhe nëse më shumë, zgjidhet F14VectorMap.

Burimi: opennet.ru