Hotrace

Le programme lit l’entrée standard en deux temps. Avant une ligne vide, les lignes vont par paires : une clé, puis sa valeur. Après la ligne vide, chaque ligne est une clé à chercher : on affiche sa valeur, ou un message si elle n’existe pas. Le classement se fait au temps d’exécution, sur des fichiers énormes.

Toutes les cases vivent dans un seul tableau contigu (adressage ouvert). Une clé est hachée avec FNV-1a, et sa position de départ est hash & mask : la capacité étant toujours une puissance de deux, le modulo devient un simple ET binaire. Si la case est prise, on avance d’une case (sondage linéaire), ce qui reste dans le même cache.

Chaque case garde aussi le hash de sa clé : on ne compare les chaînes que si les hash sont égaux. Quand la table dépasse 75 % de remplissage, elle double de taille. Le seuil est calculé en entiers pour éviter les flottants.

strcmp est réécrit en SSE2 : pcmpeqb compare 16 octets d’un coup, puis pmovmskb résume le résultat en un masque de 16 bits. Une garde évite de lire 16 octets à cheval sur la fin d’une page mémoire, ce qui pourrait planter.

strlen utilise l’astuce SWAR (8 octets par registre) pour repérer l’octet nul, et bsf / bsr servent à trouver le premier bit à 1, par exemple pour calculer la puissance de deux suivante.