ハクソク

世界を動かす技術を、日本語で。

これまでにない方法でのProtobufの解析

312日前原文(mcyoung.xyz)

概要

  • hyperpb はGo向けの高性能Protobufパーサライブラリ
  • UPB の最適化をGoに移植しつつ、独自の最適化も多数導入
  • Goの ランタイム特性 を活かした設計とJIT的PGO（プロファイルガイド最適化）対応
  • 競合他製品と比較して圧倒的な性能 を実現
  • 設計思想・API・内部構造・最適化手法の概要解説

Go向け高性能Protobufパーサ「hyperpb」の設計と最適化

  • Protobuf の高速パーサ開発経験（C++/Rust/UPB統合）を活かしたGo用新規実装
  • hyperpb はUPBのノウハウをGoに移植しつつ、Go独自の最適化も追求したライブラリ
  • AMD Zen 4 環境でベンチマークを実施し、Go向け他パーサ（標準・vtprotobuf等）より高いスループットを記録
  • hyperpbは ゼロコピー/アリーナ再利用/PGO など複数の最適化を段階的に適用可能
  • 競合実装との比較ベンチマークでは、 全ての最適化を適用したhyperpbが圧倒的な性能 を発揮

生成型パーサの課題とUPBアプローチ

  • 従来のProtobufパーサは 型ごとに専用コードを生成 する方式
    • 型ごとに事前コンパイルが必要
    • 多数の型を扱うと 命令キャッシュの効率悪化 や デコードスループット低下 が発生
    • 巨大なswitch文やバイナリサーチによる分岐遅延
  • UPB はCで書かれた動的パーサカーネル
    • パーサはデータテーブルに基づく テーブル駆動型インタプリタ
    • 各言語でC FFI経由で利用可能
    • アリーナ最適化 による高速メモリアロケーション

hyperpbがGoでUPBを再発明した理由

  • Goの cgo（C FFI） はパフォーマンス・メモリ管理・スケジューラ連携が非常に非効率
    • CメモリとGo GCの相互運用が困難
    • C呼び出しが遅く、Goスケジューラとの相性も悪い
  • Go独自の特性を活かした新規実装を選択
    • x86_64のレジスタABI でパーサ状態を全てレジスタ渡し
    • Go特有の 未定義動作の少なさ を利用した「邪悪な」ポインタ最適化
    • Goの 反射API （protoreflect）への最適化
    • 起動時コスト許容 の文化を活かし、インタプリタのプログラムを ランタイム生成 （オンラインPGO/JIT）

hyperpbのAPI設計

  • hyperpb.Compile 系関数でメッセージディスクリプタからhyperpb.MessageTypeを生成
  • *hyperpb.MessageTypeから 新しいメッセージインスタンスを生成 し、proto.Unmarshalでデシリアライズ
  • 反射APIを通じて Bufのprotovalidate 等のバリデーションライブラリと連携
  • メッセージの ミューテーション（書き換え）は未対応 （主用途が読み取りのため）
  • コンパイルは高コスト なのでキャッシュ推奨（regexp.Compileと同様の設計思想）
  • PGOプロファイル を利用し、実際のワイヤデータに最適化した再コンパイルが可能

コア実装構造（internal/tdp配下）

  • tdp ：インタプリタ用「オブジェクトコード形式」の定義
    • 型・フィールド情報の保持
  • tdp/compiler ：protoreflect.MessageDescriptorからtdp.Libraryへの変換ロジック
  • tdp/dynamic ：動的メッセージ型の定義とレイアウト管理
  • tdp/vm ：インタプリタVM本体、パーサ状態管理、varint解析・UTF-8検証の最適化ルーチン
  • tdp/thunks ：フィールドのアーキタイプ管理（約200種）

tdp.Typeとフィールド管理

  • ルートメッセージから到達可能な全MessageDescriptorが tdp.Type として管理
  • 各tdp.Typeは 動的サイズ・デフォルトパーサ・フィールド情報 を保持
  • tdp.TypeParser はエンコード済みProtobufデータの解析用情報をコンパクトに保持
    • 各フィールド/拡張ごとに tdp.FieldParser を持つ
    • タグ対応・パース関数・次に試すフィールド情報 を持つことで分岐コスト最小化
    • フィールドスケジューリング （宣言順・PGOによる「ホット度」考慮）で分岐予測最適化
  • cold region 管理
    • 大半のメッセージで未使用な拡張や低頻度フィールドは 別領域（cold region） に遅延確保
    • 必要時のみcold regionを割り当て、メモリ効率と高速化を両立
    • cold判定はPGOで動的に変化

パーサVMの最適化

  • Goの ABIを最大限活用 し、パーサ状態（8つの64bit整数）をレジスタ渡し
  • vm.P1/vm.P2 構造体で状態管理（Goコンパイラの制約回避のため分離）
  • 全パーサ関数はこれら2構造体を引数・戻り値に持つことで レジスタ間のみで状態遷移
  • スタック利用最小化 による高速化

hyperpbの今後の展望と参考情報

  • さらなるPGO最適化 （分岐予測アルゴリズムの精緻化）に取り組み中
  • internal/arena パッケージによるGCフレンドリーなアリーナ管理（詳細は別ブログ記事参照）
  • 詳細・セールスポイントは Buf公式ブログ にも掲載

Hackerたちの意見

つまり、UPBパーサーは実際にはインタープリタVMの設定で、Protobufメッセージをバイトコードとして実行するんだ。ちょっと混乱するけど、VMは特定のprotobufメッセージタイプだけを解析するために作られてるの？第二のフタムラ投影、かな…それとも、VMは一般的なprotobufメッセージに特化していて、ランダムなメッセージも解析できるけど、それがprotobufメッセージでないとダメなの？似たようなシステムの設計に取り組んでるけど、一般的なバイナリ解析用（バイソン/yaccみたいな）で、特化したVMでデータを扱うか、一般的なVMでバイトコード+データを扱うかは考えてもみなかった。正直、'最大の怠惰'を考慮して設計されてるから（入力を解析・検証してメタデータを作成するだけで、実際に使うバイトのデコードにしかお金を払わない）、I/OのオーバーヘッドがVMのディスパッチよりもはるかに大きいから、これを試すのは「早すぎる最適化はすべての悪の根源」的なケースかもしれないけど、興味深いね。

└

protobufの内部構造について知っていることから、UPBが何をしているのか深く見ていないけど…おそらくスタックマシンで、(バイト)+をオペコードとして扱っているんじゃないかな。大体、パーサー -> AST -> バイトコードって考えるけど、protobufの「文法」なら、パーサーが解析した端末をそのままVMに命令として送ることができると思う。

└

これについて少し説明できると思うよ、upbの創設者でリーダーだからね。Protobufパーサーを「インタープリタVM」と呼ぶのは、ちょっとした誇張だと思う。これは、数年前に記事で初めて気づいた、両者の深い構造的類似性から来てるんだ。 > インタープリタループとprotobufパーサーを比較するのは奇妙に思えるかもしれないけど、protobufのワイヤフォーマットの性質が思ったよりも似ているんだ。protobufのワイヤフォーマットは、タグ/値ペアの連続で、タグにはフィールド番号とワイヤタイプが含まれている。このタグはインタープリタのオペコードに似ていて、フィールドのデータを解析するために何をする必要があるかを教えてくれる。インタープリタのオペコードと同じように、protobufのフィールド番号はどんな順番でも来るから、いつでもコードのどの部分にでも飛べるように準備しておかなきゃいけない。つまり、protobufパーサーの全体的な構造は、VMインタープリタと同じように、while()ループがswitch()文を囲んでいる概念的なものなんだ。難しいのは、Protobufパーサーの「case」ラベルのセットがメッセージ固有で、スキーマのフィールドによって定義されていること。これをどうやって対応するか？従来の答えは、メッセージごとに関数を生成して、スキーマのフィールド番号をcaseラベルとして使うことだった。ここにその例があるよ（C++で）: https://github.com/protocolbuffers/protobuf/blob/f763a2a8608... 最近では、Protobufの解析をもっとデータ駆動型にして、各フィールドのスキーマをデータにコンパイルして、一般的なProtobufパーサー関数に引数として渡すようにしている。これを「テーブル駆動解析」と呼んでいて、ブログ記事を読む限り、ミゲルがhyperpbでやっていることだと思う。じゃあ、このテーブル駆動のディスパッチをできるだけ速くするにはどうすればいいか、それがswitch()文がやっていたことをシミュレートするための課題なんだ。この質問については、上記の記事で詳しく説明しているよ。

Protobufの良い部分をCBORのような標準化されたシリアライズフォーマットに持ってくる作業がもっと見たいな。gRPC-webをWHATWGストリームやWebTransportのようなものに持っていくのも同じことを言えると思う。両方にすごくクールで重要な学びがあるけど、変なツールや前提に縛られすぎてる。IETFとW3Cの標準に基づいて再構築しようよ。

└

CBORのエンコーディング/デコーディングをブラウザAPIとしてサポートしてほしいな。今はWebAuthnで内部的にCBORを使ってるから、そんなに難しくないといいんだけど。

└

これ簡単にできるよ。Protobufはプラグイン可能なライターをサポートしてるし、スキーマを反復処理するのもかなり簡単。JSONBのためにやってるし。ただ、目的がよくわからない。Protobufは柔軟性のないスキーマが素晴らしいし、CBORは柔軟なデータ表現がいい。別のCBORスキーマの方が合ってると思う。CDDLもあるけど、あまり普及してないよね。

これ素晴らしいね。Goの内部が速いインタープリタを書くのを難しくしてる様子を詳しく説明してる。自分よりもずっと速くしようと決意してる人が書いてるから、余計に興味深い。速いインタープリタを書くことはGoチームがあまり気にしてないユースケースだと思ってたけど、もしprotobufの解析が速くなるなら、注目されるかもしれないし、こういう低レベルのトリックが必要なくなるかも？

└

そして、これらの低レベルのトリックはもう必要なくなるの？ それは期待しない方がいいよ。この言語はGolangだから。

このデザインのボトルネックを正しく特定できてるかな？1. GoのFFIが遅い 2. プロトタイプごとの生成コードの特化が遅い、キャッシュ圧力のせいで。最適化の話はもっとあると思うけど、VMを選ぶ主な理由はこれだと思う。単にコード生成を良くするか、Go以外でパーサーを実装するよりも。

└

GoのC FFIが遅いってよく聞くけど、なんで？他の言語と比べてどれくらい遅いの？

└
  1. ユースケースは動的スキーマで、アクセスはリフレクションAPIを通じて行うんだ。だからPGOはランタイムでやらなきゃいけないんだよね…

関連スレッド: Hyperpb: より速い動的Protobuf解析 - https://news.ycombinator.com/item?id=44661785

すべてのタイプは命令キャッシュにコストをもたらすため、プログラムが多くの異なるタイプを解析すると、パーサーに入るたびに命令キャッシュがフラッシュされることになる。さらに悪いことに、解析に十分なタイプが関与すると、パーサー自体が命令デコーディングのスループットの問題に直面する。面白いね。これを聞いて、nanopbがグラフに示されたパーサーとどのようにベンチマークされるか気になる。nanopbの特徴は、純粋なC99で、各メッセージのために別々の解析関数を生成しないことなんだ。nanopbは、小さなフットプリントのために多くの組み込みコードで使われてる。

前にmsgpackとprotobufをベンチマークした時は、僕の使い方ではほぼ同じだったんだよね。JSONは2～3倍遅かったけど、msgpackとprotobufはほぼ同じだった。今回のリリースで変わってるかもしれないし、楽しみだね :)

└

著者が話しているパフォーマンスのボトルネックは、大規模な使用で現れることが多いから、ベンチマークでは見えないかもしれないってことを覚えておいてね。特に、「いろんなタイプを解析しすぎると命令キャッシュが吹っ飛ぶ」問題は、実際にたくさんのタイプを解析している時だけ現れるから、そうじゃなければUPBは必要ないよ。

これには二つの見方がある。一つは、もしあなたのコーデックの解析ライブラリにコンパイラ、VM、PGOが含まれているなら、そのコーデックは非常に呪われているに違いないから、一度立ち止まって自分の人生を考え直した方がいい。もう一つは、もしあなたのコーデックの解析ライブラリにコンパイラ、VM、PGOが含まれているなら、そのコーデックは非常に人気があって、ものすごい価値を加えているってことだ。

└

何かを1日に数百億回やりたいなら、効率よくやりたいよね。

ちょっと話が逸れるけど、CapnProtoを使っている人いる？ProtoBufの元メンテナー（ここではkentonv）のその後のプロジェクトだよ。https://capnproto.org もし使っているなら、実際にはどう比較されるの？（Cloudflare Workersは何を使ってるの？）

└

Cloudflareはほぼ完全にCap'n Protoで動いてるよ、ワーカーズプラットフォーム全体もね。

└

これに関連して、フラットバッファを使ってる人いる？ CapnProtoと同じ問題を解決して、Arrowの基盤にもなってるよ。昔使ったことあるけど、もうずいぶん前だから今の状態は分からないな。

バイトコードVMのJITは本当に素晴らしいみたいだね。PythonのAvroでも似たようなトリックが使えるよ（https://journal.spencerwnelson.com/entries/avro.html）。要するに、スキーマ文書はプログラムみたいなもので、ちょっと変な言語だけど、コンパイルされたプログラムは速いってことだね。