Rubyを高速化するためにCコードをRubyで書き直す

 (jpcamara.com)
2 ポイント 投稿者 GN⁺ 2024-12-06 | 1件のコメント | WhatsAppで共有
  • 小規模な言語ベンチマークではCRubyは下から3番目だったが、ボトルネックが言語全体ではなく、YJITが中をのぞけない反復処理の実装にあることが示された
  • Ruby 3.3.6はM3 MacBook ProでFibonacci 12.17秒、Loops 28.80秒で、node.jsはどちらも1秒台だった。M2 MacBook AirではRubyがそれぞれ16.33秒と33.43秒で、さらに遅かった
  • ruby --yjitを有効にするだけでFibonacciは16.88秒から2.06秒へ大きく短縮される一方、Loopsは33.43秒から25.57秒にとどまり、Range#eachがボトルネックとして残った
  • Ruby 3.3のInteger#timesやRuby 3.4のArray#eachのように、C実装をRuby側へ移したメソッドはYJIT最適化の対象になり、反復ベンチマークが13〜14秒台まで改善した
  • CRubyはwith_yjitフックにより、YJIT有効時はRuby実装を使い、無効時はC実装を維持できるため、コアライブラリをYJITフレンドリーなRubyコードへ置き換える流れが生まれている

ベンチマークで見えたRubyの立ち位置

  • 最近共有された language comparison repo は、複数言語の小規模ベンチマークを共同で作るためのリポジトリ
  • このリポジトリでのCRubyの結果は、RとPythonだけがRubyより遅い下から3番目だった
  • ベンチマークは2つの軸を見ている
    • Loops: 反復、条件分岐、基本的な算術演算の性能を強調
    • Fibonacci: 関数呼び出しのオーバーヘッドと再帰コストを可視化
  • Loopsの例はネストしたループで合計10,000 × 100,000回、つまり10億回の反復を実行する
  • Fibonacciの例は最適化済み実装ではなく、意図的に単純なnaive Fibonacciを使っている

初期測定値とYJIT適用効果

  • M3 MacBook ProでのRuby 3.3.6は次の水準だった
    • Fibonacci: 12.17秒
    • Loops: 28.80秒
    • node.js: 両方とも1秒を少し超える程度
  • M2 MacBook Airでは同じベンチマークがさらに遅かった
    • Ruby Fibonacci: 16.33秒
    • Ruby Loops: 33.43秒
    • node.js Fibonacci: 1.36秒
    • node.js Loops: 2.07秒
  • 元のリポジトリの実行コマンドはYJITなしの ruby ./code.rb 40 だった
  • ruby --yjit ./code.rb 40 で実行すると結果が変わる
    • Fibonacci: 2.06秒
    • Loops: 25.57秒
  • YJITはFibonacciでは大きな効果を出したが、Loopsでは改善幅が限定的だった

Range#eachがYJITに不利な理由

  • Loopsコードの中核となる反復は (0...10_000).each と (0...100_000).each という Range#each
  • Ruby 3.4時点でも Range#each は依然としてCで書かれている
  • CRubyの range.c は Range クラスと each メソッドをC関数 range_each に結び付けている
  • range_each はさまざまな範囲形式を処理するため、多数の経路に分岐する
    • (0...).each
    • (0...100).each
    • ("a"..."z").each
  • C関数自体は高速でも、YJITはその内部を見られない
    • 最適化は関数呼び出し地点で止まり、C関数の返却後に再開される
    • YJITはホットパスに特化した最適化を作れるが、C実装はこの利点を制限する

Integer#timesに置き換えたときの変化

  • Ruby 3.3では Integer#times が C関数からRubyメソッドへ移行 した
  • 核となる構造は while i < self, yield i, i = i.succ から成る単純なRubyループ
  • Rubyコードで書かれているため、YJITが内部を解析して最適化できる
  • Range反復を 10_000.times と 100_000.times に置き換えると、Loopsの時間は大きく短縮される
    • Range#each: 25.57秒
    • Integer#times: 13.66秒
  • 別の測定環境では Integer#times が9秒まで短縮され、Ruby 3.4では8秒という結果も出ている

Integer#succとVMレベル最適化

  • Integer#times の実装は、加算に i += 1 ではなく i.succ を使う
  • Integer#succ は整数の次の値を返すメソッド
  • Ruby VMバイトコードでは i.succ は opt_succ という1ステップで表現される
  • 一方 i += 1 は2ステップに分かれる
    • putobject_INT2FIX_1_: 整数1をVMスタックに積む
    • opt_plus: + 演算を行う
  • 一般的なRubyプログラムではほとんど気にしなくてよいが、JITやVMレベルでは何百万回、何十億回と反復される際に1ステップの差でも性能へ影響する

Array#eachもRuby 3.4でRuby実装へ移行

  • Ruby 3.4では Array#each もCからRuby側の実装へ移行した
  • 最初の試みは単純なRubyコードだったが、CRuby内部に関わるrace conditionがあった
  • 最終実装ではRubyコード内で Primitive を使っている
    • Primitive.attr! :inline_block, :c_trace
    • Primitive.cexpr!
    • ary_fetch_next
  • 完全な純粋Rubyというより、Cコード評価とRuby構造が混ざった形だが、YJITはそれでもかなりの最適化を行える
  • 配列をあらかじめ作って Array#each で反復すると、Integer#times と近い性能になる
    • Range#each: 25.57秒
    • Integer#times: 13.66秒
    • Array#each: 13.96秒

Ruby Microbenchでの測定

  • 別リポジトリ ruby_microbench は、元の例とさまざまなRubyの反復形式を比較している
  • Ruby 3.4でYJITを有効にした結果は次の通り
    • Fibonacci: 2.19秒
    • array#each: 14.02秒
    • range#each: 26.61秒
    • times: 13.12秒
    • for: 14.91秒
    • while: 37.10秒
    • loop do: 13.95秒
  • Ruby 3.4でYJITを無効にすると、ほとんどがさらに遅くなる
    • Fibonacci: 16.49秒
    • array#each: 34.29秒
    • range#each: 33.88秒
    • times: 33.18秒
    • for: 36.32秒
    • while: 37.14秒
    • loop do: 50.65秒
  • while の例は予想より遅く、実装方法の問題かもしれない
  • for in と array#each はRuby VMバイトコードのレベルでほぼ同一で、性能も近い
    • for in は概ねVM上で #each 呼び出しへ変換される構文糖衣に近い

他のRuby実装との比較

  • 同じベンチマークは複数のRuby実装でも実行された
  • 一部の結果は次の通り
    • TruffleRuby 24.1
      • Fibonacci: 0.92秒
      • array#each: 0.97秒
      • range#each: 0.92秒
      • times: 2.39秒
      • for: 2.06秒
      • while: 3.90秒
      • loop do: 0.77秒
    • MRuby 3.3
      • Fibonacci: 28.83秒
      • array#each: 144.65秒
      • range#each: 126.40秒
      • times: 128.22秒
    • Artichoke
      • Fibonacci: 19.71秒
      • array#each: 236.10秒
      • range#each: 214.55秒
      • times: 214.51秒

Range#eachをRubyでモンキーパッチした実験

  • Range#each を単純なRuby実装でモンキーパッチすると、性能は大きく改善する
  • 実装は begin, end, loop, yield, i.succ を使う単純な形
  • 測定値は次の通り
    • C実装の Range#each: 25.57秒
    • Ruby実装の Range#each: 16.64秒
  • この実装はすべての Range ケースを処理しない過度に単純化された版
  • それでもCからRubyへ移すことでYJITが最適化でき、通常のCコードでは再現が難しい、あるいは不可能な形の性能改善が可能になる

YJIT標準ライブラリとwith_yjit

  • Aaron Pattersonの Ruby Outperforms C は、GraphQLパース用のC拡張をRubyで書き直し、YJIT最適化によってRubyコードがCより速くなった事例
  • CRubyの中核YJITチームは、一部のコア機能でCコードを除去するか、YJITが有効なときだけRuby実装を使う方式を進めている
  • with_yjit ブロックは、YJITが有効な場合にのみそのRuby実装を適用する
    • YJITが無効ならC実装がそのまま実行される
    • YJITが有効ならYJITで最適化可能なRuby版を使う
  • Ruby 3.3以降、YJITは遅延初期化が可能で、with_yjit コードはYJITが有効化された瞬間に適切なメソッド版を適用する
  • with_yjit はYJITフックで、呼び出し後にランタイムで undef :with_yjit により削除される

YJITが生成した機械語を見る方法

  • CRubyを --enable-yjit=dev オプション付きでビルドすると、YJITが生成する機械語ディスアセンブリを見られる
  • ビルド例は次の通り
    • ./configure --enable-yjit=dev
    • make install
  • 実行時には --yjit-dump-disasm フラグを使う
    • ./ruby --yjit --yjit-dump-disasm test.rb 40
  • Integer#times の i.succ はVMバイトコード上で opt_succ として現れる
  • YJITのRust実装は opt_succ に対して次を行う
    • レシーバが Fixnum かどうかをガードする
    • Fixnumでなければ別の実行経路へ出る
    • Fixnumなら内部タグ表現の都合で、1を足すために実際には2を足す
    • オーバーフローが起きたら別経路へ出る
  • この例は、JIT最適化がRubyコード、Cコード、VMバイトコード、Rust実装、機械語まで複数の層をまたいで動作することを示している

CRuby最適化の方向性

  • Ruby実装の作業はRubyより低レベルな言語で行われることが多く、CRubyでは主にCと一部Rustが使われている
  • YJITのような層は、より多くの言語機能を通常のRubyコードへ移していく可能性を生み出している
  • コア機能がさらにRubyで書かれるようになれば、Ruby開発者がCRubyへ貢献しやすくなるかもしれない
  • Javaのように、小さな低レベルコアの上に言語の大半が自己記述で構築される形は、CRubyの将来像の1つとして語られている
  • 現在の流れでは、C実装をそのまま維持するより、YJITが最適化できるRuby実装をコアパスへ導入する方式が引き続き重要になる

関連記事

1件のコメント

 
GN⁺ 2024-12-06
Hacker News のコメント

  • ループの例は 10億回のネストしたループを回す奇妙なベンチマークに見え、手で最適化すれば実行時間の99%以上が前半に集中しそう
    配列要素ごとの 生存区間解析（liveness analysis） を行えば外側のループ全体を取り除けそうに見えるが、こうした解析を実際に行うコンパイラがあるのか気になる
    u がコンパイル時点で分かっていなくても内側のループも数個の命令に置き換えられそうで、これは clang などが近いうちに行うかもしれない、より標準的な最適化に見える

    • コンパイラは通常、配列の個々の要素について生存区間解析を行わない
      追跡すべきデータが多すぎるし、このような誤ったコードの場合にしか役立たない可能性が高い
      以前AIコンパイラを作っていたとき、テンソルの個々の要素の生存区間解析は実際には有用だったはずなのに、コンパイル時間とメモリ要件が途方もないものになるため行わなかった
    • ほとんどの場合は閉じた形で計算できる:
      result = ((u * (u - 1)) / 2 * (100000/u)) + (100000%u * (100000%u - 1) / 2) + r)

  • 記事は今後登場する Ruby バージョンを扱っていて、気になって見ると ruby 3.4.0 は今年のクリスマスに、ruby 3.5.0 は来年のクリスマスに出るようだ
    また、こうしたループで Python の最小限の JIT がどんな影響を与えるのかも気になる
    Python 3.13 は JIT を有効にしてビルドする必要があるので、誰かがビルドした環境でベンチマークを回してみると興味深そう: https://drew.silcock.dev/blog/everything-you-need-to-know-ab...

    • Ruby はいつも クリスマスにリリースされるので、予測しやすくてかわいいスケジュールだ
      性能改善はポイントリリースにも入ることがあったと記憶している

  • Integer#succ は性能だけでなく 可読性のためにもよく使う
    例えば UUID ライブラリの #bytes メソッドでコードを読むとき、頭の中を「ビットスライシングモード」に保つために2回使った
    16回のループは 0xF.succ、ループ内で256で割る部分は 0xFF.succ と表現している: https://github.com/okeeblow/DistorteD/blob/ba48d10/Globe%20G...

    • この場合に 0xF.succ が 0x10 より良いと感じる理由が気になる

  • https://github.com/bddicken/languages に貢献していて、Lua のアプローチを試した後、どこかで言及されていた TruffleRuby も思い出したが、main.rb を走らせたときは TruffleRuby と通常の Ruby の間に実質的に大きな差はなかった
    時には通常の Ruby の方が TruffleRuby より速いこともあった
    記事の TruffleRuby 速度ベンチマークがどの変更後に出たものなのか確認してみたいし、検証できるならメインリポジトリにコミットとして追加してみたい
    TruffleRuby の実装が実際に Node.js より速く、Bun や Go に近い水準ならかなり驚きだ

    • TruffleRuby は 起動時間と最高性能に到達するまでの時間を考慮する必要があり、これはネイティブ/JVM ランタイム設定によって変わる
      詳細は https://github.com/oracle/truffleruby を参照

  • Ruby は本当に速くなっていて、特に TruffleRuby はさらに印象的だ

    • それは Oracle のもの: https://github.com/oracle/truffleruby
    • Rails は Truffle では動作せず、理解している限りでは当面も難しそうだ
      Ruby の性能に最も大きな影響を与える可能性が高い組み合わせなので残念

  • YJIT が Rust で書かれているとは知らなかったが、本当に興味深い

    • 最初は C で書かれていて、その後 Rust に移植されたが、良い判断だったように思う
      欠点は、適切なツールチェーンやプラットフォームがないとビルド時に有効化されない可能性がある点だが、悪くない妥協に見える

  • より長く運営され、より多くの言語を扱う言語比較リポジトリもある: https://github.com/niklas-heer/speed-comparison

    • もう一つの言語比較リポジトリだが、表現方法が読みにくい
      グラフの軸ラベルと棒のラベルが互いに重なっていて、縦のグリッド線もない
      シンプルな HTML テーブルだったらよかった

  • Python がベンチマークで最も遅い言語だったにもかかわらず、2024年10月時点で GitHub で最も使われている言語である点が興味深い
    遅い言語ほど人気があるという相関があるように見える

    • 比較し直すなら コンパイル時間も含め、そのビルドが実行されると予想される回数にわたって償却すべきだ
      Rust をかなり深く好きな立場だが、すべての言語とランタイム、インタプリタ、コンパイラは道具だ
      問題と解決アプローチに応じて良い道具の組み合わせが必要で、数回しか実行されないかもしれないプログラムなら、実行速度が遅いことはあまり重要ではない
      Python や R のプログラムにはそういう場合が多い
    • 食べ物に似ていて、上に 砂糖 をかけると人々はずっと好む
      概して Ruby は遅いが、コーディングするのが本当に楽しいので入門者にはより魅力的だ
    • 遅い言語はより 高水準なので使いやすい
    • 人気上位20言語を見てもその相関が維持されるのか気になる

  • 自分の Advent of Code の解答が驚くほど似た形なので、流れを変える変化のように見える