開発日記

JITコンパイラの開発日記だった

qrintfの最適化

H2Oの内部では,数値,文字列のフォーマッタとしてsprintfが用いられています.

我々は,最近までsprintf専用ソースコード変換器, qrintfのチューニングを行っていました. 本稿ではqrintfの概要と今回適応した工夫,そして今後の課題についてまとめておきます.

1. qrintfとは?

qrintfとはCコンパイラの1つであるgccプリプロセッサのラッパーであり,snprintfを高速化するソースコード変換器です. 本稿執筆時点でのqrintfの変換対象はsprintfとsnprintfです.以下本文中では特にことわりのない限りsprintfと記述した場合sprintf, snprintfの両方を指します.

qrintfはソースコードに出現するsprintfで利用するフォーマット文字列を解析し,型ごとに用意された関数呼出にコードを書き換えsprintfの高速化を行います. 例えば以下のようなコードにqrintfを適応すると

sprintf(buf, "%d == 0x%x", 100, 0x64);

以下のコードに変換されます.

_qrintf_nck_finalize(
    _qrintf_nck_x(
        _qrintf_nck_s_len(
            _qrintf_nck_d(
                _qrintf_nck_init(buf),
                100
            ),
            " == 0x",
            sizeof(" == 0x") - 1
        ),
    0x64,
    "0123456789abcdef")
);

qrintfを用いるとなぜ速くなるのでしょうか?これはsprintfが実行時に行っていたフォーマット文字列の解析をコンパイル時に行うことで文字列解析コストが削減されたためと考えられます.

また,READMEによるとqrintfを用いるとで今までsprintfで行われていた処理は10倍以上の高速化すると記述されています.

$ gcc -O2 examples/ipv4addr.c
$ time ./a.out 1234567890
result: 73.150.2.210

real    0m2.602s
user    0m2.598s
sys     0m0.003s
$ qrintf-gcc -O2 examples/ipv4addr.c
$ time ./a.out 1234567890
result: 73.150.2.210

real    0m0.196s
user    0m0.192s
sys     0m0.003s

なおsprintfを含めたprintf系関数(printf, fprintf, sprintfなど)用の最適化はすでにコンパイラに最適化は導入されています.すでにclang(おそらくGCCにも)には導入されており,例えばLLVMではinstcombineの最適化パスによりprintf("x")putchar('x')に変換されます.ただ,(LLVMの場合)非常にナイーブな最適化のみが用意されており,sprintfをシリアライザ用途で用いる場合には十分ではありません.

2. 高速化の余地

qrintfを使うことでユースケースによっては10倍以上の高速化が達成可能となりました.ただ,このままだとこの記事は情報量がゼロとなってしまうのでさらなる高速化が可能かqrintfでサポートしているフォーマッタの1つである%ldを例に検討をしていきたいと思います. 以下のコードはqrintfのランタイムで%ldを処理するコードです.

  98 static inline qrintf_chk_t _qrintf_chk_s_len(qrintf_chk_t ctx, const char *s, size_t l)
  99 {
 100     size_t off = ctx.off;
 101     ctx.off += l;
 102     if (off + l <= ctx.size) {
 103     } else if (off < ctx.size) {
 104         l = ctx.size - off;
 105     } else {
 106         goto Exit;
 107     }
 108     for (; l != 0; --l)
 109         ctx.str[off++] = *s++;
 110 Exit:
 111     return ctx;
 112 }

 276 static inline char *_qrintf_ld_core(char *p, long v)
 277 {
 278     if (v < 0) {
 279         if (v == LONG_MIN) {
 280             *--p = '1' + LONG_MAX % 10;
 281             v = LONG_MAX / 10;
 282         } else {
 283             v = -v;
 284         }
 285     }
 286     do {
 287         *--p = '0' + v % 10;
 288     } while ((v /= 10) != 0);
 289     return p;
 290 }

 769 static inline qrintf_chk_t _qrintf_chk_ld(qrintf_chk_t ctx, long v)
 770 {
 771     char buf[sizeof(long) * 3], *p;
 772     if (v < 0) {
 773         do { int ch = '-'; if (ctx.off < ctx.size) ctx.str[ctx.off] = ch; ++ctx.off; } while (0);
 774     }
 775     p = _qrintf_ld_core(buf + sizeof(buf), v);
 776     return _qrintf_chk_s_len(ctx, p, buf + sizeof(buf) - p);
 777 }

まずqrintfはCコードのコンパイル時にsnprintf(buf, bufsiz, "%ld", v)_qrintf_chk_ld({.buf=buf, .off=0, .size=bufsiz}, v)と変換します.

_qrintf_chk_ldではまず一時バッファを用意し(771行目),バッファに1桁目から順に数値を文字列化していきます(_qrintf_ld_core関数). 最後にバッファに保持されている文字列を書き込み先にコピーし処理を終えます.(_qrintf_chk_s_len関数)

さて,プロファイルをとって見ると以下2点が実行時間の多くを占めていることがわかります.

  1. 一時バッファ,書き込みバッファへのコピー
  2. 数値の文字列化ループ

それぞれについて高速化が可能か検討していきたいと思います.

2.1 一時バッファへの書き込みの除去

数値から文字列への変換の際,qrintfでは変換結果を書き込みバッファに直接書き込まずCスタックに確保した一時バッファに一旦書き込む方法をとっています.

なぜ直接書き込みバッファへの書き込みを行わずに一旦一時バッファに書き込むのでしょうか? 理由は2つあり,1つはこれから書き込みを行う数値が実際にどの程度の長さの文字列になるかは不明でありバッファ溢れが発生する可能性があるためです. もう1つは上位桁から文字列化することができないためです.

高速に数値の桁数を計算できれば一時バッファから書き込みバッファへのコピーは除去可能と考えられます.

2.2 数値の文字列化ループ

CPU上で行う数値計算において割り算(div)はコストの高い計算の1つです.div, modを行いながら数値を文字列に変換するこのループは非常に実行コストの高い計算だと考えられます.

3. 整数値文字列変換の最適化

本節では上記で述べた2つの高速化の余地がある点について2つのコードの最適化を行います. 1つ目は桁数を特定するために対数を利用する方法,もう1つはlookupテーブルを使ったdiv/mod計算の除去,ループ展開です.

3.1 自然数の桁数

int, longなどC99の範囲でサポートされている整数型で表現可能な(0を含まない)自然数の桁数は,その自然数の常用対数と等しいです. libmで用意されているlog10(double)を利用して常用対数を求めることも可能ですが,浮動小数点数への変換など,実行コストが高いため自然数専用のlog10関数を用意し桁数を求めることとしました.

hacker's delightやBit Twiddling Hacks に掲載されているコードを用いてlog10の計算を行っています.

 208 /* from http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog10 */
 209 static inline unsigned _qrintf_ilog10u32(unsigned long v)
 210 {
 211 #define LOG2(N) ((unsigned)((sizeof(long) * 8) - __builtin_clzl((N)-1)))
 212     static const unsigned long ilog10table[] = {
 213         1UL,
 214         10UL,
 215         100UL,
 216         1000UL,
 217         10000UL,
 218         100000UL,
 219         1000000UL,
 220         10000000UL,
 221         100000000UL,
 222         1000000000UL,
 223         ULONG_MAX,
 224     };
 225     if (v != 0) {
 226         unsigned t;
 227         assert(sizeof(long) == sizeof(int));
 228         t = ((LOG2(v) + 1) * 1233) / 4096;
 229         return t + (v >= ilog10table[t]);
 230     }
 231     else {
 232         return 1;
 233     }
 234 #undef LOG2
 235 }

3.2 lookup-tableの利用

事前にlookupテーブルを用意しておく方法は古くから利用されてきた高速化手法の1つです. 今回は以下で紹介されている手法を利用し,数値を100で割った時の余り(0~99)を事前に文字列テーブルとして用意しておき,div/modの実行回数,そしてループ展開を行っています.

 191 static inline const char *_qrintf_get_digit_table(void)
 192 {
 193     static const char digits_table[] = {
 194         "00010203040506070809"
 195         "10111213141516171819"
 196         "20212223242526272829"
 197         "30313233343536373839"
 198         "40414243444546474849"
 199         "50515253545556575859"
 200         "60616263646566676869"
 201         "70717273747576777879"
 202         "80818283848586878889"
 203         "90919293949596979899"
 204     };
 205     return digits_table;
 206 }

 289 static inline void _qrintf_long_core(char *p, unsigned long val)
 290 {
 291     const char *digits = _qrintf_get_digit_table();
 292     while (val >= 100) {
 293         unsigned idx = val % 100 * 2;
 294         *--p = digits[idx + 1];
 295         *--p = digits[idx];
 296         val /= 100;
 297     }
 298     if (val < 10) {
 299         *--p = '0' + val;
 300     } else {
 301         *--p = digits[val * 2 + 1];
 302         *--p = digits[val * 2];
 303     }
 304 }

3.3 細かな工夫

3.3.1 実行時のバッファ溢れ検査のループ外巻上げ

snprintfのようにバッファが文字列を出力するのに十分な長さがない場合を考慮しながら文字列を出力する場合, これまでは1文字出力しバッファ溢れが起きていないことを確認というループを実行していました. 前述のように事前に数値の桁数がわかっていればバッファ溢れが起こるかどうかは文字列への変換前に1回確認すれば十分です.

以下のPRでは文字列変換前に数値をバッファにフィットするように値を丸め込みバッファ溢れの検査回数の削減を行っています.

https://github.com/h2o/qrintf/pull/10

3.3.2 16進数数から文字列への変換の最適化

16進数の整数は10進数の整数と異なり上位桁から4bitずつ文字列化することで数値を文字に変換することが可能です.

https://github.com/h2o/qrintf/pull/3

4. 評価

上記の最適化により,さらに約二倍の高速化を達成しました.

Original:

$ git co master
Switched to branch 'master'
Your branch is up-to-date with 'origin/master'.
$ ./bin/qrintf-gcc -O3 examples/ipv4addr.c && time ./a.out 1234567890
result: 73.150.2.210
./a.out 1234567890  0.22s user 0.00s system 99% cpu 0.219 total

Optimized version:

$ git co optimize_itoa
Switched to branch 'optimize_itoa'
Your branch is up-to-date with 'imasahiro/optimize_itoa'.
$ ./bin/qrintf-gcc -O3 examples/ipv4addr.c && time ./a.out 1234567890
result: 73.150.2.210
./a.out 1234567890  0.12s user 0.00s system 99% cpu 0.120 total

5. 関連技術

特定のライブラリ関数に特化した最適化はgccLLVMなどコンパイラJava言語を中心に多くの言語に搭載されています. 例えば,前述の通りLLVMではナイーブな場合ではあるがprintf関数をputs関数やputchar関数に変換する最適化が組み込まれています.(調べていませんが)おそらくCコンパイラならgcciccJVMならhotspotなどの最適化コンパイラにも組み込まれているでしょう.

また,本稿で紹介したlookup-tableを利用した最適化を用いているライブラリとしてhttps://github.com/miloyip/rapidjsonが挙げられます.

rapidjsonでは,lookup-tableを使って数値から文字列への変換(qrintfでは_qrintf_long_core関数)で行ったループ展開の最適化を更に適応し,ループをすべて展開しています.

本稿でもrapidjsonと同じ方法を適応することでループ除去は可能ですhttps://github.com/imasahiro/libtoa/blob/master/libtoa.h#L139. ただしコードサイズの増加は避けられず,また本稿で用いた評価環境では逆に低速化したため採用は見送っています.

6. まとめと今後の課題

本稿では,上記で述べた最適化により数値から文字列への変換の高速化を行いました. 本稿で述べた最適化はh2o/qrintf · GitHubにすでに取り込まれており,Cコンパイラgccを利用する環境では利用可能となっています.

今後の課題として,(1) clang/llvm環境の対応, (2) 他のフォーマッタ(特に浮動小数点型)への対応があると考えられます.まずclang対応についてですが,clangではgccと全く同じインターフェースは提供していません.そのためqrintf-gccをそのままclang上で利用することはできません. 一応,qrintfをclang/llvmの最適化パスとして実装したpull requestを準備しています. ただしメンテナンスコストや,そもそもこれは正しい道なのかも含めて議論する必要はあります.

次に整数型以外の型への対応,特に浮動小数点型への対応があります.ただ,これはすでにFlorian Loitsch氏によるgrisu[1]と呼ばれる高速な浮動小数点数から文字列への変換手法があります. これを適応することで,浮動小数点数を文字列への変換の高速化が可能であると考えられます. ただ,現在私がsprintfを利用するユースケースとして浮動小数点型はほとんど無いため,あまり優先度は高くはありません.

[1] Loitsch, F.: Printing Floating-point Numbers Quickly and Accurately with Integers, Proceedings of the 2010 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’10, New York, NY, USA, ACM, pp. 233–243 (online), DOI: 10.1145/1806596.1806623 (2010).