Facebook-företag om implementering av hashtabeller med öppen källkod , optimerad för effektiv minnesförbrukning. F14 används i Facebooks infrastruktur som en ersättning för de flesta typer av hashtabeller och kan minska minnesförbrukningen utan att ge avkall på prestanda. F14 överträffar märkbart google::sparse_hash_map hashtabeller, som hittills ansetts vara de mest effektiva vad gäller minnesförbrukning. Projektkoden är skriven i C++ och ingår i biblioteket .
F14 hänvisar till algoritmer med ett kollisionsupplösningssystem baserat på dubbelhashning med 14 (en kedja av 14 platser lagras i en hashtabellcell och intervallet mellan cellerna beräknas med hjälp av en extra hashfunktion). För att påskynda cellfiltreringsoperationer använder implementeringen vektorinstruktioner SSE2 för x86_64-system och NEON för Aarch64, som möjliggör parallellisering av utförandet av operationer för att välja luckor med nyckelringar och sålla bort nycklar inom kedjan. Block med 14 platser bearbetas åt gången, vilket är den optimala balansen mellan effektiviteten i att använda processorcachen och antalet kollisioner.
En speciell egenskap hos F14 är möjligheten att välja olika datalagringsstrategier:
- F14NodeMap - förbrukar minst minne för stora och medelstora nycklar. Säkerställer att element lagras indirekt med ett anrop till malloc vid varje infogning;
- F14ValueMap - ger minimal minnesförbrukning för små nycklar. Element lagras i själva cellerna (inline). För medelstora och stora nycklar leder detta tillvägagångssätt till märkbara minneskostnader;
- F14VectorMap - fungerar snabbare för stora tabeller och komplexa nycklar, men långsammare för enkla nycklar och små tabeller. Elementen packas i en kontinuerligt fylld array och adresseras av en 32-bitars indexpekare;
- F14FastMap är en kombinerad strategi. Om nyckeln är mindre än 24 byte väljs F14ValueMap och om fler är F14VectorMap vald.
Källa: opennet.ru