Rubyで最速のテンプレートエンジンを作る方法

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

github.com

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

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

もう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_sjoin は通常のメソッド呼び出し分のオーバーヘッドがかかっている。*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 のコード内に改行がない

ちなみに、 StringSplitterDynamicMerger のように、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を使ってない人、速度に妥協していませんか。 GitLabMastodonも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

セルフホストで学ぶJVM入門

RubyJIT開発でやろうと思ってることが大体 @_ko1 さんの作業待ちでブロックしていて暇なので何かを書こうと思い、JVMを書くことにした。 まだその辺のアプリを気軽に動かせるレベルでは全然ないが、別に秘密裏に開発する必要もないと思ったので公開した。

github.com

これの紹介と、現時点で学べたことをこの記事に記録しておく。

何故JVMなのか

仕事でJVM言語を使っている

僕が所属しているTreasure Dataでは、大雑把に言うと本番サーバーのサービスは大体Ruby, Java, Scala, Kotlinで書かれている*1ので、既にRubyVMはある程度わかる*2ことを考えると、JVMさえ理解してしまえば社内の主要な言語評価系を抑えたことになり、運用面で活躍の機会が増える気がしている。

また、自分が最近一番書いているのはKotlinなのだが、JVMで動かしていることに由来した問題が垣間見えることがあるので、JVMに詳しいとその背景を理解したり問題に対処したりするのに役に立つと思っている。

OpenJDKの良いところを今後CRubyで真似したい

Ruby 2.6で導入されたJust-In-Timeコンパイラの開発をしているので、なんか遅くて困った、という時に他の処理系が同様の問題をどう解決しているか参考にしたいことがある。

その上で、Rubyと同じくスタックマシンであるHotSpot VMは、既に長く運用され洗練されたJITを持っているのですごく参考になりそうだし、CRubyと性能を競うJRubyやTruffleRubyもJVMで動くので、JVMの挙動が解析できると他のRuby処理系の挙動理解にも役に立つ感じがする。

何故Javaで実装したのか

C言語コンパイラをCで書いてセルフホストしようとして結局途中でやめた、ということがあり、今回こそセルフホストにこぎつけようと思いJVM言語で書くことにした。

JVM言語の中でもJavaなのは、仕事で使うのでJavaのコードを割と読む機会があるが、書いてるのは大体Kotlinなので、Javaを書く方の経験の足しにしておこうと思ったため。*3

JJVMは今どこまで実装してあるか

testディレクトリに置いてある奴は動くが、VM命令と一対一対応みたいなものしか置いてないのであまり参考にならなそう。テストを書くのが面倒くさいので、セルフホストを主な結合テストとして利用しようとしている。

それから、Systemクラスの初期化に10秒くらいかかるので起動がめちゃくちゃ遅いというのと、割と自明に実装できるところもテストを用意していないうちはRuntimeExceptionで落としてわざと動かさないでいる場所が結構ある (nop命令すらコメントアウトしている) ので、読んでいる皆さんが過去に書いたアプリケーションを動かしてみる、とかはおすすめできない状態にある。

BytecodeInterpreter.javaを眺めたり、-Xjjvmtraceというオプションの出力を眺めると簡単に雰囲気がわかると思う。

実装スコープ

以下のものを実装している:

Javaを使うと本来クラスファイルパーサーはimportするだけでも使えるが、Javaバイトコードそのものに多少興味があったので自前で書いている。クラスファイルパーサーを書く時の雰囲気は他に最近JVMを趣味で書いてる人たちが 書い てた ので省略する。

どこでインチキをしているか

クラスファイルパーサーでは異常な真面目さを発揮しているが、それ以外の場所は手抜き感に溢れている。

  • GC不要、JITはサボリ
  • ホストのrt.jarをそのまま利用
  • バグったらとりあえずスタブ
  • publicなネイティブメソッドはホストのを呼ぶだけ

GCがある言語でインタプリタを実装すると、一般に、GCはホスト言語のものをそのまま使えることになる。最近JITばかり書いていたのでJITはお休み。

上述した "ホストJVMのbootclasspathの利用" により、ホストのランタイムライブラリに依存している*4

また、とりあえず達成感を得るためにセルフホストまで行きたいが、何か面倒っぽい細かいところの呼び出しをスタブして逃げたりしている。が、 System.out の初期化とか PrintStream.print() の実装は可能な限り下のレイヤーまで本来の挙動を再現するよう実装してあって、Hello Worldにも結構な労力をかけている。

一番インチキっぽいのはpublicなネイティブメソッドをJavaで実装するパートで、例えば System.arraycopy の実装はJavaSystem.arraycopy を呼ぶだけなのである。セルフホストする都合Javaで書かなければならないことを考えると保守性も性能も共に最高の実装のはずだが、勉強にはならない。どうか NativeMethod.java ファイルは探さないでほしい。

セルフホストの進捗

java コマンド相当のCLI-help が動くようになった。…以上である。

System.out.println() を完全にスタブした状態で -help でのセルフ起動・終了が達成できた時も結構な達成感があったものの、それ以降はセルフホストらしい進捗はまだない。というか、肝心のインタプリタ部分の実行に至っていないので普通はセルフホストとは呼ばない状態にあると思う。

その次のマイルストーンとして、上述した通り System.out.println() をなるべくスタブを避けて実装する、というのをがんばった*5。これでも結構動いててがんばっている感じがするが、次はやはり評価系をセルフホストできる状態にしたい。

これまでの開発でJVMについて学べたこと

(このセクションは、Javaのモヒカンの方々は多分皆知ってる内容なので読み飛ばして欲しい)

Java バイトコードの読み方

公式ドキュメントのThe class File FormatThe Java Virtual Machine Instruction Setを読めばわかる話なので、印象に残ったことだけ触れておく。

クラスファイルパーサーを書くと、descriptorと呼ばれる ([Ljava/lang/String;)V みたいな初見では奇妙なフォーマットが自然に理解できるようになる。これはクラスファイルに対し javap -s すると出てくるが、普通に生活してても、Kotlinを書いてる時に same JVM signature というエラーとかでdescriptorにお目にかかることはある。

あと、深淵な理由により.javaが得られず.classだけが渡された時に、 javap -v で挙動を解析したりバイナリエディタで勝手にハックしたりできて便利そうな感じがする。まあIDEAのJava Decompilerとかあれば、無理してjavapの出力を読まなくてもいいこともあるかもしれないけど。

Kotlinコンパイラが生成するクラスファイルも読んで違いを見てみたいと思っているが、それは未着手。

標準のクラスのソースやjarの場所

OpenJDKの公式リポジトリMercurialらしいが、僕はGitしか使い方がわからない*6ので、 https://github.com/openjdk/jdk のミラーをcloneして使っている。仕事では openjdk-8-jre 上でKotlinを動かしていることもあり、少し古いがJDK 8系のタグ(jdk8-b120 とか)をチェックアウトして読んでいる。

主要なクラスは大体 jdk/src/share/classes に入っているのでそこを探すと様々なクラスの実装が読める。まあ openjdk/jdk にある全ファイルをまるごと unite.vim でフィルタして探してるので僕は jdk/src/share/classes とかは記憶してないけど。

また、JDKを動かしている時などに使われる実際のクラスファイルは、JDK 8系だとJDKディレクトリ内の jre/lib/rt.jarjar -xvf で展開すると出現する。Java 8を使っているのでJJVMの実装は System.getProperty("sun.boot.class.path") してこれを探しにいっているが、より新しいバージョンではこれらは違うパス / プロパティ名になっているらしい。

クラスやフィールドがどのように初期化されるか

The Structure of the Java Virtual Machineを読むと、JVMの型にはPrimitive TypeとReference Typeがあり、前者のデフォルト値は0、後者はnullになることが書かれている。

クラスのstaticなfieldの初期値は、何も指定されていない場合は最初から上記のルールの通りの値になる。そうでない場合、内部的には、初期化するクラスの <clinit> *7 を呼び出して putstatic 命令で初期化されている。初期値が定数な場合はクラスファイルのfield部分にConstantValueというattributeがついていてそこにconstant poolへのindexがあり静的に初期値が解析できるが、動的な初期値だと <clinit> のCode以外ではクラスファイルレベルを見ても初期値がわからないように見える。

OpenJDKには Threads::create_vm という名前からしVMの初期化に使いそうな関数があり、いくつかのクラスはそこで既に initialize_class されるが、Systemクラスに関しては更に call_initializeSystemClass から System.initializeSystemClass() というメソッドが呼ばれていて、皆さんがよく使う System.out 等はそこで初期化されている。

オブジェクトの生成はバイトコードでは new 命令の後 invokespecial 命令で <init> (コンストラクタの内部的な名前) というメソッドを呼び出して行なわれるが、new 命令のドキュメントには上記の通りのデフォルト値にインスタンス変数を初期化することが明示されているので、コンストラクタに入った時点でPrimitive Typeのインスタンス変数は0になっていることが信頼できる、といったことがわかる。

JVMRuby VMと違うところ

Rubyだとパーサやコンパイラみたいなフロントエンドが評価系と同居している、みたいな当たり前の話は省略する。

バイトコード省サイズ化の努力が見られる

.jarや.classで配布することを見越してか、単にJVMの内部実装の都合に合わせたのかはわからないが、クラスファイル内で出現するあらゆる名前はcontant poolで必ず共有されている。*8

VM命令やオペランドが1ワード使うRubyとは異なり、Javaバイトコードでは名前の通り命令のopcodeやオペランドの基本サイズは1バイトになっている。オペランドがconstant poolの参照の時はインデックスの指定に必要なバイト数に応じて別のopcodeが使われていたり(ldc, ldc_w)、頻出オペランドがopcodeにエンコードされてたりする(iconst_0, iconst_1, ...)。

頻出オペランドで命令が特殊化されるのはRubyにもあるが、それは命令の実装におけるオペランドのインライン化(による最適化)が目的なので、それも兼ねているかもしれない。

Primitive Typeごとに命令が細分化され、ネイティブメソッドも少ない

Ruby VMだとPrimitiveっぽいクラスの処理のほとんどはネイティブなメソッドかその最適化用のVM命令でCで記述されているが、静的に型が定まらないことがほとんどなRubyの特性上、その最適化命令の実装はあるクラスに特化したものにしておく、ということが難しい。

なので Integer#+ 用の命令があるわけではなく、その最適化命令はどんな #+ でも動く作りになっていて、例えば Array#+ の呼び出しは Integer, Float, String など他の様々な型のチェックの後 Array かどうかがチェックされやっと動く、という作りになっている。

JVMの命令でその命令に相当するのは iadd, ladd, fadd, dadd で、ちゃんとPrimitive Typeごとにバラバラになっている。配列の操作はそれぞれまた別の命令があるし、 String というのは所詮 char[] value というfieldを持つ普通のオブジェクトに過ぎないので、 iadd および配列操作の命令まで落とすことができる。

今ではどちらもJITを持つ処理系だが、JITをする上でどちらが最適化に都合がいいかというと、圧倒的にJVMの状態の方が良い。そもそも1つの命令が様々なクラスに対応してて分岐が多かったりすると、命令単位で色々こねくりまわしてミクロな最適化をするのが難しくなる。ネイティブなメソッドは、インライン化してVM命令と混ぜて最適化する、ということが難しい *9 ので、全てがVM命令の組合せで定義され数値演算や配列操作の小さな命令たちに落ちるのが理想である。

ところでRubyでも Integer#+ 専用の命令を使うようにすることはできないことはなくて、「Integer が来たら Integer#+、それ以外なら命令を別のに書き換えつつフォールバック」というような命令を含む全命令セットのリプレース提案をした人がいた。これで命令内の型分岐は1つに絞れるが、全命令リプレースはリスクが高いので現状のVMにその特化命令アイデアだけ入れるパッチを書いてみたことがあるが、ベンチマークでの結果があまりよくならずまだ入れていない。

所感

手を動かす時間が長すぎてOpenJDKの実装を読む時間がそれほど取れてないんだけど、これで割と読む準備ができてきた気がするので、気になっていたところを読むのをそろそろ進めていきたい。

*1:コンソールとかは例えばJavaScriptで書かれているし、TDで使われている言語がこれだけという主張ではない。若干本番から離れたところではPythonが使われているが、まあ雑に捉えると大体Rubyと同じと思って生活している。

*2:単にRubyと書く時はCRubyのことを意図している。JRubyを使っている箇所もあったが、社内のJRubyコミッターの人数よりCRubyコミッターの人数の方が多いので…というのは冗談だけど今は大体CRubyで動いている。

*3:同様の目的でJavaだけでAtCoder水色にしたり、趣味でも現職でもJavaで一からサービスを書いたりしてはいるが、長くメンテしているものが少ない

*4:もちろんJJVMの方で評価しているのでこれはそこまでインチキではないが、例えばAOTコンパイルで動かそうとすると壊れるリスクがある

*5:というかそれをがんばったせいで、1秒もかかっていなかった初期化が10秒になってしまった。

*6:念のため補足すると、Rubyの公式リポジトリSubversion→Git移行に僕が結構貢献していた、という前回の記事にかけたジョーク

*7:javap -v だと static {} になってしまうのがやや不満。<init> も同様

*8:RubyのInstruction Sequenceをシリアライズした時のフォーマットがどうなってるか知らないというか、Rubyではそれはそれほど重要ではなくあまり興味もないので、この部分に関して公平な比較は特に書いてなくて申し訳ない、が言及したかった

*9:GraalのSulongではそういうことをやれると記憶してるけど、同じことを一人で実装・メンテしたいかというと、やりたくない…

令和時代のRubyコア開発

Ruby Core Development 2019というタイトルでRubyKaigiのCFPにプロポーザルを書いたのだが、 もう一つ書いた方の話が採択されたのでその話はしなかった。

さて、今日はRubyコア*1の開発がSubversionからGitに移った節目でもあったので、そっちのトークで言いたかったことの一部を記事にしておこうと思う。

Subversion → Git 移行 [Misc #14632]

去年くらいから @hsbt さんが cgit というGitフロントエンドを使ってGitリポジトリの準備を始め Misc #14632、ついに今日正式にcgitの方がupstreamになった。平成の時代でSubversionでのtrunkのRubyコア開発は幕を閉じた。

この辺を進めているのは主に @hsbt さんな中、僕がこれを偉そうに書いたり今回のRubyKaigiで壇上でアナウンスをやったりしていたのは、必要な作業量が多そうで半年くらい前から僕も移行作業を手伝っていて、割と多くのパートで貢献していたため。

そもそも何故Gitにするのか

他の場所でのSubversionの用途は知らないが、Rubyコミッタの間では、大体以下の話が散見された。

  • 最近は多くのコミッタがgit-svnを使っているが、git-svnを使うのが微妙に面倒くさい
    • そもそも一からgit-svnでcheckoutするのに無限の時間がかかるので、そのsnapshotのtarを落としてくるのが地味に面倒
    • rXXXXX なSubversionのリビジョンをgit-svnのshaに変換するのが面倒くさい
    • Rubyコアの開発以外でgit-svnを使わないので、git svnの使い方をこれのためだけに記憶していないといけないし、たまに忘れる
    • MinGWではgit-svnが破滅的に壊れているので使えず、そこでだけsvnの方を使う必要がある
  • Subversionだとコミッタ以外のパッチをマージする時にauthor情報がコミットメッセージにしか残らない

GitよりSubversionの方が優れている点も当然あるが、Git化したいという話は作者のまつもとさんが時おり言っており、 MatzがGoと言えばGoなのである。

何故GitHubではなくcgitなのか

コミットhookが svn.ruby-lang.org のサーバー上で動くことを多少前提にしているのでいきなりGitHubに持っていくと少し大変という話もあるが、ブロッカーなのは以上の一点しかないという理解をしている。

今のところ彼はメンテナをやめる意向をたまにRedmineに書いているがおそらくまだ公式にそうなったという感じではない。僕らがGitHubでマージボタンを押せず、自分たちでgitサーバーを運用するコストに見合うくらい彼の貢献や活動力は貴重なので、すぐにGitHubに移行しよう、とはならない気がする。特に、auto-fiberと呼ばれている目玉機能は彼が作ったがまだコミットされていないのである。

Git化に必要だった作業達

最初の2つを僕がやった。半年前にガッと進めて、かつ今回のRubyKaigi中もガッとやってやっと終わった程度には、作業量があった。

懸念した点

  • リビジョンがインクリメンタルな数字ではなくなる
    • chat botのbisectとかCIがこれに依存していたりするので移行が必要になる。が、git bisect通りの挙動をすればまあいいはず
    • RUBY_REVISION の型がIntegerがStringに変わってしまう。これはどうしようもない。すみません。
  • 我々のcgitの運用方法が共有ユーザーでsshしてコミット、なので署名しない限りあるコミットを誰がコミットしたのか信頼できない
    • authorized_keys で鍵ごとの環境変数をセットする機能があり、それでユーザーを判定してコミットのCommitterをverifyする、という機能を @mame さんが作った。
  • GitHubのマージボタンをどうにか使えるように双方向同期するか?
    • GitHubへの移行を諦めるならいつかやりたい気はする。実装が面倒そうなのでいつか。
  • trunk を master に変えるか?
    • Gitでtrunkブランチを使うのは不自然で間違えるのでやめたい。が、CIとかが決めうちしてそうなので、一度に壊しまくらないようそれの移行はタイミングを分ける
    • @yugui さんが git symbolic-ref refs/remotes/origin/master refs/remotes/origin/trunk というのを共有していた
  • 古いバージョンのブランチをGit化するとそれ自体が非互換になりそう
    • なので 2.6 までのブランチはSubversionのままやることになった
  • Subversion用のViewVCでクローラーがサーバーに負荷をかけており、同居しているcgitがたまに使えなくなる
    • ViewVCは今日落とされた。あと、git.ruby-lang.org は信頼性が高い構成ではないので、コミッター以外はcgitのかわりにGitHubを使って欲しいというポリシーにしている。

Git化してよかったこと

  • git-svnを使わずにgitで普通〜に開発できる。
    • git svn dcommitするのに比べ、git pushが速い。cgitが軽量なのと、git.ruby-lang.org のサーバーが日本にあるので日本からだと特に速い。
    • 全体のgit cloneは1分で終わるし、--depth=1だと数秒で開発が始められる。
    • (僕は) svnコマンドやgit svnコマンドの使い方を忘れてよくなった。
  • コミットすると https://github.com/ruby/ruby/graphs/contributors に名前が残るのでcontributorのモチベーションが上がる?
    • 僕はコミッターになる前の機能のgit blameが自分じゃないのはちょっと寂しいなと思っていた
    • まあでも実際そこに名前が残らないから何もしない、という人はどの道コミットしないような気もする :p
  • 将来GitHub化するなりGitHubからも同期するなりでPull Requestのマージボタンが押せる世界が近付いた
    • 今は多くのコミッター(僕も含む)はPull Requestなしでいきなりtrunkに突っ込んで何かあったらrevertするという原始的な開発手法を採用しているが、trunkのCIが破滅しがちで辛いので、文化を変えた方がよさそう

C99化 [Misc #15347]

古いVisual StudioSolarisで動かないことに懸念があり、Rubyコアは去年まで長らくの間C89/C90で開発されていた。 どういうことかというと、 // コメントが書けないとか、boolが使えないとか、関数途中で変数を宣言できないとか、arrayやstructの便利な初期化シンタックスが使えないとか、そういう感じになる。

2019年にこれはしんどい。C99というのは1999年だからC99なんだけど、もう20年たったのだ。もう平成は終わりなのだ。

記事が長くなってきて疲れたので適当にまとめるが、Ruby 2.7からplatformの要求バージョンを上げるなどで対応した。また、C99を全てはサポートしていないplatformがあるが、それら用に重点的にCIを回すことで対策をするなどした。詳細に興味がある人は https://github.com/ruby/ruby/pull/2064 をどうぞ。このプロジェクトは主に僕が主導していた。

インデントのハードタブ廃止 [Bug #14246]

去年の途中まで、Rubyコアはインデントが4つまではスペース、8つに達するとハードタブ、その次の4つはスペース、といった方法でインデントされていた。 僕のエディタ(Vim)で普通にRubyコアのリポジトリを開くとデフォルトではインデントがめちゃくちゃになりがちで、vim-cruby をいれ、cloneする度に .vimrc.local を書きそれを有効にする、といった苦労があった。また、GCCやClangがVMのコードをpreprocessしてJIT用のヘッダを生成する時にタブだけ1スペに変換されるという挙動があり、gdbデバッグするのがものすごく辛い、という実害があった。

Rubyの二大コミッタのうち、 @nobu さんが上記の方法でコミットし、 @akr さんが常にスペースだけでコードを書いていてインデント方法陣取り合戦みたいになっていて、@shyouhei さんがどっちかにしてくれという話をしたのが Bug #14246。結果全部スペースに倒すことになった。

今はいじった行や新しい行にハードタブが含まれているとbotが勝手にspaceに変換してくるというフックが入っており、revertする時とかに鬱陶しいという話があるが、一気に置換すると、git blameの歴史が一層積まれる他にbackportのconflictが辛そう、という話があり妥協でそのままになっている。まあ、なんか困ったらファイルごとに一括置換していくなりしたらいいと思う。

僕は他に misc/ruby-style.el の更新とかをやったりした。

MinGW, JIT 向けCIの追加

RubyJITは最初のWindows platformとしてMinGWに対応したため、MinGWのCIが欲しくなった。 AppVeyorでMinGWが動かせるので、AppVeyorにこれを追加した。これは確か僕が最初にやって @nobu さんが修正した感じだった気がする。

また、JITは普通は非同期にコンパイルを行なうが、JITがリクエストされた瞬間同期的に必ずメソッドをコンパイルするようにすると、結構シビアなJITのテストができる。なので、これをWerckerといういままで使ってなかったCIで実行することによって、JITはテストされている。これのおかげでJIT向けにがんばってテストを書かなくても、既存のテスト資産全てがJITの開発に利用できている。すごい楽!!! これは僕用なので一人でメンテしている。

Werckerはコミットごとに1回なんだけど、ランダムで発生する失敗を見つけまくるため、 @ko1 さんが http://ci.rvm.jp/ というCIをメンテしていて、そこでJITのCIが24時間ぶん回っていて、これが2.6のバグ減らしにかなり貢献していたりする。

bundler, bundled-gems 向けCIの追加

@hsbt さんがAzure Pipelineに新たなCIを設定した。僕もちょっと手伝った。 これは標準ライブラリであるがRubyコアに直接存在していないbundled-gemsや、 存在はするが時間がかかるのでCIに参加させにくいbundlerのCIを、並列度が高く新設のAzure Pipelinesで実行しようというもの。

Azure Pipelinesが新しすぎて通知周りがいろいろいけてないとか、単純にbundled-gemsのCIが不安定などでtrunk限定で実行している。 Ruby trunkでbundlerやbundled-gemsが動かなかった時にすぐ気付けて大変便利。 最近 @nobu さんがおもむろに加えた変更でbundlerのテストがコケたので僕がbundlerにパッチを送って直した、ということがあった。

まとめ

Rubyの開発はとても快適になったので今すぐ https://github.com/ruby/ruby にPull Requestしよう!!! *3

*1:この記事ではRuby言語の参照実装であるインタプリタ、つまりMRI, CRubyのことをRubyコアと表記している。これはruby-coreというメーリングリストの名前から取っている。

*2:Unicornやgit-svnの作者。GVLやTimer threadの他低レイヤーの難しい奴をメンテしていた。Webrickもメンテナだった。

*3:ちなみにPull RequestはGit化もGitHub移行も何も関係なく受けつけているが、Pull Requestを送る側が何が快適になっているかは記事に書いたつもり

2018年にやったこと

ハイライト

  • 所属しているTreasure DataがArmに買収され、給料が増えた
  • ジョブタイトルがSenior Software Engineerになった
  • Ruby 2.6のJITコンパイラを開発し、Ruby Prize 2018をいただいた

おかげ様で経済的に大分余裕ができ、結婚式や新婚旅行、奨学金繰り上げ返済などを経たものの、前年比で結構資産が増えた。

発表

JITの話を4回、JITに関係ない発表を2回やり、あとRuby Prize受賞スピーチがあり計7回登壇した。そのうち海外での登壇は2回。

RubyConf, RubyKaigi, RubyElixirConf Taiwan, TD Tech Talk: JITの話

2年くらいずっとこれに取り組んでいるのもあり、過去にJITの話を7回やってて、来年も既に2つJITで話す予定が入っている。自分自身が飽きないよう、可能な限り毎回スライドを新作にしたり、過去に話してないネタを話すようにしているが、そろそろ聞く側が飽きてる気がするので別のネタを考えたい…。しかし「JITRailsをX倍速くしたぞ!!」と言える日が来たら、是非一度壇上でやりたいと思っている。

年の始めにオンライン英会話をやった後、会社で英語話者ばかりのチームに入ったのもあり、5月にRubyElixirConfで話した時より11月にRubyConfで話した時の方が英語が改善したと思えたのはよかった。2年前に初めてRubyConfで話した時はほとんど資料読んでるだけだったし、成長した感じがする。

speakerdeck.com

Ruby Association Grant: Rubyベンチマーク環境の話

あまり知られていないと思うけど、今年Rubyベンチマーク環境は一新された。具体的にはruby/rubyリポジトリbenchmarkディレクトリは去年から今年にかけて私が開発した benchmark_driver.gem というベンチマークツールで実行されるものに移行され、既存のRubyBenchといったシステムもこれをベースに動くようになった。

何が嬉しいのかは資料に書いてある通りだけど、そもそもベンチマーク環境の整備というのは言語処理系の最適化を考えるのに比べると(私にとっては)あまり面白みがないのでお金でも貰わないとやらないと思うんだけど、その割にはとても重要な話で、Rubyアソシエーション様や協賛企業様のおかげで今回私が50万円をいただいてこれを完遂できたのはとても良かったと思う。

speakerdeck.com

Rails Developers Meetup 2018: マイクロサービス化の話

2017年11月〜2018年2月くらいにかけてやっていた仕事の話。コントローラと密結合しているモデルの実装がRailsアプリとは別のリポジトリYAMLとして管理されていて、かつそのYAMLのメンテをするチームが異なることから、そのYAMLだけAPIで動的にリリースされているという状況があった。

あるモデルに変更を加える場合、それに対応するコントローラの実装も同時に変えてリリースすれば少なくとも同じプロセス内では整合性が取れて壊れにくいのだけど、それらが独立してリリースされている上、そのYAMLに後方非互換な変更が加えられることが多く、その全てが障害に繋がっていた。「モデルだけ切り離すんじゃなくて、APIの実装として独立させた方が疎結合になって安全なんじゃない?」という発想で生まれたプロジェクト。

サービスが分散するとそれはそれでまた新たな問題を解決しないといけなくなるのだけど、上記の問題は解決したし、去年の状態に比べるとかなりマシな状態になっていると思っている。

speakerdeck.com

仕事

2017年は主にRailsアプリケーションの開発をしていたが、2018年はSREチームに移りレガシーなインフラの改善を進めていた。具体的には、以下のようなことをやっていた:

  • 障害のあったインスタンスの自動ローテーション、負荷の高いサービスのAutoScaling有効化
  • スケールアウト時のインスタンスの起動時間短縮や安定化のためのパッケージング、Docker化
  • 乱立していたデプロイ基盤の統一化
  • 開発やテスト、本番用のクラスタをオンデマンドに作れるマルチクラウドな基盤の整備

僕がチームに入る前Rubyを書ける人よりPythonを書ける人の方が多かったのと、当時RubyがLambdaでサポートされていなかったのもあり、AWS Lambdaに乗せるPythonのコードを書く仕事が多かった。

弊社はSREチームも割と最近まで存在せず、創業時ごろに整備されたインフラを少数の人が片手間でメンテしつつほとんどの人はプロダクトの開発に集中してるという雰囲気だった。これはある程度の期間うまくいくけれど、組織やビジネスが大きくなると少しの負債が大きな障害や開発速度の鈍化に繋がるので、このくらいの規模・タイミングで基盤の改善に投資するのはビジネス上も効果が高いだろう、と思いながら仕事をしていた。

僕は長期的にはSREというよりSWE(ソフトウェアエンジニア)でやっていくつもりなのだけど、社内でもかなりトラフィックが多めなサービス達の負債を返済するべく足を突っ込んできた結果、色々ご迷惑もおかけしてしまったが、オペレーション上色々経験させていただけたのは良かったと思う。

なお2019年の頭からバックエンドチームに移ることになっていて、主にJavaミドルウェアや分散システムを書く感じになると期待している。最近入った人たちの間ではKotlinが流行っている様子。

執筆

初めて執筆っぽい活動を達成した。WEB+DB PRESSの特集記事で、Ruby 2.5における処理系自体の最適化の話と、Rubyのコードの最適化の話を書かさせていただいた。

8ページだけでもものすごい労力がかかったので、今後もし本を出したくなった時の参考になった。

ホッテントリ

意識が高くなって英語のブログを書くようになった反動で日本語の記事は減った。スライドも含め、ブクマがついてたのはこのへん。

タイトル
1. SQLで羃等にDBスキーマ管理ができるツール「sqldef」を作った - k0kubun's blog
2. 個人で運用するKubernetesクラスタ - k0kubun's blog
3. リモートでアメリカの大学院のCSの授業を取ってみた話 - k0kubun's blog
4. Ruby 2.6にJITコンパイラをマージしました - k0kubun's blog
5. 安全かつ高速に進めるマイクロサービス化 / railsdm2018 - Speaker Deck
6. RubyのJITに生成コードのメモリ局所性対策を入れた話 - k0kubun's blog
7. The Method JIT Compiler - Speaker Deck

英語で書いた奴はこういう感じ

タイトル claps
1. The method JIT compiler for Ruby 2.6 – k0kubun – Medium 944
2. Ruby 2.6 JIT - Progress and Future – k0kubun – Medium 460
3. Benchmark Driver Designed for Ruby 3x3 – k0kubun – Medium 195

最初の奴は英語版と日本語版両方書いたけど、これは本当に大変だったので、両方の言語で書くというのはもうやらないと思う。適当に棲み分けてやっていこうと思う。

OSS活動

GitHubで結構芝が生えてたけど、そのうちprivateなコミット(仕事)が5000くらいで、publicなコミットは2500くらいだった。

今年開発していたOSS

Star リポジトリ
★349 k0kubun/sqldef
★70 benchmark-driver/benchmark-driver

新作がsqldefだけで寂しい感じ。というか、これも「このままでは今年は新作無しになってしまう!」みたいな気持ちがあって出した奴でもある。benchmark-driverもほとんど今年に完成させたようなものなのでいれておいた。

Contribution

Rubyに636コミットしていて、何人かいるフルタイムコミッターよりコミット数が多かった。JITの開発に加え、MinGWJIT用のCIを新たに加えたり、CIを安定化させたり、ベンチマーク環境を刷新したり、といった変更をしていた。

2019年は

JITRailsアプリが高速化できるようにしたい。そのために、JITがある他の処理系の実装を読んだりいじったりしてみようと思っている。それが落ちついたら、今知らない技術で何か新しいものを作るのをまたやっていきたい。

2019年もどうぞよろしくお願いします。

リモートでアメリカの大学院のCSの授業を取ってみた話

Armの福利厚生プログラム FlexPot

私が所属しているトレジャーデータは今年Armに買収され、福利厚生周りがArmのものに刷新された。

その中にFlexPotというものがあり、自己啓発にお金をつかってその領収書を会社に出すと、1年間の合計で上限XX万円まで会社が負担してくれるというもの。具体的な額の公開情報が見当らなかった*1のでふせておくが、割とがんばって使わないと損だなと感じる程度にはもらえる。

何に使うか考えたところ、私は主に家庭と自分の経済的な理由で大学院に行かず働き始めたものの、だんだん会社に給与的な意味で認めてもらえるようになり今は経済的に余裕ができたので、FlexPotも活用しつつちょっと大学院の授業受けてみようかなという気持ちになった。

スタンフォードの Non Degree Option

アメリカに移住を考えている都合、日本ではなくアメリカの大学院に行った方がアメリカでビザを取るのが有利になるためアメリカの大学院の授業を取ってみようかと思ったが、あんまりアメリカの大学のことを知らないので、Rui Ueyamaさんがブログに書いていて面白そうだなと思ったスタンフォードの授業を取ってみることにした。リモートで単位が取れるからというのもある。

卒業できるレベルまで単位を取るのに必要な授業料が高いので、働きながら自分が勉強もこなせるのかとりあえず試しに1つだけ受けてみたかったというのと、そもそも私の学部時代の成績は微妙*2なので、一度履修生として授業を取って内部で良い成績を取るなどしないと、卒業できるコースで出願しても落とされるのではないかという懸念もあり、卒業できないものの後で単位をtransferすることが可能なNon Degree Optionで出願することにした。

出願

Webでポチポチした後、過去に卒業した大学から英語の成績証明書をスタンフォードに郵送すると出願できる。郵送は時間がかかるので、スキャンしてpdfにしてメールで送ると早めにプロセスが進む。ちなみに国際便の郵送をした方は失敗したのか数週間後に返送されてたので、少なくともNon Degree Optionではコピーだけで通ってる気がする。

あと、パスポートのコピーも送らないといけないのだけど、それに全く気付いておらず期限の数時間前くらいに "Please submit ASAP" というメールが来ていて大変だった記憶がある。

授業料

実は上記に加えて、最初に取る単位の授業料を払ってやっと申請が完了になる。つまり受けられるかもまだわからない授業の費用を払うことになるのだが、落ちた場合は返金されるので、クレカの利用可能枠が圧迫されて困った以外の心配はなかった。

授業ごとに取れる単位数が違い、単位数に応じてその授業の費用が変わる。私が取った授業は5単位だったため、6300ドルだった。これはほぼ70万円で、私の大学時代の半期の(複数の授業が受けられる)授業料が半額免除で13万くらいだったことを考えると、高い感じがする。

受講方法

クオーターで授業が区切られており、秋期の9〜12月で週2回80分の授業を受けていた。実際の授業のあと2時間以内にビデオがアップロードされ、リモートの人はそれを見て授業を受ける。英語なんだけど、先生の話すスピードがゆっくりめかつ割と滑舌がよくて聞き取りやすい感じだったので大体1.5〜1.75倍速で再生していたため、46〜53分くらいで受講できる。

私の授業では宿題が毎週出て、難易度に応じて2時間〜休日丸々2日くらいかかる感じだった。あと、これは授業によるのかもしれないがLabというのも毎週あり、テキストが渡され任意の時間に実験室で先生に質問しながら取り組むような奴なのだが、当然リモートだと参加できないため普通に宿題が毎週1個増えるような感じになるが、成果物は2時間取り組んだ後の内容の理解度に応じた質問フォームを埋める程度なのと、宿題に比べると物量が少ないので大体1〜2時間で終わる。

上記を総合すると、毎週最低5時間、運が悪いと土日が完全に潰れることを覚悟しないといけない。2つ同時に授業を受けるなら、1週間に土日が2つ必要になる可能性があることになるので、有給が必要になるかも。

試験

秋期では、11月頭に2時間の中間テストが1回と、12月中旬に3時間の期末テストが1回あった。

リモートで試験を受ける場合、ある条件を満たす人をExam Monitorとして申請し、その人に試験監督をしてもらわないといけない。家族や友人はダメで、会社の上司やHRの人にお願いするなどしなければいけない。

スタンフォードのリモート受講ではこれが唯一面倒なポイント*3で、現地で試験が始まってから24時間の期間に、全く業務に関係ない目的のために同僚の時間を2〜3時間確保しないといけないことになる。私の場合試験が両方Pacific Timeの金曜日だったので、JSTでは土曜の午前3:30みたいな意味不明な時間で始まるため、同僚の休日出勤を避けるために試験開始前の24時間以内でもいいかお願いするところから始まる。これは許されたが、上司の一人は金曜の都合がつかず月曜にできないか依頼したところそれは通らなかったため、二人目の上司に依頼することになった。

Exam Monitorになった人は、メールで問題のpdfをもらい印刷し、2〜3時間の監視の後同じ紙をスキャンしてメールで送り返すのだが、試験の2時間前とかに送られる問題のpdfのメールが、期末試験の時、中間試験の時に依頼した上司に(前日に宛先を先生にダブルチェックしたにも関わらず)送られてしまい、かつUSでは夜の時間のやり取りなので反応も遅いため試験開始の10分前くらいまでバタバタしてギリギリ間に合う感じだった。本当に面倒なので、試験の日だけは現地で受けられるような状態じゃないと辛い*4と思う。

あと、私は松江で行なわれるRuby World Conferenceの2日目と中間試験が被ったため、1日目にRuby Prizeを受賞してスピーチをし100万円をもらった後、2日目は上司に試験監督をしてもらうためさっさと東京に帰っている一見失礼な人間になっていた。カンファレンスと日程が被るかどうかも注意しないといけない。

CS107: Computer Organization & Systems

最近RubyのJITコンパイラの開発をしているのもあり、低レイヤープログラミングっぽい授業があったらそれを受けたいなと思って授業を探していたところ、CS107が一番それっぽかったのでこれを取ることにした。 なお、Ruiさんのスタンフォードのコンピュータサイエンスの授業の感想という記事でもCS107の内容について解説されているが、この記事の存在は受講し始めてから気付いた。

内容

シラバスにもっと丁寧に書いてあるが、私の記憶に残っているものの中では、CS107は大体以下の内容をカバーしていた。

  • 前半: C言語の基礎、デバッグ方法
    • Unixの基本的なコマンドや、gdbやvalgrindの使い方
    • Cのプログラムのメモリレイアウト、様々な型のバイナリ表現、2進数/16進数や2の補数
    • Cでのメモリ操作やポインタ演算周り
  • 後半: アセンブリ、最適化
    • 浮動少数点数の表現や精度の議論
    • アセンブリ言語レジスタや呼び出し規約
    • GCCの最適化やmalloc/freeの実装の理解
    • valgrind (callgrind) を使ったCのコードのプロファイリング

前半はとにかく難易度が低い。Cで普段言語処理系を開発してるような人が受けても得るものはほとんどない。が、課題はセル・オートマトン、UTF8の扱い、Cのライブラリ関数の実装を読みながらUnixコマンド(getenv, which, cat, tail, uniq, ls, sort)を実装しまくるといった内容で、毎回丁寧にコードを添削してもらえるので、C言語を学びたい人にとっては素晴らしい題材になると思う。

後半は学ぶ内容のレベルがちょうどいい感じだった。大学でアセンブリ言語でプログラミングするような授業があったのでそこは復習みたいな感じになったが、初めて知った(か単に忘れていた)ことが割とあったし、課題も試験もかなり練習になる感じなのでよかった。浮動小数点数の仕組みもふんわりとは理解してたけど、バイナリ表現を試験で回答できる程度に理解したのも初めてな気がする。GCCがコード生成の過程でどういう最適化をやってるかを少しだけでも理解しておくと私のJITの開発にはダイレクトに役に立つし、課題でmallocを2パターン実装するのも面白かった。

あと、2年前の期末試験問題とかを見るとELFのシンボルテーボルといった話題にも触れられていたようだが、今年はそれが含まれていなかったのは少し残念だった。

成績

Aだった。GPAにすると4.0で、上にA+があるらしい。テストも別に最高点というわけでもなく、体調崩してる間にLab一つすっぽかしたりしてるので、A+じゃないのはまあしょうがない気がする。

所感

11月にUS出張していた期間がこれと被っていたので、現地で受講したり図書館行ったりすることも可能だったのだけど、体調を完全に崩していて諦めたのがちょっと残念だった。まだキャンパス入ったこともない。

授業1つ取ってるだけで大分忙しくなるので、次授業受けるならもう少しJITの開発が落ちついて暇になったタイミングかなあと考えている。

*1:年間費用とかは見つかった https://cdn.group.softbank/corp/set/data/irinfo/presentations/results/pdf/2019/softbank_presentation_2019_002_004.pdf

*2:プログラミング系の奴の成績がよくて、文系科目が大体単位ギリギリの点数みたいな感じ

*3:アメリカのリモート受講が可能な他の大学だと、試験を受けている様子を自分で動画で取って提出するのもあると聞いた

*4:大学付近に住んでいるならテストだけ現地で受けることも可能で、その場合Exam Monitorは用意しなくて済むという話

SQLで羃等にDBスキーマ管理ができるツール「sqldef」を作った

sqldefのリポジトリ

github.com

これは何か

Ridgepoleというツールをご存じでしょうか。 これはRubyDSLcreate_tableadd_index等を書いてスキーマ定義をしておくとそれと実際のスキーマの差異を埋めるために必要なDDLを自動で生成・適用できる便利なツールです。一方、

f:id:k0kubun:20180825111557p:plain:w400

で言われているように、Ridgepoleを動作させるためにはRubyActiveRecordといった依存をインストールする必要があり、Railsアプリケーション以外で使う場合には少々面倒なことになります。*1 *2

そこで、Pure Goで書くことでワンバイナリにし、また別言語圏の人でも使いやすいよう、RubyDSLのかわりに、誰でも知ってるSQLCREATE TABLEALTER TABLEを書いて同じことができるようにしたのがsqldefです。

使用例

現時点ではMySQLPostgreSQLに対応しているのですが、このツールはmysqlコマンドやpsqlコマンドとインターフェースを揃えるため、 それぞれのDBに対しmysqldef、psqldefという別のコマンドを提供しています。

README用にgifアニメを用意しておいたので、こちらで雰囲気を感じてください。

f:id:k0kubun:20180825111815g:plain

どうやって動いているのか

mysqldef

  1. show tables; と show create table xxx; を発行して現在のスキーマを取得
  2. 入力のDDLとインクリメンタルに比較を行ない、必要なDDLを生成
  3. 生成したDDLを実行


簡単ですね。go-sql-driver/mysqlというPure GoのMySQLのDBドライバを使っており、mysql(1)やlibmysqlclientに依存していません。

psqldef

  1. pg_dump コマンドを実行して現在のスキーマを取得
  2. 入力のDDLとインクリメンタルに比較を行ない、必要なDDLを生成
  3. 生成したDDLを実行


これもlib/pqというPostgreSQLのDBドライバがPure Goのため、こちらもpsql(1)やlibpqに依存していません。 pg_dump への依存は、クエリだけでスキーマを取れるようにし、そのうちなくせたらいいなと思ってます。

実装済の機能

  • MySQL
    • カラムの追加、変更、削除
    • テーブルの追加、削除
    • インデックスの追加、削除
    • 外部キーの追加、削除
  • PostgreSQL
    • カラムの追加、削除
    • テーブルの追加、削除
    • インデックスの追加、削除
    • 外部キーの追加、削除

あまり無駄にシミュレートをがんばりたくないのと、どうせ対応しても僕は使わないので、CREATE TABLE, CREATE INDEX, ALTER TABLE ADD INDEX の羅列以外の入力に対応していません。DROPは常に書いてあるものを消すことで生成する想定です。テーブルやカラムにリネームが必要な場合は手動でリネームを発行して --export し直す想定です。

お試しください

まだ本番じゃ全然使えないクオリティなんですが、ISUCONとかでは割と便利に使えるかもしれません。 sqldefがそのまま使えるスキーマ定義が置いてあることが多いようですし。

そういうわけで、よろしくお願いします

github.com

追記: schemalexとの比較

schemalexの作者の方にschemalexと比較して欲しいというコメントをいただいているので軽く補足します。

SQL同士を比較してSQLを生成する既存のマイグレーションツールはあるんですが、その中でもGo製でMySQL向けにスキーマ生成ができるschemalexが既にある中で何故一から作ったかというと、正直なところ完全に調査不足で羃等にスキーマ管理するツールをRidgepole以外に知らなかったことによります。

その上で、2018年8月現時点でsqldefに実装されている機能とschemalexを比較すると、それぞれ主に以下の利点があると思います。

  • schemalex
    • URL形式やgit形式同士で柔軟な比較ができ、広いユースケースをカバーしている
    • 任意の2者の比較に特化した、テストや検証向きのCLI
  • sqldef
    • PostgreSQLに対応している
    • mysql-clientをインストールしなくてもスキーマを適用できる機能をリリース済 *3
    • mysqlpsqlコマンドとほぼ同じインターフェースで使えるCLI

どれもお互い今後の開発次第で解決できる問題ですが、おそらく思想的に変わらなそうなのはそれぞれ最後のCLIに関する部分でしょう。なので、私が羃等なスキーマ管理ツールのユースケースとして想定している以下の状況における、それぞれの現時点での使い方を比較したいと思います。

DBサーバースキーマのexport

schemalex

$ echo "" | schemalex -o schema.sql - "mysql://root:@tcp(localhost:3306)/test"

BEGIN;COMMIT; が含まれているのを消す必要があるため、私が把握していないだけでより正しい方法があるかもしれません。

sqldef

$ mysqldef -uroot test --export > schema.sql

Pull Requestマージ後に実行されるDDLの表示、適用

schemalex

もともとgit-schemalexとして開発されていた機能が活用できるため、こちらはschemalexが便利なユースケースだと思います。

# PRチェックアウト時、masterのスキーマ適用のためのDDL表示
$ schemalex "mysql://root:@tcp(localhost:3306)/test" "local-git://.?file=schema.sql&commitish=master"

BEGIN;

SET FOREIGN_KEY_CHECKS = 0;

CREATE TABLE `users` (
`id` BIGINT (20) DEFAULT NULL,
`name` VARCHAR (40) DEFAULT NULL
);

SET FOREIGN_KEY_CHECKS = 1;

COMMIT;

# PRチェックアウト時、masterのスキーマの適用
$ schemalex "mysql://root:@tcp(localhost:3306)/test" "local-git://.?file=schema.sql&commitish=master" | mysql -uroot test

# マージ後に実行されるDDLの表示
$ schemalex "mysql://root:@tcp(localhost:3306)/test" schema.sql

BEGIN;

SET FOREIGN_KEY_CHECKS = 0;

ALTER TABLE `users` ADD COLUMN `created_at` DATETIME NOT NULL;

SET FOREIGN_KEY_CHECKS = 1;

COMMIT;

# マージ後のスキーマの適用
$ schemalex "mysql://root:@tcp(localhost:3306)/test" schema.sql | mysql -uroot test

sqldef

sqldefは標準でgit連携を持っていないため、mysqlコマンドが不要なかわりにgitコマンドが必要になります。*4

# PRチェックアウト時、masterのスキーマ適用のためのDDL表示
$ git show master:schema.sql | mysqldef -uroot test --dry-run
-- dry run --
CREATE TABLE users (  id bigint,  name varchar(40) DEFAULT NULL);

# PRチェックアウト時、masterのスキーマの適用
$ git show master:schema.sql | mysqldef -uroot test
-- Apply --
CREATE TABLE users (  id bigint,  name varchar(40) DEFAULT NULL);

# マージ後に実行されるDDLの表示
$ mysqldef -uroot test --dry-run < schema.sql
-- dry run --
ALTER TABLE users ADD COLUMN created_at datetime NOT NULL;

# マージ後のスキーマの適用
$ mysqldef -uroot test < schema.sql
-- Apply --
ALTER TABLE users ADD COLUMN created_at datetime NOT NULL;

なおBEGIN;COMMIT;は表示していませんが、applyはトランザクション下で行なわれます。

最新のスキーマファイルのDBサーバーへの適用

schemalex

# masterチェックアウト時、スキーマ適用のためのDDL表示
$ schemalex "mysql://root:@tcp(localhost:3306)/test" schema.sql

BEGIN;

SET FOREIGN_KEY_CHECKS = 0;

ALTER TABLE `users` ADD COLUMN `created_at` DATETIME NOT NULL;

SET FOREIGN_KEY_CHECKS = 1;

COMMIT;

# スキーマの適用
schemalex "mysql://root:@tcp(localhost:3306)/test" schema.sql | mysql -uroot test

sqldef

# masterチェックアウト時、スキーマ適用のためのDDL表示
$ mysqldef -uroot test --dry-run < schema.sql
-- dry run --
ALTER TABLE users ADD COLUMN created_at datetime NOT NULL;

$ mysqldef -uroot test < schema.sql
-- Apply --
ALTER TABLE users ADD COLUMN created_at datetime NOT NULL;

まとめ

どちらのCLIユースケースにマッチするかは要件によると思いますが、2018年8月現時点では、MySQLの用途においては実績のあるschemalexを採用するのが現実的だと思います。私自身は自分の自由が効くsqldefをMySQLでも使いメンテを続けるつもりのため、時間が経てばこの問題は解決するでしょう。

一方PostgreSQLでワンバイナリのスキーマ管理ツールが必要な場合は、PostgreSQL未対応のschemalexに対応を入れるよりはsqldefを使ってしまう方が楽かと思われます。

*1:例えばRuby以外の言語でアプリを書いてCircleCIでテストする場合、CirlceCI公式のDockerイメージは普通に一つの言語しか入ってないので、アプリ用の言語とRidgepole用のRubyが両方入ったDockerイメージを自分で用意しないといけないですよね

*2:Ridgepoleの作者のwinebarrelさんにコメントをいただいてますが、現在はomnibus-rubyによってRubyを同梱したrpmdebのパッケージとしても配布されているため、バイナリをダウンロードするかわりにパッケージをダウンロードしてインストールする、ということもできそうです。一方手元でmacOSを使っていたりするとrpmdebは使えないですし、これはItamaeとmitamaeに関しても言える話ですが、一切依存のないバイナリ一つで動作する方が何かと管理が楽であろうという考えのもとこれらのツールを作っています。

*3:schemalexでもこのPR https://github.com/schemalex/schemalex/pull/52 で同様の機能が実装されると理解していますが、未マージのようです

*4:GitHubリポジトリを置いていたらCIからcloneしてくる際に必要になるので、普通は入ってるとは思います

RubyのJITに生成コードのメモリ局所性対策を入れた話

昨日、RubyJITの性能改善のためのパッチを入れた。

github.com

JITすればするほどRailsが遅くなる問題

Rubyの次期バージョンである2.6には、バイトコードをCのコードに変換した後、gcc/clangでコンパイルして.soファイルにしdlopenすることで生成コードのロードを行なう、MJITと呼ばれるJITコンパイラが入っているのだが、マージしたころのツイートにも書いていた通り、Railsで使うとより多くのメソッドがJITされるほど遅くなってしまうという問題があった。

結果、"MJIT slows down Rails applications"というチケットが報告されることとなり、昨日までの5か月の間閉じることができなかった。

元の構成

f:id:k0kubun:20180729202530p:plain

対策を始める前のMJITは大雑把に言うとこういう感じだった。メソッド1つごとに1つの.soファイルが作られ、ロードされる。

無制限にロードしまくるわけではなく、--jit-max-cacheオプションで指定した数(デフォルトでは1000)までしか生成コードを維持しないようになっており、JITされた数が--jit-max-cacheに到達すると、「呼び出し回数が少なく、かつ現在呼び出し中でないメソッド」と「メソッドがGC済のメソッド」向けにdlcloseを行なってから、他の呼び出し回数の多いメソッドのJITを開始する。

遅くなる理由

JITのためにgccやclangが走っている最中は、そこにリソースが取られるからかある程度遅くなってしまうのだが、今回報告されたチケットの計測方法では計測中ほとんどコンパイルが走らない状態になっていた。

いくつかのマイクロベンチマークや、ピュアRubyNESエミュレータでの性能を計測するOptcarrotというベンチマークではJITした方が明らかに速いのだが、先のチケットの計測方法だと遅くなってしまう。この理由は最初は不可解だったが、Optcarrotで普通にベンチを取ると20〜30メソッドくらいしかJITされないのに対し、このRailsでの計測は4000〜5000メソッドがJITされているという大きな違いがあった。

そもそも生成コードの最適化がRailsのコードに対して全然効いてなさそうなのも問題なのだが、最適化の余地が全くないようなただnil*1を返すだけのメソッドをたくさん定義して呼び出してみると、定義して呼び出すメソッドの数が多いほど遅くなることが発見された。

perfで計測してみると、遅くなっているのはicacheにヒットせずストールする時間が長くなっているのが原因のようで、それはメソッドごとに.soをdlopenしていることで生成コードが2MBおきに配置されてしまっておりメモリ局所性が悪いことが原因と結論づけた。*2

どうやって解決するか

解決策1: ELFオブジェクトを直接ロード

僕がこれに関する発表をRubyKaigiで行なってすぐ、shinhさんがELFオブジェクトを自力でロードしてくるパッチを作ってくださっていた。試してみると、ロードにかかる時間を遅くすることなく、40個くらいのメソッドを呼び出してもJIT無効相当の速度が出ていた。

一方で、shinhさん自身がブログで解説しているが、これを採用するとなると以下のような懸念点があった。

  • ELFを使うOSでしか動かない
  • (現状のパッチだと)ロードしたコードのデバッグ情報がgdbで出ない
  • ローダ自体の保守やデバッグが大変そう
  • 生成コードのメモリ管理が大変 (1GB固定アロケートか、遅くなるモードのみ実装されている)

そのためこれは直接採用はせず、以下の手法の評価にのみ利用した。

解決策2: 全てのメソッドを持つsoファイルを作ってdlopen

別々の.soになっているから問題が起きるわけなので、何らかの方法でコンパイル対象のメソッドが全て入ったsoを生成し、全てのコードをそこからロードしてくれば良いという話になる。コンパイル対象のメソッドの数が適当にハードコードした数に達したらまとめてコンパイルしてロードするようにしてみたら、実際速かった。

考慮したポイント

しかし、4000メソッド(計測に使われているRailsアプリのエンドポイントを叩いて放置するとコンパイルされる数)くらいをまとめてコンパイルすると普通に数分かかったりするので、この最適化をどのタイミングでどう実現するかは全く自明でない。

その戦略を考えるのが結構大変だったので、RubyKaigiの時点では定期的にまとめてコンパイルするだけのスレッドを新たに立てるつもりだったが、実装が複雑になるのでMJIT用のワーカースレッドは増やさないことにした。

その上で、短期間に少量のメソッドをコンパイルするOptcarrotでのパフォーマンスを維持しながら、数分かけて大量のメソッドをコンパイルするRailsでの性能を改善するため、以下の要素を考慮して設計することにした。

  1. 初めてコンパイル+ロードされるまでの時間
  2. soをまとめた後コンパイル済メソッドそれぞれのためにdlsym + ロックを取って生成コードを差し替える時間
  3. 生成コードの数が溢れた時にメインスレッドで生成コードをdlcloseする時間
  4. まとまったsoのコードに差し替えられるまでの時間
  5. メモリ使用量
  6. Ruby実行中 /tmp に持ち続けるファイルの数とサイズ

より上にある奴がより優先度が高く、下の方は(どうせ大した量使わないのもあり)どうでもいいと思っている。

最終的な構成

f:id:k0kubun:20180729212437p:plain

上記の1のためにワーカーはメソッドを1つずつコンパイルし、4のためにそのコンパイル結果の.oを /tmp に残し続けることにし、一方で一つ.oが増える度に一つのsoにしてロードし直してると2が線形に重くなって厳しいので4は多少犠牲にして一定回数おきにだけまとめてロードすることにして、そうするとある程度3や5が小さくて済み、6に関してはどうにかしたくなったら複数の.oファイル達を1つの.oにまとめれば良いだろう、という方針で作り始めた。

で、速度に関してはその方針でいいとして、メモリ使用量を考慮すると上記の図の"Sometimes"にあたる頻度がちょっと難しい。現状の実装では、呼び出されている最中の生成コードをそのフレームの外からVM実行に置き換えるOSR*3を実装できていないので、あるタイミングで1つの.soにまとめて生成したコードがどのフレームで使われているかを新たに管理するようにしないと、使われなくなったコードの破棄*4ができないのだが、それをやるとコードが結構複雑になる上に結局メモリ使用量も増えてしまう問題があり、あまりやりたくない。

それをサボる場合、頻度を上げれば上げるほどメモリリーク的な挙動になる*5わけなので、とりあえず キューイングされた全てのメソッドがコンパイルされた時--jit-max-cacheに達した時 だけ一つの.soにまとめてロードする処理をやる状態でコミットした。

OSRは他の最適化にどの道必要なので、長期的にはOSRを実装して任意のタイミングで古い生成コードを全て破棄できる状態にしようと思っている。

ベンチマーク

チケットの報告に使われているDiscourseというRailsアプリの、ウォームアップ*6後の GET / リクエスト100回で、以下のものを計測した。

レスポンスタイム(ms)

trunk trunk JIT single-so JIT objfcn JIT
50%ile 38 45 41 43
66%ile 39 50 44 44
75%ile 47 51 46 45
80%ile 49 52 47 47
90%ile 50 63 50 52
95%ile 60 79 52 55
98%ile 91 114 91 91
100%ile 97 133 96 99

速度増加の割合

小さい値の方が良く、 太字 が速くなっている箇所。

trunk trunk JIT single-so JIT objfcn JIT
50%ile 1.00x 1.18x 1.08x 1.13x
66%ile 1.00x 1.28x 1.13x 1.13x
75%ile 1.00x 1.09x 0.98x 0.96x
80%ile 1.00x 1.06x 0.96x 0.96x
90%ile 1.00x 1.26x 1.00x 1.04x
95%ile 1.00x 1.32x 0.87x 0.92x
98%ile 1.00x 1.25x 1.00x 1.00x
100%ile 1.00x 1.37x 0.99x 1.02x

50%ileと60%ileは微妙だが、1000リクエストする計測でやり直すと50%ileや60%ileのtrunkとの差が1msとかだけになる*7ので、微妙に遅くなるか運が良いとちょっと速いという状態まで改善した。

感想

objfcnに比べ遜色ない効果が出せているし、Optcarrotも仕組み上今回の変更ではベンチマーク結果に影響はないので、生成コードのメモリ局所性の問題に関してはうまく解決できたと思う。Railsで遅くはならない状態にできたので、今度は速くしていくのをがんばりたい。

*1:RubyにおけるNULL

*2:メソッドごとに実際に2MB使われているわけではないことに関する詳細はshinhさんがブログで解説しています http://shinh.hatenablog.com/entry/2018/06/10/235314

*3:On-Stack Replacement

*4:対応するハンドルのdlclose

*5:というかこれの対策は今入ってないわけだけど、まあ2.6のリリースにOSRが間に合わなそうなら適当な回数で.soをまとめる処理をやめるようにしようと思っている

*6:詳細は https://github.com/ruby/ruby/pull/1921 を参照

*7:最初からそうやって計測すればいいのだけど、一応起票されたチケットのやり方に合わせた