State of Valhalla – Section 1: The Road to Valhalla

原文はこちら。
The original article was written by Brian Goetz (Java Architect, Oracle)
http://cr.openjdk.java.net/~briangoetz/valhalla/sov/01-background.html

Project Valhallaの目標は、より柔軟なフラットなデータ型をJVMベースの言語にもたらし、プログラミングモデルを最新のハードウェアのパフォーマンス特性に合わせることです。中核となる機能はinline typeですが、JVMの型システムのこのような基本部分の揺れは、ジェネリックスの特殊化のような多くの機能と課題だけではなく、既存のAPIをinline typeや特殊化されたジェネリクスへの互換性ある移行を可能にするツールをももたらします。

Project Valhalla
http://openjdk.java.net/projects/valhalla

Project Valhallaは2014年にスタートしました(当時、ジェームズゴスリングが “six Ph.D theses, knotted together” と説明していました)。過去5年間で、5個のプロトタイプを作成してきました。それぞれは別々の問題の側面を理解するためのものです。現在我々は以下の状態にあると考えています。

  • Java言語と仮想マシンを値型で強化するための明確で一貫したパスがある
  • 既存のジェネリックと完全に相互運用し、既存の値ベースのクラスをinlineクラスに、既存のジェネリクスクラスから特殊化されたジェネリクスに移行する互換性のあるパスがある

この一連のドキュメントは、そのパスをまとめたものです(開始地点と落ち着き先を比較したい場合は、設立文書を参照してください)。

State of the Values
http://cr.openjdk.java.net/~jrose/values/values-0.html

Motivation

JVMの型システムには、8つのプリミティブ型(int、longなど)、クラス(Identityを持つ異質な集合体)、および配列(Identityを持つ同質な集合体)が含まれます。これらのビルディングブロックは柔軟で、必要なデータ構造をモデル化できます。利用可能なプリミティブ型にうまく当てはまらないデータ(例えば複素数、3次元ポインタ、タプル、10進数値、文字列など)は、オブジェクトを使って簡単にモデリングできます。ただし、オブジェクト(VMが十分に狭いスコープで別名が付けられていないことを証明できない場合)はヒープに割り当てられ、オブジェクトヘッダー(通常は2マシンワード)が必要であり、メモリの間接参照を介して参照する必要があります。例えば、XYポイントオブジェクトの配列は、以下のメモリレイアウトを有しています。

Layout of XY points
Layout of XY points

Java仮想マシンが設計されていた1990年代初頭、メモリフェッチのコストは、加算などの計算操作と同程度でした。複数階層のメモリキャッシュと今日のCPUの命令レベルの並列処理により、1回のキャッシュミスが最大1000算術(命令)発行スロットに相当する可能性があり、相対コストが大幅に増加します。その結果、JVMが好むポインターが豊富な表現は、小さなデータアイランド間の多くの間接参照を伴うため、現在のハードウェアにとって理想的ではなくなりました。開発者が今日のハードウェアのパフォーマンスモデルとデータレイアウトを一致させることができるようにすることを目指し、Java開発者に対して、抽象化や型安全性を損なうことなく、フラット(キャッシュ効率)および高密度(メモリ効率)のデータレイアウトへの簡単なパスを提供します。

Object identity

この不幸なレイアウトの根本的な原因はオブジェクトのアイデンティティです。現在、すべてのオブジェクトインスタンスにはオブジェクトIDがあります(90年代前半、「すべてがオブジェクトである」は魅力的なマントラであり、それを実現するためのパフォーマンスコストは面倒ではありませんでした)。アイデンティティによって可変性がもたらされます。オブジェクトのフィールドを変更するには、どのオブジェクトを変更しようとしているか分かる必要があります。アイデンティティは多態性(polymorphism)もサポートしています。各オブジェクトインスタンスはクラスに関連付けられており、クラスからメモリレイアウトと仮想メソッドディスパッチを導出できます。ただし、(多くの場合)可変性と多態性を回避するクラスであっても、オブジェクトの等価性(==)、同期、System::identityHashCode、弱参照などを含むさまざまなアイデンティティ依存の操作によってアイデンティティを観察できます。その結果、VMは、ユーザーが最終的にアイデンティティ依存の操作(たとえその操作が結局なされないとしても)を実行する場合に備えて、IDを悲観的に保持する必要があります。そのため、現在のポインタをたくさん使うメモリレイアウトになります。

Inline classes

Inlineクラスは、アイデンティティを明示的に否認する異種集合です。そのため、Inlineクラスは不変でなければならず、レイアウト多態性であってはなりません。しかし、これら(Mutability、layout-polymorphic)を放棄する意思がある場合は、よりフラットで高密度のメモリレイアウトだけでなく、最適化された呼び出し規約(inlineクラスインスタンスは、ヒープではなくスタックまたはレジスタで渡すことができます)を見返りに受けることができます。次のように宣言するだけで、クラスがinlineクラスであることを示すことができます。

inline class Point {
    int x;
    int y;
}

inlineクラスには、通常の(アイデンティティ)クラスと比較していくつかの制限があります。

  • final
  • fieldはfinal
  • 継承に参加できない

これらの制限を受け入れる見返りに、ランタイムはそれらをデータのみとして自由に扱うことができるため、ヒープオブジェクトへの参照としてではなく、値によって配列またはオブジェクトにフラット化して渡すことができます。この命令により、ランタイムは次のようなメモリレイアウトを日常的に提供できます。

Flattened layout of XY points
Flattened layout of XY points

これは、以前のバージョンよりも間接参照がなくてフラットであり、ヘッダーがなく高密度です。これらの制限を除き、inlineクラスは、クラスで利用できるメソッド、コンストラクタ、フィールド、カプセル化、型変数、注釈などのほとんどのメカニズムを使用できます。スローガンは ”Codes like a class, works like an int”「クラスのようなコードがintのように機能する」です。inline typeは、「より高速なクラス」または「ユーザー定義可能なプリミティブ」と同等に考えることができます。

すべてのレベルでinline typeのアプリケーションがあります。数値、日付、カーソル、Optionalのようなラッパーなど、多くのAPI抽象化は、当然inline typeです。 HashMapなどの多くのデータ構造では、実装でインライン型を使用して効率を改善できますし、言語コンパイラは、組み込みの数値型、タプル、複数のreturnのような機能のコンパイルターゲットとしてinline typeを利用できます。

Generic specialization

Javaジェネリクスの初期の妥協点の1つは、ジェネリック型の変数は、プリミティブ型ではなく参照型でのみインスタンス化できる、という点です。ボクシングを使わなければプリミティブ型を生成できず、常にいらいらさせられてきました。それは抽象化や再利用の利点を得るためにパフォーマンスを犠牲にせざるを得ないためです。inline typeを追加すると、この制限はさらに厳しくなります。上記のPointのようなフラット化可能なデータ型を作成することができれば、ArrayListの背後にフラット化されたPointの配列がないのは、ポイントを無効にしているように思われます。

パラメトリックな多態性は、常にコードのフットプリント、抽象化、および特異性の間のトレードオフを伴いますし、異なる言語では異なるトレードオフを選択してきました。

一方で、C ++はテンプレートのインスタンス化ごとに特殊化されたクラスを作成し、異なる特殊化は互いに型定義の関係を持ちません。このような異種間の変換は、a+bのような式がaとbのインスタンス化された型の+の動作と相対的に解釈できる点で高い特異性を提供しますが、大きなコードフットプリントだけでなく、抽象化の損失を伴います。JavaにはFoo<?>に相当する型はありません。

他方、すべての参照インスタンス化に対して1つのクラスを生成し、プリミティブなインスタンス化をサポートしない現在の型消去された実装がJavaにはあります。すべての参照インスタンス化に対して1つの型とオブジェクトレイアウトをインスタンス化できるため、このような同種の変換では高度な再利用が可能になります。プリミティブではなく参照型のみを範囲とすることができる制限は、参照型とプリミティブ型の操作に異なるバイトコードを使用するJVMのバイトコードセットにそのルーツがあります。

While most developers have a certain degree of distaste for erasure, this approach has a powerful advantage that we could not have gotten any other way: gradual migration compatibility. This is the ability to compatibly evolve a class from non-generic to generic, without breaking existing sources or binary class files, and leaving clients and subclasses with the flexibility to migrate immediately, later, or never. Offering users generics, but at the cost of throwing away all their libraries, would have been a bad trade in 2004, when Java already had a large and vibrant installed base (and would be a worse trade today.)

Our goal today is even more ambitious than it was in 2004: to extend generics so that we can instantiate them over primitives and inline classes, with specialized (heterogeneous) layouts, while retaining gradual migration capability. (Further, migration compatibility in the abstract is not enough; we want to actually migrate the libraries we have, including Collections and Streams.)

A brief history of Project Valhalla

Project Valhalla has ambitious goals, and its intrusion is both deep and broad, affecting the classfile format, VM, language, and libraries. Over the past five years, we have done several prototypes, each aimed at deepening our understanding of different aspects of the problem.

Our first three prototypes explored the challenges of generics specialized to primtives, and worked by bytecode rewriting. The first (“Model 1”) was primarily aimed at the mechanics of specialization, and identifying what type behavior needed to be retained by the compiler and acted on by the specializer. The second (“Model 2”) explored how we might represent wildcards (and by extension, bridge methods) in a specializable generic model, and started to look at the challenges of migrating our existing libraries. The third (“Model 3”) consolidated what we’d learned, building a sensible classfile format that could be used to represent specialized generics. (For a brief tour of some of the challenges and lessons learned from each of these experiments, see this talk (slides here).

The results of these experiments were a mixed bag. On the one hand, it worked – it was possible to write specializable generic classes and run them on an only-slightly-hacked JVM. On the other hand, roadblocks abounded; existing classes were full of assumptions that were going to make them hard to migrate, and there were a number of issues for which we did not yet have a good answer.

We then attacked the problem from the other direction, with the “Minimal Value Types” prototype, whose goal was to prove that we could implement flat and dense layouts in the VM.

The turning point for Valhalla came with the most recent prototype, dubbed “L World” (because inline classes can share the L carrier with object references.) In our early explorations, we assumed a VM model where inlines were more like primitives – with separate type descriptors, bytecodes and top types – because it seemed too daunting to unify references and inlines under one set of type descriptors, bytecodes, and types. L-world attempted this unification, and (somewhat to our surprise) managed to do so without significant compromises. And the unification of types and descriptors provided by L-world addressed a significant number of the challenges we encountered in the early rounds of prototypes.

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Google フォト

Google アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中