Facebook ouvre la mise en œuvre des tables de hachage F14

Entreprise Facebook annoncé le à propos de l'implémentation open source des tables de hachage F14, optimisé pour une consommation efficace de la mémoire. F14 est utilisé dans l'infrastructure Facebook en remplacement de la plupart des types de tables de hachage et peut réduire la consommation de mémoire sans sacrifier les performances. F14 surpasse sensiblement les tables de hachage google::sparse_hash_map, qui étaient jusqu'à présent considérées comme les plus efficaces en termes de consommation de mémoire. Le code du projet est écrit en C++ et est inclus dans la bibliothèque Folie.

F14 fait référence aux algorithmes dotés d'un système de résolution de collision basé sur un double hachage avec 14 séquences d'échantillons (une chaîne de 14 emplacements est stockée dans une cellule de la table de hachage et l'intervalle entre les cellules est calculé à l'aide d'une fonction de hachage auxiliaire). Pour accélérer les opérations de filtrage des cellules, l'implémentation utilise les instructions vectorielles SSE2 pour les systèmes x86_64 et NEON pour Aarch64, qui permettent de paralléliser l'exécution des opérations de sélection d'emplacements avec des chaînes de clés et de filtrage des clés au sein de la chaîne. Des blocs de 14 emplacements sont traités à la fois, ce qui constitue l'équilibre optimal entre l'efficacité d'utilisation du cache du processeur et le nombre de collisions.

Une particularité de F14 est la possibilité de sélectionner différentes stratégies de stockage de données :

• F14NodeMap - consomme le moins de mémoire pour les clés de grande et moyenne taille. Garantit que les éléments sont stockés indirectement avec un appel à malloc à chaque insertion ;
• F14ValueMap - fournit une consommation de mémoire minimale pour les petites clés. Les éléments sont stockés dans les cellules elles-mêmes (en ligne). Pour les clés moyennes et grandes, cette approche entraîne une surcharge de mémoire notable ;
• F14VectorMap - fonctionne plus rapidement pour les grandes tables et les clés complexes, mais plus lentement pour les clés simples et les petites tables. Les éléments sont regroupés dans un tableau rempli en continu et adressés par un pointeur d'index de 32 bits ;
• F14FastMap est une stratégie combinée. Si la clé fait moins de 24 octets, alors F14ValueMap est sélectionné, et si plus, F14VectorMap est sélectionné.

Source: opennet.ru