Optimisation : fin du « problème du 33e bit », déjà dans LLVM, mises à jour GCC et MSVC en approche

Une optimisation supprime le « problème du 33e bit » : déjà déployée dans LLVM, mises à jour GCC et MSVC en approche

Des ingénieurs de la société japonaise Cybozu Labs, spécialisée dans le développement logiciel et l’optimisation des calculs, ont proposé une nouvelle technique de division par constante pour les processeurs 64 bits. L’idée consiste à tirer parti de la largeur supplémentaire des registres actuels afin de lever les contraintes héritées d’algorithmes 32 bits plus anciens. Le correctif est déjà intégré à LLVM (Low Level Virtual Machine), le projet open source qui inclut le compilateur Clang (version 23.0.0). Des évolutions équivalentes pour GCC (GNU Compiler Collection) et MSVC (Microsoft Visual C++) sont, elles, en phase de test.

Contexte : pourquoi les compilateurs 64 bits traînaient encore des méthodes 32 bits

Jusqu’à aujourd’hui, des compilateurs modernes comme GCC, Clang et MSVC continuaient d’employer des algorithmes vieux d’environ 30 ans, initialement conçus et optimisés pour des processeurs 32 bits, y compris lorsque le code s’exécute sur des machines 64 bits nettement plus puissantes.

Depuis 1994, la référence pour la division par une constante dans les compilateurs est la méthode de Granlund et Montgomery (méthode GM). Son principe est de remplacer une division par une multiplication par une « constante magique », suivie de décalages binaires. Le procédé fonctionne bien, mais il se heurte à une limite spécifique avec les « diviseurs sur 33 bits », ce qui entraîne des opérations supplémentaires et dégrade les performances sur les architectures 64 bits actuelles.

En pratique, dans environ 3 % des cas de division d’entiers 32 bits par une constante (par exemple une division par 7, 19 ou 107), l’optimisation exige des calculs intermédiaires à l’aide de « nombres magiques » sur 33 bits. Cette étape allonge le chemin critique et réduit le parallélisme possible.

Division par constante 64 bits : la transformation de Mitsunari Shigeo et Hoshino Takashi

L’innovation proposée par Mitsunari Shigeo et Hoshino Takashi consiste à abandonner l’imitation d’une arithmétique 33 bits, pour reformuler directement le calcul en s’appuyant sur une grille 64 bits. Au lieu d’enchaîner une séquence de corrections relativement lourde, ils utilisent une modélisation mathématique plus directe : (x⋅(2^64−a ⋅c))//2⁶⁴, où x est le dividende étendu en 64 bits et c la constante magique.

Côté implémentation, sur x86-64, l’approche exploite l’instruction MULX (Unsigned Multiply Without Affecting Flags), qui évite de modifier les drapeaux du processeur. Sur ARM/Apple Silicon, elle s’appuie sur UMULH (Unsigned Multiply High), qui récupère les 64 bits de poids fort du produit. Grâce à ces instructions, la division peut être réalisée en une seule opération, ce qui accélère nettement le traitement.

Moins d’instructions, meilleures latences : résultats sur Intel Xeon et Apple M4

Pour situer le gain, l’ancienne méthode GM peut nécessiter jusqu’à 9 instructions à l’intérieur d’une boucle, avec notamment des additions et des décalages, ce qui crée une chaîne d’exécution longue. La nouvelle technique réduit cette chaîne à 3 opérations, en limitant à la fois la latence et les dépendances de données - un point particulièrement important sur les processeurs contemporains.

Des tests de performance menés sur un Intel Xeon w9-3495X et un Apple M4 montrent des accélérations pouvant atteindre 1.67x et 1.98x respectivement. Sur l’Apple M4, l’amélioration ressort davantage, en raison du débit élevé des unités de multiplication. Sur le Xeon, la méthode apporte aussi une meilleure prévisibilité des temps d’exécution, un critère clé côté charges serveur : par exemple, l’écart-type du temps d’exécution est passé de 0.013 à 0.009 seconde.

L’intégration de cette nouvelle division par constante dans LLVM et GCC doit accélérer des logiciels manipulant de gros volumes de données, notamment des bases de données, des systèmes cryptographiques et des outils d’analyse du trafic réseau.

Il ne s’agit pas uniquement d’un résultat académique : l’optimisation est déjà en cours d’adoption industrielle. À ce stade, le patch est entièrement intégré dans LLVM, tandis que les mises à jour pour GCC et MSVC sont en phase finale de validation. Concrètement, cela signifie que, dans un avenir proche, la majorité des programmes recompilés avec ces nouveaux compilateurs pourront bénéficier d’un gain sensible sans modification du code source. Par la même occasion, un anachronisme historique disparaît des compilateurs, qui exploitent enfin la puissance des processeurs 64 bits pour une opération arithmétique de base, avec un gain proche du double dans certains scénarios.