Converting an Integer to a Decimal String in Under Two Nanoseconds
lundi, 16 févr. 2026·
,
Jaël Champagne Gareau
Daniel Lemire
Résumé
Converting binary integers to variable-length decimal strings is a fundamental
operation in computing. Conventional fast approaches rely on recursive division
and small lookup tables. We propose a SIMD-based algorithm that leverages
AVX-512 IFMA instructions available on recent AMD and Intel processors. Our
method eliminates lookup tables entirely and computes multiple quotients and
remainders in parallel.
Additionally, we introduce a dual-variant design with dynamic
selection that adapts to input characteristics: a branch-heavy variant optimized
for homogeneous digit-length distributions and a branch-light variant for
heterogeneous datasets. Our single-core algorithm consistently outperforms all
ten competing methods across the full range of integer sizes, running
1.4–2$\times$ faster than the closest competitor and 2–4$\times$ faster than
the C++ standard library function
std::to_chars across tested workloads.Type
Publication
Software: Practice and Experience
This paper has been submitted for peer review. Data are shared here for reviewer access.
Auteurs
Chercheur postdoctoral en informatique
Je suis actuellement chercheur postdoctoral en informatique à l’Université
TÉLUQ, où mes travaux portent sur l’accélération de la conversion de nombres
entiers et flottants en chaînes de caractères décimales. Au cours de mon
doctorat, j’ai conçu des algorithmes et des structures de données exploitant
l’architecture moderne des ordinateurs afin de résoudre de grandes instances
de processus décisionnels de Markov (MDP). Durant ma maîtrise, j’ai développé
des algorithmes de planification d’itinéraires pour véhicules électriques,
visant à déterminer le chemin optimal entre deux points tout en minimisant
le temps total du trajet (déplacement, recharge et attente aux bornes).
Auteurs