Hachage adaptatif dans SBCL : rendre les tables de hachage plus rapides et plus robustes

Une présentation à l'ELS 2024 a porté sur le hachage adaptatif, visant à rendre les tables de hachage à usage général plus rapides et plus robustes. La théorie traditionnelle des tables de hachage se préoccupe principalement des coûts asymptotiques du pire des cas, négligeant l'impact des facteurs constants sur les performances réelles. Cette recherche introduit une approche adaptative en ligne, ajustant la fonction de hachage en fonction de la distribution réelle des clés pour réduire les collisions et améliorer l'utilisation du cache. Des expériences montrent des améliorations significatives en réduisant les comparaisons attendues et en accélérant les opérations PUT, en particulier avec des distributions de clés spécifiques. Les tables de hachage intégrées de SBCL utilisent désormais cette technique, commutant dynamiquement les fonctions de hachage (y compris la recherche linéaire, le hachage par décalage de bits et MurmurHash) en fonction des nombres de collisions et de la taille de la table de hachage. Pour les clés composées telles que les chaînes et les listes, une stratégie de troncature est utilisée, ajustant dynamiquement la longueur de troncature lorsque trop de collisions se produisent. Cette amélioration améliore la vitesse des tables de hachage SBCL dans les cas courants et la robustesse dans d'autres.