Facebook tuam txhab hais txog qhib qhov kev siv ntawm cov rooj hash , optimized rau kev nco noj. F14 yog siv nyob rau hauv Facebook infrastructure raws li kev hloov pauv rau feem ntau ntawm cov rooj hash thiab tuaj yeem txo qis kev siv lub cim xeeb yam tsis muaj kev txi. F14 noticeably outperforms google:: sparse_hash_map hash tables, uas tau tam sim no tau suav hais tias yog qhov zoo tshaj plaws nyob rau hauv cov nqe lus ntawm nco noj. Txoj haujlwm code yog sau hauv C ++ thiab suav nrog hauv lub tsev qiv ntawv .
F14 hais txog algorithms nrog kev sib tsoo kev daws teeb meem raws li ob chav hashing nrog 14 (ib txoj hlua ntawm 14 qhov tau muab khaws cia rau hauv ib lub rooj sib tham ntawm tes, thiab lub sijhawm nruab nrab ntawm lub hlwb raug suav nrog kev pabcuam hash ua haujlwm). Txhawm rau kom ceev cov kev ua haujlwm ntawm tes lim dej, qhov kev siv siv vector cov lus qhia SSE2 rau x86_64 systems thiab NEON rau Aarch64, uas tso cai rau kev ua kom zoo sib xws ntawm kev ua haujlwm rau kev xaiv cov slots nrog cov saw tseem ceeb thiab tshem tawm cov yuam sij hauv cov saw hlau. Blocks ntawm 14 slots yog ua tiav nyob rau hauv ib lub sij hawm, uas yog qhov zoo tshaj plaws tshuav nyiaj li cas ntawm kev ua tau zoo ntawm kev siv lub processor cache thiab tus naj npawb ntawm kev sib tsoo.
Ib qho tshwj xeeb ntawm F14 yog lub peev xwm los xaiv cov tswv yim sib txawv ntawm cov ntaub ntawv khaws cia:
- F14NodeMap - siv lub cim xeeb tsawg kawg rau cov yuam sij loj thiab nruab nrab. Xyuas kom meej tias cov khoom raug khaws cia tsis ncaj nraim nrog kev hu rau malloc ntawm txhua qhov ntxig;
- F14ValueMap - muab kev nco tsawg kawg nkaus rau cov yuam sij me. Cov ntsiab lus khaws cia hauv cov hlwb lawv tus kheej (inline). Rau cov yuam sij nruab nrab thiab loj, txoj hauv kev no ua rau pom kev nco qab;
- F14VectorMap - ua haujlwm sai dua rau cov ntxhuav loj thiab cov yuam sij nyuaj, tab sis qeeb dua rau cov yuam sij yooj yim thiab cov rooj me me. Cov ntsiab lus tau ntim rau hauv ib qho chaw nyob tsis tu ncua thiab hais los ntawm 32-ntsis index pointer;
- F14FastMap yog ib lub tswv yim ua ke. Yog tias tus yuam sij tsawg dua 24 bytes, ces F14ValueMap raug xaiv, thiab yog tias ntau dua, F14VectorMap raug xaiv.
Tau qhov twg los: opennet.ru