HamlitというRubyで使うテンプレートエンジンをメンテしてて、ちょっと前に思いついたけどこれまで実装してなかった最適化のアイデアを昨日それに実装したので、それについてちょっと書きたい。

StringTemplate というテンプレートエンジン

amatsuda/string_template というテンプレートエンジンがあって、これは "the fastest template engine for Ruby" であると主張されている。

I think I just invented the fastest template engine for Ruby (Rails). Please enjoy! https://t.co/N056SReLh2 https://t.co/74MdR5DINj
— Akira Matsuda (@a_matsuda) December 28, 2017

もう2年も前の話になりつつあるが、今でもこれは最速だと思う。何故か?

String Interpolation を使った生成コード

「Rubyのテンプレートエンジン」というのは例えばERB, Haml, Slimとかがあるのだけど、これらは .erb, .haml, .slim ファイルを裏側でRubyのコードに変換しevalすることで動作している。

Railsなどの用途ではRubyのコードにコンパイルするのは最初の一回で良いので、それをevalする時の性能が重要なのだけど、StringTemplateでは以下のようなテンプレート hello.string があると、

hello, #{ @world }
hello, #{ @world }
...

以下のようなRubyのコードを生成する。

%Q\0hello, #{ @world }
hello, #{ @world }
...\0

%Q\0 ... \0 というのは、テンプレート内容とコンフリクトしないようデリミタにヌル文字が使われている文字列リテラルで、要するに " ... " と同じで、#{ } のようなString Interpolationが使えるだけの一つの文字列リテラルになっている。

他の生成コードパターン1: String Buffer

この "hello, " と @world を連結しまくる方法はString Interpolationに限らない。これと同様のテンプレートをERBで書くと

hello, <%= @world %>
hello, <%= @world %>
...

で、これは

_erbout = +''; _erbout.<< "hello, ".freeze; _erbout.<<(( @world ).to_s); _erbout.<< "\nhello, ".freeze
; _erbout.<<(( @world ).to_s); _erbout.<< "\nhello, ".freeze
; ...; _erbout

にコンパイルされる。@world の行番号をテンプレートに合わせるために読みづらくなっているが、一つのStringをつくり、そこに << で部分文字列を連結し続けるため、String Bufferと呼ばれている。*1

テンプレート全体をまるごと文字列リテラルにいれて動くシンタックスのテンプレートエンジンはStringTemplateくらいで、普通はString Bufferのようなコードを生成することでテンプレート内での分岐を可能にしたりしている。

他の生成コードパターン2: Array Buffer

StringをBufferとして利用するかわりに、Arrayにいれておいて最後に join するという方法もある。

_erbout = []; _erbout.<< "hello, ".freeze; _erbout.<<(( @world ).to_s); _erbout.<< "\nhello, ".freeze
; _erbout.<<(( @world ).to_s); _erbout.<< "\nhello, ".freeze
; ...; _erbout.join

テンプレートが長くなるとString BufferよりArray Bufferの方が速くなる傾向にあるので、いくつかのHaml実装*2はこのようなコードを生成している。 *3

何故String Interpolationが最速なのか

レンダリング時に @world の値を見て連結していくRubyのコードは主に上記の3パターンがあるが、 @world 部分をHTMLエスケープしない文字列連結*4において、以下の2つの観点によりString Interpolationを使ったコードが最速になると思っている。

バッファのアロケーション

String Bufferだと、最初にバッファを作る際に事前に文字列のサイズを知ることが困難なので、最悪 << を呼ぶ度に文字列のバッファを拡張しないといけないことになる。 Array Bufferだと、join する時の文字列の長さは計算できても、Arrayのバッファ拡張は << を呼ぶ度に走り得るし、Arrayオブジェクトは他の方法では作っていないので、その分無駄になる。

String Interpolationでは、Ruby 2.5から @south37 さんによりバッファのプリアロケーションが実装され、各要素の長さの合計を事前に計算してから文字列用のメモリを確保するようになっており、アロケーションコストが O(1) になる。また、要素数が少ないときは元の実装の方が速いらしく、状況に応じて適切に最適化がスイッチするようになっている。

メソッド呼び出しの数

StringやArrayの << はVMが特化命令を持っているため通常のメソッド呼び出しに比べてオーバーヘッドが軽いが、他の to_s や join は通常のメソッド呼び出し分のオーバーヘッドがかかっている。*5

String Interpolationだと、interpolateされたオブジェクトはVMのchecktype命令でStringかどうかをチェックし、Stringじゃなかった場合のみ to_s を呼ぶので、文字列がinterpolateされている時高速で、また文字列連結はconcatstringsという単一の命令内で完結するのでとにかく余計なメソッド呼び出しが発生せず速い。

もう一つの最速のテンプレートエンジン: Hamlit

StringTemplateが出るよりもさらに2年前、HamlitというHamlの高速な実装を作り、当時最速のテンプレートエンジンだった。

k0kubun.hatenablog.com

しかし、StringTemplateが出てから最近までの間、Hamlitで同等のテンプレートを書いてもArray Bufferのコードを生成するようになっており、StringTemplateの方が速くなってしまっていた。

実際、StringTemplateのリポジトリにあったベンチマークを、StringTemplateの機能相当に近付けてHamlitを参加させたベンチマークでは、Hamlit v2.9.5では*6以下のような結果になっていた。

Calculating -------------------------------------
              string    39.969k i/s -    100.000k times in 2.501936s (25.02μs/i)
              hamlit    34.498k i/s -    100.000k times in 2.898699s (28.99μs/i)

Comparison:
              string:     39969.0 i/s
              hamlit:     34498.2 i/s - 1.16x  slower

HamlはStringTemplateのスーパーセット

StringTemplateで使える #{ } は実はHamlでも完全にvalidなので、.string なテンプレートはシンタックスが衝突しない限り .haml としてもそのまま使うことができる。なので、もしHaml実装が同様に高速なコードが生成できれば、わざわざStringTemplateな用途に別のgemをインストールしなくてもよくなるはずである。ちなみにERBだと <%= %> になるし、Slimだと | を書いたりする必要があるので、それらは互換ではない。

しかも、StringTemplateのREADMEにはこう書いてある:

So this template engine is recommended to use only for performance hotspots. For other templates, you might better use your favorite template engine such as haml, or haml, or haml.

performance hotspotsにもHamlが同様の性能で使えれば、もし #{ } だけじゃなくて分岐とかしたくなった時にすぐできるし、便利なのではなかろうか。

Hamlit v2.10.0 でStringTemplate相当のコード生成を可能にした

なので、以下のPull Requestで、StringTemplate互換のテンプレートな時に単一のString Interpolationのコードが生成されるような最適化を導入した。*7

github.com

これにより、 Hamlit v2.10.0 では StringTemplateと同等の性能が出るようになった。 *8

Calculating -------------------------------------
              string    39.740k i/s -    100.000k times in 2.516339s (25.16μs/i)
              hamlit    39.719k i/s -    100.000k times in 2.517673s (25.18μs/i)

Comparison:
              string:     39740.3 i/s
              hamlit:     39719.2 i/s - 1.00x  slower

Haml実装でString Interpolationコード生成をする難しさ

これは、Array Bufferのコード生成器で単にString Interpolationを生成するように変えれば良い、という程度の簡単な話ではない。そんなことをしたら分岐ができなくなるし。

まず、HamlitではHamlとの高い互換性を実現するためにHamlのパーサーをそのまま使っている。以下のようなテンプレートは、

hello, #{ @world }
hello, #{ @world }
...

次のようなASTにパースされる:

#<struct Haml::Parser::ParseNode
 type=:root,
 line=nil,
 value=nil,
 parent=nil,
 children=
  [#<struct Haml::Parser::ParseNode
    type=:script,
    line=1,
    value={:text=>"\"hello, \#{@world }\"", :escape_html=>false, :preserve=>false, :keyword=>nil},
    parent=#<struct Haml::Parser::ParseNode:...>,
    children=[]>,
   #<struct Haml::Parser::ParseNode
    type=:script,
    line=2,
    value={:text=>"\"hello, \#{@world }\"", :escape_html=>false, :preserve=>false, :keyword=>nil},
    parent=#<struct Haml::Parser::ParseNode:...>,
    children=[]>,
   ...
  ]>

せっかく元のテンプレートではそのままString Interpolationに使えそうな感じになってるのに、入力がわざわざ各行で別の文字列リテラルに分解されている。これはテンプレートエンジンが行番号を維持しながらコード生成をする必要があるため、このような挙動にすることによって後続のコンパイラの実装を楽にしているのだと思う。

しかもこれは任意のRuby スクリプト (:script) として文字列リテラルを抱えているので、これを受け取ったコンパイラはまずRubyのスクリプトをパースして、それが文字列リテラルだった時のみ、連続した文字列リテラルを結合するということが必要になる。

そして上記の通り行番号を維持する必要があるため、コード生成器で改行するための特別な中間表現を文字列リテラル内の改行と交換する必要があったり、またもしStringTemplateと互換でないテンプレートも最適化したいなら、既にトークンがバラバラの中間表現になった世界で、どの改行は文字列リテラル用のものなのかを適切に判別しないといけない。

どうやって単一のString Interpolationにコードを最適化するか

HamlitではTempleというテンプレートエンジンフレームワークを使っていて、先ほどのASTをコンパイルしていくつかのフィルタを通すと*9以下のTemple中間表現になる。

[:multi,
 [:dynamic, "\"hello, \#{@world }\""],
 [:newline],
 [:static, "\n"],
 [:dynamic, "\"hello, \#{@world }\""],
 [:newline],
 [:static, "\n"],
 ...
]

:multi は単に複数ノードの配列、:static はそのままバッファに繋げられる静的な文字列リテラル、:dynamic は to_s して繋げるRuby スクリプト *10、:newline は生成コード上の改行である。 [:static, "\n"] は _buf << "\n" として生成され、文字列リテラル内での実際の改行ではなく \n になるので、生成コードの改行は通常 [:newline] だけで行なわれる。

さて、これを見ると "\n" と "hello, " 部分が分かれているのが無駄だが、これらを結合する最適化はHamlit v2.9 の時点でも入っていた。これはまず StringSplitter というフィルタ*11をかけると、RipperというRuby標準添付のパーサを利用して以下のように :dynamic 内の文字列リテラルを分解でき、

[:multi,
 [:static, "hello, "],
 [:dynamic, "@world "],
 [:newline],
 [:static, "\n"],
 [:static, "hello, "],
 [:dynamic, "@world "],
 [:newline],
 [:static, "\n"],
 ...
]

StaticMerger というフィルタをかけると、連続した :static を結合できる。

[:multi,
 [:static, "hello, "],
 [:dynamic, "@world "],
 [:newline],
 [:static, "\nhello, "],
 [:dynamic, "@world "],
 [:newline],
 [:static, "\nhello, "],
 ...
]

これでHamlのパーサーの困りポイントは解消され、比較的まともな中間表現列になっている。さて、今回Hamlit v2.10.0 で導入した DynamicMerger というフィルタを使うと、これが

[:dynamic, "%Q\u0000hello, \#{@world }\nhello, \#{@world }\nhello, ...\u0000"]

に変換される。:dynamic 内の改行はそのままコードに出力されるので :newline 相当の働きをし、行番号は維持されている。これをコード生成器に渡すわけなので、StringTemplate同等の機能しか持たないコード生成器*12に渡せば、この文字列リテラル一つだけが生成される。めでたしめでたし。

DynamicMerger の中身がどうなっているかというと、:multi の要素の部分列が以下の条件を全て満たす時に、その範囲にのみ上記のような変換を行なうようになっている。

:static, :dynamic がそれぞれ1つ以上含まれる
:static の \n の数と :newline の数が一致する
:dynamic のコード内に改行がない

ちなみに、 StringSplitter や DynamicMerger のように、to_s しないString Interpolationと :static, :dynamic を相互変換するのは String#to_s がモンキーパッチされてると等価ではなくなるんだけど、まあこれで文句を言ってくる人がいたらコンパイル時点でそれが再定義されてるかどうかチェックして必ず to_s を呼ぶようにすればいいかなと思っている。*13

String InterpolationとArray Bufferのハイブリッドなコードの性能

DynamicMerger で遅くなるケースはほとんどないと思っていたのだけど、「:static, :dynamic がそれぞれ1つ以上含まれる」という条件は少しチューニングの余地があるとリリース後に気がついた。*14

コード生成器にArray Bufferを使う時、例えば元々以下のようなコードを生成していたのが、

buf = []
buf << 'hello, '
buf << @world.to_s
buf.join

以下のように部分的にString Interpolationで結合すると微妙に遅くなってしまう。*15

buf = []
buf << "hello, #{@world}"
buf.join

じゃあArray Bufferを使っている時は DynamicMerger を使うべきではないかというとそんなことはなく、例えば :dynamic が2つある以下のものは元のコードより速くなった。*16

# before
buf = []
buf << @world.to_s
buf << 'hello, '
buf << @world.to_s
buf.join

# after
buf = []
buf << "#{@world}hello, #{@world}"
buf.join

なので、次のバージョンとかで、:dynamic を2つ以上要求するなど DynamicMerger の適用条件を少し厳しくしようかなと思っている。

まとめ

Hamlitを使ってない人、速度に妥協していませんか。 GitLabやMastodonもHamlitを利用しています。

*1:出展: https://github.com/judofyr/temple/blob/master/lib/temple/generators/string_buffer.rb

*2:faml.gem と hamlit.gem のこと

*3:余談だが、ERBでもArray Bufferを使おうとした https://github.com/ruby/ruby/commit/ec7a964dca57821d2d7a36f168c2355a46a76ca2 ことがあるが、ERBの内部実装に強結合なライブラリがいくつか発見されrevertされた https://github.com/ruby/ruby/commit/0516a3378f03e8563350b8c4fe94ac3f9e9c9f75

*4:StringTemplate はinterpolateされた値のHTMLエスケープをサポートしていない

*5:Array Bufferでは一見 to_s を飛ばしても動きそうに見えるが、Array#join は to_str が存在する時はそちらを呼んでしまうので、互換性上明示的に to_s を呼ぶ必要がある

*6:Ruby 2.6.4, ActionView 6.0.0, Erubi 1.8.0, StringTemplate 0.2.1

*7:厳密には、Array Bufferの生成器を使っている時に to_s の呼び出しと _buf への代入が余計に生成されていて、それをなくす方法 https://github.com/k0kubun/hamlit/pull/147 も考えたが、そもコストはほぼ無だと思うのでそのままにした

*8:ベンチマークコードと、Hamlitのバージョン以外の条件はさっきと同じ

*9:わかりやすさのために、実際と少し違う順序でフィルタを通した結果を書いているが、やっていることは同じ

*10:ちなみに、記事内でテンプレートの分岐に言及しているがそれは :code で実現されており、:dynamic を文字列のinterpolationとすることは問題ない

*11:これは僕が発明した https://github.com/judofyr/temple/pull/96

*12:これは例えばHTTP Streamingサポートのための ActionView::OutputBuffer や、html_safe? 状態で結果を返すための ActiveSupport::SafeBuffer をラップしないコード生成器、という意味。これらはStringTemplateではサポートされていない

*13:つまり、速度の都合eval時にはチェックしたくないので、コンパイルしてから生成コードをevalするまでの間に初めて再定義されるケースは諦めたいという話

*14:というか、当然リリース前に考慮してマイクロベンチを書いてチェックしてたが、そのコードに少しミスがあって正しくチェックできてなかったのだった

*15:https://gist.github.com/k0kubun/4329c599685f467b212b565bb561743b

*16:https://gist.github.com/k0kubun/9c2c705be681c98984be97ad6a5b96bd