原文はこちら。
The original article was written by Casper Norrbin (Software Engineer, Oracle).
https://inside.java/2025/01/08/thesis-zgc-buddy-allocators/
この記事はOracle、Uppsala University、KTH (KTH Royal Institute of Technology / 王立工科大学) による共同研究プロジェクトの一環から作成したものです。
Oracle, Uppsala University, and KTH in joint JVM research projects
https://inside.java/2020/06/12/joint-research-projects/
最近、Uppsala Universityでコンピュータ・情報工学 (Computer and Information Engineering) の5年制課程を修了したCasperです。修士論文では、ストックホルムのOracleオフィスでGCチームと共同作業を行う機会に恵まれ、Joel SikströmとNiclas Gärdsとともに、関連プロジェクトを並行して進めました。今回は、この春に実施した作業の概要をご紹介します。
Casper Norrbin
https://github.com/caspernorrbin/
Addressing Fragmentation in ZGC through Custom Allocators
https://inside.java/2024/06/19/thesis-zgc-fragmentation/
https://logico-jp.dev/2024/06/28/addressing-fragmentation-in-zgc-through-custom-allocators/
Problem Background
ZGCはページでバンプポインタ割り当て (bump-pointer allocation) を使用しており、これにより高速なシーケンシャル割り当てが可能になりますが、時間の経過とともに断片化が生じます。オブジェクトが無効になると、バンプポインタの背後に未使用メモリのギャップができます。このメモリを再利用するには、ZGCは生存オブジェクトを別のページに再配置してから対象のページのバンプポインタをリセットする必要があります。私の研究では、ZGCをセカンダリ・フリーリストベースの割り当て機能（具体的にはbuddy allocator）と組み合わせることで、最初にページのリセットをしなくてもメモリのギャップを再利用できる可能性があることを調査しました。
Exploring Buddy Allocators
buddy allocatorは代替の割り当て戦略で、メモリを2のべき乗のサイズのブロックに分割し、必要に応じて動的に結合または分割する、というものです。今回特に次の3件のバリエーションを評価しました。各buddy allocatorには、それぞれ独自の強みと弱みがあります。
| 動作の概要 | Pros/cons | |
|---|---|---|
| Binary Buddy Allocator | オリジナルの設計 適切なサイズが見つかるまでブロックを再帰的に分割する | Binary Buddy Allocatorは汎用性が高く、理解しやすい |
| Binary Tree Buddy Allocator | フリーリストの代わりに二分木構造を使用し、未使用のブロックを追跡および保存する | 高速だが、余分なメタデータのオーバーヘッドが発生する |
| Inverse Buddy Allocator | ブロックを事前に分割しておき、それらのブロックを結合してより大きな割り当て要求を満たす | 小さなブロックの割り当ては高速ですが、大きなブロックの割り当ては低速 |
Adaptation for ZGC
アロケーターをZGCに統合する場合、固有の課題が出てきます。アロケーターは、アロケーション対象のメモリを完全に制御できず、代わりに与えられたメモリで動作する必要があります。各アロケーターはZGCの単一ページに関連付けられ、最初は新規割り当てのためのスペースがないため、fullとしてマークされます。その後、各空きメモリ範囲が利用可能としてマークされ、結果としてアロケーターが動作するためのページ内の領域が「切り分け」られます。
Buddy Allocator Adaptations
アロケーターをZGCに適応させることに加え、アロケーターの一般的なパフォーマンスを向上させるために、いくつかの他の最適化も試みました。
| Lazy Splitting and Merging (遅延分割とマージ) | 空きメモリーブロックのマージを遅延させることで、分割とマージの操作を削減できる。lazy layer (遅延レイヤー) が解放済みブロックを追跡し、必要な場合にのみマージする。 |
| Allocator Regions (アロケーターの領域) | アロケーターのメモリをリージョンに分割して同時実行性を向上させることで、異なる領域にまたがる同時割り当てを実現できる。一部のリージョンを優先することで断片化を抑制し、より大きなアロケーション用のスペースが確保する。 |
Results
割り当て速度、断片化、メモリオーバーヘッドに基づいてアロケーターを評価しました。アロケーション速度とメモリオーバーヘッドでは良好な結果を示しましたが、断片化は今回のユースケースでは最も重要な評価基準です。全体的には、メモリをうまく利用して堅実なパフォーマンスを発揮しましたが、バディ型アロケーター (buddy-style allocator) の固有の制限が明らかになりました。具体的には、アロケーションサイズは2のべき乗に最も近い値に丸められ、それに応じて整合を取る必要があるため、最小化が困難なメモリ浪費が避けられません。この構造的な非効率性により、スペースが十分に活用されず、フラグメンテーションが増加するため、使用にあたっては大きなトレードオフが生じます。
Conclusions and Future Work
本研究では、アロケーターをZGCと統合することは可能であり、この目的に合わせて既存のアロケーターを適応させることができることを示しています。これにより、断片化を低減し、メモリの再利用を可能にし、必要な再配置の回数を削減できます。バディ型アロケーターを使用する場合、前述の制限があるため、特定の考慮事項を評価する必要があります。
次のステップは当然ながら、アロケーターをZGCと統合することでしょう。このテーマは、Niclas Gärdsが彼の論文で同時に調査しています。今後の研究では、アロケーターのさらなる改良と、異なるバディ型アロケーターを組み合わせたハイブリッドアプローチの開発に焦点を当て、それぞれのアロケーターの弱点を相殺することが考えられます。さらに、アロケーターを使用する場合は、Project Lilliputで導入された新しい最小アロケーションサイズへの準備が不可欠です。
Liliput
https://wiki.openjdk.org/display/lilliput/Main
この記事に興味を持たれた方は、DiVAに関する私の完全版レポートをぜひご覧ください。このレポートでは、ここで取り上げたトピックについてさらに掘り下げ、この記事で取り上げられなかった分野についても議論しています。
Adapting and Evaluating Buddy Allocators for Use Within ZGC: ZGC’s New Best Friend
https://uu.diva-portal.org/smash/record.jsf?pid=diva2%3A1902805&dswid=-4283
最後に、Oracle Stockholmオフィスの皆さまの温かい歓迎に心より感謝申し上げます。また、プロジェクト全体を通じて、貴重なご指導と揺るぎないサポートをいただいたErik ÖsterlundとTobias Wrigstadに特に感謝いたします。最後に、このプロジェクトとこの春を素晴らしいものにしてくれたJoelとNiclasにも感謝いたします。
Logico Inside 