Binuksan ng Facebook ang pagpapatupad ng mga F14 hash table

kumpanya sa Facebook inihayag ang tungkol sa open source na pagpapatupad ng mga hash table F14, na-optimize para sa mahusay na pagkonsumo ng memorya. Ginagamit ang F14 sa imprastraktura ng Facebook bilang kapalit ng karamihan sa mga uri ng hash table at maaaring bawasan ang pagkonsumo ng memory nang hindi sinasakripisyo ang pagganap. Ang F14 ay kapansin-pansing mas mahusay sa google::sparse_hash_map hash tables, na sa ngayon ay itinuturing na pinakamabisa sa mga tuntunin ng pagkonsumo ng memorya. Ang project code ay nakasulat sa C++ at kasama sa library Kabulaanan.

Ang F14 ay tumutukoy sa mga algorithm na may sistema ng paglutas ng banggaan batay sa double hashing na may 14 pagkakasunud-sunod ng mga sample (isang chain ng 14 na puwang ay nakaimbak sa isang hash table cell, at ang pagitan sa pagitan ng mga cell ay kinakalkula gamit ang isang auxiliary hash function). Upang mapabilis ang mga pagpapatakbo ng pag-filter ng cell, ang pagpapatupad ay gumagamit ng mga tagubilin sa vector na SSE2 para sa mga x86_64 system at NEON para sa Aarch64, na nagbibigay-daan sa pag-parallelize sa pagpapatupad ng mga operasyon para sa pagpili ng mga puwang na may mga key chain at pagsasala ng mga susi sa loob ng chain. Ang mga bloke ng 14 na puwang ay pinoproseso sa isang pagkakataon, na siyang pinakamainam na balanse sa pagitan ng kahusayan ng paggamit ng cache ng processor at ang bilang ng mga banggaan.

Ang isang espesyal na tampok ng F14 ay ang kakayahang pumili ng iba't ibang mga diskarte sa pag-iimbak ng data:

• F14NodeMap - kumokonsumo ng pinakamaliit na memorya para sa malaki at katamtamang laki ng mga key. Tinitiyak na ang mga elemento ay hindi direktang nakaimbak na may isang tawag sa malloc sa bawat pagpapasok;
• F14ValueMap - nagbibigay ng kaunting memory consumption para sa maliliit na key. Ang mga elemento ay naka-imbak sa mga cell mismo (inline). Para sa katamtaman at malalaking key, ang diskarte na ito ay humahantong sa kapansin-pansing memory overhead;
• F14VectorMap - gumagana nang mas mabilis para sa malalaking talahanayan at kumplikadong mga key, ngunit mas mabagal para sa mga simpleng key at maliliit na talahanayan. Ang mga elemento ay naka-pack sa isang patuloy na populated array at tinutugunan ng isang 32-bit index pointer;
• Ang F14FastMap ay isang pinagsamang diskarte. Kung ang key ay mas mababa sa 24 bytes, ang F14ValueMap ay pipiliin, at kung higit pa, ang F14VectorMap ang pipiliin.

Pinagmulan: opennet.ru