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点が実行時間の多くを占めていることがわかります.
- 一時バッファ,書き込みバッファへのコピー
- 数値の文字列化ループ
それぞれについて高速化が可能か検討していきたいと思います.
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. 関連技術
特定のライブラリ関数に特化した最適化はgccやLLVMなどコンパイラやJava言語を中心に多くの言語に搭載されています. 例えば,前述の通りLLVMではナイーブな場合ではあるがprintf関数をputs関数やputchar関数に変換する最適化が組み込まれています.(調べていませんが)おそらくCコンパイラならgccやicc,JVMなら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).