不要な処理が実行速度を速くする謎を追う

こんにちは。 id:Pocke です。マネーフォワードでは Rails を用いた Web アプリケーションの開発と、RBS という Ruby の静的型システムの開発を行っています。

最近 RBS の開発をする中で、「不要な処理を削除すると実行速度が遅くなる」という不思議な現象に遭遇しました。この記事ではその現象を解説しようと思います。

なおこの記事は Ruby の知識を前提としないように執筆されており、Ruby の知識が必要となるところには注釈を加えて補足しています。 普段 Ruby を書かない方にも読んでいただければ幸いです。

問題を引き起こした変更

今回の問題は、RBS のメモリ使用量の削減を行っている中で遭遇しました。まずはどんな変更を行おうとしていたかを解説します。

変更の動機

最近私は RBS のメモリ使用量の削減に取り組んでいます。¹ その取り組みの中で、RBS のパーサーが作るオブジェクトのメモリ使用量に目をつけました。

RBS 言語は Ruby 言語とは別の言語として設計されています。そのため RBS 言語のパーサーは Ruby 言語のパーサーとは別に、RBS のライブラリの一部として実装されています。 RBS 言語をパースした結果は AST の形で表現されます。

今回ターゲットとしたのは、AST の中に含まれる Hash² オブジェクトです。

メモリのプロファイリングをしていく中で、空もしくは少ない要素数の Hash オブジェクトが多くのメモリを消費していることがわかりました。そしてその Hash オブジェクトはパース中に作られており、キーワード引数のために使われていました。

RBS の AST では、メソッドのキーワード引数を Hash オブジェクトに保存しています。たとえばdef f(x:) endで定義されるメソッドはxというキーワード引数を受け取りますが、これに対して、{ x: 型を表すオブジェクト }という Hash オブジェクトが生成されます。 そしてたとえメソッドがキーワード引数を受け取らなくても、空の Hash オブジェクトが生成されてしまいます。たとえばdef g() endで定義されるメソッドは引数を受け取りませんが、キーワード引数を受け取らないことを示すために空の Hash オブジェクトが生成されます。

Ruby ではキーワード引数を受け取らないメソッドも多く、そのようなメソッドのために空の Hash オブジェクトが多く生成されてしまっていました。

変更内容

この問題を解決するために、1つの空の Hash オブジェクトを共有する変更を試みました。

このコミットがその変更です。差分の概略を次に示します。³

+EMPTY_HASH = rb_obj_freeze(rb_hash_new());

 (snip)

-params->required_keywords = rb_hash_new();
-params->optional_keywords = rb_hash_new();
+params->required_keywords = EMPTY_HASH;
+params->optional_keywords = EMPTY_HASH;

 (snip)

+if (*keywords == EMPTY_HASH) {
+  *keywords = rb_hash_new();
+}
 rb_hash_aset(*keywords, key, param);

まずEMPTY_HASHグローバル変数に、freeze⁴ された空の Hash オブジェクトを保存します。これが共有される Hash オブジェクトとなります。

そしてキーワード引数に対応するparams->required_keywordsとparams->optional_keywords⁵の初期化時に、EMPTY_HASHをセットします。 従来はrb_hash_new()関数で新しい Hash オブジェクトを生成していましたが、この変更によって共有された Hash オブジェクトを使うようになりました。

そしてメソッドがキーワード引数を受け取るとわかった段階でEMPTY_HASHを新しい Hash オブジェクトで置き換え、置き換えた Hash オブジェクトにキーワード引数を追加します。

この変更によってキーワード引数を受け取らないメソッドでは、共通の Hash オブジェクトが使われるようになります。 メソッドを表すのに必要な Hash オブジェクトの数が減り、メモリ使用量の削減に成功しました。簡単なベンチマークでは、13%ほどメモリ使用量が改善されていることが確認できました。

起こった問題

この変更を取り込む前に、実行速度の計測も行うことにしました。今回の変更では不要なrb_hash_new()の呼び出しをなくしたため、実行速度も多少改善されているだろうと想定していました。

ところがそんな期待とは裏腹に、実行速度はかなり遅くなってしまいました。以下がベンチマークの結果です。

# 変更前
$ bundle exec ruby benchmark/benchmark_new_env.rb
(snip)
             new_env      6.426 (±15.6%) i/s -     64.000 in  10.125442s
       new_rails_env      0.968 (± 0.0%) i/s -     10.000 in  10.355738s

# 変更後
$ bundle exec ruby benchmark/benchmark_new_env.rb
(snip)
             new_env      4.371 (±22.9%) i/s -     43.000 in  10.150192s
       new_rails_env      0.360 (± 0.0%) i/s -      4.000 in  11.313158s

このベンチマークでは、RBS ファイルをパースし、RBS::Environment というオブジェクトを作る時間を計測しています。 またnew_envとnew_rails_envでは、それぞれ規模の大小が異なる環境で計測しています。具体的には、前者は Ruby の組み込みライブラリの型定義を表す RBS ファイルのみを対象にしているのに対し、後者では Ruby on Rails の型定義を含めたより多くの RBS ファイルを対象にしています。

出力の中央の列に注目します。ここでは速度が i/s (iterations per second)、つまり1秒あたりの実行回数で表されています。これは数字が大きいほど速いことを示します。

この出力を見ると、変更後のほうが速度が低下していることがわかります。特にnew_rails_envではそれが顕著であり、2.7倍ほどの速度差が出てしまっています。

これだけの速度差が出ると、メモリ使用量が減るとはいえこの変更を取り込むのにはかなり抵抗があります。そのため速度低下の原因を調査することにしました。

遅くなる原因を探る

速度低下の原因を特定するために、いくつか仮説を立てて検証していきました。

立てた仮定の中の1つに「追加した比較がオーバーヘッドになっているのではないか」というものがあります。今回の変更では AST のノードが保持する Hash オブジェクトがEMPTY_HASHかどうかをチェックする比較を追加しています。 この比較はVALUE⁶同士の比較であるためこれが遅いことは考えづらいですが、検証することにしてみました。

この検証のために、以下のように変更のうちの2行をリバートして、再度速度の計測を行いました。

diff --git a/ext/rbs_extension/parser.c b/ext/rbs_extension/parser.c
index ca48d002..a5d172b2 100644
--- a/ext/rbs_extension/parser.c
+++ b/ext/rbs_extension/parser.c
@@ -616,8 +616,8 @@ static void initialize_method_params(method_params *params){
   params->optional_positionals = EMPTY_ARRAY;
   params->rest_positionals = Qnil;
   params->trailing_positionals = EMPTY_ARRAY;
-  params->required_keywords = EMPTY_HASH;
-  params->optional_keywords = EMPTY_HASH;
+  params->required_keywords = rb_hash_new();
+  params->optional_keywords = rb_hash_new();
   params->rest_keywords = Qnil;
 }

required_keywordsなどの初期値がEMPTY_HASHでなくなるため、従来と変わらず Hash オブジェクトが毎回生成されるようになります。一方でEMPTY_HASHかどうかをチェックする比較は残り続けます。 そのためリバート後でも速度が低下していれば、この比較処理が速度低下を引き起こしていると考えられます。

ところがこのリバート後の実行速度は、そもそも今回の修正を取り込む前の速度と同等でした。これは比較処理が速度低下の原因ではないことを示しています。

そしてこの結果は更に謎を深めました。2行リバートすることで変わるのは、Hash オブジェクトの生成個数と生成タイミングのみです。

	Hash オブジェクトの生成	実行速度
もともとの変更	共有を利用して生成するオブジェクトを削減	遅い
2行リバート後	必要がなくても常に生成	速い

つまり「Hash オブジェクトを無駄に生成することで、実行速度が速くなる」というかなり不思議な構造が明らかとなりました。

2行の差分という小さい再現コードを作れたこと、自分だけでは解決が難しいであろうことから、この段階で Ruby コミッターが集まる Slack ワークスペース で相談することにしました。 幸いにも mame さんや ko1 さん、soutaro さんに調査を手伝ってもらえました。

推測される原因

調査の結果、Hash オブジェクトの生成を減らしたことでヒープ領域が伸びづらくなり、それによって速度が低下したのではないかという推測が得られました。 以下が行った調査の概要です。⁷

• GC.statメソッド⁸で GC(Garbage Collection) の統計情報を見ると、マイナー GC の回数が2倍以上に増加していた。
  • GC やメモリ管理が今回の問題に関連していることが示唆されている。
• ベンチマーク前に大量の Hash オブジェクトを生成して暖気を行うと、速度低下がほとんど見られなくなった。
  • 0..30_000_000).map { {} }のようなコードをベンチマーク前に実行した。
  • 一見不要な Hash オブジェクトの生成が速度の改善に寄与していることが、別の視点からも示された。
• ヒープ領域を広がりやすくする設定をすると、速度差がほとんど見られなくなった。
  • RUBY_GC_HEAP_FREE_SLOTS_MIN_RATIO環境変数をセットすると、ヒープ領域の広がりやすさを制御できる。⁹
  • ヒープ領域の大きさが速度に影響していることが示された。

これらの調査結果から、「一見無駄な Hash オブジェクトが作られていたことにより、ヒープ領域が広がりやすくなり、それによって高速に動作していた」という仮説が立てられました。 なぜヒープ領域が広がると速度が改善するのかは理解できていないのですが、調査結果から GC の回数が速度低下に関係しているのではないかと想像しています。

Hash では起きて、Array では起きない

実は今回の問題には、不思議な点がもう1つありました。この速度低下が Hash の生成を減らしたときには起こるけれども、Array の生成を減らしても起こらなかったことです。

Ruby のメソッドには位置引数と呼ばれる引数があり、これは RBS の AST では Array で表現されています。これもキーワード引数と同様に引数がない場合に空の Array が個別に生成されており、メモリを消費していました。

そのため空の Array も1つのオブジェクトを参照するような変更を行いました。¹⁰そして、その変更は速度低下を引き起こさなかったのです。これは Hash と Array でなにか異なる事情があることを示唆しています。

調査の結果、この違いは Ruby に最近導入された可変幅アロケーションが影響している可能性が高そうだとわかりました。

可変幅アロケーションとは

可変幅アロケーション(Variable Width Allocation / VWA)は、Ruby 3.1 (2021年末リリース)で試験的に導入され、Ruby 3.2 (2022年末リリース)でデフォルトで有効となった Ruby の機能です。 その名の通り、Ruby のオブジェクトのサイズが可変になりました。

Ruby 3.1 までは、すべての Ruby オブジェクトのサイズは 40 バイトで固定でした。そして 40 バイトを超えるようなオブジェクトは、mallocなどで Ruby が管理する領域の外にメモリを確保していました。別途メモリを確保する必要があるオブジェクトの例としては、大きな文字列や大きな配列などが挙げられます。

可変幅アロケーションではオブジェクトのサイズは 40 バイトに固定されず、40, 80, 160, ...と複数のサイズに分けられて、それぞれ別のヒープ領域に割り当てられます。これによって 40 バイトに収まらないオブジェクトも Ruby が管理する領域の中に収めることができ、メモリの局所性の改善やmalloc, freeのコスト削減により、実行速度の改善が期待できます。

より詳しく知りたい方は、次の記事などを参照してください。

• https://shopify.engineering/ruby-variable-width-allocation
  • 可変幅アロケーションの作者の1人である Peter による、可変幅アロケーションの解説記事です。
• https://techracho.bpsinc.jp/hachi8833/2022_06_08/118447
  • 可変幅アロケーションについて日本語で解説した記事です。

可変幅アロケーションが及ぼす影響

では可変幅アロケーションが今回の問題にどう関わっているのでしょうか？ 結論から言うと、Hash オブジェクトが割り当てられるヒープ領域の違いが速度に影響していると考えました。

Ruby 3.3 からは Hash オブジェクトに対しても可変幅アロケーションが導入されました。¹¹ そして空の Hash オブジェクトは、160 バイトのヒープ領域に割り当てられています。一方で空の Array オブジェクトは、他のオブジェクトと同様に 40 バイトのヒープ領域に割り当てられています。

GC.stat_heapメソッド¹²を使用して、ヒープの状況を観察することでこれを確認できます。たとえばruby -e '1000000.times.map { {} }; pp GC.stat_heap'のように空の Hash を大量に作ってからGC.stat_heapを見ると、slot_sizeが 160 のヒープ領域で多くのオブジェクトが作られていることがわかります。一方で空の Array の場合は、slot_sizeが 40 のヒープ領域でオブジェクトが作られています。

# Hash オブジェクトを生成する場合
$ ruby -e '1000000.times.map { {} }; pp GC.stat_heap'
{0=>{:slot_size=>40, ..., :total_allocated_objects=>40818, ...},
 1=>{:slot_size=>80, ..., :total_allocated_objects=>14348, ...},
 2=>{:slot_size=>160, ..., :total_allocated_objects=>1005747, ...},
 3=>{:slot_size=>320, ..., :total_allocated_objects=>165, ...},
 4=>{:slot_size=>640, ..., :total_allocated_objects=>123, ...}}

# Array オブジェクトを生成する場合
$ ruby -e '1000000.times.map { [] }; pp GC.stat_heap'
{0=>{:slot_size=>40, ..., :total_allocated_objects=>1040818, ...},
 1=>{:slot_size=>80, ..., :total_allocated_objects=>14348, ...},
 2=>{:slot_size=>160, ..., :total_allocated_objects=>5747, ...},
 3=>{:slot_size=>320, ..., :total_allocated_objects=>165, ...},
 4=>{:slot_size=>640, ..., :total_allocated_objects=>123, ...}}

GC.stat_heapメソッドの結果からもわかりますが、多くのオブジェクトは依然として 40 バイトで確保されるため、40 バイトのヒープに比べて 160 バイトのヒープはオブジェクト数が少ないです。 そのため Hash の生成数の変化による影響が相対的に大きく、今回のような速度低下が起きたのだと想像しています。

Hash オブジェクトの可変幅アロケーションが実装されていない Ruby 3.2 で計測をすると速度低下が起きていなかったことも、この仮説を補強しています。

バグトラッカーに報告

ここまでの調査で RBS 側の変更でこの問題を解決することは難しそうだと判断しました。そのため今回の問題を整理して、Ruby のバグトラッカーにチケットとして報告しました。以下がそのチケットです。

bugs.ruby-lang.org

その結果、問題は修正され、無事 Hash の生成を減らしても速度低下が起きないようになりました。 今回の RBS の変更は、この修正がリリースされる Ruby 3.4 に合わせて取り込もうと考えています。

最後に

この記事では、不要な処理を消したら遅くなるという、矛盾しているかのような問題を紹介しました。 なかなか原因がわからず苦しくもありましたが、あまり知らなかった領域に触れることができたのはとても楽しくもありました。

この記事を読んで、Ruby のメモリ管理に興味を持っていただけたら幸いです。

また、来たる2024年10月15日に弊社福岡開発拠点で開催される Money Forward Tech LT大会で、RBS のメモリ使用量削減についてこの記事の内容も含めて発表する予定です。よろしければそちらもぜひご参加ください。

moneyforward.connpass.com

---

1. この背景については先月書いた記事で紹介しているので、詳しくはそちらをご覧ください。 Steepのメモリ使用量を改善するつもりが、実行速度の改善をしていた - Money Forward Developers Blog↩
2. Ruby における連想配列。↩
3. RBS のパーサーは C言語で実装されています。↩
4. freeze されたオブジェクトはイミュータブルになります。↩
5. それぞれ、必須のキーワード引数と、省略可能なキーワード引数を表します。↩
6. Ruby のあらゆるオブジェクトへのポインタで、unsigned longと定義されています。↩
7. 調査に使用した具体的なコードは、Ruby のバグトラッカーに報告した次のチケットを参照ください。 https://bugs.ruby-lang.org/issues/20710↩
8. https://docs.ruby-lang.org/ja/latest/method/GC/s/stat.html↩
9. 詳しくは公式ドキュメントを参照してください。 https://docs.ruby-lang.org/ja/latest/class/GC.html↩
10. https://github.com/ruby/rbs/pull/1950↩
11. https://github.com/ruby/ruby/blob/73c39a5f93d3ad4514a06158e2bb7622496372b9/doc/NEWS/NEWS-3.3.0.md#gc--memory-management↩
12. https://docs.ruby-lang.org/en/3.3/GC.html#method-c-stat_heap↩