URI Template の C++ 実装 (Xbyak による JIT 版ほか)
その昔はテキスト整形ツールすらアセンブラで書くほどのバイナリアンでもあったんですが、X68000 から卒業せざるをえなくなると同時にすっかり足を洗っていたのです。
が、何の因果かこのたび、C++の世界に引き摺り込まれ、メモリやクロック数にきゅうきゅう呻吟する日々が再びやってきてしまいました……。もはやGCの無い言語でプログラミングするまい、と堅く心に誓っていたのになあ(涙)。
まあ、嘆いてばかりいても始まらない。
バイナリアンは××年ぶり(x86 の知識は 286 が最後)、C++ は実質初めて、勉強しないといけないことがたんまり。
んー中谷は何か作ってみないとわかんない人なんで、身近で手頃な題材を……
というわけで URI Template を実装してみました。調べた範囲内ではC++の実装もなさそうだし。
勉強が主目的なので、仕様は簡易に draft-01 準拠(単純な substitution のみ)。
その代わり、素直に string::const_iterator を使って実装したもの、boost::regex 利用版、そして Xbyak による JIT 版という３タイプをこしらえてみました。
http://coderepos.org/share/browser/lang/cplusplus/URITemplates (CodeRepos)
Xbyak とは、光成さんによるC++で実行時に動的に x86 のコードを生成するライブラリです。というとインラインアセンブラと勘違いされるんですが、「実行時に動的に」がポイント。
例えばこの Xbyak 版 URI Template では、"weather/{state}/{city}?forecast={day}" というテンプレートを与えてインスタンス化すると、例えば以下のような「専用のネイティブコード」を生成します。
おーなんか速いんじゃないのこれ、という期待がふくらむんじゃあないでしょうか(笑)。
リポジトリの URITemplate_test.cpp がベンチマーク用のコードになっていますので、こちらを VC++ 2008 でビルドした実行結果を見てみましょう。なお、g++ でビルドした場合もこれとリニアに近い結果が出ることを確認しています。
URITemplatesNormal が string::const_iterator を使った一番素直な実装です。URITemplatesRegex, URITemplatesJIT は名前の通り。
expand はテンプレートに値を埋め込んで URI を得るメソッド、extract はその逆で、１ループあたりの実行時間を算出しています。
regex 版で expand が飛び抜けて遅いのは regex_replace をパラメータの数だけ繰り返しているからです。まあ、値の抽出ならともかく、置き換えに正規表現を無理に使う必要はないですね。これはまあ regex の速度感を掴むためにやってみた、という感じでしょうか。
Normal と JIT を比べたときに、extract の差が expand ほど大きくないのですが、これは extract の返値である std::map に値を放り込むオーバーヘッドが大きいせいです。JIT 版の extract の実行時間のうち７割くらいが std::map に値をセットするのに費やされてしまっています(苦笑)。vector に入れるなり、構造体に入れておいてリフレクションでアクセスするなどの工夫をすればそこのオーバーヘッドはかなり小さくできそうです。ただ、extract は１リクエストに対して１回しか必要ないので、そんなに頑張らなくても良さそうな気もしないでもないです。
extend の方はとても単純な文字列処理でしかないので、正直２割も差が付けば御の字と思っていたのですが、期待していた以上に差が出ました。JIT の底力なのか、std::string が重いのか、まあ両方なのでしょうが。こんな単純な処理でもこれだけの差をたたき出せるなら、もう少し複雑な文字列を扱う処理を JIT 化するメリットもそれなりにありそうです。
参考として、.NET の URI Template 実装(draft-01 準拠)でも同じ形式のベンチマークを同一マシン上で取ってみたのであげておきます（というより、先に試したのはこっち。だからサンプルデータが Redmond になってるｗ）。
C++/CLI で書かれてあり、したがって CLR 上で動作する訳なので単純に実行時間を比較しちゃいけません。あくまで参考ということで。
比べるな、と言いつつ比べると、.NET 版 URI Template もなかなか頑張った数字が出ているんじゃないかな～。
そんなこんなで。
冒頭では一通り泣き言など書いてみたわけですが、ブラックボックスなくダイレクトにコンピュータを叩くのはやっぱり楽しいですね(苦笑)。ちょっと C++ が好きになってきました。変なところでハマったりしなければ……
p.s. パフォーマンスチューニングとかで役に立つかも知れない情報
(1) URITemplates::expand() でコメントアウトされている buf.reserve(256) を有効にすると、VC++ で１割、g++ で５割程度の速度向上が得られます。
expand() では std::string buf への文字列追加処理が繰り返し行われているのですが、あらかじめ reserve することで自動拡張のオーバーヘッドが抑えられているのだと思われます。
VC++ と g++ の向上率の違いは、std::string のサイズの違いが現れているのだと推測。g++ では sizeof(std::string) = 4 ですが、VC++ では sizeof(std::string) = 28 だったりします。ちなみに Effective STL の第１５項にもそこらへんのことが触れられています。
(2) VC++ のコンパイルオプションに /D_SECURE_SCL=0 を追加すると、vector や配列などのイテレータの範囲チェックが緩やかになり、URITemplates(Normal) で２割ほど速度向上します。JIT はループの割合が少ないのでほとんど変わりません。
ただし regex は通常の環境でこのオプションを付けるとライブラリ不整合で正しく動作しなくなります。boost にもこのオプションを付けてビルドしてあげれば期待通りに動くようになります(光成さん、ありがとう)。
が、何の因果かこのたび、C++の世界に引き摺り込まれ、メモリやクロック数にきゅうきゅう呻吟する日々が再びやってきてしまいました……。もはやGCの無い言語でプログラミングするまい、と堅く心に誓っていたのになあ(涙)。
まあ、嘆いてばかりいても始まらない。
バイナリアンは××年ぶり(x86 の知識は 286 が最後)、C++ は実質初めて、勉強しないといけないことがたんまり。
んー中谷は何か作ってみないとわかんない人なんで、身近で手頃な題材を……
というわけで URI Template を実装してみました。調べた範囲内ではC++の実装もなさそうだし。
勉強が主目的なので、仕様は簡易に draft-01 準拠(単純な substitution のみ)。
その代わり、素直に string::const_iterator を使って実装したもの、boost::regex 利用版、そして Xbyak による JIT 版という３タイプをこしらえてみました。
http://coderepos.org/share/browser/lang/cplusplus/URITemplates (CodeRepos)
Xbyak とは、光成さんによるC++で実行時に動的に x86 のコードを生成するライブラリです。というとインラインアセンブラと勘違いされるんですが、「実行時に動的に」がポイント。
例えばこの Xbyak 版 URI Template では、"weather/{state}/{city}?forecast={day}" というテンプレートを与えてインスタンス化すると、例えば以下のような「専用のネイティブコード」を生成します。
003959D0 53 push ebx 003959D1 56 push esi 003959D2 8B 4C 24 0C mov ecx,dword ptr [esp+0Ch] 003959D6 8B 74 24 10 mov esi,dword ptr [esp+10h] 003959DA B8 13 00 00 00 mov eax,13h 003959DF C6 01 77 mov byte ptr [ecx],77h ; 'w' 003959E2 C6 41 01 65 mov byte ptr [ecx+1],65h ; 'e' 003959E6 C6 41 02 61 mov byte ptr [ecx+2],61h ; 'a' 003959EA C6 41 03 74 mov byte ptr [ecx+3],74h ; 't' 003959EE C6 41 04 68 mov byte ptr [ecx+4],68h ; 'h' 003959F2 C6 41 05 65 mov byte ptr [ecx+5],65h ; 'e' 003959F6 C6 41 06 72 mov byte ptr [ecx+6],72h ; 'r' 003959FA C6 41 07 2F mov byte ptr [ecx+7],2Fh ; '/' 003959FE 8D 49 08 lea ecx,[ecx+8] 00395A01 8B 16 mov edx,dword ptr [esi] 00395A03 EB 05 jmp 00395A0A 00395A05 88 19 mov byte ptr [ecx],bl 00395A07 40 inc eax 00395A08 41 inc ecx 00395A09 42 inc edx 00395A0A 8A 1A mov bl,byte ptr [edx] 00395A0C 84 DB test bl,bl 00395A0E 75 F5 jne 00395A05 00395A10 C6 01 2F mov byte ptr [ecx],2Fh ; '/' 00395A13 41 inc ecx 00395A14 8B 56 04 mov edx,dword ptr [esi+4] 00395A17 EB 05 jmp 00395A1E 00395A19 88 19 mov byte ptr [ecx],bl 00395A1B 40 inc eax 00395A1C 41 inc ecx 00395A1D 42 inc edx 00395A1E 8A 1A mov bl,byte ptr [edx] 00395A20 84 DB test bl,bl 00395A22 75 F5 jne 00395A19 00395A24 C6 01 3F mov byte ptr [ecx],3Fh ; '?' 00395A27 C6 41 01 66 mov byte ptr [ecx+1],66h ; 'f' 00395A2B C6 41 02 6F mov byte ptr [ecx+2],6Fh ; 'o' 00395A2F C6 41 03 72 mov byte ptr [ecx+3],72h ; 'r' 00395A33 C6 41 04 65 mov byte ptr [ecx+4],65h ; 'e' 00395A37 C6 41 05 63 mov byte ptr [ecx+5],63h ; 'c' 00395A3B C6 41 06 61 mov byte ptr [ecx+6],61h ; 'a' 00395A3F C6 41 07 73 mov byte ptr [ecx+7],73h ; 's' 00395A43 C6 41 08 74 mov byte ptr [ecx+8],74h ; 't' 00395A47 C6 41 09 3D mov byte ptr [ecx+9],3Dh ; '=' 00395A4B 8D 49 0A lea ecx,[ecx+0Ah] 00395A4E 8B 56 08 mov edx,dword ptr [esi+8] 00395A51 EB 05 jmp 00395A58 00395A53 88 19 mov byte ptr [ecx],bl 00395A55 40 inc eax 00395A56 41 inc ecx 00395A57 42 inc edx 00395A58 8A 1A mov bl,byte ptr [edx] 00395A5A 84 DB test bl,bl 00395A5C 75 F5 jne 00395A53 00395A5E C6 01 00 mov byte ptr [ecx],0 00395A61 5E pop esi 00395A62 5B pop ebx 00395A63 C3 ret
おーなんか速いんじゃないのこれ、という期待がふくらむんじゃあないでしょうか(笑)。
リポジトリの URITemplate_test.cpp がベンチマーク用のコードになっていますので、こちらを VC++ 2008 でビルドした実行結果を見てみましょう。なお、g++ でビルドした場合もこれとリニアに近い結果が出ることを確認しています。
==== URITemplatesRegex city:Redmond day:today state:Washington >> test1(extract) : 6.062usec weather/Washington/Redmond?forecast=Today >> test2(extend) : 12.094usec ==== URITemplatesNormal city:Redmond day:today state:Washington >> test1(extract) : 4.344usec weather/Washington/Redmond?forecast=Today >> test2(extend) : 1.842usec ==== URITemplatesJIT city:Redmond day:today state:Washington >> test1(extract) : 3.188usec weather/Washington/Redmond?forecast=Today >> test2(extend) : 0.72usec
URITemplatesNormal が string::const_iterator を使った一番素直な実装です。URITemplatesRegex, URITemplatesJIT は名前の通り。
expand はテンプレートに値を埋め込んで URI を得るメソッド、extract はその逆で、１ループあたりの実行時間を算出しています。
regex 版で expand が飛び抜けて遅いのは regex_replace をパラメータの数だけ繰り返しているからです。まあ、値の抽出ならともかく、置き換えに正規表現を無理に使う必要はないですね。これはまあ regex の速度感を掴むためにやってみた、という感じでしょうか。
Normal と JIT を比べたときに、extract の差が expand ほど大きくないのですが、これは extract の返値である std::map に値を放り込むオーバーヘッドが大きいせいです。JIT 版の extract の実行時間のうち７割くらいが std::map に値をセットするのに費やされてしまっています(苦笑)。vector に入れるなり、構造体に入れておいてリフレクションでアクセスするなどの工夫をすればそこのオーバーヘッドはかなり小さくできそうです。ただ、extract は１リクエストに対して１回しか必要ないので、そんなに頑張らなくても良さそうな気もしないでもないです。
extend の方はとても単純な文字列処理でしかないので、正直２割も差が付けば御の字と思っていたのですが、期待していた以上に差が出ました。JIT の底力なのか、std::string が重いのか、まあ両方なのでしょうが。こんな単純な処理でもこれだけの差をたたき出せるなら、もう少し複雑な文字列を扱う処理を JIT 化するメリットもそれなりにありそうです。
参考として、.NET の URI Template 実装(draft-01 準拠)でも同じ形式のベンチマークを同一マシン上で取ってみたのであげておきます（というより、先に試したのはこっち。だからサンプルデータが Redmond になってるｗ）。
C++/CLI で書かれてあり、したがって CLR 上で動作する訳なので単純に実行時間を比較しちゃいけません。あくまで参考ということで。
using namespace System;
using namespace System::Collections::ObjectModel;
using namespace System::Collections::Specialized;
const int LOOPS = 500000;
int main(array<System::String ^> ^args) {
UriTemplate^ temp = gcnew UriTemplate("weather/{state}/{city}?forecast={day}");
Uri^ prefix = gcnew Uri("http://localhost");
NameValueCollection^ parameters = gcnew NameValueCollection();
parameters->Add("state", "Washington");
parameters->Add("city", "Redmond");
parameters->Add("day", "Today");
Uri^ fullUri = gcnew Uri("http://localhost/weather/Washington/Redmond?forecast=today");
DateTime d1;
TimeSpan t;
d1 = DateTime::Now;
for(int i=0;i<LOOPS;i++) {
UriTemplateMatch^ results = temp->Match(prefix, fullUri);
if (i == 0 && results != nullptr) {
for each( String^ name in results->BoundVariables->Keys ) {
Console::WriteLine("{0}: {1}", name, results->BoundVariables[name]);
}
}
}
t = DateTime::Now -d1;
Console::WriteLine("time : {0} usec", t.TotalMilliseconds / LOOPS * 1000);
d1 = DateTime::Now;
for(int i=0;i<LOOPS;i++) {
Uri^ namedUri = temp->BindByName(prefix, parameters);
if (i==0) Console::WriteLine("namedUri: {0}", namedUri);
}
t = DateTime::Now -d1;
Console::WriteLine("time : {0} usec", t.TotalMilliseconds / LOOPS * 1000);
return 0;
}
STATE: Washington CITY: Redmond DAY: today time : 23.53125 usec namedUri: http://localhost/weather/Washington/Redmond?forecast=Today time : 7.625 usec
比べるな、と言いつつ比べると、.NET 版 URI Template もなかなか頑張った数字が出ているんじゃないかな～。
そんなこんなで。
冒頭では一通り泣き言など書いてみたわけですが、ブラックボックスなくダイレクトにコンピュータを叩くのはやっぱり楽しいですね(苦笑)。ちょっと C++ が好きになってきました。変なところでハマったりしなければ……
p.s. パフォーマンスチューニングとかで役に立つかも知れない情報
(1) URITemplates::expand() でコメントアウトされている buf.reserve(256) を有効にすると、VC++ で１割、g++ で５割程度の速度向上が得られます。
expand() では std::string buf への文字列追加処理が繰り返し行われているのですが、あらかじめ reserve することで自動拡張のオーバーヘッドが抑えられているのだと思われます。
VC++ と g++ の向上率の違いは、std::string のサイズの違いが現れているのだと推測。g++ では sizeof(std::string) = 4 ですが、VC++ では sizeof(std::string) = 28 だったりします。ちなみに Effective STL の第１５項にもそこらへんのことが触れられています。
(2) VC++ のコンパイルオプションに /D_SECURE_SCL=0 を追加すると、vector や配列などのイテレータの範囲チェックが緩やかになり、URITemplates(Normal) で２割ほど速度向上します。JIT はループの割合が少ないのでほとんど変わりません。
ただし regex は通常の環境でこのオプションを付けるとライブラリ不整合で正しく動作しなくなります。boost にもこのオプションを付けてビルドしてあげれば期待通りに動くようになります(光成さん、ありがとう)。