Hatena::ブログ(Diary)

Islands in the byte stream

2011-02-02

Why Xslate is so Fast

(There is the Japanese version bellow)

There are reasons why Xslate so fast, so this article explains them, which will be added to the Xslate document.

Taking precompiling style

Template engines which precompile templates are always faster than line-by-line interpreters. Almost all the engines implemented in scripting languages (e.g. Template-Toolkit or Text::MicroTemplate) takes precompiling style, but most of the C implementations (e.g. HTML::Template::Pro) don't, or compile templates but don't have a way to reuse them (e.g. ClearSilver).

Virtual machine specialized for template processing

Xslate has its own virtual machine specialized for template processing, esp. for string concatenation, which is very effective in Perl because template processing is much simpler than what is expected to Perl (specialized VMs would be more effective in other scripting languages because they have no operator for string concatenation). Moreover, some VM optimization techniques which Perl doesn't take are applied (e.g. direct-threaded code).

HTML escaping bytecode

HTML escaping in pure Perl template engines is a bottleneck. I saw Text::MicroTemplate became several times faster by implementing its HTML escaping routine in C (this modification will be ported to the next major update of Text::MicroTemplate!). Moreover, Xslate VM has a special bytecode to escape inputs and concat them to the output buffer.

Preallocating the output buffer

Reducing malloc() is a basic optimization in C. The size of buffers which a template outputs is considered to be stable, so the rendering routine can estimate the size of the buffer to malloc() by the previous result. This is a micro optimization but makes rendering significantly faster.

(Japanese)

他の言語の方にもXslateに興味を持っていただいたようなので、なぜXslateが速いのかをまとめておきます*1。参考までに。

事前コンパイル方式であること

Perlに限りませんが、事前にコンパイルするタイプのテンプレートエンジンはそうでないものより速いです。スクリプト言語の場合、そのままホスト言語のソースコードに変換したほうが実行が楽だという事情もあり、事前コンパイル式が多いようですが*2、C実装だとデータ構造を別途用意するのが煩雑なためか、都度解釈が多いようです*3。内部形式に変換はするものの、キャッシュできないものもあります*4

独自VMであること

先の記事でも触れたTenjinの最適化の分析*5によれば、文字列連結演算子のあるPerlではTenjinの性能が非常に高かったということでした。ところが、文字列連結に特化した仮想マシンを作った結果、Perlよりもさらに高速になりました。特定の目的のために仮想マシンを作成することで、汎用的なスクリプト言語よりも高速化させることができるのです。バイトコードの実行そのものも、Perlでは採用していないテクニック*6を駆使することで高速化を図っています。

HTMLエスケープ専用のバイトコード

これは"How to Create a Highspeed Template Engine in Python"で「エスケープ関数」として言及されていたものの中にはいります。確かに、HTMLエスケープの処理は非常に時間がかかります。これをCで実装するだけでも効果はあり、試しにText::MicroTemplateのエスケープ処理をXSにしたところ、それだけで実行速度が数倍になったという結果も出ています*7。Xslateではほぼすべてのテンプレート変数に対してHTMLエスケープを行うのですが、「エスケープしつつ出力バッファに追記する」という処理が専用のバイトコードになっており、これの効果が少なくありません。

出力バッファの事前割り当て

基本的に、文字列連結を行うときはいかにmalloc()を少なくするかが重要になります。そこで、テンプレートの出力はいつも概ね似たような大きさになるという仮定の元に、複数回レンダリングしたときは前回の出力サイズでmalloc()します。ごく小さなテクニックですが、こういう小さな最適化をいくつか行うことでもベンチマークスコアを稼いでいます。

*1How Xslate works (YAPC::Asia 2010)のp.42からの抜粋+補足です。

*2:Template::ToolkitやText::MicroTemplate

*3:たとえば、HTML::Template::Pro

*4:たとえば、ClearSilver

*5How to Create a Highspeed Template Engine in Python

*6:direct-threaded codeなど

*7:この成果はオリジナルのTMTにフィードバックする予定です。