# 中間報告: シェイプ事前構築とメソッド特殊化によるCRubyの最適化 Tadashi Saito (齋藤 匡) ## 実施した作業 現在・中間報告時点までに実施できた作業は、残念ながら、本格的な開発の準備段階である調査に留 まっている。 1. シェイプ構造の調査 2. インラインキャッシュ実装の調査 なお以下の報告で単に「論文」として言及するものは、報告者が第一著者であり、また応募時にも言 及ししている、今回CRubyへの適用を目指す手法を示した論文[^1]を指す。 [^1]: Integrating Static Optimization and Dynamic Nature in JavaScript https://doi.org/10.1145/3742876.3742877 ### 1. シェイプ構造の調査 CRubyのshape.cを中心に、シェイプにまつわる大まかなコードリーディングを行った。報告者は (残念ながら) コミッターとして活発に活動していなかったため、近年のファイル再編成の把握を含 めた作業となった。 論文中で取り上げ、改良の対象としたJS実装・QuickJSにおけるシェイプは、極めて単純なハッシュ 表 (オープンアドレス法) であった。一方、CRubyではそれが赤黒木として実装されていることを理 解した。またコード全体は平易で読みやすく書かれているため、変更の際にも理解や把握に手間取る ことはなさそうであることも分かった。 とくに、メンターでもあるPatterson氏がRubyKaigi 2024で行った講演を動画[^2]として視聴し、実 装を理解する上での大きな助け (そして楽しみ) となった。図と動きの多い動画が残ることの (そし て、それをいつも行ってくださるRubyKaigiスタッフの方々の働きの) 価値の大きさを実感した。 なおこの視聴は、ruby-jp Slack内の #rubykaigi チャンネルがきっかけとなった。そこではいちユー ザーである eririn (Eriko Sugiyama) 氏によって、「RubyKaigiの動画を毎週一つずつ・全部見る」 という呼びかけが継続されている。私は開発期間中、この動画が取り上げられていたところにたまた ま出くわすことができた。分かりやすく楽しいきっかけを作ってくださったeririnさんには感謝を申 し上げたい。 [^2]: https://rubykaigi.org/2024/presentations/tenderlove.html #### 疑問点 (改善点の候補) ソース読解中、以下のような疑問が数点生まれた。これらは現状のRubyに対する改善点の候補ではあ るが、調査途中である上、今回の開発の中核からも外れるため、評価を含めた実作業は後回しとなっ ている。 1. データ構造として赤黒木が適切な選択であったのか、ベンチマークによる検証が欠けている * 当該のコミット・PRを遡っても、そういった記録・データは見つからなかった * (定性的な話となるが) 赤黒木が優れているのは一般に、悲観的なシナリオにおける性能 (最悪 計算量が抑えられる) と言える。一方で、シェイプは「同じ構造がたくさんできることが多い」 という、楽観的な経験則を元に採用される。ここにミスマッチがあるように思われた * 例えば、楽観的なシナリオ下の簡素なデータ構造では、性能が逆転することも考えられる (類似例: 要素数が少ないリストから検索するなら、 ArrayでなくHashを使う意義は薄い) * そのため、楽観シナリオ・悲観シナリオのそれぞれを実用的なベンチマークとして用意し、 現行の赤黒木実装とより単純な仮実装 (ハッシュ表等) を比較する価値があると思えた 2. コア部分の関数に再帰呼び出しが存在する * 具体的には、redblack_find関数は再帰呼び出しで実装されている[^3] * しかしC言語における再帰は (例えばSchemeのような) 最適化が保証されていないため、手動で ループとして書き直すことで性能に変化が生じ得る * 実際にループとして簡単に書き換えられることと、出力されるアセンブリに自明でない変化が あることまでは確認した。しかしこれらの性能比較は、前述の理由で未検証である * 参考情報: Clangでは、以前から [[musttail]] 関数属性が提供されており、再帰呼出における 一種の最適化が保証できる。さらに昨年から、GCCにも導入された事実[^4]は注目に値する。し かし、後者はリリースされてまだ1年未満であるため、やはり手動による最適化の意義が十分に 残っていると考える 3. (些細なスタイルの話だが) 他のファイルに比べると、if.. return; 後のelseが多く、ネストが 深くなる傾向が見て取れた * 例: https://github.com/ruby/ruby/blob/v4.0.1/shape.c#L879-L900 [^3]: https://github.com/ruby/ruby/blob/v4.0.1/shape.c#L69 [^4]: https://gcc.gnu.org/onlinedocs/gcc-15.1.0/gcc/Statement-Attributes.html#index-musttail-statement-attribute ### 2. インラインキャッシュ実装の調査 上述の動画視聴をきっかけにして、設計上とても重要な事実に気付くことができた。論文中ではイン ラインキャッシュ (IC) が実装されていないケースを前提に論じていたが、CRubyにはすでに存在す ることを理解した。 論文内での提案手法はICが存在しない処理系に対するものであり、それを基準として性能向上を評価・ 確認した。特に属性 (Rubyでのインスタンス変数) へのアクセス高速化が全体の性能向上に寄与して いたことが推定されるが、これはICに因っても類似の効果が期待できるものである。 そのため、論文で観測されたような（数割程度の) はっきりした速度改善がCRubyで見込める可能性 は、残念ながらかなり下がってしまったと言える。 報告者は応募前の調査時点で、CRubyでのICと他のキャッシュとを混同しており、上記の事実を理解 できていなかったのがありのままの事実である。この点は、率直に言えば応募者としての落ち度であ り、真摯に反省すべき点であると理解している。 ただ、その後もCRubuにおけるICの調査を進め、ZJIT内でもICの活用を進めていること[^5]、その中 で多相 (Polymorphic) ICの導入を検討していること[^6]等も把握した。JITによってよりICの活用が 進むことが見込まれる上、キャッシュは実行時の予測不可能性に備える繊細な存在であるため、この ICへの悪影響・オーバーヘッドを生じさせない設計が一層重要になることが分かった。 [^5]: https://github.com/ruby/ruby/commit/1cca3efa5a1a348cab93a6dc2486bc9a71519d39 [^6]: https://github.com/ruby/ruby/commit/ef95e5ba3de65d42fe0e1d41519dcf05db11a4e8 ## 当初計画との比較 当初の計画での開発目標および段階と、現在の状況とを比較して示す。 ### 目標 当初の応募時、今回の開発で期待できる効果として以下を上げ、またそれを目標として捉えていた。 1. インスタンス生成時のメモリ消費量の低減・処理速度の向上 2. メソッド中のインスタンス変数参照での処理速度の向上 現段階でも両者の効果は見込めるが、前述の通りICの存在から、2番目に期待できる効果は小さいこ とが判明した。そのため残念ながら、論文で観測されたような大きな改善が望める可能性は下がって しまった。 一方で、(論文中でも論じた通り) インラインキャッシュと今回の手法は共存可能である。さらに1番 目の効果については、ICの存在有無に関わらず有効であると考える[^7]。 これらの点から、今後の開発では2の点に注力した開発・評価を行う意義が増えたと考えている。 [^7]: 論文に記載しなかった途中経過データではあるが、その効果の一例として、マイクロベンチマー クを特定の条件で評価した場合、ICやJITを備えるGoogle開発のV8よりも高速に実行されるケー スが存在した。 ### 開発順序 応募時に想定していた開発の流れは以下であった。 1. まずコードを変更せず、インスタンス変数のリストを早期に確定できる 方法を調査する。 2. 単純な設計と実装方針で、正しい動作を重視したプロトタイプを作成する。 * 既存の各種ユニットテスト・ベンチマークプログラムを活用する。 3. 最適化の効果を定量的・継続的に確認しながら、実装を仕上げる。 * 既存のべンチマークで評価を行うが、それをマイクロベンチマークに限定 せず、より現実的なマクロベンチマークによる効果の裏付けを目指す。 現在は残念ながら、これらの本格的な開発には着手できていない。 一方、前述のような調査は継続している上、上記それぞれの必要性がより補強されたと考えている。 なお3で当初から掲げていた「現実的なベンチマークによる効果測定」という観点は、Rubyハッカソ ン at RWC 2025中に笹田耕一氏にもアドバイスをいただき、そこでの議論から具体的な流れをイメー ジすることができた。同氏、そしてハッカソン主催のRubyアソシエーションにも感謝申し上げたい。 ## その他タスク 上記の開発の手前として、必要と考えるタスクを示す。 * (少なくとも) RubyKaigiにおけるシェイプ関連のすべての発表を把握 * コードを読むよりも外観を素早くつかめるため * シェイプがどう使われているか、統計データを採取・評価 * 事前と事後の評価として * マイクロベンチでなく実用的なアプリケーションで取れることが理想 * さらなるIC関連コードの把握 * 特に、今回の開発とコンフリクトさせないための条件を究明・理解 ## まとめ 現時点で、CRubyのシェイプ構造とインラインキャッシュ実装を調査し、開発方針を具体化し、また 評価のために何が必要であるかを理解した。残念ながら、本格的な実装には着手できていないが、そ の準備となる部分の試験実装は継続している。 またここに至るまで、コミュニティの複数の方々に様々な形で支えていただいていたことを確認でき た。関係するすべての方に感謝を表したい。