きっかけ

まず、たまたまこの議論 https://github.com/h2o/h2o/issues/15 を見て「なんか怒ってるなあ」と思ったのが興味を持ったきっかけでした。

この議論のなかでh2oの作者であるOkuさんが「ステートマシンなんかカス」的なことをおっしゃっていて、私の中では「Okuさん＝ウィザード」とカテゴライズされているので、「へーそうなんだ」みたいなことを無批判に思ってたのですが、自分の経験上、ステートマシンがだめというよりはテーブルがだめだと思っていて、しばらく脳内に漂わせていた後「そうはいってもなんとかはなるんじゃねえの〜」などと思ったりもしたのですが、そもそもその部分が全体に対してそんなに大きな位置を占めるのかなあとメタな疑問を持ったりして、なんとなくそのまま忘れていました。

しかし最近Okuさんのこのスライド http://www.slideshare.net/kazuho/h2o-20141103pptx を見て、ご本人がh2oにおいて文字列探索に結構関心を割いていらっしゃっていて、そこを速くすれば速くなると考えていらっしゃるらしいということを知り、じゃあ「多少なんかしら貢献できるかもな」と思えたのです。

前提

一応私自身についてどんな人間か語っておくと、過去にschemeインタプリタとか60FPSで動く物理エンジン(http://qiita.com/jonigata/items/dd3198e817f7e956613f )とかラスタライザみたいな画像処理ルーチンとか実装した経験上、そこそこ高速に動くプログラムを書くのは割と得意です。

ですが、ちゃんとクロック数とかパイプラインとかレイテンシとか計算することはなくて、ネットで聞きかじった知識と実測だけでやってるので、ものすごく高速なプログラムを書くのはさほど得意ではありません。もっとも8bitの頃からパソコン触ってますし、コンパイラを実装した経験があったりもするので、自然にやっている大雑把な見積もりはそんなに外してないとは思います。

そんなわけで、せっかくなのでこれを機会に多少は理論的な部分も勉強しながらやるかと思い立って、こんな本(http://www.amazon.co.jp/gp/product/4904807057?psc=1&redirect=true&ref_=oh_aui_detailpage_o02_s00 )を買いました。ただしこの本がアマゾンから届いたのがこの文書に書いた作業の後だったので、文末で答え合わせのような形で触れたいと思います。

測定方法とかも全く自信がないので、識者の方にコメントをいただけたらなと思います。

この文書の流れは、概ね時系列に沿ったものとなっていますが、筆者の知識の更新があったり後知恵が挿入されたりしているので大変読みづらいものになっているかもしれません。どうかご容赦ください。

リーディング

さて、まずpicohttpparserを読んでみた所、「picohttpparserはコロンと改行の分割しかしてない」ということがわかりました。これを私が高速化できる気は全くしなかったので（素人考えだとこっちのほうが入力が長いのでSSE向きな気がする -- と思ったら実際SSE対応したらしい http://blog.kazuhooku.com/2014/12/improving-parser-performance-using-sse.html ）、次にh2oのソースを読んでみた所、h2o_lookup_tokenという関数でヘッダのタグを分類しているらしいということがわかりました。

そのアルゴリズムを知ってまたちょっと驚いたのですが、lex的ステートマシンではなく「長さ」と「最後の文字」だけで分類はほとんど完了していて、strcmp的な文字列照合(h2o__lcstris_core)は確認のためにしかしていないようでした。これも一瞬「これ高速化するの無理では」と思ったのですが、それでもなんとなく眺めていると全くどうにもならないこともないような気がしてきました。理由は以下です。

そうは言ってもh2o__lcstris_coreは毎回1回は呼ばれる
h2o__lcstris_coreは3つの引数(マッチ対象、キーワード、キーワード文字数)をとるが、後ろの２つはほぼコンパイル時に決定される。またマッチ対象の文字数もキーワード文字数と等しいと確定している。
tolowerが毎文字呼ばれている
最内周で文字数カウントをしている

strcmpを高速化してみる

キーワードとキーワード文字数は定数なので、最初はC++のvariadic templateで

inline bool kcmp(const char*) {
    return true;
}

template <class... T> inline
bool kcmp(const char* target, char key_car, T... key_cdr) {
    if (tolower(*target) != key_car) return false;
    return kcmp(target+1, key_cdr...);
}

// usage: kcmp("hello", 'w', 'o', 'r', 'l', 'd') -> false
// usage: kcmp("hello", 'h', 'e', 'l', 'l', 'o') -> true

みたいなコード書けば一発で済みそうだなと思ったのですが、CMakeの使い方がよくわからなくてC++のコードをリンクするのがめんどうそうだったので、とりあえず次のようなコードを書いてみました（この時点でなんかもう色々ヒドイ）

#define CASE_GOTO(x) case x: goto T##x;
#define COMPARE_CHAR(x) T##x: if (target[x-1] != test[x-1] && target[x-1] != test[x-1] - 0x20) return 0;

int h2o__lcstris_core(const char *target, const char *test, size_t test_len)
{
    switch(test_len) {
        case 0: return 1;
        CASE_GOTO(1);
        CASE_GOTO(2);
        CASE_GOTO(3);
        CASE_GOTO(4);
        CASE_GOTO(5);
        CASE_GOTO(6);
        CASE_GOTO(7);
        CASE_GOTO(8);
        CASE_GOTO(9);
        CASE_GOTO(10);
        CASE_GOTO(11);
        CASE_GOTO(12);
        CASE_GOTO(13);
        CASE_GOTO(14);
        CASE_GOTO(15);
        CASE_GOTO(16);
        CASE_GOTO(17);
        CASE_GOTO(18);
        CASE_GOTO(19);
        CASE_GOTO(20);
        CASE_GOTO(21);
        CASE_GOTO(22);
        CASE_GOTO(23);
        CASE_GOTO(24);
        CASE_GOTO(25);
        CASE_GOTO(26);
        default: assert(0); return 0;
    }

    COMPARE_CHAR(26);
    COMPARE_CHAR(25);
    COMPARE_CHAR(24);
    COMPARE_CHAR(23);
    COMPARE_CHAR(22);
    COMPARE_CHAR(21);
    COMPARE_CHAR(20);
    COMPARE_CHAR(19);
    COMPARE_CHAR(18);
    COMPARE_CHAR(17);
    COMPARE_CHAR(16);
    COMPARE_CHAR(15);
    COMPARE_CHAR(14);
    COMPARE_CHAR(13);
    COMPARE_CHAR(12);
    COMPARE_CHAR(11);
    COMPARE_CHAR(10);
    COMPARE_CHAR(9);
    COMPARE_CHAR(8);
    COMPARE_CHAR(7);
    COMPARE_CHAR(6);
    COMPARE_CHAR(5);
    COMPARE_CHAR(4);
    COMPARE_CHAR(3);
    COMPARE_CHAR(2);
    COMPARE_CHAR(1);

    return 1;
}

ゴミみたいなコードなのでよく意味がわからないかたもいらっしゃって当然とは思いますが、文字数に応じて「残りN文字を照合する」場所に放り込むことで文字数確認を1回で済ますコードです。Z80プログラマだったら自己書き換えとか演算オフセットジャンプで何とかしそうな感じ（よく知らないので想像ですが）。ちなみにswitchのfall throughで同じことできるんじゃないかと思ってやってみましたが、なぜかこれより遅くなりました。アセンブリを見てないので理由はなんとなくしかわかりません。

さて、これでwrk(httpベンチ)を使ってrpsを測ってみたのですが、誤差が大きくてよくわからん感じだったので、次のようなプログラムを用意してh2o_lookup_tokenの速度だけ測ってみることにしました。この確認コードもあんまりよくはなさそうだなと思うのですが、厳密さを求められる状況でチューニングしたことがないのでどうしていいかよくわからないです。

#define H2O_USE_LIBUV 0
#include "h2o.h"
#include "token_table.h"
#include <assert.h>

typedef struct {
    const char* str;
    int length;
    int success;
} Data;

Data data[] = {
    {"content-length", 14, 1},
    {"if-modified-since", 17, 1},
    {"last-modified", 13, 1},
    {"user-agent", 10, 1},
    {"Content-Length", 14, 1},
    {"If-Modified-Since", 17, 1},
    {"user-agemt", 10, 0},
    {"if-modified-sinke", 17, 0},
};

int main() {
    unsigned int i = 0;

    for (i = 0 ; i < 10 * 10000 * 10000; i++) {
        const Data* p = &data[i&0x7];
        const h2o_token_t* q = h2o_lookup_token(p->str, p->length);
        assert((p->success && q) || (!p->success && !q));
    }   
}
// gcc -I../include -I../deps/picohttpparser -I../deps/yoml -O3 main.c string.c memory.c

これを
% time ./a.out
として測りました。ループやassertのオーバーヘッドなどあるとは思いますが、とりあえず速くなったかどうか知れればOKなのでこのまま。

まず、元のコードは18.8秒。

変更後のコードは13.3秒ということで、誤差でない範囲で高速化できてるようでした。

多分狙い通り字数カウントを省略できてる（アセンブリ見てないので憶測）のと、順序に対する依存性がないので並列実行できるとかそういうのじゃないでしょうか（知らないので憶測）。（あとで「これunrollと大体一緒だよな」と思ってググったらgcc4ではO3でもunroll-loopsはオフらしいのでオンにして元のコードを調べてみたら15.6秒でした)

lookup高速化

前節の最適化でrpsに影響がでないようなので、次にh2o_lookup_tokenに照合コードを展開してみることにしました。

個人的な経験則による最適化の優先度としては、高い順から

メモリに触らない
関数呼び出ししない
分岐しない

くらいの感じです。これが現代のアーキテクチャにマッチしてるかどうかは正直そんなに自信がないのですが、まあやってみます。一応展開によってこれらのポイントはカバーできるはずです。

token_table.hのソースは、もちろんスクリプト(ruby)で自動生成しました。

strcmpを展開

とりあえず、h2o__lcstris_coreを馬鹿みたいに展開します。これによってループのジャンプと長さ判定を削除することができます。展開するので前節のコードはサクッと削除。

抜粋になりますが、こんなコードです。

const h2o_token_t *h2o_lookup_token(const char *name, size_t len)
{
    switch (len) {
    case 3:
        switch (h2o_tolower(name[2])) {
        case 'a':
            if (h2o_tolower(name[0]) != 'v') return NULL;
            if (h2o_tolower(name[1]) != 'i') return NULL;
            return H2O_TOKEN_VIA;
        case 'e':
            if (h2o_tolower(name[0]) != 'a') return NULL;
            if (h2o_tolower(name[1]) != 'g') return NULL;
            return H2O_TOKEN_AGE;
        }
        return NULL;
    case 4:

多分一定以上長い奴はh2o__lcstris_core呼び出しのままにしておいた方がよいとかあると思いますが、ヒューリスティックな話ですし面倒なのでそのまま。

これで13.6秒。ちょっと遅くなってしまいましたね。なぜでしょうか。コード肥大化のせいかな？

tolowerを減らす

次に、tolower呼び出しを一個減らしてみました。

const h2o_token_t *h2o_lookup_token(const char *name, size_t len)
{
    switch (len) {
    case 3:
        switch (name[2]) {
        case 'a':
        case 'A':
            if (h2o_tolower(name[0]) != 'v') return NULL;
            if (h2o_tolower(name[1]) != 'i') return NULL;
            return H2O_TOKEN_VIA;

これは多分元のコードでも試せるし特にデメリットもない最適化だと思います（効くかどうかは知りませんが）。
これで13.0秒。微妙に効いたかもしれませんが、誤差かも知れません。何度か試しましたが、0.1秒もブレない感じではありましたので、一応効いてるっぽいです。

一応素人なりに考えてみます。h2o_tolowerがもともと適切にインライン展開されていると考えた場合、switchまでに行われる処理は

ロード1回
定数比較最大2回
条件ジャンプ最大2回
定数演算1回
テーブルジャンプ1回（もしくは定数オペランド比較最大n回+条件ジャンプ最大n回)

これが

ロード1回
テーブルジャンプ1回（もしくは定数オペランド比較最大2*n回+条件ジャンプ最大2*n回)

になります。ああ結構減ってるかも知れませんね。あとレジスタ消費も多分1つ少ない気がします（※アセンブリ出力みないで全部憶測で言ってます！）。

tolowerをもっと減らす

一応効果あるみたいなので、次は各文字比較におけるtolowerも削除してみます。やり方は上と同じですが、各文字については展開したからこそできる処理と言えるかも知れません。右辺が定数でないと演算が必要になるし記号の処理もややこしかったりするからです。

const h2o_token_t *h2o_lookup_token(const char *name, size_t len)
{
    switch (len) {
    case 3:
        switch (name[2]) {
        case 'a':
        case 'A':
            if (name[0] != 'v' && name[0] != 'V') return NULL;
            if (name[1] != 'i' && name[1] != 'I') return NULL;
            return H2O_TOKEN_VIA;

7.3秒 なにこれちょう速い！

こちらは厳密に言うと比較回数は減ってないような気がするのですが、ショートサーキットが起きやすいとか演算が少ないとか右辺が定数とかのせいでしょうか。頭が悪いのでロジック的に本当に等価なのかといったあたりも不安があります。

一応コンパイラの気持ちになって考えてみます（またアセンブリ出力を見ずに憶測で語る）。文字単位で、

元のコード

ロード2回
定数比較最大2回
レジスタ比較最大1回
定数演算1回
条件ジャンプ最大3回

改造後のコード

ロード1回
定数比較最大2回
条件ジャンプ最大2回

さらに関数呼び出しコストとループのコストが削除されているので、このくらい速くなっていても別におかしくはないような気もします。

※書いてて気付きましたが、h2o_tolowerの定義'A' <= ch && ch <= 'Z'よりch <= 'Z' && 'A' <= chの方がよかったりするかもしれませんね。小文字が来た時にショートサーキットされやすいので。多分どうでもいい範疇だと思いますけど。

さらにひどいことをする

さらにこんな風に書き換えてみました。

    case 10:
        switch (name[9]) {
        case 'e':
        case 'E':
            if ((*((uint32_t*)(name + 0)) | 0x20202020) != 0x2d746573) return NULL;
            if ((*((uint32_t*)(name + 4)) | 0x20202020) != 0x6b6f6f63) return NULL;
            if (name[8] != 'i' && name[8] != 'I') return NULL;
            return H2O_TOKEN_SET_COOKIE;

4バイトずつ処理するコードです。5.1秒、ヒー速い！

しかしこのコードは問題が多いので参考記録です。

':'や'-'で誤動作する(0x1aをコロンと、0x0dをハイフンと認識してしまう)。
CPUのエンディアンの影響を受ける
picohttpparserの返却値にはアラインメントの保証がないので、例外になるCPUがある。
テストデータのアラインメントが揃っているので、86系でも実際にはペナルティで少し遅くなる。

1.ははなんとかなる(!isprintなのでpicohttpparserで弾かれてるかも？)し、2.も判定すればよいだけだと思いますが、3.は対処が難しいですね。試しに

inline uint32_t charpack(const char* s, int n) {
    int m = n*4;
    return (
        (
            ((uint32_t)(unsigned char)(s[m+0]) << 24) |
            ((uint32_t)(unsigned char)(s[m+1]) << 16)
        )
    |
        (
            ((uint32_t)(unsigned char)(s[m+2]) << 8) |
            ((uint32_t)(unsigned char)(s[m+3]) << 0)
        )
    ) | 0x20202020;
}

こんな感じで動的に作るコードを書いてみましたが、7.9秒と前節より遅くなってしまいました。このコード、一応依存関係に気をつけてみたつもりのコードなんですが。

ワンチャンあるとすれば、h2o_lookup_token全体をアドレスの剰余で分岐しておくこと！？

※後知恵: よく考えたら1.についてはマスク値をいじれば解決できますね。

小細工

このあともいくつか小細工を試しましたが、全然ダメでした。

ちなみに、ここでpicohttpparserで知った__builtin_expectを使ってみたら、なぜか遅くなりました。この条件真になることまずないと思うんですけど、なぜだろう。しかもむしろ真とヒントを与えたら元に近い速度（しかしどっちにしろ遅い）になった。

以下のコードもむしろ遅くなりました。なんででしょうね。依存関係のせいかな。

    //if (name[0] != 'v' && name[0] != 'V') return NULL;
    if ((name[0] | 0x20) != 'v') return NULL; // うろ覚えだけどこんな感じ

再びrpsを測る

まあとりあえず関数単体では3倍くらい速くなったはずですので、これでrpsを測ってみます。

……ほとんど変わりませんでした。

なんだこれ効果あるのか、と思いつつしばし考えた後、ふとh2o__lcstris_coreの段階で入力を表示させてみました。

Hostヘッダしか来てませんでした。そりゃ変わらんわ（最初に調べろ）。

というわけで5行くらい適当にヘッダを足してみました。

……別に変わりませんでした。

うーん、効果あるのでしょうか。

これも最初にプロファイルとっとけよという話だと思うのですが、もちろん自分のプログラムだったらプロファイル取りますよ。取りますとも。ただ今回はCMakeの使い方とかわからなくて……（言い訳）

Okuさんによると、今後ファイルキャッシュを導入すればrpsが最強に強まってh2o_lookup_tokenの速さが生きてくるはずとのことでしたので、導入されたらもう一回試してみようかなと思います。

twitterでぶつぶつ言ってたらherumiさん(http://developer.cybozu.co.jp/tech/?p=7982 )とかすごそうな人が集まっちゃって出る幕がない感じになってきてしまいましたが、集めるのに微かに貢献したような気はするし自分自身は勉強にもなったので損はしてないかな。

あとで思いついたこと

「strcmpを高速化してみる」の節のコードみたいな変なコード書く前に、このコード試せばよかったですね。

inline int cmp(const char* s, const char* key, int n) {
    if (n == 1) {
        return h2o_tolower(*s) == *key ? 1 : 0;
    } else {
        if (h2o_tolower(*s) != *key) return 0;
        return cmp(s+1, key+1, n-1);
    }
}

今試してみたら、元のコードよりは早かった模様。でも例の変なコードよりはだいぶ遅かったので、うまく展開されてないような。あとn==1のときでなくn==0を特殊処理にしたら遅くなるあたりも意味不明。その方がシンプルなコードになるし、全部展開されてるなら最適化したら同じのような気が。

考察

OkuさんはSSE方向に可能性を見出していらっしゃるようでしたが、picohttpparserの返すデータの仕様上アラインメントもパディングも全く保証されていないはずなのと文字列が短いのとで効果なさそうだな〜と漠然と思って心の中で枝刈りしていました（もっとも私はSSE全然詳しくないので、ただの素人の印象にすぎないのですが）。関数呼び出しとインラインアセンブラ使用による前後のコードの最適化抑制(これは昔のVCだけ？　最近追ってないのでよく知らない)だけで赤字っぽいイメージです。すべてのアライメント✕すべての定数分のコードをあらかじめ生成しとくとかすればいける？

※と思ったら、herumiさんのツイートによると最近のSSEだとアラインメントそんなに気にしなくていいらしい。それならだいぶ使いやすそう。

他に思いつく高速化手法としては、ツイッターにも書きましたが「長さと最後の文字と最初の文字くらいでパーフェクトハッシュ作る」とかですが、さすがにそこまで分岐減らしても元が取れなさそう。と思ったけど、大文字・小文字の吸収までできれば一定の価値はあるかも？（そんなハッシュ式あるのか）

~~というわけで、本気でh2o_lookup_tokenで長さと最後の文字しかみないというソリューションを推したいです。恐らく誰も困らない。~~ ←ダメだそうです。コメント欄を参照されたし。

「Cプログラム高速化研究班コードを高速化する20の実験と達人の技」を読んでの考察

「Cプログラム高速化研究班コードを高速化する20の実験と達人の技」を読んだ感じによると、上述の私の経験則（再掲

メモリに触らない
関数呼び出ししない
分岐しない

のうち、2と3は特に問題ない感じでした。1についてなんですが、私の感覚だと「メモリアクセスは普通の演算と比べてヘタすると1桁違うくらい遅い」なんですが、そこまで遅くはないようです。せいぜい3〜4倍程度？

なぜ私はこのような感覚を持っているのでしょうか。理由を考えてみます。

自分が想像してるよりも遙かに多くキャッシュミスしている
気のせい

う〜ん。メモリ触ったら犯罪、というのは、それこそPentiumくらいの時に横スクロールシューティング作ってて、MMXを試してみたくらいの頃からの印象なんですが。その時よりCPUとメモリの速度差は開いているはず。

ただ、「Cプログラム高速化研究班」を読むと、この他にも、実世界アプリケーションでは関係ありそうな感じのことがいくつか書いてありました。

メモリアクセスは並列実行できる本数が少ない
メモリアクセスのレイテンシが結構大きいらしい

これらの理由が複合すると、シーケンシャルな一括転送でないメモリアクセスは実際に私が思ってる程度に重くなってしまうのかもしれません。あるいは、局所的に理論的に速くても、実世界アプリケーションでは結局汚したキャッシュを周囲に押し付けてるだけになる、といったようなこともありえそうな話に思えました。

分岐が遅いというのはちょっと疑っています。現代CPUが分岐予測でどんな魔法使ってるのかは全然知らないのですが、件の物理エンジンでも分岐まわりをいじって速度が変わることはほとんどありませんでしたし、変わるときも（私の能力では）ほとんど予測できませんでした。今回も概ねそうでした。分岐するときは大抵比較の両辺のロードや依存関係のある処理が入るので、その遅さによる風評被害を受けているのではないかなと思っていたりします。関数呼び出しが遅いのも、実はレジスタをメモリにセーブするせいではないかと思っていたりします。要するにメモリアクセスが諸悪の根源。ここまで行くと宗教っぽいですかね。

それと今回の一人遊びを通じて、「さらにひどいことをする」の結果のように比較が8個から1個に減ってても遅くなることがあることなどから、依存関係の有無がものすごくデカイのではないかという気がしてきました。これから最適化するときは、依存関係を減らすことの優先度を上げてみよう。というより、凡人によるヤマカン最適化用統一理論としては「メモリアクセスが遅いのも依存関係が生じるせい」と考えてしまったほうがコストパフォーマンスがよいかも。だんだん純粋関数型言語に近づいてきた。

これを逆から考えると、現在の環境でhacker's delightっぽいテクを手癖で使ってしまうと、却って遅くなってしまうケースも結構ありそうですね。将来もっとCPUが賢くなって、今回やったような展開も「するな」と言われるような時代がくるのかな。

まとめ

というわけで、「うまくいきませんでしたガハハ」といったあたりの感想で締めたいと思います。一応まあターゲットにした関数自体は3～5倍位速くなってる気がするので、単純計算するとrpsにも0.5～1％くらいのインパクトはありそうな気がするんですけど、うまく測定できませんでした。プロに色々教えていただけると嬉しいですね。

あと、これはこれとして、トークンルックアップテーブル自動生成ツールみたいなの作って、時代の変化はそちらで吸収しちゃうというのもアリかなと思いました。ウェブアプリケーションのルータにも使えるので。HTTP2になったらいらなくなっちゃうのかな（よく知らないけど）

h2o高速化チャレンジ(失敗)記