Bonjour Nal,
On avait passé un bon moment de convivialité autour d'une table de hachage il y a quelques mois, alors je me suis dit qu'on pourrait remettre ça.
1) Les petits plats dans les grands
Depuis la dernière fois, je me suis penché sur la fonction de tri de ma table. Elle fonctionnait bien, mais il fallait penser à l'appeler chaque fois que l'on voulait mettre de l'ordre, ce qui est agaçant quand on y pense. J'ai donc ajouté une fonctionnalité de tri paresseux (optionnel) : après avoir tout bien rangé une première fois, on garde d'une part la fonction de comparaison en mémoire, et d'autre part on surveille si l'ordre est perturbé par de nouvelles écritures. Lorsque des changements ont eu lieu, le contenu de la table sera automatiquement trié « juste à temps » pour la parcourir, que ce soit avec un itérateur ou la fonction map_foreach.
2) Cuisine fusion
J'utilisais un algorithme de tri par fusion adapté aux listes chaînées, mais je l'ai modifié pour être plus efficace sur une liste déjà partiellement ordonnée : j'utilise désormais une variante dite « naturelle » qui regroupe les suites de données déjà triées. Ça rend cette fonctionnalité de tri incrémental délicieusement légère.
3) Incrémental ? Ça me fait penser à la Suisse
Et tu as bien raison. Nous avions justement évoqué la dernière fois Abseil avec sa belle table suisse, et j'affirmais que notre table, bien que rustique, était ma foi tout aussi bonne. Tu n'as désormais plus besoin de me croire sur parole, car j'ai réalisé un banc de test pour appuyer mes dires. Le voici : https://github.com/RaphaelPrevost/hashmap-benchmark (en angliche dans le texte).
J'ai aussi renforcé la robustesse de ma table lorsqu'elle commence à devenir trop chargée grâce à d'amusants pointeurs étiquetés. Lors de l'insertion d'une nouvelle clef, je modifie dans l'index l'adresse de son emplacement en y inscrivant, dans la poignée de bits restés vierges (…), une partie de l'empreinte (hash) de la clef (la taille a ici son importance, cela fonctionne évidemment mieux avec des pointeurs de 64 bits). Cela permet ensuite, lorsque l'on cherche une clef parmi dix millions, de vérifier si l'empreinte partielle extraite d'un pointeur vers un emplacement potentiel correspond à celle de notre clef - et dans le cas contraire, d'éviter ainsi un accès mémoire non servi par le cache. Une table bien servie, c'est agréable.
4) Où il y a de la gêne, il n'y a pas de plaisir
C'est meilleur avec les mains : https://godbolt.org/z/h4ffsWdq8
Envoyer un commentaire
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.