Gibuksan sa Facebook ang pagpatuman sa F14 hash tables

kompanya sa Facebook gipahibalo mahitungod sa open source nga pagpatuman sa hash tables F14, gi-optimize alang sa episyente nga pagkonsumo sa memorya. Ang F14 gigamit sa imprastraktura sa Facebook isip usa ka puli sa kadaghanan sa mga tipo sa hash nga mga lamesa ug makapakunhod sa konsumo sa memorya nga walay pagsakripisyo sa performance. Ang F14 namatikdan nga labaw sa google::sparse_hash_map hash tables, nga sa pagkakaron giisip nga labing episyente sa termino sa memory consumption. Ang code sa proyekto gisulat sa C++ ug gilakip sa librarya Kabuang.

Ang F14 nagtumong sa mga algorithm nga adunay sistema sa resolusyon sa pagbangga base sa double hashing nga adunay 14 han-ay sa mga sample (usa ka kadena sa 14 ka mga slots ang gitipigan sa usa ka hash table cell, ug ang interval tali sa mga cell kalkulado gamit ang auxiliary hash function). Aron mapadali ang mga operasyon sa pagsala sa cell, ang pagpatuman naggamit sa mga instruksyon sa vector nga SSE2 para sa x86_64 nga mga sistema ug NEON para sa Aarch64, nga nagtugot sa pagparis sa pagpatuman sa mga operasyon alang sa pagpili sa mga slot nga adunay mga yawe nga kadena ug pag-ayag sa mga yawe sulod sa kadena. Ang mga bloke sa 14 nga mga puwang giproseso sa usa ka higayon, nga mao ang kamalaumon nga balanse tali sa kahusayan sa paggamit sa cache sa processor ug ang gidaghanon sa mga bangga.

Usa ka espesyal nga bahin sa F14 mao ang abilidad sa pagpili sa lainlaing mga estratehiya sa pagtipig sa datos:

• F14NodeMap - naggamit sa pinakagamay nga memorya alang sa dagko ug medium-sized nga mga yawe. Naghatag dili direkta nga pagtipig sa mga elemento nga adunay tawag sa function sa malloc sa matag pagsal-ot;
• F14ValueMap - naghatag gamay nga konsumo sa memorya alang sa gagmay nga mga yawe. Ang mga elemento gitipigan sa mga selula mismo (inline). Alang sa medium ug dako nga mga yawe, kini nga pamaagi modala ngadto sa mamatikdan nga memorya sa ibabaw;
• F14VectorMap - mas paspas nga molihok alang sa dagkong mga lamesa ug komplikado nga mga yawe, apan mas hinay alang sa yano nga mga yawe ug gagmay nga mga lamesa. Ang mga elemento giputos sa usa ka padayon nga populated array ug gitumong sa usa ka 32-bit index pointer;
• Ang F14FastMap usa ka hiniusang estratehiya. Kung ang yawe dili mubu sa 24 bytes, unya F14ValueMap ang gipili, ug kung daghan pa, gipili ang F14VectorMap.

Source: opennet.ru