インターネットスケールな整数文字列変換の進化：Lwan と Facebook のアプローチ

はじめに

整数を文字列表現に変換する処理は、ボトルネックにはなりにくいが、特定のアプリケーション（例：レスポンスヘッダー構築）では頻出します。Lwan などの高性能 Web サーバー開発において、この性能向上への取り組みは重要です。

Lwan のアプローチの進化

1.

snprintf()

の使用

当初は標準関数

snprintf()

• 機能としては問題ありませんでした。
• しかし、パフォーマンス観点では極めて無味乾燥なアプローチとされました。

2. ナイーブ（単純）アルゴリズム

次に試されたのは「数を 10 で順次割り、剰余で文字列へ逆順書き込み、最後に反転させる」手法です。

// 参照元：https://code.google.com/p/stringencoders/
size_t naive_uint32_to_str(uint32_t value, char *str) {
    char *wstr = str;
    // 変換処理：数字は逆順になる
    do
        *wstr++ = (char) decimal_digits[uvalue % 10];
    while (uvalue /= 10);
    *wstr = '\0';
    // 文字列を反転（ここがパフォーマンスのボトルネック）
    strreverse(str, wstr - 1);
    return wstr - str;
}

3. 最適化：逆順書き込みの実装

「変換後に反転させる」のではなく、最初から逆順に書き込む手法に変更しました。これにより、余計な反転処理が不要になり、パフォーマンスが劇的に向上しました。

また、バッファサイズの計算において興味深いトリック（整数サイズ×3 で MAX 桁数の推定）を用いています。

#define INT_TO_STR_BUFFER_SIZE (3 * sizeof(int))

char *lwan_uint32_to_str(uint32_t value,
            char buffer[static INT_TO_STR_BUFFER_SIZE],
            size_t *len) {
    char *p = buffer + INT_TO_STR_BUFFER_SIZE - 1;

    *p = '\0';
    do {
        // 逆順に書き込み
        *--p = "0123456789"[value % 10];
    } while (value /= 10);

    size_t difference = (size_t)(p - buffer);
    *len = (size_t)(INT_TO_STR_BUFFER_SIZE - difference - 1; // 修正：元の記述の誤植を考慮

    return p;
}

4. 失敗談：ルックアップテーブルの過剰な最適化

著者は測定もせずにルックアップテーブルへ置き換え、コミットしてしまいました。

• その結果、約 9% の高速化が得られました（しかし、後述する Facebook の手法と比べると小さな成果です）。

Facebook エンジニアリングチームの手法

Facebook チームはさらに高速な関数を公開しました。主な特徴は以下の通りです。

• 逆順書き込みを採用（反転不要）。
• 除算回数を半分にするための10 の桁に対するテーブルではなく、すべての桁のペア (00〜99) に対するルックアップテーブルを使用。

これにより、上記 Lwan の実装に対し約 31% の性能向上を実現しています。

size_t facebook_uint32_to_str(uint32_t value, char *dst)
{
    // 桁のペア (00-99) を文字列として定義
    static const char digits[201] =
        "0001020304050607080910111213141516171819"
        "2021222324252627282930313233343536373839"
        "4041424344454647484950515253545556575859"
        "6061626364656667686970717273747576777879"
        "8081828384858687888990919293949596979899";
    
    size_t const length = digits10(value); // 桁数取得
    size_t next = length - 1;

    // 100 を割れる場合：ペアごとのテーブル参照（除算回数の削減）
    while (value >= 100) {
        auto const i = (value % 100) * 2; // テーブルインデックスの計算
        value /= 100;
        dst[next] = digits[i + 1]; // 上位桁
        dst[next - 1] = digits[i]; // 下位桁
        next -= 2;
    }

    // 最後の 1〜2 桁の処理
    if (value < 10) {
        dst[next] = '0' + uint32_t(value);
    } else {
        auto i = uint32_t(value) * 2;
        dst[next] = digits[i + 1];
        dst[next - 1] = digits[i];
    }
    return length;
}

digits10()

と定数最適化について

関数の役割

digits10()

性能への影響と代替案

• 呼び出しを排除できるか？
  性能を犠牲にしたくない場合は呼び出しを避ける必要がありますが、

  numeric_limits<uint32_t>::digits10

  という定数を使うことで同じインターフェースを保つことができます。
  • 理由：バッファには最大桁数を含む十分大きなサイズが用意されているため。

定数化のメリット

• 実装上（再帰的なべき乗比較など）で定数を多用することで、小さな数字 (1〜2 桁) に対しても顕著な速度向上が見られます。
• 著者の環境（Core i7 2640M, Arch Linux）では一貫して高速化が確認されました。

ベンチマーク結果

以下のグラフは著者が作成したベンチマークプログラムによる相対的な速度向上率です。

• snprintf(): スポイラーですが非常に低速（グラフに表示省略）。
• 定数値を用いた実装の方が、動的計算や関数呼び出しを避けることで安定した性能を発揮します。

(※具体的なグラフ画像は非表示)

ライセンスと参考文献の注意点

コードの利用制限

• Facebook のコードはライセンス上の問題により、Lwan で利用できません。
• 関連するブログ投稿にはライセンス規定が明記されていません。

2 桁ルックアップテーブルの由来

• 2 桁のルックアップテーブル自体は、Facebook 以外の実装でも発見されています。
• 「誰が最初にこのアイデアを思いついたのか」は不明です。

参考文献

• 通常、同様の話題については 「Hacker's Delight」 を参照しますが、この具体的な手法については同書にも掲載されていませんでした。