整数から文字列への変換 (2014)

整数から文字列への変換
2014-06-23

整数をその文字列表現に変換するには、さまざまな方法があります。これらの変換がパフォーマンスのボトルネックになることは稀ですが、特定のアプリケーションのプロファイリング中にしばしば現れます。例えば、Lwanでレスポンスヘッダーを構築する際には非常に一般的です。

Lwanを例に取ると、当初は数値を変換するためにsnprintf()が使用されていました。これは機能しますが、パフォーマンスの観点からは非常に退屈です。

第二のアプローチは、単純なアルゴリズムを使用することでした。これは基本的に、数値を10で連続して割り、10で割った余りを文字列に逆順に書き込み、数値が0になったら文字列を反転させるというものです。

// 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;
}

これはしばらくは問題ありませんでしたが、その文字列反転のステップは常に私を悩ませていました。なぜ逆順に書き込まないのだろうか？

そこで、Lwanのコードを次のスニペットに変更しました。整数型がバイト単位で占めるサイズに3を掛けることで、ゼロ終端文字を含めてMAX_INTの桁数のおおよその値を、sizeof(int)の値に関わらず取得できるという、便利なトリックに注目してください。

#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;
}

配列への書き込み回数を減らしたことで、このアルゴリズムは大幅に高速化されました。しかし、最終的にはこのようなことをいじるときに常に避けるべきことをしてしまいました。配列ルックアップを足し算に変更したのです。それがよりパフォーマンスが良いか測定せずに、とにかくコードをコミットしてしまいました。ルックアップテーブルは約9%高速です。しまった！

昨年、Facebookエンジニアリングチームは、さらに高速な整数から文字列への変換関数を投稿しました。彼らも、変換が終わった後に文字列を反転させる必要をなくすという同じアイデアを使用しており、ルックアップテーブルも使用しています。

しかし、素晴らしいトリックは、10桁すべてに対応するルックアップテーブルを持つ代わりに、00から99までのすべての2桁のペアに対応するテーブルを持っていることです。これにより、除算の回数が半分になり、大幅に高速なアルゴリズムが得られます。上記のコードスニペットより約31%高速です。

size_t facebook_uint32_to_str(uint32_t value, char *dst)
{
    static const char digits[201] =
        "0001020304050607080910111213141516171819"
        "2021222324252627282930313233343536373839"
        "4041424344454647484950515253545556575859"
        "6061626364656667686970717273747576777879"
        "8081828384858687888990919293949596979899";
    size_t const length = digits10(value);
    size_t next = length - 1;
    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()関数も、数値の桁数を非常に効率的に計算する別の関数です。パフォーマンスが良いとはいえ、この呼び出しを完全に削除することも可能です。numeric_limits<uint32_t>::digits10のような定数を使用すれば、同じインターフェースを維持できます。これは、dstバッファが最大の32ビット符号なし整数のすべての桁を保持するのに十分な大きさであるべきだからです。

実装の詳細（関数は基本的に数値を10のべき乗と比較し、桁数が比較対象の最大べき乗を超えた場合に再帰する）により、定数長を使用した場合の速度向上は、小さな数値（1桁または2桁）ではそれほど大きくありません。しかし、このレベルまで最適化するのであれば、定数を使用しても問題ありません。私のマシン（Core i7 2640Mラップトップ、最新の64ビットArch Linux）では、常に高速です。

［画像: relativespeedup］

digits10()と定数値を使用したfacebook_uint32_to_str()の相対的な速度向上

このグラフは、整数から文字列への変換方法をすべてテストするベンチマークプログラムを使用して取得しました。他の方法と比較するために、完全なグラフを以下に示します。

［画像: benchmark］

snprintf()の結果は、結果を歪めないように省略されています。ネタバレ：遅いです。

残念ながら、ライセンスの問題で、このコードをLwanで使用できません。ブログ記事にはライセンスが記載されていません。Facebookとは無関係な場所で、この2桁ルックアップテーブルも見つけましたが、誰が最初にこのアイデアを思いついたのかは不明です。このような情報源としてよく参照するHacker's Delightでも見つかりませんでした。