Facebook maatskappy oor oopbron-implementering van hash-tabelle , geoptimaliseer vir doeltreffende geheueverbruik. F14 word in die Facebook-infrastruktuur gebruik as 'n plaasvervanger vir die meeste soorte hash-tabelle en kan geheueverbruik verminder sonder om prestasie in te boet. F14 vaar merkbaar beter as google::sparse_hash_map hash-tabelle, wat tot dusver as die doeltreffendste beskou is in terme van geheueverbruik. Die projekkode is in C++ geskryf en is by die biblioteek ingesluit .
F14 verwys na algoritmes met 'n botsingsresolusiestelsel gebaseer op dubbele hashing met 14 ('n ketting van 14 gleuwe word in een hash-tabelsel gestoor, en die interval tussen selle word met behulp van 'n hulphash-funksie bereken). Om selfiltreringsoperasies te bespoedig, gebruik die implementering vektorinstruksies SSE2 vir x86_64-stelsels en NEON vir Aarch64, wat die uitvoering van bewerkings paralleliseer vir die kies van gleuwe met sleutelkettings en die uitsif van sleutels binne die ketting. Blokke van 14 gleuwe word op 'n slag verwerk, wat die optimale balans is tussen die doeltreffendheid van die gebruik van die verwerkerkas en die aantal botsings.
'n Spesiale kenmerk van F14 is die vermoë om verskillende databergingstrategieë te kies:
- F14NodeMap - verbruik die minste geheue vir groot en medium-grootte sleutels. Verseker dat elemente indirek gestoor word met 'n oproep na malloc op elke invoeging;
- F14ValueMap - verskaf minimale geheueverbruik vir klein sleutels. Elemente word in die selle self gestoor (inlyn). Vir medium en groot sleutels lei hierdie benadering tot merkbare geheue oorhoofse koste;
- F14VectorMap - werk vinniger vir groot tafels en komplekse sleutels, maar stadiger vir eenvoudige sleutels en klein tafels. Die elemente word verpak in 'n voortdurend bevolkte skikking en aangespreek deur 'n 32-bis indekswyser;
- F14FastMap is 'n gekombineerde strategie. As die sleutel minder as 24 grepe is, word F14ValueMap gekies, en indien meer, word F14VectorMap gekies.
Bron: opennet.ru