Converting an integer to a decimal string in under two nanoseconds [r-libre/4056]

Champagne Gareau, Jaël et Lemire, Daniel (sous presse). Converting an integer to a decimal string in under two nanoseconds. Software: Practice and Experience.

Fichier(s) associé(s) à ce document :

PDF - numbertostring-7.pdf
Contenu du fichier : Document de travail
Licence : Creative Commons CC BY.

Télécharger

Catégorie de document :	Articles de revues
Évaluation par un comité de lecture :	Oui
Étape de publication :	Accepté (sous presse)
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 integer multiply-add 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 competing methods across the full range of integer sizes, running 1.4-2x faster than the closest competitor and 2-4x faster than the C++ standard library function std::to_chars across tested workloads.
Déposant:	Lemire, Daniel
Responsable :	Daniel Lemire
Dépôt :	29 avr. 2026 15:57
Dernière modification :	29 avr. 2026 15:57

Actions (connexion requise)

RÉVISER