serde_jsonの文字列処理を20%高速化

 (purplesyringa.moe)
2 ポイント 投稿者 GN⁺ 2024-08-25 | 1件のコメント | WhatsAppで共有
  • Rustエコシステムで事実上の標準JSONパーサとして使われているserde_jsonは、文字列が多いベンチマークにおいて、小さな内部最適化だけで**10%、23%、32%**の性能向上を達成
  • エラー位置の計算は、文字列の先頭を直接なぞる代わりにmemchrで行数と最後の改行を見つける方式に変更され、成功パスより2倍以上遅かったエラーパスとの性能差が縮小
  • 文字列パースの中核ループは、\\、\"、制御文字を別々に探さず、SWARで一度に検査することで、実際のSIMDなしでも短い文字列で低レイテンシを確保
  • \\u escapeのデコードは、LUT、符号付き整数、事前シフト済みテーブルで分岐とshiftコストを削減し、ロシア語版War and PeaceのJSONパースは284 MB/sから344 MB/sへ高速化
  • その後ボトルネックになったUTF-8エンコードは、char::encode_utf8とVec::extend_from_sliceの初期化・コピーコストを避ける手動UTF-8生成で処理し、同じベンチマークは374 MB/sまで向上

なぜserde_jsonの最適化が大きな効果を持つのか

  • serdeはRustを代表するシリアライズ・デシリアライズフレームワークであり、serde_jsonはJSON処理の公式な組み合わせとして広く使われている
  • 掲載時点でserde_jsonの逆依存は26,916件、simd-jsonは66件だった
  • これほどの利用規模では、serde_json内部の小さな改善でもRustエコシステム全体に累積効果をもたらせる
  • 多くの利用者が他のJSONパーサへ簡単に置き換えない状況では、既存ライブラリ内の低リスク最適化が実用的

エラー位置計算: 単純ループからmemchrへ

  • エラーパスのベンチマークでは、serde_jsonは同じデータの成功パスより2倍以上遅かった
    • canada、citm_catalog、twitterデータセットで、エラーパスは成功パス比で**-48%〜-77%**遅かった
  • ボトルネックは、エラーメッセージの整形のためにインデックスをline/columnへ変換するposition_of_index()関数だった
    • 従来実装はself.slice[..i]をバイト単位で走査し、\nに出会うたびにlineとcolumnを更新していた
  • 計算を2段階に分けるとmemchrを適用できる
    • self.slice[..i]内の\nの個数を数えて0始まりのline番号を求める
    • 最後の\nの位置を見つけ、iから引いてcolumn番号を求める
  • memchrは単一文字検索と個数カウントに最適化された実装を提供し、内部的にSIMDを使用する
  • PR #1160がマージされた後、エラーパス性能は大幅に改善
    • canada DOM基準でエラーパスは122 MB/sから216 MB/sへ向上
    • citm_catalog struct基準では195 MB/sから736 MB/sへ向上
    • エラーパスは依然として成功パスより遅いが、その差は縮小した

文字列エスケープ探索: 3条件を一度に見つける

  • 文字列パースの従来の中核ループは、ESCAPEテーブルを見ながらエスケープ不要のバイトを読み飛ばしていた
    • JSON文字列で処理すべきエスケープ対象は\\、\"、および0x1F以下のASCII制御文字
    • JSON仕様上、文字列内の制御コードは許可されない
  • 最初の試みは、memchr2で\\または\"を先に探し、その後で制御文字を別途確認する方式だった
    • 文字列を高速に1回、低速に1回の2回走査することになり、従来より遅かった
    • 単純に半分だけベクトル化し、残りをスカラーのままにしても全体改善にはつながらなかった
  • 2回目の試みは、memchr2と手動SIMDで制御文字がないか確認する構成だった
    • 短い文字列では実行時選択関数の呼び出しコストが重い
    • 長い文字列ではメモリを2回読む問題が残る
  • 最終実装は、\\、\"、制御文字を1回のパスで見つける方向に整理された

SWARでSIMDに近い処理を実装

  • プラットフォーム別のSIMDコードを個別に追加しないため、**SWAR(SIMD Within A Register)**手法を使用
    • 128ビットSIMDの代わりに64ビットワードを8バイトのように扱う
    • ビット演算で各バイトが条件を満たすかを同時に検査する
  • 制御文字の検査はc >= 0 && c < 0x20条件をビット演算の形に変換して処理
    • 8バイト単位では!c & (c - 0x2020202020202020) & 0x8080808080808080というマスクで確認する
    • 64ビット減算のborrowが上位バイトへ伝播する可能性はあるが、最も低い位置の制御文字を見つける目的では問題にならない
  • \\と\"も同様の方法で検査し、1つの式にまとめた
    • 全体の式は9個のビット演算で構成される
    • x86 SIMDなら7演算で済むためスループットは劣るが、短い文字列ではレイテンシの方が重要
  • json-benchmarkでは、このSWARコードが実際のSIMDコードより効率的だった
  • 非常に短い文字列ではSWARがスカラーコードより遅くなることがある
    • およそ5文字の文字列で回帰が見られた
    • 空文字列\"\"や連続escapeの\\r\\n、\\uD801\\uDC37のような一般的パターンを守るため、SWARループに入る前に先頭文字がescapeかどうかを確認する
  • 文字列探索最適化の結果はデータセットごとに異なった
    • twitter structは638 MB/sから785 MB/sで**+23%**
    • twitter DOMは305 MB/sから335 MB/sで**+10%**
    • citm_catalog structは865 MB/sから905 MB/sで**+5%**
    • 空文字列は一部のマイクロベンチマークで依然として2%以内の範囲で遅くなった

Unicode escapeデコードの最適化

  • serde_jsonは生のUnicode文字列と\\u escapeの両方を処理する
    • 例: \"🥺\"と\"\\ud83e\\udd7a\"
  • 従来のhexデコードは256要素のLUTを使い、各文字を0〜15の値へマッピングしていた
    • '0'..='9'、'A'..='F'、'a'..='f'を処理する
    • 不正な文字はセンチネル値で表していた
  • \\u escapeは4つのhex digitを読むため、従来方式では反復ごとにshift、加算、比較、条件分岐が入っていた
  • 改善実装では、反復のたびにエラーを返すのではなく、4桁すべてを処理した後で妥当性を確認する
  • 最終実装は[i8; 256] LUTで不正なdigitを-1とし、32ビット整数で計算する
    • 成功時は結果が負にならず、失敗時は負になる
    • x86ではメモリロードとsign extensionがmovsxに統合できる
  • shiftレイテンシを減らすため、2つのテーブルを使う
    • HEX0: 元の値
    • HEX1: 値をあらかじめ4ビット左シフトしたテーブル
  • ループを明示的にunrollしたdecode_four_hex_digits()実装へ整理された
  • この最適化により、ロシア語版War and PeaceをJSONエンコード形式でパースする性能は284 MB/sから344 MB/sへ向上し、**21%**改善した

UTF-8エンコードのボトルネックと手動生成

  • Unicode escapeデコード後のボトルネックはUTF-8エンコードへ移った
  • UTF-8はcodepointを長さに応じて1〜4バイトにエンコードする
    • 1バイト: 0xxxxxxx
    • 2バイト: 110xxxxx 10xxxxxx
    • 3バイト: 1110xxxx 10xxxxxx 10xxxxxx
    • 4バイト: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
  • Rust標準ライブラリのchar::encode_utf8は&mut [u8]バッファへ書き込むため、バッファにはあらかじめ有効なu8値が入っている必要がある
    • 未初期化バッファへそのまま書き込むことはできない
    • UTF-8は可変長エンコーディングなので、LLVMが不要なzeroizationを除去しにくい
  • serde_jsonはscratch.extend_from_slice(c.encode_utf8(&mut [0u8; 4]).as_bytes())という形で処理していた
    • ローカルの[0u8; 4]バッファを使えば理論上はalias解析が役立つ可能性がある
    • 実際には1〜4バイトの可変長コピーのため、LLVMはmemcpy呼び出しを生成していた
  • memsetとmemcpy呼び出しを避けるため、UTF-8を直接生成した
    • アルゴリズム自体は単純だがunsafeが必要だった
    • いくつかの小変更と合わせて、War and Peaceベンチマークは344 MB/sから374 MB/sへさらに**+9%**改善した

最終結果

  • 文字列が多いJSONベンチマークで、serde_jsonの性能はそれぞれ**10%、23%、32%**改善した
  • 多くのJSONデータは文字列を多く含むため、この最適化はserde_jsonを使うRustコード全体に影響を及ぼす可能性がある
  • 改善は、エラー位置計算、文字列escape探索、Unicode escapeデコード、UTF-8エンコードといった異なるボトルネックを順番に解消する形で進められた

関連記事

1件のコメント

 
GN⁺ 2024-08-25
Hacker News の意見

  • UTF-8 のトリックは、パーサー混乱攻撃をあまりにも多く見てきたのでかなり不安
    serde は速度よりも正確性を重視して使う側なので、不正な UTF-8 文字列を大量に入れて最後までファジングしていてほしい

    • 幸い UTF-8 の構造は平均的なパーサーに比べて非常に単純
      バグがないという意味ではないが、パーサーの内部状態は大きくないはずで、網羅的テストも可能に見える
    • こういう領域こそ、ファザーを走らせた結果を見たい
    • この種のバグで、すぐ思い浮かぶ事例があれば教えてもらえる？

  • serde がこれほど速く動いているのは素晴らしい
    さっき simdutf8 を見ていて、SIMD 対応 UTF-8 パースの PR がほぼ 5 年越しだと知った
    https://github.com/rust-lang/rust/issues/68455

  • この人のブログから強い jart 感が出ていて、楽しく読めた
    「車輪を再発明しなければならないだろうが、考えてみるとなかなか素敵だ」というくだりは、本気なのか皮肉なのか分からない
    読んで著者を笑いものにしながら笑い始めたが、ページの残りはかなり自虐が強いように見える

    • その言葉は、車輪を再発明しなければならないという事実ではなく、アプローチがなかなか素敵だという意味だと思う
    • jart ってどういう意味？

  • 「考え方を教えることは、コーディングを教えるのと同じくらい重要だが、ほとんど行われていない」だなんて
    相手が考えていないと見なす傲慢さを感じる

    • その文に傲慢さはないと思う
      他の人が考えていないと仮定しているのではなく、ほとんどのブログ記事や使い方記事は最終結果だけを示し、そこに至る段階を必ずしも見せない、という観察に近い
    • 著者はそんな主張をしているわけではない
      考え方を教えるというのは、調査しなければならず、その段階を飛ばせないし、調査したからといって自分で結論を出す責任がなくなるわけでもない、という意味
      どちらか一方を飛ばすのは簡単だが、間違ったやり方

  • serde_json はデバッグビルドとリリースビルドを一度ずつ行うと、依存関係が3GBにもなる
    活発なプロジェクトをいくつかで serde を使うとディスク容量が尽きる
    JSON パースにどうして 3GB の依存関係が必要なのか分からないし、コード再利用には賛成だが、serde の JSON 側の依存関係はかなり雑然として見える
    その依存関係の一つからエクスプロイトが出るだけで、Rust エコシステムの半分が脆弱になる
    Rust には JSON が組み込まれるべき

    • 依存関係は 5 つだけで、そのうち 1 つはオプション、もう 1 つは serde 自体: https://github.com/serde-rs/json/blob/master/Cargo.toml
      indexmap = { version = "2.2.3", optional = true }
      itoa = "1.0"
      memchr = { version = "2", default-features = false }
      ryu = "1.0"
      serde = { version = "1.0.194", default-features = false }
      3GB の依存関係と言うとき、実際に測ったものがそれではない可能性が高い
      証拠なしに事実のように言っているので確信はできないが、推測するなら #[derive(Serialize, Deserialize)] を大量に使ってコードが大量生成され、その後 target ディレクトリ全体のサイズを測っているように思える
      単純なビルドは、他のコメントが示しているように数十 MB 規模になる
    • Rust に JSON を組み込むのは妥当なアプローチではないと思う
      それは肥大化を招くやり方でしかなく、標準ライブラリは安定性保証以外では他のクレートと変わらないため利点がない
      結局、ライブラリのリリース周期をコンパイラのリリース周期に縛る効果しか生まない
      実際、昔は rustc-serialize が組み込みに近く、Rust はすでにその方向を試したことがある
      そしてデフォルト状態の serde_json は大きくない
      serde_json も serde も大きくなく、どちらも他のクレートがあまりサポートしない非常に低い MSRV を維持しているので、実質的に依存関係を多く持つこともできない
    • 依存関係の肥大化は Rust 全般の問題
      ある程度の規模がある Rust プロジェクトの依存関係ツリーはすぐかなりひどいものになり、このすべての依存関係を監査するのは現実的に不可能で、多くに対する信頼度も低い
      数年間 Rust で仕事をしてみてからは、エコシステムがはるかに成熟するまでは Rust を再び触ることはなさそう
      その成熟は大企業による採用があってこそ来るもので、そうでなければ no-std、no-deps、純粋な C 代替用プロジェクトでしか使わないと思う
      ただし Zig が安定化すれば、この用途でも Rust を押しのける可能性がある
    • Rust はデバッグ情報を異常なほど大量に吐き出す
      あまりにも奇妙に大きいので、単にバグだろうと予想している
      何をコンパイルしても target フォルダにギガバイト単位で積み上がるが、デバッグ情報を削除したり、少なくとも詳細度の低い設定を使ったりした後の最終成果物を代表するものではない
    • ある程度の規模があるプロジェクトなら、target フォルダは文字どおり常に最低でも数 GB にはなる気がする