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

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

とにかく速い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