Diviser plus vite : un nouvel algorithme pour la division entière signée 64-bit
Sommaire
En bref
- Un développeur propose un algorithme inédit pour la division entière signée 64-bit par constante compile-time, plus rapide que les approches existantes (Granlund-Montgomery, Robison).
- Sur ARM, le gain atteint 10–20% en débit pour la plupart des diviseurs 64-bit, avec une latence égale ou meilleure.
- Sur x86, le bénéfice varie selon le diviseur : +5–10% en débit pour ~80% des diviseurs positifs, mais plus lent sur les autres cas.
- L'article documente aussi un bug de 4 ans dans une bibliothèque logicielle majeure, et déplore l'absence de division étage native dans C/C++/Go/Swift.
Ce que dit la source
La division entière signée par arrondi vers −∞ (floor division) est ignorée par les compilateurs mainstream et les langages courants, qui implémentent plutôt la division tronquée (vers 0). L'auteur affirme que la floor division « donne plus souvent le résultat qu'on veut » (citation de Hacker's Delight), mais reste mal optimisée : les ressources en ligne et les modèles d'IA ne surfacent que les algorithmes lents, et au moins une bibliothèque de premier plan a connu une implémentation buggée pendant plus de 4 ans. L'article présente un algorithme nouveau combinant des techniques existantes d'une façon jusque-là non documentée.
- L'algorithme utilise une variante sign-selected multiplier qui ajuste une constante multiplicatrice pré-calculée selon le signe du dividende, puis effectue un décalage de bits.
- Les benchmarks couvrent plus de 40 diviseurs sur ARM (M4 Pro, Snapdragon X1) et x86 (Ryzen 9, Intel Core i7).
- L'approche Granlund-Montgomery (1994) reste compétitive sur x86 pour les négatifs, et Robison (2005) brille surtout quand le diviseur n'est pas compile-time constant ou quand on vectorise (même code pour tous les diviseurs).
- Un commentateur note que depuis Ryzen 7000, le hardware seul suffit pour diviser vite, rendant ces algorithmes logiciels moins critiques pour le SIMD.
- L'article détecte aussi un bug ancré dans une grande bibliothèque logicielle, sans la nommer explicitement dans la source fournie.
Dans les commentaires
Débat technique et courtois, sans conflit majeur. Quelques acteurs reconnaissent l'intérêt de la contribution (meilleure structuration du sujet), tandis que d'autres rappellent les cas où Robison reste pertinent ou signalent que le hardware récent marginalise déjà ces optimisations logicielles.
- Plusieurs commentateurs soulignent les cas d'usage où l'algorithme proposé ne gagne pas : Robison brille quand le diviseur n'est pas compile-time constant, ou quand plusieurs diviseurs sont vectorisés avec le même code.
- Un commentaire rappelle que le hardware moderne (Ryzen 7000 et plus récent) rend l'optimisation logicielle moins pertinente pour le SIMD, diminuant l'urgence de choisir entre ces algorithmes.
- Un développeur signal que ces techniques sont utiles dans les boucles imbriquées où divisor est pré-calculé, suggérant que le sujet n'est pas nouveau en pratique, même s'il manque de documentation formelle.
- Peu de débat substantiel sur la correction ou les erreurs de micro-benchmark ; le fil reste exploratoire plutôt que contradictoire.
Notre lecture
Contribution solide de clarification et de micro-optimisation : l'auteur resserre la documentation autour d'une technique simple et montre des gains réels sur des architectures concrètes. Intéressant pour les équipes gérant du code numérique bas-niveau (systèmes, image processing, quantization) où chaque % compte. Cependant, l'impact est niche : C/C++ n'expose pas ces optimisations nativement (l'utilisateur doit les implémenter manuellement), et le hardware récent (Ryzen 7000+) amenuise le gain relatif. À tester si vous divisez souvent par la même constante dans une boucle critique ; à ignorer si vous comptez sur le compilateur pour le faire seul. Aucun action DSI immédiate.