« サイボウズ・ラボ 第7回テーマ発表会 | メイン | 英単語タイピングゲーム iVoca をβテスト公開しました »

URI Template の C++ 実装 (Xbyak による JIT 版ほか)

その昔はテキスト整形ツールすらアセンブラで書くほどのバイナリアンでもあったんですが、X68000 から卒業せざるをえなくなると同時にすっかり足を洗っていたのです。
が、何の因果かこのたび、C++の世界に引き摺り込まれ、メモリやクロック数にきゅうきゅう呻吟する日々が再びやってきてしまいました……。もはやGCの無い言語でプログラミングするまい、と堅く心に誓っていたのになあ(涙)。

まあ、嘆いてばかりいても始まらない。
バイナリアンは××年ぶり(x86 の知識は 286 が最後)、C++ は実質初めて、勉強しないといけないことがたんまり。
んー中谷は何か作ってみないとわかんない人なんで、身近で手頃な題材を……

というわけで URI Template を実装してみました。調べた範囲内ではC++の実装もなさそうだし。
勉強が主目的なので、仕様は簡易に draft-01 準拠(単純な substitution のみ)。
その代わり、素直に string::const_iterator を使って実装したもの、boost::regex 利用版、そして Xbyak による JIT 版という3タイプをこしらえてみました。

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 はその逆で、1ループあたりの実行時間を算出しています。

regex 版で expand が飛び抜けて遅いのは regex_replace をパラメータの数だけ繰り返しているからです。まあ、値の抽出ならともかく、置き換えに正規表現を無理に使う必要はないですね。これはまあ regex の速度感を掴むためにやってみた、という感じでしょうか。

Normal と JIT を比べたときに、extract の差が expand ほど大きくないのですが、これは extract の返値である std::map に値を放り込むオーバーヘッドが大きいせいです。JIT 版の extract の実行時間のうち7割くらいが std::map に値をセットするのに費やされてしまっています(苦笑)。vector に入れるなり、構造体に入れておいてリフレクションでアクセスするなどの工夫をすればそこのオーバーヘッドはかなり小さくできそうです。ただ、extract は1リクエストに対して1回しか必要ないので、そんなに頑張らなくても良さそうな気もしないでもないです。

extend の方はとても単純な文字列処理でしかないので、正直2割も差が付けば御の字と思っていたのですが、期待していた以上に差が出ました。JIT の底力なのか、std::string が重いのか、まあ両方なのでしょうが。こんな単純な処理でもこれだけの差をたたき出せるなら、もう少し複雑な文字列を扱う処理を JIT 化するメリットもそれなりにありそうです。

参考として、.NET の URI Template 実装(draft-01 準拠)でも同じ形式のベンチマークを同一マシン上で取ってみたのであげておきます(というより、先に試したのはこっち。だからサンプルデータが Redmond になってるw)。
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++ で1割、g++ で5割程度の速度向上が得られます。
expand() では std::string buf への文字列追加処理が繰り返し行われているのですが、あらかじめ reserve することで自動拡張のオーバーヘッドが抑えられているのだと思われます。
VC++ と g++ の向上率の違いは、std::string のサイズの違いが現れているのだと推測。g++ では sizeof(std::string) = 4 ですが、VC++ では sizeof(std::string) = 28 だったりします。ちなみに Effective STL の第15項にもそこらへんのことが触れられています。

(2) VC++ のコンパイルオプションに /D_SECURE_SCL=0 を追加すると、vector や配列などのイテレータの範囲チェックが緩やかになり、URITemplates(Normal) で2割ほど速度向上します。JIT はループの割合が少ないのでほとんど変わりません。
ただし regex は通常の環境でこのオプションを付けるとライブラリ不整合で正しく動作しなくなります。boost にもこのオプションを付けてビルドしてあげれば期待通りに動くようになります(光成さん、ありがとう)。

トラックバック

このエントリーのトラックバックURL:
http://labs.cybozu.co.jp/cgi-bin/mt-admin/mt-tbp.cgi/1955