64ビット整数を10進文字列表現に変換することは、ログ記録、JSONシリアライズ、CSV出力、デバッグプリントなど至る所に登場するありふれたタスクです。C++ではstd::to_chars、sprintf、または何らかのライブラリルーチンを使用できます。

これらの関数はどのように動作するのでしょうか？高レベルでは、繰り返し10で割ります。整数kから始めます。それを10で割り、余りを最後の桁として使用します（0以上9以下）。次に文字0のコードポイント値を加えてASCII桁を取得します。高速化するには、100で割り、0以上99以下の値を文字列にマッピングするルックアップテーブルを使用できます。

これで十分です。しかし、これらの最適化を行っても、この文字列生成がパフォーマンスのボトルネックになることがあります。より良い方法はあるでしょうか？

最近のAMDプロセッサまたはIntelサーバーを使用していると仮定しましょう。その場合、強力なデータ並列命令（AVX-512）があり、一度に8つの64ビット整数を乗算できます。これらの命令はしばしばSIMD（単一命令複数データ）と呼ばれます。同僚のJaël Champagne Gareauと私は、この問題に関する新しい論文を最近発表しました。タイトルがすべてを物語っています：2ナノ秒未満での整数から10進文字列への変換。

n / 100をコードで記述すると、最適化コンパイラは乗算とシフトの操作に変換します。これはしばしば乗法逆元として説明されます。一般に、nをdで割る操作を、c * nまたはc * n + cをmで割る操作に置き換えることができます。ここで、cとmは適切な整数で、c/m ~= 1/dとなるように選ばれます。c * n + cは融合乗算加算と呼ばれることがよくあります。mを2の累乗に選ぶと、mによる除算は単なるシフトになります。次に、mによる除算の余りを使って、dを掛けて再度mで割ることで除算の余りを得ることができます。これは本質的に乗算とシフトの操作です（Lemire et al., 2021）。

最近のIntelおよびAMDプロセッサで利用可能なInteger Fused Multiply-Add (IFMA)命令を活用できます。これらの命令は本質的に、8つの(c * n + c)/mのインスタンスを1つの命令で計算することを可能にします。式(c * n + c)/mは除算を与えますが、余りが必要なので、代わりに(c * n + c)%mを選び、それを除数で乗算する必要があります。

AVX-512命令の面白い点は、8つの操作それぞれに異なるcと異なる除数を使用できることです。Intel intrinsic関数を使用して、10^8より小さい値を8桁に変換するコアルーチンは次のようになります：

__m512i to_string_avx512ifma_8digits(uint64_t n) {
  __m512i bcstq_l   = _mm512_set1_epi64(n);
  constexpr uint64_t twoto52 = 0x10000000000000ULL; // 2^52
  __m512i ifma_const = _mm512_setr_epi64(
    twoto52 / 100000000, twoto52 / 10000000,
    twoto52 / 1000000, twoto52 / 100000,
    twoto52 / 10000, twoto52 / 1000, 
    twoto52 / 100, twoto52 / 10
  );
  __m512i zmmTen    = _mm512_set1_epi64(10);
  __m512i asciiZero = _mm512_set1_epi64('0');
  __m512i lowbits_l  = _mm512_madd52lo_epu64(ifma_const, 
    bcstq_l, ifma_const); // ifma_const * bcstq_l + ifma_const
  __m512i highbits_l = _mm512_madd52hi_epu64(asciiZero, 
    zmmTen, lowbits_l);
  return highbits_l;
}

これは2つの乗算加算命令vpmadd52huqにコンパイルされます。それだけです。8桁を生成するのに2命令です。

nを__m512iベクトルの8つの64ビットレーンすべてにブロードキャスト（bcstq_l）することで動作します。次に、10^8、10^7、…の逆数を表す慎重に選ばれた乗法逆元のベクトル（ifma_const）を準備します。魔法は単一の_mm512_madd52lo_epu64命令で起こり、8つの融合乗算加算を同時に実行します。各レーンは52ビット低半乗算を使用して(ifma_const[i] * n + ifma_const[i])を計算し、対応する10の累乗で割ったときの商を効果的に抽出します。2番目の_mm512_madd52hi_epu64命令（10のベクトルと'0'のベクトルを使用）は、桁の値を分離し、ASCII '0'オフセットを上位52ビットに加算し、単一の512ビットレジスタに8つのパックされた桁文字を生成します。

すべての整数が8桁を必要とする場合、これで完了です。しかし、一般的なケースでは、これを有効に活用するには少し努力が必要です。

幸いなことに、たとえば6桁しか必要ない場合でも、完全な8桁の計算を実行し、6桁のみを保存したい場合はマスク付きストアを使用できます。つまり、AVX-512のような命令セットでは、メモリにデータの一部のみを書き込むことができ、これは非常に便利です。

2つのバリアントがあります。1つは分岐が多いもので、同種のデータ（類似の桁長の数値）で良好に動作します。もう1つは分岐が少ないもので、混合ワークロードに適しています。クイックプロファイリングステップで、データセットに適したものを選択できます。

私たちの実装は、幅広い入力に対して最良の競合他社より一貫して1.4–2倍高速で、std::to_charsより2–4倍高速です。std::to_charsの実装が全く素朴ではない場合でも、多くの方法で大幅に改善できる点が興味深いです。James Anhaltのアプローチ（jeaiii）も現代のハードウェアで非常に高速です。

参考文献
– 論文: doi:10.1002/spe.70079
– ベンチマークはGitHubにあります（完全に再現可能）
– 論文公開後まもなく、Barend Erasmusが私たちの提案したアプローチを実装したソフトウェアライブラリを作成しました。Barendが同種および異種の両方のアプローチを含んでいるかどうかは確かではありません。