Konpayi Facebook sou aplikasyon tab hash sous louvri optimize pou konsomasyon memwa efikas. F14 yo itilize nan enfrastrikti Facebook la kòm yon ranplasman pou pifò kalite tab hash epi pèmèt ou diminye konsomasyon memwa san sakrifye pèfòmans. F14 notables depase google::sparse_hash_map tab hash, ki te byen lwen tèlman yo te konsidere kòm memwa ki pi efikas. Kòd pwojè a ekri nan C++ epi li enkli nan bibliyotèk la .
F14 refere a algoritm ak yon sistèm rezolisyon kolizyon ki baze sou hachaj doub ak 14 (yon sèl selil tab la estoke yon chèn 14 fant, epi entèval ant selil yo kalkile lè l sèvi avèk yon fonksyon oksilyè). Pou akselere operasyon filtraj selil yo, aplikasyon an sèvi ak enstriksyon vektè SSE2 pou sistèm x86_64 ak NEON pou sistèm Aarch64, ki pèmèt ou paralelize operasyon yo nan seleksyon fant ak chèn kle ak kle tès depistaj andedan chèn lan. Blòk nan 14 fant yo trete nan yon moman, ki se balans ki pi bon ant efikasite nan lè l sèvi avèk kachèt processeur a ak kantite kolizyon.
Yon karakteristik nan F14 se kapasite nan chwazi diferan estrateji depo done:
- F14NodeMap - konsome pi piti kantite memwa pou kle gwo ak mwayen gwosè. Bay depo endirèk nan eleman ak yon apèl chak fwa yo mete fonksyon malloc la;
- F14ValueMap - Bay konsomasyon memwa minim pou ti kle. Eleman yo estoke nan selil yo tèt yo (inline). Pou kle mwayen ak gwo, apwòch sa a mennen nan yon sou tèt memwa aparan;
- F14VectorMap pi vit pou gwo tab ak kle konplèks, men pi dousman pou kle senp ak ti tab. Eleman yo chaje nan yon etalaj kontigue epi adrese pa yon pointeur endèks 32-bit;
- F14FastMap se yon estrateji konbine. Si kle a se mwens pase 24 bytes, Lè sa a, F14ValueMap chwazi, epi si plis, F14VectorMap chwazi.
Sous: opennet.ru