SSEを使ってHTMLエスケープを高速化してみた

高速なHTMLエスケープをするライブラリを作った

ある日HTMLエスケープを速くしたくなって、hescapeというライブラリを作った。

github.com

とにかく速いHTMLエスケープがしたい

Railsアプリのビューのレンダリングにおいて、CGI.escapeHTMLを高速化*1することでRailsのデフォルトのテンプレートエンジンが大きく高速化されたり*2、GitHubでもHTMLエスケープが全体のパフォーマンスに影響が大きかった事例もある*3など、常に自動でHTMLエスケープが行なわれるRailsの環境ではHTMLエスケープの速度が割と大きな意味を持っている。

従って、Hamlitの最速性を維持するためにHTMLエスケープのパフォーマンスを極めておきたかった。

vmg/houdini を倒したい

前述したGitHubの人が既にhoudiniというかなり速いエスケープライブラリを作っていて、escape_utilsというgemを使うとHamlやSlimでそれが使え、HamlitやFamlはデフォルトでそれが使われるようになっている。Rubyにおいてこれより速くHTMLエスケープを行う手段を知らないので、これを越えることが目標になる。

Streaming SIMD Extensions

とはいえhoudiniはよくできているので、一緒に協力してテンプレートエンジンを作っている*4 id:eagletmt さんと去年「(HTMLエスケープは)まああれより速くしようがないですよね」みたいな話をしたのだけど、この前Tokyo RubyKaigi 11の懇親会で id:nurse さんが「HTMLエスケープはSSE使えば速くできるよ」とおっしゃっていた。

h2oのHTTP/1パーサに使われているpicohttpparserもSSE命令(PCMPESTRI)で速くなっていて *5、ループで1文字ずつチェックしていたのが1命令で16文字同時にチェックされるようになっている。HTMLエスケープでも、エスケープすべき文字がない時特に速くなりそうな感じがしたので、試してみることにした。

一人チューニング大会

SSEを使う以前にそもそもCで速いコードを書くのがあまり得意ではないので、事前にテストとベンチマークを用意して、ひたすらベンチマークの結果をよくする、という一人ISUCONみたいなことをやっていた。結構面白いので、やってみたい人は以下を読まずにHTMLエスケープ(CGI.escapeHTMLコンパチのもの)を実装してみると良いかもしれない。

ベンチマークには、一切エスケープをやらないもの全部エスケープするもの、あとライバルのhoudiniが使っているものを用意し、CIでhoudiniの何倍速いかというのを出していた*6。以下は実装ログとwercker上でのベンチマークの結果(houdiniより何倍速いか)の推移である。

コミット 概要 no escape all escape houdini bench
Implement HTML escape 素直に実装した奴。遅い。 0.04x 0.43x 0.08x
Reduce allocation times エスケープが発生した時のみreallocするようにした 0.53x 0.43x 0.85x
Lazily copy unescaped characters 非エスケープ文字はエスケープが発生した時にまとめてコピーするようにした 0.62x 0.35x 0.93x
Skip allocation when nothing is escaped エスケープが行なわれない時はmallocが起きないようにした 1.13x 0.34x 0.91x
Increase allocation size by 1.5 houdiniのパクリ。2回目以降のエスケープ時、メモリが足りない時に必要分の1.5倍メモリを確保している。いいのか…と思うけど対houdiniなら公平。 1.12x 0.61x 1.01x
Optimized strlen of escaped string strlen対象が限られてるのを利用してstrlenを四則演算に変えている。やんちゃチューニング感ある。 1.08x 0.99x 1.11x
Change ensure_allocated to be static ある関数をstaticに変えただけ 1.08x 1.16x 1.13x
Skip non-escaped characters fast この辺で語られてるテクニック(をやっているつもり)。エスケープしない時に局所的にループを回している。 1.17x 1.16x 1.14x
Optimize by pcmpestri intrinsics ここでSSEを使った。全部エスケープだと遅くなるが、エスケープがない場合は本当に速い。 7.70x 追記 0.83x 1.63x

結果

普通のWebアプリのほとんどのケースでは実際のエスケープは走らないわけだけど、そのケースにおいて PCMPESTRIを使っただけで6〜7倍になった(下記の追記を参照)。ただ、あまり何も考えないで作った非現実的なベンチなので、参考にするなら例えばURLくらいの長さの文字列のエスケープを見た方が良いと思う。

本当はHamlitにいれようと思ってたけど、保守性が下がる割に全てのケースで速くなるわけではない*7のと、ビルドの時に考えることが増えるので、HamlitでSSEを使うのは一旦見送ることにした。

08/16 23:35 追記

shinhさんににご指摘いただいた致命的なバグを直したことによりエスケープなしのケースが 7.29x→2.78x くらいに変化している。いろいろ指摘をいただいたので直している最中で、それが終わってみないと実際どのくらいの速さになるものなのか不明。

感想

最初どうやって使うのかが全然わからず難しいなと思ったけど、その難しさに見合う結果は得られたのでよかった。picohttpparserのコードを参考にしてたのでSSE4を使っているけれど、後で後継のAVXも試したい。

*1:https://github.com/ruby/ruby/pull/1164

*2:http://k0kubun.hatenablog.com/entry/2016/05/29/215851

*3:https://github.com/blog/1475-escape-velocity

*4:http://k0kubun.hatenablog.com/entry/2015/12/12/000037

*5:http://blog.kazuhooku.com/2014/12/improving-parser-performance-using-sse.html

*6:10%エスケープというのも見てたけど、houdiniのベンチとあんま変わらんのと横幅の関係でこの記事からはカット

*7:これもうちょっとなんとかならないかな…