Facebook-selskap om åpen kildekode-implementering av hash-tabeller , optimalisert for effektivt minneforbruk. F14 brukes i Facebook-infrastrukturen som erstatning for de fleste typer hash-tabeller og kan redusere minneforbruket uten å ofre ytelsen. F14 utkonkurrerer merkbart google::sparse_hash_map hashtabeller, som så langt har vært ansett som de mest effektive med tanke på minneforbruk. Prosjektkoden er skrevet i C++ og er inkludert i biblioteket .
F14 refererer til algoritmer med et kollisjonsoppløsningssystem basert på dobbel hashing med 14 (en kjede med 14 spor er lagret i én hash-tabellcelle, og intervallet mellom cellene beregnes ved hjelp av en ekstra hash-funksjon). For å øke hastigheten på cellefiltreringsoperasjoner, bruker implementeringen vektorinstruksjoner SSE2 for x86_64-systemer og NEON for Aarch64, som tillater parallellisering av utførelse av operasjoner for å velge spor med nøkkelringer og sile ut nøkler i kjeden. Blokker med 14 spor behandles om gangen, noe som er den optimale balansen mellom effektiviteten ved bruk av prosessorbufferen og antall kollisjoner.
En spesiell funksjon ved F14 er muligheten til å velge forskjellige datalagringsstrategier:
- F14NodeMap - bruker minst minne for store og mellomstore nøkler. Sikrer at elementer lagres indirekte med et kall til malloc ved hver innsetting;
- F14ValueMap - gir minimalt minneforbruk for små nøkler. Elementer lagres i selve cellene (inline). For mellomstore og store taster fører denne tilnærmingen til merkbare minnekostnader;
- F14VectorMap - fungerer raskere for store tabeller og komplekse nøkler, men tregere for enkle nøkler og små tabeller. Elementene er pakket inn i en kontinuerlig fylt matrise og adressert av en 32-bits indekspeker;
- F14FastMap er en kombinert strategi. Hvis nøkkelen er mindre enn 24 byte, er F14ValueMap valgt, og hvis mer, er F14VectorMap valgt.
Kilde: opennet.ru