すべてのバイトが重要です

9時間前原文(fzakaria.com)

概要

Java開発経験 からくる「巨大クラス」への慣れとその弊害
キャッシュラインやページサイズ の理解がパフォーマンスに直結
Struct of Arrays（SoA）とArray of Structs（AoS） の違いによるキャッシュ効率
アクセスパターン（順次・ランダム） によるキャッシュヒット率の違い
構造体サイズとワーキングセット の管理が性能最適化の鍵

ハードウェアの基礎知識とキャッシュ構造

Javaの現場 では、新機能追加時に既存クラスへフィールドやメソッドを追加しがち
フィールド追加コスト は軽視されがちだが、ハードウェア的には無視できない影響
パフォーマンス評価 はアルゴリズムのオーダー（O(N)など）に偏りがちだが、実際にはハードウェアの理解が重要
lscpuコマンド でキャッシュサイズやインスタンス数を確認可能
- L1d: 352 KiB（10インスタンス）→1コアあたり約35 KiB
- L2: 10 MiB（5インスタンス）→1ペアあたり約2 MiB
- L3: 12 MiB（共有）
キャッシュラインサイズ は64バイト（getconfコマンドで確認）

キャッシュラインとデータ配置の影響

1バイト読み込み時、周辺64バイトがまとめてキャッシュラインにロードされる
空間的・時間的局所性 を活かす設計が高速化のカギ
Jeff Deanの“Latency numbers” を参考に、レイテンシとキャッシュ階層を把握
- L1d: 約35 KiB/コア、1-2ns
- L2: 約2 MiB/コアペア、4-5ns
- L3: 12 MiB共有、10-15ns
- DRAM: 60-100ns

Array of Structs（AoS） vs Struct of Arrays（SoA）

Array of Structs（AoS） ：各Monster構造体（例：64バイト）が配列状に並ぶ
- 1キャッシュラインに1体分だけ格納
- is_aliveだけを取り出す場合でも、他の無関係データもキャッシュされ非効率
Struct of Arrays（SoA） ：各フィールドごとに配列化
- is_alive配列なら64体分が1キャッシュラインに収まる
- キャッシュ効率が大幅向上、最大30倍の高速化も観測

構造体サイズ・アクセスパターンとパフォーマンス

構造体サイズが大きいほど、ワーキングセットサイズも増加
- 例：512体×64B=32KiB（L1dに収まる）、128Bなら64KiB（L2に溢れる）
順次アクセス ならCPUプリフェッチャが予測しやすく高速
ランダムアクセス ではキャッシュヒット率が急落
- ハッシュマップやツリー、グラフ探索などで顕著
- ワーキングセットがキャッシュに収まらないと、レイテンシが一気に増加

ワーキングセットサイズ管理の重要性

構造体を小さく保つ ことで、高速なキャッシュ階層にデータを収めやすくなる
ランダムアクセスパターン では、構造体サイズやデータ量がパフォーマンスを左右
実装時はデータレイアウトとアクセスパターンを意識 し、ハードウェア特性を最大限活用する設計が重要

このように、 構造体の設計やデータ配置、 アクセスパターン の工夫が、単なるアルゴリズムの理論的オーダー以上に 実際のパフォーマンス へ大きく影響します。 キャッシュ階層・ワーキングセットサイズ・プリフェッチャの挙動 を理解し、 データレイアウト最適化 を積極的に検討することが、現代のソフトウェア高速化の鍵です。

Hackerたちの意見

だから、スピードが必要なら、オブジェクト指向プログラマーのプライドを捨てて、データを配列に入れるしかないね。

└

誰かが、構造体の配列を自動的に構造体の配列として保存するオブジェクト指向言語を作ってくれたらいいな。ちょっと冗談だけどね。

└

それに、物理スレッド間でデータを移動させるのはできるだけ避けた方がいいよ。見かけるボトルネックのほとんどは、データの整理が原因じゃないから。無駄なデータのやり取りが一番の原因だよ。

└

もし何百万回も繰り返すホットループがあるなら、コードをそれに合わせて構造化しよう。仕事に合ったデータ構造を選ぶのは、オブジェクト指向に反するわけじゃないよ。

└

... それがメインのパフォーマンス問題ならね。ORMやレイジーロードのセマンティクスによる巨大なパフォーマンス問題に悩まされてるのは分かってる。I/Oの悪用は、メモリやキャッシュの問題よりもずっとひどいことが多いから。Javaは主にビジネス情報システムで使われてるから、I/Oが重要なんだよね。普通のメモリの悪用も大きな問題だし。でも、私の主な問題は、経営陣がAIの魔法の杖であらゆる問題が消えると思い込んでること。彼らがそれに気づくまでに5年かかるだろうね。でも、キャッシュ最適化について学ぶのは楽しいよ、特に誰かがこうやって理解しやすくしてくれるとね。それに、OOPが特別な真理じゃないって認識する助けにもなるかも。

JVMは今、メモリ割り当てがかなり悪いんだ。すべてのオブジェクト（プリミティブじゃないやつ）は、確か12バイトのヘッダーを持ってる。でも、JVMの世界にはいいニュースがあるよ：次のJVMリリースでこれが8バイトに減るんだ。それに、プロジェクト・ヴァルハラがあれば、場合によってはヘッダーを完全に取り除くツールも手に入る。プロジェクト・ヴァルハラには、オフヒープメモリを管理するツールもあって、これが重要なケースも多い。JVMは、AOTコンパイルされた言語と競争するにはヒープが多すぎるけど、インタープリタ言語と比べると起動時間が遅すぎるっていう変な場所なんだ。これらの改善は、このプラットフォームを relevancy を保つために必要だと思う。

└

Javaプラットフォームの実際の使用は、こういうことに関してほとんど心配がないんだ。もっとニッチなユースケースには恩恵があるかもしれないけど、全体的な成功の地図はすぐには変わらないよ。その長期的な成功の理由は他にあるんだ。

└

すべてのオブジェクト（プリミティブじゃないやつ）は、確か12バイトのヘッダーを持ってる。でも、JVMの世界にはいいニュースがあるよ：次のJVMリリースでこれが8バイトに減る。JDK 25からはすでに64ビットで、-XX:+UseCompactObjectHeadersフラグを使うと [1]、JDK 27ではデフォルトになる [2]。 > AOTコンパイルされた言語と競争するにはヒープが多すぎる。競争するためじゃなくて、勝つためだし、多すぎるわけじゃなくて、ちょうどいい量なんだ。低レベル言語は制御のために最適化されてるけど、パフォーマンスのためじゃない（その制御が小さなプログラムではパフォーマンス向上につながるけど、大きなプログラムでは逆に悪化することもある）。特定の制約があるから、JITコンパイルやムービングコレクタが提供する重要な最適化を享受できないんだ。これらはAOTコンパイラやフリーリストアロケータが発生させるオーバーヘッドを取り除くからね。彼らのメモリ管理は、制約によってフットプリントを最適化するよう強制されてる。メモリ管理や、なぜムービングコレクタがmalloc/freeのCPUオーバーヘッドを減らすために作られたのかについて、一般的な誤解があるんだ。特に大きなプログラムでは、実質的に無料のRAMと引き換えにね。だから、ムービングコレクタはそれを使うのに十分な制約がない言語や、実装するリソースがある言語（Java、.NET、V8）に選ばれるんだ。Zigを除けば（そこでも少し努力が必要だけど）、低レベル言語がムービングコレクタの背後にある基本的な最適化を使うのは難しい。前回のJava Oneで、ムービングコレクタがメモリ管理を最適化する方法について話したんだけど、その動画はもうすぐYouTubeにアップされるはずだよ [3]。 > インタープリタ言語と比べると起動時間が遅すぎる。それはもうしばらく前からそうじゃないよ。ただ、起動/ウォームアップ時間はAOTコンパイルされた言語より悪いのはその通りで、JITの最適化のトレードオフなんだ。大きなプログラムでのAOTコンパイルに伴うオーバーヘッドを減らす代わりにウォームアップを犠牲にするっていうね。プロジェクト・レイデンのおかげで、起動とウォームアップはすでに改善されてるけど、Cのようにはいかないよ。一般的に、トレードオフは大きなプログラムを助ける最適化と小さなプログラムを助ける最適化の間にあるんだ。 [1]: https://openjdk.org/jeps/519 [2]: https://openjdk.org/jeps/534 [3]: ここでメモリ管理の数学に関する全ての話を再現することはできないけど、ムービングコレクタのことは、最近まで（オープンソースの低レイテンシのムービングコレクタはChatGPTより新しい）、ポーズが必要だったから、低レイテンシが求められるプログラムには適してなかったんだ。そのせいで、多くの開発者はムービングコレクタがどれだけ効率的かを忘れたり、学ばなかったりしたんだ。でも、重要なのは、RAMにアクセスするためには必ずCPUが必要だから、CPUをうまく使うことで、プログラムが使っていなくてもRAMをキャッチできるってこと。CPUとRAMの使用を良いバランスに保つことが、一方を最小限に抑えようとするよりも効率的なんだ。これが、ハードウェア（物理的または仮想的）がRAM/core比の非常に狭い範囲内でパッケージされる理由でもあるんだ。 [4]: https://www.youtube.com/watch

ちょっと脱線するけど、ミリ秒、マイクロ秒、ナノ秒も大事だよね。レスポンスタイムに対して、かなり無頓着になってる気がするし、無駄な計算サイクルも多いよ。

新しいフィールドのコストはほとんど考慮されない。ほとんどの開発者は、Javaや他の多くの言語で、すべてのフィールドのコストを考えないけど、マイクロ最適化が必要な人たちは確実に気にしてるよ。Javaの標準ライブラリでは、レイアウトはかなり重要な問題なんだ（もちろん、本当に重要なことを最適化したいけど、実際のプログラムでホットスポットになりそうもないものを最適化しても意味がないからね）。でも、時には、同時実行が関わるときにキャッシュラインの共有を避けるために、意図的にレイアウトを広げたくなることもある。そういう例も標準ライブラリにあるよ。

└

Javaや他の多くの言語では、ほとんどの開発者が各フィールドのコストを考慮していないって言ってるの？ほとんどの開発者が悪いってこと？これは、ほとんどの従業員が雇用主にとっての各行動のコストを考えないのと同じで、会社の支出が膨れ上がる原因になるんだよ。

└

たぶん、その最適化はLLMによって自動化できるかもね。

記事は「すべてのバイトが重要」というのが間違いだと上手く示してる。最初に新しいフィールドのコストについて話してるけど、実際のトピックは配列の構造体と構造体の配列の違いなんだよね。で、これ：> どれくらいの影響があるの？ > 読み込みは：alive（1バイト） 1Mのモンスターに対して。ここで1バイトを読んでるわけじゃなくて、1Mバイトを読んでるんだよ！もちろん、1Mバイトへのアクセスを最適化するのは考慮すべきだけど、1バイトへのアクセスを最適化する必要はない。この記事は読む価値があると思うけど、もう少し良い見出しが必要だね！

└

さらに言うと、SoA（構造体の配列）データ構造を使うと、1Mのモンスターにフィールドを追加しても影響が少ないってことが分かるね。

└

すべての構造体が重要だよ。

それにしても、主要な言語がSoAやAoSとしてオブジェクトの配列を最適化するための組み込みの方法を持ってないのは変だと思う。

└

オブジェクトのアイデンティティを言語レベルで維持するのは、あんまり意味がない気がする。配列のデータは、オブジェクトのフィールドのメモリとは同じじゃないからね。スピードアップを図るには、アクセスパターンとして抽象化するだけじゃダメで、メモリの配置方法に依存するから。もし行と列の両方でクエリできるようなコレクションタイプを作ろうとしているなら、常に両方の方法で保存して、両方の表現を同期させる必要があるから、結局その目的が薄れてしまうと思う。こういうパターンをやろうとしているなら、オブジェクトを保持するのは意味がない気がするな。

僕は256バイト（KBじゃなくて）のRAMを持つデバイスで機械語から始めたんだ。それは、実行可能ファイルをインストールし、スタックを確保し、ヒープを設定するための256バイトだった。情報を伝えるためにビット（バイトじゃなくて）フィールドをよく使ってたから、生活は大変だったよ。でも、だらしなくできることには明確な利点があるんだ。高度に最適化されたものを設計するのには時間がかかるからね。新しいプロパティをいくつか宣言するのに30秒かかるなら、ビットフィールドを設計するのに1時間かかるとしたら、そこには本当のコスト削減があるよ。とはいえ、最近は狂ったように時間がかかることもある。数日間、メモリをむさぼる問題を追いかけてたんだ。ギガバイトのメモリを消費する操作だった。実際の原因はApple MapKitだったことが分かって、簡単な回避策を見つけたけど、そこにたどり着くまでに時間がかかったよ。OSが怪しいと思ったら、たいていは自分のせいで、OSに戻る前にあれこれ試すのに時間がかかるんだ。

└

Macでこれをやってるすべてのデーモンや自動的なクソをどう対処してるの？SIPによって強化されてるんじゃないの？

ヒント：MacでLNキャッシュサイズを取得するには、コマンドは $ sysctl -a | grep "l.*cachesize" | gnumfmt --field=2 --to=si だよ。 hw.perflevel1.l1icachesize: 132k hw.perflevel1.l1dcachesize: 66k hw.perflevel1.l2cachesize: 4,2M hw.perflevel0.l1icachesize: 197k hw.perflevel0.l1dcachesize: 132k hw.perflevel0.l2cachesize: 13M hw.l1icachesize: 132k hw.l1dcachesize: 66k hw.l2cachesize: 4,2M で、LEVEL1_DCACHE_LINESIZEに相当するのは $ sysctl -a | grep hw.cachelinesize だよ。 hw.cachelinesize: 128

キャッシュの行数は、しばしば行数とは異なることがあるから、特定のワークロードには関係があるかもしれない。普通のキャッシュのサイズは、行数 × ウェイ数 × サイズ（行）で、行数は 2 ↑ num-idx-bits だよ。例えば、ほとんどのIntel 64やAMD 64プロセッサは、L1キャッシュ用に log₂(size(page)) − log₂(size(line)) = 12 − 6 = 6 インデックスビットを使ってるから、8-wayの関連性を持つL1キャッシュは 64 セット × 8 行/セット × 64 バイト/行 = 32 KB になるし、12-wayの関連性を持つL1キャッシュは 64 × 12 × 64 = 48 KB になるんだ。ほとんどのプロセッサがL1キャッシュに64行しか持ってないって知ったときは驚いたな！ *仮想インデックスと物理インデックスが同じだから、行の取得がTLBルックアップと並行して行えるんだ。

ZigのMultiArrayListは、コレクションのオブジェクトをサポートするクールな言語機能で、もっと多くの言語がこれをファーストクラスでサポートしてくれたらいいのにな（コピーのオーバーヘッドなしで）。

ハクソク