RubyのJSON最適化、Part 1

 (byroot.github.io)
1 ポイント 投稿者 GN⁺ 2024-12-19 | 1件のコメント | WhatsAppで共有
  • Ruby標準のjson gemは、プロファイリングでボトルネックを取り除くことで改善され、速度のためにojへ乗り換えなければならないという実務上の圧力を減らす方向で進化した
  • 目標はojに無条件で勝つことではなく、Oj.mimic_JSONやOj.optimize_railsのようなモンキーパッチなしでも、十分に高速で予測可能なJSON処理を提供することにある
  • ojは一部のベンチマークでは速かったが、script_safeオプションの無視、Railsシリアライズの差異、Rubyクラッシュなどにより、運用安定性とAPI互換性の面で負担を生んでいた
  • 主な最適化は、重複したUTF-8検査の削除、頻出条件の優先判定、ジェネレータ設定コストの削減、エンコーディングポインタ追跡の回避、ルックアップテーブルベースのエスケープ判定で構成される
  • twitter.json 467KiB生成ベンチマークでは、変更ごとに3%、8%、15%、30%の改善が得られ、小さなHashの生成は設定コスト削減だけで1.51倍高速化した

json gemを高速化した背景

  • 最近json gemのメンテナになって以降、古いバグを修正しつつ性能改善にも注力し、その結果、ほとんどのベンチマークでRuby向け最速のJSONパーサ兼ジェネレータになった
  • 性能パッチの大半は、特別な秘訣というよりプロファイリングでボトルネックを見つけ、単純な無駄を減らす作業に近い
  • 中核的な動機は、ruby/jsonが十分に速くなり、ユーザーが速度を理由に代替gemを選ばなくてもよい状態を作ることにあった

ojへの置き換え利用が生んだ負担

  • json 2.7.2とojの差は、実際のサイズに近い一部ベンチマークでは大きくなかった
    • 100件のツイートからなる467KiBのJSONドキュメントのパースは、json 2.7.2が1.9ms、ojが1.6ms
    • 同じドキュメントの生成は、json 2.7.2が0.8ms、ojが0.4ms
  • 多くのユースケースでは、遅い部分はJSONシリアライズ自体ではなく、Active RecordモデルをRubyのHashやArrayへ変換する上位レイヤーである
  • ojはShopifyのコードベースを含む多くのプロジェクトで使われており、その人気は速度による可能性が高い

  • モンキーパッチによるAPI不一致

    • Oj.mimic_JSONはjson gemを、Oj.optimize_railsはActiveSupport::JSONをモンキーパッチする形でよく使われる
    • JSON.dump(data, script_safe: true)は、JSONを<script>タグ内に安全に埋め込むため、</script>を<\/script>へエスケープできる
    • ojはscript_safeオプションを認識せず無視するため、単体では安全だったgemでも、Oj.mimic_JSONを呼び出したアプリケーション内ではXSS攻撃の可能性を生みうる
    • Oj.optimize_railsも、オブジェクトシリアライズで微妙な差異を生むことがある
    • ActiveSupport::JSON::Encoding.time_precision = 0の状態では、ActiveSupport::JSON.encode(t)は秒単位の文字列を生成できる
    • Oj.optimize_railsとOj.mimic_JSONの適用後は、ミリ秒を含む文字列が出力される例がある
    • この事例はロード順によって生じるコーナーケースだが、過去にはこれ以上に多くの動作変更があった

  • 本番環境での安定性の問題

    • 大規模環境では、ojはRubyクラッシュの目立つ原因の1つであり、grpcに次いで問題が多かった
    • native gemの実装にはRuby VM、特にGCへの理解が必要で、そうでなければクラッシュやメモリ破損が起こりうる
    • ojのコードベースには信頼を難しくするhackがあり、かつてはバグ回避のため一部状況でGCを無効化していた
    • GCを再有効化すると、major GC cycleが誘発される可能性がある
    • こうしたコードはマイクロベンチマークには有利でも、実際のプロダクション性能を落としかねない
    • この経験からShopifyのモノリスではOjを削除し、その過程でOj.mimic_JSONと実際のjsonの間にある微妙な差異を確認した

ベンチマークとプロファイリングでボトルネックを探す

  • 目標は、ruby/jsonが実運用とマイクロベンチマークの両方でojと近い挙動を示し、速度を理由にOj.mimic_JSONを使う魅力を減らすことだった
  • 最初の段階は、ベンチマークスイートを構築することだった
    • マイクロベンチマークと、より実態に近いベンチマークを併せて含めた
    • John Hawthornのrapidjson-ruby gemにあったベンチマークスイートをベースにし、一部を追加した
  • Cプロファイラとしてはsamplyを使用した
    • Firefox Profiler互換のレポートを出力するため、共有しやすいのが利点だった

重複したUTF-8検査の削除

  • twitter.jsonペイロードでJSON.dumpをプロファイリングしたところ、JSON自身のisLegalUTF8に9%、rb_enc_str_asciionly_pに1.9%が費やされていた
  • RubyのStringはcoderangeという内部属性を持ち、文字列のエンコーディング状態やASCII-onlyかどうかを一度走査した後でキャッシュする
    • ENC_CODERANGE_UNKNOWN: まだ走査されていない
    • ENC_CODERANGE_VALID: エンコーディングが有効
    • ENC_CODERANGE_7BIT: エンコーディングが有効で、ASCII文字のみ
    • ENC_CODERANGE_INVALID: エンコーディングが無効
  • 既存のconvert_UTF8_to_JSON_ASCIIは、最初にrb_enc_str_asciionly_pを呼び、その後あらためて文字列を手動走査してUTF-8の妥当性を確認する重複作業をしていた
  • 変更後は、すでに計算済みのcoderangeを比較してUTF-8の妥当性を判断するようにした
    • Rubyで表すと、string.ascii_only?でなければstring.encoding != Encoding::UTF_8または!string.valid_encoding?のときにJSON::GeneratorErrorをraiseする形である
    • #ascii_only?と#valid_encoding?はいずれもキャッシュされたcoderangeを使うため、文字列走査は最大1回で済む
  • 期待した9%とは異なり、実際の改善は約**3%**にとどまった
    • isLegalUTF8で使われていた時間のかなりの部分がconvert_UTF8_to_JSONへ移った
    • 理由は確かではないが、9%の大部分は文字列バイトをRAMからCPU cacheへ持ってくるコストだった可能性がある
    • twitter.json生成ベンチマークは1077.3 i/sから1113.3 i/sへ向上し、1.03x高速化した

より安く、より起こりやすい条件を先に判定する

  • fbuffer_inc_capaは全ランタイムの5.7%を占め、その大半の時間はバッファがすでに確保済みかを確認することに使われていた
  • この関数はバッファへ何かを書き込むたびに呼ばれるが、最初の呼び出し以後はバッファは常にすでに確保されている
  • 従来の構造は、ほとんど当たらない条件を先に判定しており無駄が大きく、さらにバッファが未確保ならfb->capaが0なので、required > fb->capaの確認とも一部重複していた
  • 修正後は、最も一般的なケースである「バッファ容量が十分ある」を最初に判定し、RB_LIKELYとRB_UNLIKELYでCPUのbranch predictionにヒントを与えた
  • 関数はinline指定され、呼び出しコストが減り、ほとんどのケースで必要な作業は減算と比較程度まで小さくなった
  • この変更により、twitter.json生成ベンチマークは1068.6 i/sから1224.7 i/sへ伸び、1.15倍高速化した
  • 同じ原則はRubyコードにも適用でき、最も安く、最も起こりやすい条件を先に判定するという考え方である

JSONジェネレータの設定コストを減らす

  • RubyコミッタのYusuke Endoh aka Mameもruby/jsonの最適化に参加しており、複数の最適化を含む古いPRがあった
  • 多くの変更は、JSON生成前に必要な設定コストを減らすことに焦点を当てていた
    • 引数パース
    • generatorと関連構造体の割り当て
    • 生成処理に入る前の準備作業
  • ruby/jsonはこの設定コストが代替実装より大きく、マイクロベンチマークでは不利に見えていた
  • JSON.generateはpretty JSON生成のためにarray_nl、object_nl、indent、spaceといったオプションを受け取れる
  • 従来は、与えられた文字列から区切り用バッファを事前計算していた
    • 例: ",#{opts[:array_nl]}", ",#{opts[:object_nl]}", ":#{opts[:space]}"
    • 長い断片を1回appendする意図だったが、実際に節約できる作業は小さかった
    • ほとんどの場合これらのオプションは使われず、事前計算コストのほうが大きく効いていた
  • Mameはこの最適化を実質的に巻き戻し、設定コストを大幅に削減した
    • 大きなベンチマークでは差は大きくない
    • 65 bytesの小さなHash生成ベンチマークは2,112,189.3 i/sから3,199,311.0 i/sへ向上し、1.51倍高速化した

ポインタ追跡を避け、エンコーディングindexを比較する

  • Mameによる別の最適化は、rb_enc_get呼び出しを1つ削除することだった
  • JSONは文字列がUTF-8互換かどうかを頻繁に確認する必要があり、従来はrb_enc_get(obj)でrb_encoding *を取得してから、US-ASCIIまたはUTF-8かを比較していた
  • rb_enc_getは防御的な高水準APIであり、複数の型チェックを行う
    • String、Symbol、Regexp、File、Dataなどさまざまなオブジェクトを扱えるようになっている
    • 条件分岐が多く、CPUのbranch predictionが外れるとコストが大きくなりうる
  • RubyのStringは概念的にはencoding参照を持つが、実際には64-bitポインタではなく、各String内部のbitmapにより小さな7-bitのencoding indexを格納している
  • 完全なencodingオブジェクトのポインタを得るには、VM内部のグローバル配列を介して実際のencodingを引く必要があり、これは低レベルコードではポインタ追跡に当たる
    • すでにCPU cacheにあれば高速だが、RAMから取る必要があるとCPUは待たされる
  • jsonは対象がすでにStringであることを知っており、必要な情報もASCIIまたはUTF-8かどうかだけなので、RB_ENCODING_GETでencoding indexを直接比較できる
  • この変更により、twitter.json生成ベンチマークは1159.6 i/sから1253.3 i/sへ向上し、1.08倍高速化した

ルックアップテーブルで文字列エスケープを高速化する

  • JSON文字列のdumpでは、各文字がそのままコピー可能か、エスケープが必要かを確認する必要があり、コストが高い
  • 素朴な方法では、各文字ごとに複数の条件を判定する
    • ASCII control characterかどうかを確認
    • \n、\r、\t、\f、\bかどうかを確認
    • "または\かどうかを確認
  • ルックアップテーブル方式では、この判定を静的配列として事前計算し、各文字ごとに複数比較する代わりに動的offsetからbooleanを読む
  • 静的メモリを少し多く使う代わりに、ループは大幅に高速化する
  • ほとんどの文字列にはエスケープが必要な文字が含まれないという前提のもと、Mameはまずfast pathかどうかを低コストで確認し、該当する場合は文字列全体をまとめてバッファへコピーする前提条件を追加した
  • MameのpatchはCコードのためより複雑だが、同じパターンを使っている
  • この変更だけで、twitter.json生成ベンチマークは1258.1 i/sから1630.2 i/sへ向上し、1.30倍高速化した

続く最適化

  • 取り上げる最適化はまだ残っており、続編の記事が予告されている
  • その後、part twoが公開された

関連記事

1件のコメント

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

  • byrootの仕事は本当に大好き。貢献の種類だけでなく、生産性の規模がいつも驚異的
    Rubyコア周りに何度か入り込もうとしたことはあるけれど、自分の実力に合っていて前向きに貢献できる仕事を見つけられず、数週間成果が出ないとやる気がなくなってしまった。記事で共有されているような文脈を身につけるのが本当に難しいから
    RubyのC周りの人たちがもっと頻繁に記事を書いてくれれば、Rubyをさらに改善するために必要なスキルを持つ人がもっと増える気がする。Cプロファイラの助言も良かったし、Cコードを含むRuby gemを手に取って最適化をもう一度いじってみるところから始めてもいいかもしれないと思った

    • Peter Zhuの素晴らしい連載もある: https://blog.peterzhu.ca/ruby-c-ext/
      C拡張ではあるけれど、いくつかの概念を理解する助けになる
    • 「驚異的な生産性」もその通りだけど、本当にとてつもなく頭の切れる人でもある。Shopifyで同じオフィスで働いたことがあるけれど、到達不可能に見えるレベルの人だった

  • パート2も公開されている: https://byroot.github.io/ruby/json/2024/12/18/optimizing-rub...

  • 言及する価値があるものの一つが、Railsの標準的な使い方であるjbuilder。jbuilder自体はJSONシリアライズ部分ではないけれど、Ruby/RailsでJSONレンダリングを遅くする要因を挙げるなら自分のリストの一番上に来る
    jbuilderで大量のpartialをレンダリングすると本当に遅い

  • このテーマの記事は追いやすくて、自分のRubyコードもベンチマークして最適化してみたくなる。記事も作業も素晴らしかった

  • 見落としているかもしれないけれど、すべての最適化を適用した新バージョンがTwitter JSONダンプのパース/エンコードにどれくらいかかるのか書かれている場所はある？

  • 素晴らしい記事だし、仕事も見事。今後もまだOjを使う理由はある？

    • 著者です
      Ojには、標準のjson gemが真似しようともしていない非常に大きなAPIがある。たとえば「SAJ」（SAXスタイルのパース）や複数のエスケープ方式など
      自分の目標は、おおむね95%のユースケースでOjが不要になるようにすることだけなので、多くの用途では依然としてOjは有用だと思う

  • この記事が出たあと、この現在はメンテナンスされていない実装よりどれくらい速くなったのか気になる
    https://netflixtechblog.com/fast-json-api-serialization-with...
    この純粋なRuby実装はかなりきれいだと思ったけれど、実運用で使ったことはない。ずっと前に放置された状態
    全体として純粋Ruby実装の現状も気になる。json_pureがなくなったように見えるけれど、もしそうなら残念。詳しい事情を知っている人はいる？ 記事で一番興味深いのはC最適化よりRuby最適化の部分

  • 面白く読んだ。ただ、Ruby特有ではない最適化、たとえばエスケープ文字用のルックアップテーブルのようなものについては、なぜsimdjsonのような既存ライブラリを活用しないのか気になる

    • ある程度はhttps://news.ycombinator.com/item?id=42450085で答えている
      手短に言えば、ruby/jsonはRubyと一緒に配布されるのでRubyの制約に適合しなければならず、現時点では純粋なC99で、C++は使えないということ。simdjsonのApache 2ライセンスも問題になるかもしれないが、確信はない
      全体としてdragonboxのような優れたC++ライブラリを使いたいけれど、それはできない
      それから最後に確認したとき、simdjsonはパーサしか提供していなかった。ruby/json gemはパースとエンコードの両方を行うので、問題領域の半分にしか役立たない
    • この記事の良いところは、既存コードベースに対する実際のエンジニアリング作業だという点。少しでも速くするために何かをごっそり置き換えたりライブラリを切り替えたりするのではなく、実際のコードを掘り下げて、速度だけでなく効率まで本当に改善しようとしている
      現代のプロジェクトでは、こういう作業があまりにも不足している。こうしたことがもっと定期的に行われていたなら、そもそもsimdjsonやojのようなライブラリが必要だったのかと思う。この問題領域はそこまで難しくない

  • Ruby JSONはintrinsicsを使う？ 使える？
    それと複数のJITとはどう噛み合う？

    • intrinsicsが正確に何を指しているのかはよく分からない
      json gemはCで実装されているので、YJIT、つまり参照実装のJITから見るとブラックボックス
      TruffleRuby JITは以前、sulongでC拡張を解釈して言語境界をまたいでJITできたが、把握している限りでは、いくつかの互換性問題のため最近はその方式をやめている
      さらにTruffleRubyではJSONパーサはCで実装されているが、エンコーダは純粋なRuby: https://github.com/ruby/json/blob/e1f6456499d497f33f69ae4c1a...

  • 記憶が正しければ、分岐予測ヒントは現代のCPUでは役に立たない

    • 現代のCPUでは役に立たなかったが、一部のCPUでは再びある程度有用になっている。 https://www.phoronix.com/news/GCC-Clang-Intel-x86-Branch-Hin...
      「Redwood Coveマイクロアーキテクチャ以降、予測器にその分岐に関する保存済み情報がなく、かつその分岐にIntel SSE2 branch taken hint、つまり命令プレフィックス3EHが付いている場合、コーデックが分岐をデコードするときに分岐予測をnot-takenからtakenへ反転させる。その後、フロントエンドのパイプラインをflushし、taken側の経路を取るようパイプラインを誘導する
      ...
      このヒントは、予測器にその分岐に関する保存済み情報がない場合にのみ使われる。コード膨張や命令fetch帯域幅の低下を避けるため、反復回数の多いループ内の分岐のようなhot codeの分岐にはヒントを追加すべきではない。予測器がその分岐に関する情報をすでに保存している可能性が高いためだ。理想的には、まれにしか実行されないが大半がtakenとなる分岐にだけヒントを追加すべきだが、そのような分岐を特定するのは難しいことがある。コンパイラは、一方の実行経路をfall-throughとして配置できない場合、プロファイルベース最適化の一部としてヒントを追加することが推奨される。Redwood Coveマイクロアーキテクチャは、ヒント配置を導くための新しい性能モニタリングイベントを導入した」