Facebook opent de implementatie van F14-hashtabellen

Facebook-bedrijf kondigde het over open source implementatie van hashtabellen F14, geoptimaliseerd voor efficiënt geheugengebruik. F14 wordt in de Facebook-infrastructuur gebruikt als vervanging voor de meeste soorten hashtabellen en kan het geheugengebruik verminderen zonder dat dit ten koste gaat van de prestaties. F14 presteert merkbaar beter dan de hashtabellen van google::sparse_hash_map, die tot nu toe als de meest efficiënte worden beschouwd in termen van geheugengebruik. De projectcode is geschreven in C++ en is opgenomen in de bibliotheek Dwaasheid.

F14 verwijst naar algoritmen met een botsingsresolutiesysteem gebaseerd op dubbele hashing met 14 reeksen monsters (een keten van 14 slots wordt opgeslagen in één hashtabelcel en het interval tussen de cellen wordt berekend met behulp van een hulphashfunctie). Om de celfilterbewerkingen te versnellen, maakt de implementatie gebruik van vectorinstructies SSE2 voor x86_64-systemen en NEON voor Aarch64, waarmee de uitvoering van bewerkingen voor het selecteren van slots met sleutelhangers en het uitzoeken van sleutels binnen de keten parallel kan worden uitgevoerd. Blokken van 14 slots worden tegelijk verwerkt, wat de optimale balans is tussen de efficiëntie van het gebruik van de processorcache en het aantal botsingen.

Een speciaal kenmerk van F14 is de mogelijkheid om verschillende strategieën voor gegevensopslag te selecteren:

• F14NodeMap - verbruikt het minste geheugen voor grote en middelgrote sleutels. Zorgt ervoor dat elementen indirect worden opgeslagen met een aanroep naar malloc bij elke invoeging;
• F14ValueMap - biedt minimaal geheugengebruik voor kleine sleutels. Elementen worden in de cellen zelf opgeslagen (inline). Voor middelgrote en grote sleutels leidt deze aanpak tot merkbare geheugenoverhead;
• F14VectorMap - werkt sneller voor grote tabellen en complexe sleutels, maar langzamer voor eenvoudige sleutels en kleine tabellen. De elementen zijn verpakt in een continu bevolkte array en worden geadresseerd door een 32-bits indexaanwijzer;
• F14FastMap is een gecombineerde strategie. Als de sleutel kleiner is dan 24 bytes, wordt F14ValueMap geselecteerd, en als er meer zijn, wordt F14VectorMap geselecteerd.

Bron: opennet.ru