原文はこちら。
The original article was written by John Rose (Java Virtual Machine Architect, Oracle).
https://cr.openjdk.java.net/~jrose/values/iterator-vs-cursor.html
immutableなオブジェクト型（特に値ベースのクラス）と、immutableであり、値ベースのクラスと似たような性質を持つ値型との間には明確な類似性があります。合理的に、すべての値クラスが値ベースのクラスであるとも言えるでしょう。いずれにしても、値ベースのオブジェクトクラスを完全な値型に移行するためのストーリーを現在形成中です。
ステートフルなオブジェクト型と値型の間にも別の類似性がありますが、それはもっと微妙です。多くの場合（すべてではありませんが）、オブジェクトの現在の状態をモデル化する値が、その状態を読む必要のあるすべてのコードで利用できるようになっている限り、ステートフルなオブジェクトを値に変換できます。これは、状態を更新するには、以前の値を破棄し、更新されたオブジェクトの状態をモデル化する新しい値を使用しなければならないことを意味します。
これはすべて複雑に聞こえますが、実際にはシンプルに感じます。“Codes like a class but works like an int”（クラスのようなコードだが、intのように動作する）ということは、現在の状態の値は、それを見ているどのような変数にも常に代入されるということを意味します。実際に、整数のように動作します。
int x = 0; Value v = Value(0); … x + 1; // bad code x = x + 1; // good code v.bump(); // bad code v = v.bump(); // good code
（ふむふむ、そろそろAPIで値を返すための__NoDiscard修飾子をサポートした方がいいかもしれないですね。xをとる悪いコードは構文エラーですが、vをとる悪いコードは黙って受け入れられます。これを追跡するために、JDK-8199429 を作成して、後で対処するためにいくつかのアイデアを投げ込みました）。
JDK-8199429 [valhalla] value type (re)constructors expressions should not be discardable
https://bugs.openjdk.java.net/browse/JDK-8199429
ステートフルなIteratorオブジェクトをステートレスなCursor値に変換する例を見てみましょう。このコードは JDK からそのまま引用したものです。
class CharIterator implements PrimitiveIterator.OfInt {
int cur = 0;
public boolean hasNext() {
return cur < length();
}
public int nextInt() {
if (hasNext()) {
return charAt(cur++);
} else {
throw new NoSuchElementException();
}
}
// omitted forEachRemaining
}
これは length() および charAt(i) の操作を持つenclosing object (CharSequence) の上にストリームを構築するために使用される内部クラスです。通常の Iterator としても使用できます（そして、Boxed Integerを返すことになります）。
（これについては、java.lang.CharSequence$1CharIterator として知られているローカルクラスを javap で調べてみましょう）
このクラスのインスタンスには、外部CharSequenceへのポインタと、変化するインデックスcurという、2つのフィールドがあります。イテレータが1つの固定フィールドと1つの変動フィールドを持つことはよくありますし、時には、可変フィールドへの制限のような固定フィールドが追加されることもあります。
時には、プリフェッチされた現在値のような、追加の可変フィールドが存在することもあります。これらの固定フィールドと可変フィールドはループ変数に対応しており、（それぞれ）ループ不変型とループ可変型ですが、これらはイテレータの内部にきちんとパッケージ化されています。
このオブジェクトのpublicなインターフェースは非常にシンプルで、java.util.Iteratorのバリエーションです。
public interface PrimitiveIterator.OfInt
extends … Iterator<Integer> {
@Override boolean hasNext();
int nextInt();
}
このイテレータのfor-loopは以下のようです。
for (final var t = myIntIterator(); t.hasNext(); ) {
var x = t.nextInt();
workOn(x);
}
このfor-loopは、ループ不変の1つの反復変数tだけを使用しているように見えますが、その背後には、CharSequenceへのループ不変ポインタとループ可変インデックスがあります。
イテレータで繰り返し発生する問題は，反復変数を保持するためにヒープの割り当てを必要とすることです．これは、tをループ不変にするために必要ですが、ループ変数であるcurをカプセル化するためにも必要です。この問題を繰り返し修正するには、”エスケープ解析 “と呼ばれるものを使って、tがfor-loopに対してローカルであることを判断し、そのフィールドをfor-loopと同じスタックフレームに直接展開します。
ここに上記と同じループがありますが、イテレータのフィールドを（ソースコードとして）for-loopにインライン化しています。
final var t = myIntIterator();
final var tcs = t.this$0; // CharSequence.this
for (var tcur = t.cur; tcur < tcs.length(); ) {
var x = tcs.charAt(tcur++);
workOn(x);
}
（hasNext()メソッドは、a[i++]のような、手作りのループで書くようなものまで簡略化されていることに注意してください。この効果は、hasNextとnextを正しく使うことで得られるものです）
理論的には素晴らしいのですが、エスケープ解析の修正は実際には脆いものです。値型は、フラット化されたデータ構造を提供するだけでなく、（必要なコンポーネントとして）エスケープ解析の意味で決して「エスケープ」しない固有の性質を提供しています。したがって、ローカル変数のグループへの最適化を享受するために分析を必要としません。
問題点は、エスケープ解析を回避し、フラット化を可能にするために、値が異なる特性を持つ点です。具体的には、値はIDフリーでimmutableでなければなりません。これを正しく使用するためには、ソースコードのパターンが異なる必要があります。ある値が上記の CharIterator と同じ状態変数をモデルとしている場合、その値はループ不変イテレータオブジェクトではなく、ループ可変値として for-loop に現れなければなりません。値が豊富な世界では、このループ変数をイテレータに置き換えることで、ループはイテレータを用いる場合と同様に一般的にコード化されますが、状態を保持するためのヒープの割り当てはありません。このようなループ可変なループ制御値がイテレータのように一般的になる可能性があるように思われます。そこでこれらのことをcursorと呼んでいます。
値型カーソルがどのようにイテレータを置き換えるのか、イテレータの例をもう一度見てみましょう。まず、tcsとtcur変数を値クラスに再グループ化します。
inline class CharCursor extends … {
//CharSequence this$0; // make it a nested class
int cur = 0;
…
}
では、拡張ループの名前を変えて、値クラスを埋める方法を見てみましょう。
var c = myIntCursor();
final var ccs = c.this$0; // CharSequence.this
for (var ccur = c.cur; ccur < ccs.length(); ) {
var x = tcs.charAt(ccur++);
workOn(x);
}
そして、ccs/ccur を c に再グループ化します。
for (var c = myIntCursor(); c.hasNext(); c = c.afterNext()) {
var x = c.nextInt();
workOn(x);
}
（名前は多かれ少なかれ恣意的に選びましたが、既存のイテレータAPIとの概念的な重複を最大化しようとしました。”hasNext”という名前は、”hasCurrent”や “notAtEnd”にすることもでき、”next”という名前は、”current”や “get”にすることもできます。”afterNext”という名前は、”advance”、”bump”、”increment”などが考えられます。ここでは、”afterNext”のための安価な根拠があります。これは、APIに統一性を与えるために “next”という用語をそのまま使い、先ほど訪れたものの後に来るものへと進む、という意味です。先ほど訪れたもののことを “next”と呼んでいたので、その後のものは “afterNext “と呼びます）。
さらに重要なのは、ループの値バージョンは3つのメソッドを必要としますが、オブジェクトバージョンは2つのメソッドを必要とします。これはどこかで間違っているのでしょうか？そうではありません。値型の核心的な原理、“codes like a class, works like an int” （クラスのようなコードだが、intのように動作する）に成功している証拠です。単純な配列/intループの前のループと比較すると、理由がわかるでしょう。
final var a = myArray();
for (var i = 0; i < a.length; i = i + 1) {
var x = a[i];
workOn(x);
}
2つの反復変数の同じパターンが発生（aとi）し、ループ制御演算も同じパターンで発生します。c.hasNext()の代わりに、i<a.lengthがあります。c.nextInt()の代わりにa[i]があり、これは反復処理する次の値です。3番目のメソッド呼び出し（イテレータのバージョンにはありませんでした）は、単にそれを更新するだけです。
配列とintの例で明らかなように、イテレータのt.nextInt()の操作は実際には2つの結果を生み出していました。1つ目は、反復系列の次の値を渡し、2つ目は、t.nextInt() が返された後の値を指すようにイテレータオブジェクトを静かに更新しました。整数ではこのトリックを行うことができません。したがって、c=c.afterNext() の代わりに、i=i+1を使っています。
c.nextInt()を何度も呼び出すと、（cが適切にコード化されていれば）同じ値が返ってくることに注意してください。別の値を取得するには、c.afterNext() を呼び出す必要があります。これはintと配列のように動作します。（行儀の良いプログラムでは）a[i]を繰り返し求めると，毎回同じ値が得られます。別の配列要素を取得するには、iを更新しなければなりません。
<digression>
Java言語では（C言語にならって）、t.nextInt()の効果を1つの式で得るための省略した方法として、有名なa[i++]が用意されています。a[i++]をよく見ると、一対の値を返していることがわかります。第一に、式の値は、スキャンしている配列の次の要素です。第二に，繰り返しの状態は，その後に配列の要素を指すように静かに自分自身を更新します．このようなシンプルな式が広く使われていることを考えると、値の型にもこのような構文の利点があるのではないかと考える価値があるように思えます。それは、変数に格納されている値に対してメソッドを呼び出し、変数を更新し、変数の前の値に対して別のメソッドを呼び出すという、次のようなものです。
for (var c = myIntCursor(); c.hasNext(); ) {
var x = c{.=afterNext()}.nextInt();
workOn(x);
}
悲しいことに、ここには明らかに良い答えはないようです。そして正直に言うと、i++ は不可欠ですが、まったく美しくありません（慣れてはいるんですけどね）。ですから、私はそのような考えからは手を引くことにします。もう少し詳しく知りたい方は、 JDK-8199429 を参照してください。
JDK-8199429 [valhalla] value type (re)constructors expressions should not be discardable
https://bugs.openjdk.java.net/browse/JDK-8199429
</digression>
これで、cursorクラスを以前よりも埋めることができるようになりました。
inline class CharCursor extends … Cursor<Integer> {
//CharSequence this$0; // make it a nested class
int cur = 0;
public boolean hasNext() {
return cur < length();
}
public int nextInt() {
if (hasNext()) {
return charAt(cur);
} else {
throw new NoSuchElementException();
}
}
public CharCursor afterNext() {
return this __With { i = i + 1; };
}
}
（同じクラスの古い値インスタンスから新しい値インスタンスを取得する方法の詳細を、そのフィールドの 1 つを更新することによって__With トークンは隠蔽します。これは、ファクトリー・メソッド、プライマリ・コンストラクタ、リコンストラクタ、デコンストラクタ、そして「枯れた」メソッドのような概念を含む、別個の複雑な会話です。この場合の __With は、単に”withfield” のようなことを処理する現在の JVM レベルのバイトコードへのパンチスルーです）。
クラスの詳細はそれほど重要ではありませんが、上記はおそらく現在の Valhalla プロトタイプでの動作例に近いものです。コードはオリジナルの CharIterator の例とほぼ同じです（例を選んだり、イテレータからカーソルへの移行に苦労したりする必要はありませんでした）。t.nextInt()メソッドの二重効果は、メソッドの中心に埋め込まれた小さな “++” に由来していることに注目してください。この “++“を削除することで、値型のセマンティクスを導出することができます。もちろん、イテレータからカーソルを作るのはこんなに簡単ではありませんが、たぶんほとんどの場合はそれほど難しくないでしょう。
2つ目の効果を落とすためにnextIntの i++ を i に変更する場合、どこかに入れないといけなくなってしまいます。実際には、予想通り、3番目のメソッドに入ってしまいました。言語での値のサポートのためのいくつかの提案では、再構成メソッドの完全なボディとして i++ を書くことができます。
public __Reconstructor afterNext() {
i++;
}
サニティチェックとして、カーソルを新しいループにインライン化し、どのように最適化されるか見てみましょう。
for (var c = myIntCursor();
c.cur < c.this$0.length();
c = __WithField(c.cur, c.cur + 1)) {
var x = c.this$0.charAt(c.cur);
workOn(x);
}
これはCharIteratorのインライン化よりも複雑です。CharIteratorの場合よりも最適化は難しいのでしょうか？まず第一に、ヒープオブジェクトやオブジェクトIDはないため、エイリアスはありません。コンパイラは、c とそのコンポーネントである c.cur や c.this$0 を、あたかもすべての変数であるかのように正確に追跡できます。実際、上記のループは、ccur++のような操作を含めて、インライン化されたループの前のバージョンに素早く折りたたまれます。コンパイラは、c.this$0が実際にはループ不変であることを簡単かつ確実に示すことができ、上のccsがそうであったようにfinalにすることができます。このループの動作は上記のccsのようなループと区別がつかないので、このループを表示する必要はありません。
カーソルベースのループを最適化するための重要な部分は、ループの不変性を認識することです。この認識は、カーソル値が更新されたとき、変更された部分（curのみ）だけではなく、明らかに（this$0を含む）カーソルのすべてのコンポーネントを更新するので、少し危険です。もしコンパイラがc.afterNext()の重要な呼び出しをインライン化できなければ、c.this$0がループ不変であることを推論できません。もちろん、変更されるものが小さな int 変数であることにも気づかないでしょう。
ループが完全に最適化されるようにするためには、CharCursorの3つのメソッドはすべてインライン化されていなければならず、それらのメソッドのボディはコンパイラが解析しやすいものでなければなりません。もちろん、CharIterator も同様です。CharCursorが1つのCharIteratorメソッドから2つのメソッドを分離していることを除いて、2つのクラスのコードがほぼ同じであることがわかりました。
ほぼ同じコードであることはもちろん問題です。イテレータから離れてカーソルに移行すると、カーソル用に1つのコピー、イテレータ用に1つのコピー、といった具合で、ループの反復コードの一般的な重複が発生するのでしょうか。結局のところ、イテレータはどこにも行かないし、時には必要になることもあります。
カーソルを広く採用するために必要なのは、常にコードを複製するのではなく、カーソルとイテレータを相互変換するためのストーリーを持つことです（パフォーマンスを向上させるためにコードを複製することもありますが、あまり頻繁に複製しないようにしています）。構造上の類似性を考えると、カーソルをイテレータから自動的に派生させることは可能でしょうか？答えは（一般的に）Noです。というのも、イテレータの2つのメソッドからカーソルの3つのメソッドを導出するには、イテレータのnextメソッドをその2つの効果に分割し、カーソルのnextメソッドとafterNextメソッドに割り当てる必要があるためです。
しかし、イテレータはカーソルから派生できるようです。ここでは、CharCursorとCharIteratorの現在の例に特化して実証します。
class CharIterator implements PrimitiveIterator.OfInt {
CharCursor c;
public boolean hasNext() {
return c.hasNext();
}
public int nextInt() {
int x = c.next(); // (where is my ++)
c = c.afterNext();
return x;
}
}
より一般化すると…
abstract class IteratorFromCursor<T> implements Iterator<T> {
protected Cursor<T> c;
protected IteratorFromCursor<T>(Cursor<T> initialState) {
c = initialState;
}
public boolean hasNext() {
return c.hasNext();
}
public T next() {
T x = c.next(); // (where is my ++)
c = c.afterNext();
return x;
}
public void forEachRemaining(Consumer<T> block) {
c.forEachRemaining(block);
}
}
（このクラスを完全にフラットにするためには、テンプレートクラスである必要があります。これは、値型に続くものとして計画されています。テンプレートクラスの前に、ジェネリックイテレータは少し複雑なヒープ構造を持つことになります。エスケープ解析が特注のイテレータで成功した場合、カーソル上に構築された汎用イテレータでも成功する可能性があります）。
このような派生を考えると、時間の経過とともに、次のメソッドの2つの効果を手で分割し、上記のようなジェネリクスを使って自動的に後方互換性のあるイテレータを供給して、いくつかの既存のイテレータをカーソルとしてリファクタリングすることが合理的なことになるでしょう。
What have we learned?
- 値クラスは、イテレータのようなある種のmutableなクラスを増分的に改善できる。その改善点は、エスケープ解析への依存性がなくなる点。
- 特に値クラスは、そのようなことを気にしている場合に、ループのためのheap pressure（ヒープの利用）を減らすことができる。
- この改善には再コーディングが必要だが、カーソルとイテレータのコードが非常に似ているため、コスト的には増分的なものである。
- カーソルの恩恵を受けるには、イテレータを使用するforループは再コーディングが必要だが、この再コーディングもまた、本質的には増分的なものである。
- カーソルが新しい方法である世界では、イテレータには下位互換性がある。
- for-loopで効果的に動作させるためには、値クラスはもう少し構文の愛が必要かもしれない。そうすると、そのintがループ変数である場合に「intのように動作する」ことができる。
カーソルに移行すると、ループとイテレータの両方を再コーディングする必要があるので、問題があるにもかかわらず、実際にイテレータに行き詰っているのかどうか疑問に思うのは当然のことです。もちろん、ほとんどのコードはそのままにしておきますが、パフォーマンスを気にするコードはループを再コード化することで恩恵を受けるかもしれません。その場合、手元に基本的なカーソルを用意しておくことは意味があります。
いずれにしても、シンプルに思考実験として、カーソルは値型がどのように動作するかについてより多くのことを教えてくれました。
