ハクソク

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

無作為なデータでベンチマークを行ったため、アセンブリの手動最適化に数週間を無駄にしました

293日前原文(vidarholen.net)

概要

  • Java最適化の現場で、分散データ処理プラットフォームのパフォーマンス向上に取り組んだ経験談
  • VarIntエンコーディングのCPUコストに着目し、SIMDアセンブリによる高速化を実施
  • ベンチマークでは大きな高速化を確認したが、実運用では効果が現れなかった理由の発見
  • ランダムな値と実際のデータ分布の違いが、最適化評価に大きく影響する事例
  • 最終的に変更をロールバックし、JIT最適化の知見を得たエピソード

Java最適化現場の挑戦とVarIntエンコーディング

  • 分散データ処理プラットフォーム開発現場での経験
  • 数十万台規模のシステムで 0.5%の改善 でも大きな価値
  • 既に徹底的に最適化された Javaコードベース
  • java.lang.String の最小限利用、GC負荷軽減策
  • さらなる最適化余地を求めた プロファイリング
  • データシリアライズ、特に VarInt（ULEB128）エンコーディング に着目

VarInt（ULEB128）エンコーディングの仕組み

  • 任意精度整数 を効率的にエンコードする方式
  • 7ビット単位で数値を分割し、8ビット目で継続判定
  • 1バイトで7ビット未満、2バイトで14ビット未満 など、リトルエンディアン順
  • 32bit intは 1～5バイト、64bit longは 1～10バイト
  • Google Protobuf, Apache/Facebook Thrift, WASM, DWARF などで採用

超最適化VarIntエンコーダの開発

  • encodeLong(byte[] buffer, int offset, long data) ：バイト数を返すインターフェース
  • 通常はネイティブコード化のメリットが小さいとされる領域
  • JVMのフォーク、独自最適化インフラ を活用
  • JIT直列化、JNIオーバーヘッド回避
  • SIMDアセンブリ（BMI2, AVX2） による分岐なし高速化
  • 既存Java実装の4倍のパフォーマンス をベンチマークで確認
    • 数十億件のランダム値でテスト、互換性も検証
  • 実装、テスト、統合、リリースまで2週間

ベンチマークと実運用のギャップ

  • 本番環境での効果測定： 差分ゼロ
  • ランダム値ベンチマークの落とし穴
    • 64bitランダム値 では大半が 9～10バイト 必要
    • 実際のデータはほとんどが 2バイト以下 で表現可能
    • VarIntの設計意図： 小さい数字が多い現実
  • Java実装は出力バイト数が増えるほど負荷増
  • 最適化効果が現れたのは 最悪ケースのみ だった事実
  • 現実的な分布 で再ベンチマーク→高速化効果消失

結論と学び

  • 変更をロールバックし、 JIT最適化の知見 を蓄積
  • SIMD最適化 の実践経験を得る
  • ベンチマーク設計の重要性、実データ分布の理解
  • 最適化は 現実的なユースケース を想定することが不可欠

Hackerたちの意見

これ、ベンフォードの法則を思い出すな。「ベンフォードの法則、別名ニューカム・ベンフォードの法則、異常数の法則、または最初の桁の法則は、多くの実際の数値データセットにおいて、先頭の桁が小さい可能性が高いという観察です。」

代表的な使用シナリオを特定して最適化するのは、マイクロベンチマークテストドライバーでそのシナリオを実装するのも、どちらも正しくやるのがめっちゃ難しいんだよね。著者が言ってたように、こういう「失敗」は、時間をかける前に気づくのが難しいことがある。配列を検索するみたいな一見 trivial なシナリオでも、配列の内容や長さが結果や最適化方法に大きな影響を与えるから、最後のセクションで検索アルゴリズムを正しくベンチマークしようとしたところでもそれが分かるよ。完璧な解決策は見たことないけど、「テストセットアップを慎重に考える」以外の方法はあまり見かけないな。（プロファイルガイド最適化や、本番プロファイルを再生してベンチマークするのは代替案になりそうだけど、あまり使われてるの見たことない。）

└

実際のユーザーからの文字列を、非常に少数の文字クラスにマッピングするフィルターを適用する能力を求めたことがあるんだけど、そのためにコーデック用のデータをユーザーデータに相当するものとして扱いたいんだ。聞いたところによると、これは時間の無駄だってさ。本当に気にするなら、ユーザーが作成した文字列の本番データ分布について色々推測して、それぞれを展開して一番良いものを残せばいいんじゃないかって。

└

代表的な使用シナリオを特定して最適化するのは、マイクロベンチマークテストドライバーでそのシナリオを実装するのも、どちらも正しくやるのがめっちゃ難しいんだよね。著者が言ってたように、こういう「失敗」は、時間をかける前に気づくのが難しいことがある。これには私も同意するよ。ウェブパフォーマンスを15年近くやってるけど、明確な代表的な問題を見つけるのが仕事の中で一番難しい部分の一つだもん。これを理解して、代表的な問題を見つけるスキルを上げるために努力したら、それが私の生産性を一番上げることになったんだ。

└

プロファイルガイド最適化の一部だけど、私はかなり頻繁に、代表的なケースからサマリーヒストグラムを集めて、それを使って自分の仮定を検証してる。（たまに、似たような分布を生成するベンチマークを書くこともあるけど、正直言って大体は「このケースは本当に珍しいと思う」って感じで、それが本当に珍しいか確認するだけなんだ。）

└

もし彼らがそのJVMをフォークして、広い開発者層に開発ツールとして提供するためにやっているなら、その最適化は残しておく価値があるかもね。誰かが大量の大きな整数をシリアライズするアプリケーションを持っているかもしれないし。これを放棄する理由はあまり強くないよ。誰が何をしているか分からないからね。プログラミング言語のランタイムやコンパイラでは、「この改善が必要な人はいるのか？」っていう推測ゲームがあるんだ。だから「はい」と言える余地があるよね。 :)

例えば、java.lang.Stringの使用は最小限だった。だって、char[]の二回目の割り当てや関連する間接参照、GCのために時間を無駄にしたくないからね。こういう理由で、Javaを避けたいと思うんだ。JavaはJITコンパイルやGCのせいで遅いって評判だけど、非プリミティブタイプがすべてボックス化されたオブジェクトになるからだと思う。これって、ガベージコレクターをすごく働かせることになるし、ローカリティも悪くなるし、誰も使わないミューテックスみたいな余分なオブジェクトでRAMやキャッシュが埋まっちゃうんだ。（今はかなりの努力の末に8バイトになったらしい。）

└

C++ユーザーもStringについて全く同じことを言ってるわけじゃないからね。問題は、Stringが本当に言語のプリミティブじゃないってこと。人やプログラムによって、Stringが何をすべきかの考え方は常に違うんだ（可変にすべき？常に有効なUTF-8であるべき？どの操作がO(1)、O(n)またはO(n log n)であるべきか？など）。

└

dotnetがこれを認めて、スタック上の値型やSpanのようなもののために最近たくさんの仕組みを提供しているのが好きだな。配列のコピーを減らすためにね。

反論：一度、CUDAを使ってブロック暗号（AESなど）を加速する論文を書いたことがあって、その時に気づいたんだけど、ほとんど（もし全て）以前の学術研究は、ゼロバイトでのベンチマークだけで驚異的なスピードアップを主張してたんだ。これらのブロック暗号はルックアップテーブルを使って実装されているから、暗号化される各ブロックで完璧なキャッシュヒットがあったってことだ。ランダムデータでのベンチマークは、全然違う、私の意見ではもっと現実的な状況を描いていたよ。

└

それなら、実際のデータを使ったらどう？大きなPDFやアーカイブを取得して、それをベンチマークに使うとか。

└

こういう論文は膨大にあるよ。私はFPGA上で小さなCNN分類器を加速する論文を書いたんだけど、前のSOTA GPU実装と比較したら、数字が論文と全然違ってた。彼らのリポジトリでgit blameをしたら、論文が発表された後に、サンプルがすべて0のときにevalをショートサーキットする行を削除していたことが分かったんだ（彼らの合成データの多くはそうだったし ¯_(ツ)_/¯）。

アセンブリ言語の最適化にかけた時間は決して無駄にはならないよ。これ、半分は皮肉だけどね。「無駄だった」っていうのは、OPが思ってたほど役に立たなかったって意味で。でも、技術的な問題に深く潜ることは、OPの心に消えないパターンを残したんだ。もしまたそんなことをやることになったら、絶対に楽になるよ。そして、AIが簡単なコーディングタスクを全部やるようになるから、人間は深くて難しいタスクに取り組まなきゃいけなくなるね。

└

それは誰かを疲れさせて、技術が存在する本当の理由を奪うかもしれないよ：誰かを助けるためにね。

1バイトと2バイトのLEBのためのファストパスを、苦労して生成したアセンブリに追加しなかったのは意外だね。こういうファストパスは絶対に価値があると思う。例えば、WizardのWasmインタープリタは、1バイトのLEBをデコードするために3つの命令でファストパスを使って、その後一般的なケースを処理するためにライン外にジャンプするんだ。これでインタープリタのパフォーマンスが5〜10%向上するんだよ。

チャンドラー・キャルスは、彼のトークの中で似たような話をしてたよ。彼はケン・トンプソンに会って、初めて美しいCコードを見たんだ。サービスでパフォーマンスの問題に直面していたからね。そのサービスは、受信リクエストに基づいてポリシーを選ぶ必要があったんだけど、各ポリシーの基準をリクエストに対して照合するのに時間がかかりすぎていた。ケンは、すべてのポリシーの述語を同時に進める有限オートマトンベースのパターンマッチャーを書いたんだ。それは完璧で、既存のコードよりもずっと速かった。でも、誰かが99.9%のリクエストが特定のポリシーに一致することに気づいて、既存のコードをその述語だけを最初にチェックするように変更したら、コードが何億倍も速くなったんだ。ケンの解決策よりもね。

└

すごくいいエピソードだね、シェアしてくれてありがとう！なんか関連して思い出したけど、プロファイルガイド最適化について初めて聞いた時のことを今でも覚えてる。これは基本的にコード全体に対して同じことをするやつなんだけど（アイデアは同じだけど、君がシェアしたエピソードと同じ結果が出るほど攻撃的かどうかはわからないな）。

└

人気のリクエストタイプが変わらないならこれでいいけど、両方の新しいマッチングバージョンが十分に速いなら、リクエストタイプの分布が変わった時に他の方が再び遅くなる可能性があるから、ケンの長期的な方がいいと思うな。

似たようなことをする最適化されたvarintエンコーダを実装しようとしたんだけど、8バイトの値を埋め込んでからRAMに保存するやり方で、アラインされてないオーバーラップストアが大きなリグレッションを引き起こしたんだ。うまくいったアプローチは別の技術が必要だった。この方法は逆方向のエンコーディング用で、1. 1バイトの場合のブランチを常にインラインで、バイトをそのまま保存する 2. ブランチフリーの構造で未エンコードのゼロプレフィックスのサイズを計算する: (((uint32_t)clz + 7) * 9) >> 6 3. ARMの固定命令幅を利用してジャンプターゲットをシフトで計算するジャンプテーブルを手動で作成する。 https://github.com/protocolbuffers/protobuf/commit/b039dfe26... これで1バイトのvarint用に1つのブランチ、さらに大きなサイズ用にもう1つのブランチができて、ブランチ予測器はループ内で変動するトリップカウントを追跡する必要がなくなる。このアプローチで中型のARMコアで全体のエンコーディング（varintだけじゃなくてもっと色々含む）で2.64%のスピードアップが得られたよ。実際に前向きまたは後ろ向きにエンコーディングする場合、1バイトのケースで単一の比較とブランチを超えるのは難しいと思う。長い1バイトの値の連続があるってわかってる場合を除いてね。

Javaをここまで最適化する理由が気になるな。超高レベルの最適化ならCやアセンブリの方が良い選択だと思う。Javaも頑張れば似たようなパフォーマンスが出せるけど、少なくとも手動でメモリ管理をしたいって思うだろうね。

これ、https://ridiculousfish.com/blog/posts/old-age-and-treachery... を思い出させるな。データ条件は確実にランタイムパフォーマンスに影響を与えるよ。マイクロアーキテクチャレベルまでね。ランダム、ソート済み、逆ソート済み、均一なデータセットはパフォーマンスに劇的な違いをもたらすことが多い。そして「おっと、私のデータセットには意外に多くのNaNや非正規化フロートが含まれてた！」ってことになる。