Precise Method and Constant Invalidation in TruffleRuby

原文はこちら。
The original article was written by Brandon Fish (Senior Member Of Technical Staff at Oracle Labs) and Benoit Daloze (TruffleRuby Lead at Oracle Labs).
https://medium.com/graalvm/precise-method-and-constant-invalidation-in-truffleruby-4dd56c6bac1a

このブログ記事では、典型的なRubyワークロードにおける脱最適化の回数を数百からゼロに減らし、起動時のパフォーマンスを大幅に向上させる、precise methodと定数の無効化について説明します。

Rubyのメソッド呼び出し時には、呼び出すべき正しいメソッドを見つけるためにモジュール階層をトラバースして、高コストなメソッド検索を実施します。モジュール階層には、レシーバーのクラス、親クラス、prependされたモジュールやincludeされたモジュールが含まれます。定数についても同様の探索が行われ、以下のキャッシュに関する議論が適用されます。このような高価な検索を避けるために、Rubyの実装ではクラスやメソッドが変更されていないことを前提にしたインラインキャッシュが使用されます。

このようなメソッド検索は、通常、与えられたレシーバーのメソッドが変更されていないと仮定して、同じメソッドエントリを返すことになります。つまり、この階層のメソッドが変更されていないことを前提に、ルックアップをキャッシュすることができるのです。メソッドは、この階層のどこででも定義、再定義、削除できます。メソッドの変更は、その変更がキャッシュされたメソッドよりも前の階層で行われたのか、 それともその以前キャッシュされたメソッドで行われたのかによって、メソッドキャッシュを無効にする必要がある場合とない場合があります。下図は、メソッド検索がどのように機能するかを示しています。

Method Lookup for First Call — Per Class Caching

下図にて、新しいメソッド bar を定義すると、クラスBとクラスBの子クラスのすべてのメソッド検索はその必要がないにもかかわらず、無効になります。(c.fooはまだ同じB#fooを呼び出します)。

Defining a New Method — Per Class Caching

CRuby 3.0未満およびTruffleRuby 21.2未満では、メソッドが定義されているモジュールに基づいて、再定義、追加、削除などのメソッドの変更がないように定数とメソッドの検索をキャッシュしています。そのため、あるモジュール/クラスでメソッドが変更されると、メソッド検索時にそのモジュール/クラスを巡回したすべてのメソッド検索のキャッシュが無効になってしまいます。

例えば、以下の例のようにKernelに新しいメソッドを定義すると、Kernelモジュールをトラバースしたメソッド検索情報を持つすべてのメソッドキャッシュが無効になります。

class Kernel
  def my_new_method
  end
end

Rails Active Supportなどでは、ロード時にこのようにクラスを再定義することが一般的です。例えば、コアとなるObject/Array/Hashクラスはここで修正されています。理想的には、このように既存のクラスにメソッドが追加されたときに、既存のジャストインタイムコンパイル(JIT)されたコードを無効にしないようにすることです。

Rubyのコードではモジュールの更新はよくあることで、追加されたメソッドが無効化されたメソッド検索結果に影響を与えないにもかかわらず、既存のメソッド検索が無効化されてしまう点で、上記の例は不必要な仮定によるキャッシュ無効化の残念なケースと言えます。TruffleRubyでは、メソッドキャッシュが無効になると、コンパイル済みのコードをインタープリタへ脱最適化し、再コンパイルが必要になったりするだけでなく、次にメソッドを呼び出す際にキャッシュが欠落してメソッドの全探索が発生したりして、パフォーマンスに悪影響を及ぼすことがあります。

Method Caching Improvements in TruffleRuby 21.2

TruffleRuby ではこの不要なメソッドキャッシュの無効化の問題を解決するために、メソッド検索をアップデートして、”per method name caching”(メソッド名ごとのキャッシュ)という、メソッド名に基づいたキャッシュを可能にしました。これはモジュール上の各メソッド名には、ルックアップのために無効化される可能性のあるその所有モジュール上のメソッドエントリがあるためです。次の例のように、メソッド検索が行われると、検索はそのメソッド名だけの検索チェーン内の各先祖に対する仮定のリストを受け取ります。

Method Lookup for First Call — Per Method Name Caching

これだと、新しいメソッドを追加したときに、変更されたメソッドのルックアップだけを無効化すればよくなります。

Defining a New Method — Per Method Name Caching

Challenges

Rubyでは、prependincludeextend、定数/メソッドの再定義、定義消去など、レシーバーのモジュールチェーン内のメソッド更新方法が多数あります。このため、それぞれのシナリオで必要なメソッドキャッシュを正しく無効化しつつ、必要以上に無効化しないようにすることが課題となっています。

Cache Invalidation Examples

次の例は、モジュールやメソッドの変更時にメソッドキャッシュを無効化するいくつかのシナリオを説明するものです。

このシナリオは、モジュールチェーンでメソッドを他の定義より先に定義した場合にメソッドキャッシュがどのように無効になるかを示しています。

Invalidation — Adding a New Method to a Child Class

次のシナリオでは、以前に使用したメソッドよりもモジュールがモジュールチェーンに早く含まれる場合に、キャッシュを無効にする方法を示しています。

Invalidation — Including a Module

Prependもまた難しいシナリオで、Prepend先のモジュールにある既存のメソッドがPrepend先のモジュールで同じ名前を共有している場合、それらを無効にする必要があります。

Invalidation — Prepending a Module

最後の例は、モジュールをprependした後に、以前使った名前のメソッドをprepend対象のモジュールに追加した場合にどのように無効化されるのかを示しています。

Invalidation — Adding a Method to a Prepended Module

上記のシナリオでは、メソッドfooの検索結果がモジュールチェーン内のprependモジュールMの後に発生するため、さらに複雑になっています。この場合、fooを正しく無効化するために、MBの前にprependされていることを追跡し、さらにBのメソッド名がMで無効化されたときに無効化するようにします。

これらは、メソッドキャッシュを無効にするために起こりうるシナリオの一部に過ぎません。他のシナリオとしては、モジュールの拡張、メソッドの削除や更新などがあります。

Drawbacks

TruffleRubyでは、メソッドが変更されないという前提をTruffle Assumptionオブジェクトで表現しています。これまでモジュール全体で 1 つの Assumptionオブジェクトを持っていたのに対し、各メソッドでAssumptionオブジェクトを持つようになったため、追加のAssumptionオブジェクトにより消費メモリが増加してしまいます。

Results

rails routes”コマンドを実行するRailsブログアプリケーションをシミュレートするベンチマークでテストを実施しました。

キャッシュ無効化の総回数定数やメソッド変更に伴うキャッシュ無効化の回数
変更前1422720
変更後8934

より詳細なキャッシュ無効化を使うことにより、定数やメソッド変更に伴うキャッシュ無効化のほぼすべてをなくすことができました。この結果、以前に無効化されたメソッドやブロックを再コンパイルする必要がなくなり、再コンパイル時にインタープリタではなく、コンパイルされたコードで実行し続けることができるため、ウォームアップが改善されました。

実際のアプリケーションをテストするために、Chris SeatonとMaple Ongに協力してもらい、Shopify Storefront Rendererの起動時のメソッドと定数の無効化回数を計測しました。この最適化以前は、メソッド修正による無効化回数が992回、定数の修正による無効化回数が424回でした。正確なキャッシュ無効化により、Storefront Rendererの起動時の無効化は、メソッド、定数ともにゼロになりました。これにより、メソッド無効化の更新で約9%、定数無効化の更新で約8%、合計で約16%のアプリケーション起動時間の短縮を実現しました。

Additional Improvements in the Future

メソッドキャッシュの改善の主な動機は、発生していた冗長な無効化および再コンパイルを排除することで、アプリケーションがピーク性能に到達するまでの時間を短縮することです。

また、無効化を処理するための他のデータ構造を検討することで、必要な仮定の個数を削減することも検討の余地があります。

Method Caching Improvements in CRuby 3.0

CRuby 3.0では、前述のTruffleRubyのキャッシュ実装と類似した、クラス単位、メソッド単位のキャッシュが追加されています。

CRubyの更新されたメソッドキャッシュの説明は、以下のURLからご覧いただけます。

Feature #16614 : New method cache mechanism for Guild
https://bugs.ruby-lang.org/issues/16614

この設計は若干トレードオフがあります。例えば、メモリフットプリントを最小化しますが、精度が低く、不必要なキャッシュの無効化を引き起こす可能性がある、といった具合です。

Conclusion

Rubyのウォームアップには、メソッドと定数の正確なキャッシュ無効化が重要であることがわかりました。このブログで説明した設計では、アプリケーションのロード中にキャッシュ無効化の回数を数百回からゼロにすることが可能です。既存のprependモジュールに後からメソッドを追加する場合など、エッジケースはたくさんありますが、結局のところはシンプルで、変更したモジュールを通して見た、そのメソッド名を持つキャッシュの検索を無効にする必要があります。

TruffleRubyに関する詳細は、以下のWebページをご覧ください。

TruffleRuby
https://www.graalvm.org/ruby/

TruffleRubyのアップデートは、Twitterをフォローしてください。

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中