Facebook obre la implementació de les taules hash F14

empresa de Facebook va anunciar sobre la implementació de codi obert de taules hash F14, optimitzat per a un consum eficient de memòria. F14 s'utilitza a la infraestructura de Facebook com a reemplaçament de la majoria de tipus de taules hash i pot reduir el consum de memòria sense sacrificar el rendiment. F14 supera notablement les taules hash de google::sparse_hash_map, que fins ara s'han considerat les més eficients pel que fa al consum de memòria. El codi del projecte està escrit en C++ i s'inclou a la biblioteca La bogeria.

F14 es refereix a algorismes amb un sistema de resolució de col·lisions basat en doble hashing amb 14 seqüències de mostres (una cadena de 14 ranures s'emmagatzema en una cel·la de la taula hash i l'interval entre cel·les es calcula mitjançant una funció hash auxiliar). Per accelerar les operacions de filtratge de cel·les, la implementació utilitza instruccions vectorials SSE2 per als sistemes x86_64 i NEON per a Aarch64, que permeten paral·lelitzar l'execució d'operacions per seleccionar ranures amb clauers i tamisar claus dins de la cadena. Es processen blocs de 14 ranures alhora, que és l'equilibri òptim entre l'eficiència d'utilitzar la memòria cau del processador i el nombre de col·lisions.

Una característica especial de F14 és la capacitat de seleccionar diferents estratègies d'emmagatzematge de dades:

• F14NodeMap: consumeix menys memòria per a claus grans i mitjanes. Assegura que els elements s'emmagatzemen indirectament amb una crida a malloc a cada inserció;
• F14ValueMap: proporciona un consum mínim de memòria per a tecles petites. Els elements s'emmagatzemen a les mateixes cel·les (en línia). Per a tecles mitjanes i grans, aquest enfocament comporta una sobrecàrrega de memòria notable;
• F14VectorMap: funciona més ràpid per a taules grans i tecles complexes, però més lent per a tecles simples i taules petites. Els elements s'empaqueten en una matriu contínuament poblada i s'adreça amb un punter d'índex de 32 bits;
• F14FastMap és una estratègia combinada. Si la clau té menys de 24 bytes, es selecciona F14ValueMap i, si és més, se selecciona F14VectorMap.

Font: opennet.ru