Facebook firmao pri malfermkoda efektivigo de haŝtabeloj , optimumigita por efika memorkonsumo. F14 estas uzata en la Facebook-infrastrukturo kiel anstataŭaĵo por plej multaj specoj de hashtabloj kaj povas redukti memorkonsumon sen oferi rendimenton. F14 rimarkeble superas google::sparse_hash_map hashtablojn, kiuj ĝis nun estis konsideritaj la plej efikaj laŭ memorkonsumo. La projektkodo estas skribita en C++ kaj estas inkluzivita en la biblioteko .
F14 rilatas al algoritmoj kun kolizio rezolucia sistemo bazita sur duobla hashing kun 14 (ĉeno de 14 fendoj estas stokita en unu hashtabelĉelo, kaj la intervalo inter ĉeloj estas kalkulita uzante helpan hashfunkcion). Por akceli ĉelfiltrajn operaciojn, la efektivigo uzas vektorajn instrukciojn SSE2 por x86_64-sistemoj kaj NEON por Aarch64, kiuj permesas paraleligi la plenumon de operacioj por selektado de fendoj kun ŝlosilĉenoj kaj kribri eksteren ŝlosilojn ene de la ĉeno. Blokoj de 14 fendoj estas prilaboritaj samtempe, kio estas la optimuma ekvilibro inter la efikeco de uzado de la procesora kaŝmemoro kaj la nombro da kolizioj.
Speciala trajto de F14 estas la kapablo elekti malsamajn strategiojn de konservado de datumoj:
- F14NodeMap - konsumas la malplej memoron por grandaj kaj mezgrandaj ŝlosiloj. Certigas ke elementoj estas stokitaj nerekte kun voko al malloc sur ĉiu enmeto;
- F14ValueMap - provizas minimuman memorkonsumon por malgrandaj klavoj. Elementoj estas stokitaj en la ĉeloj mem (enliniaj). Por mezaj kaj grandaj klavoj, ĉi tiu aliro kondukas al rimarkinda memoro superkompeto;
- F14VectorMap - funkcias pli rapide por grandaj tabloj kaj kompleksaj ŝlosiloj, sed pli malrapide por simplaj ŝlosiloj kaj malgrandaj tabloj. La elementoj estas pakitaj en kontinue loĝitan tabelon kaj traktitaj per 32-bita indeksmontrilo;
- F14FastMap estas kombinita strategio. Se la ŝlosilo estas malpli ol 24 bajtoj, tiam F14ValueMap estas elektita, kaj se pli, F14VectorMap estas elektita.
fonto: opennet.ru