Facebook ouvre F14, son implémentation de tables de hachage en C++

Par:
fredericmazue

mer, 15/05/2019 - 10:00

Les tables de hachage constituent un moyen de gérer un ensemble de clés ou de mapper des clés sur des valeurs. Elles sont un outil très répandu en informatique.

Pour ses besoins, Facebook a développé F14, une table de hachage de vérification à 14 voies au sein de Folly , sa bibliothèque open source de composants C++.  Pour mémoire Folly, signifie Facebook Open Source Library en consiste en une bibliothèque de compsants écrits en C++14.

F14 est une table de hachage à 14 voies qui résout les collisions par double hachage. Jusqu'à 14 clés sont stockées dans un bloc à une seule position de table de hachage. F14 a été conçue avec le souci de la performance. Ainsi les instructions vectorielles (SSE2 sur x86_64, NEON sur aarch64) permettent de filtrer au sein d'un bloc; la recherche intra-segment ne prend que quelques instructions. F14 indique que l'algorithme F filtre jusqu'à 14 clés à la fois. Cette stratégie permet d’utiliser la table de hachage avec un facteur de charge maximal élevé tout en maintenant les chaînes de sondes très courtes, indique Facebook.

L'implémentation de F14 est décrite dans cette page technique. F14 est également présentée sur GitHub, au sein du projet Folly qui est sous licence Apache 2.0