Truffle ライブラリガイド

Truffle ライブラリを使用すると、言語実装は、実装固有のキャッシュ/プロファイリングとキャッシュされていないディスパッチの自動サポートを使用して、レシーバータイプにポリモーフィックディスパッチを使用できます。Truffle ライブラリは、Truffle 上の言語実装の表現タイプにモジュール性とカプセル化を可能にします。これを使用する前に、このガイドを最初に読んでください。

はじめに #

このチュートリアルでは、Truffle ライブラリの使用方法に関するユースケースについて説明します。完全な API ドキュメントは、Javadoc にあります。このドキュメントでは、Truffle API の事前の知識と、@Cached アノテーションを使用した @Specialization の使用を前提としています。

動機付けとなる例 #

Truffle 言語で配列を実装する場合、効率のために複数の表現を使用する必要があることがよくあります。たとえば、配列が整数の算術シーケンスから構築されている場合 (例: range(from: 1, step: 2, length: 3))、配列全体を具体化するのではなく、start、stride、および length を使用して表現するのが最適です。もちろん、配列要素が書き込まれると、配列を具体化する必要があります。この例では、2つの表現を持つ配列実装を実装します。

バッファ：Java 配列によってバックアップされた、具体化された配列表現を表します。
シーケンス：start、stride、および length で表される数値の算術シーケンスを表します：[start, start + 1 * stride, ..., start + (length - 1) * stride]。

例を簡単にするために、int 値のみをサポートし、インデックス境界のエラー処理は無視します。また、通常はより複雑な書き込み操作ではなく、読み取り操作のみを実装します。

例をより興味深いものにするために、コンパイラが配列レシーバー値が定数でなくてもシーケンス化された配列アクセスを定数折りたたみできるようにする最適化を実装します。

次のコードスニペット range(start, stride, length)[2] を想定します。このスニペットでは、変数 start と stride が定数値であることがわかっていないため、start + stride * 2 と同等のコードがコンパイルされます。ただし、start と stride の値が常に同じであることがわかっている場合、コンパイラは操作全体を定数折りたたみできます。この最適化にはキャッシュの使用が必要です。これについては後で説明します。

GraalVM の JavaScript ランタイムの動的配列実装では、20 の異なる表現を使用しています。定数、ゼロベース、連続、穴、およびスパース配列の表現があります。一部の表現は、タイプ byte、int、double、JSObject、および Object に対してさらに特殊化されています。ソースコードはこちらにあります。注: 現在、JavaScript 配列はまだ Truffle ライブラリを使用していません。

次のセクションでは、配列表現の複数の実装戦略について説明し、最終的に Truffle ライブラリをどのように使用してこれを実現できるかを説明します。

戦略 1: 表現ごとの特殊化 #

この戦略では、最初に 2 つの表現 BufferArray と SequenceArray のクラスを宣言することから始めます。

final class BufferArray {
    int length;
    int[] buffer;
    /*...*/
}

final class SequenceArray {
    final int start;
    final int stride;
    final int length;
    /*...*/
}

BufferArray 実装には可変バッファと長さがあり、具体化された配列表現として使用されます。シーケンス配列は、final フィールド start、stride、および length で表されます。

ここで、次のように基本的な読み取り操作を指定します。

abstract class ExpressionNode extends Node {
    abstract Object execute(VirtualFrame frame);
}

@NodeChild @NodeChild
abstract class ArrayReadNode extends ExpressionNode {

    @Specialization
    int doBuffer(BufferArray array, int index) {
        return array.buffer[index];
    }

    @Specialization
    int doSequence(SequenceArray seq, int index) {
        return seq.start + seq.stride * index;
    }
}

配列読み取りノードは、バッファバージョンとシーケンスの2つの特殊化を指定します。前述のように、簡単にするためにエラー境界チェックは無視します。

次に、range(start, stride, length)[2] の例で start と stride が定数である場合に折りたたみができるように、配列の読み取りをシーケンスの値の定数性で特殊化するように試みます。start と stride が定数かどうかを判断するには、それらの値をプロファイルする必要があります。これらの値をプロファイルするには、次のように配列読み取り操作に別の特殊化を追加する必要があります。

@NodeChild @NodeChild
class ArrayReadNode extends ExpressionNode {
    /* doBuffer() */
    @Specialization(guards = {"seq.stride == cachedStride",
                              "seq.start  == cachedStart"}, limit = "1")
    int doSequenceCached(SequenceArray seq, int index,
             @Cached("seq.start")  int cachedStart,
             @Cached("seq.stride") int cachedStride) {
        return cachedStart + cachedStride * index;
    }
    /* doSequence() */
}

この特殊化の投機ガードが成功した場合、start と stride は事実上定数になります。たとえば、値 3 と 2 の場合、コンパイラは 3 + 2 * 2、つまり 7 を確認します。制限は、この推測を1回だけ試すために 1 に設定されています。これにより、コンパイルされたコードに追加の制御フローが導入されるため、制限を増やすと非効率的になる可能性があります。投機が成功しなかった場合、つまり、操作が複数の start および stride 値を観測した場合、通常のシーケンス特殊化にフォールバックします。これを実現するために、doSequenceCached のように replaces = "doSequenceCached" を追加して doSequence 特殊化を変更します。

@NodeChild @NodeChild
class ArrayReadNode extends ExpressionNode {
    /* doSequenceCached() */
    @Specialization(replaces = "doSequenceCached")
    int doSequence(SequenceArray seq, int index) {
        return seq.start + seq.stride * index;
    }
}

これで、追加のプロファイリングを含む配列表現を実装するという目標を達成しました。戦略 1 の実行可能なソースコードは、こちらにあります。この戦略にはいくつかの優れた特性があります。

操作は読みやすく、すべてのケースが完全に列挙されています。
読み取りノードの生成されたコードでは、ランタイムでどの表現タイプが観測されたかを記憶するために、特殊化ごとに 1 ビットのみが必要です。

これに問題がなければ、このチュートリアルはすでに完了しているはずです。

新しい表現を動的にロードすることはできません。静的に知っている必要があり、表現タイプと操作の分離が不可能になります。
表現タイプの変更または追加には、多くの場合、多くの操作の変更が必要です。
表現クラスは、ほとんどの実装の詳細を操作に公開する必要があります (カプセル化なし)。

これらの問題が、Truffle ライブラリの主な動機です。

戦略 2: Java インターフェース #

次に、Java インターフェースを使用してこれらの問題に対処しようとします。最初に、配列インターフェースを定義します。

interface Array {
    int read(int index);
}

実装は、Array インターフェースを実装し、表現クラスで読み取りメソッドを実装できます。

final class BufferArray implements Array {
    private int length;
    private int[] buffer;
    /*...*/
    @Override public int read(int index) {
        return buffer[index];
    }
}

final class SequenceArray implements Array {
    private final int start;
    private final int stride;
    private final int length;
    /*...*/
    @Override public int read(int index) {
        return start + (stride * index);
    }
}

最後に、操作ノードを指定します。

@NodeChild @NodeChild
abstract class ArrayReadNode extends ExpressionNode {
    @Specialization
   int doDefault(Array array, int index) {
        return array.read(index);
    }
}

この操作実装の問題は、部分評価器が配列レシーバーにどの具象型があるかを知らないことです。したがって、部分評価を停止し、read メソッド呼び出しの低速なインターフェース呼び出しを発行する必要があります。これは望ましくありませんが、次のようにポリモーフィック型キャッシュを導入して解決できます。

class ArrayReadNode extends ExpressionNode {
    @Specialization(guards = "array.getClass() == arrayClass", limit = "2")
    int doCached(Array array, int index,
           @Cached("array.getClass()") Class<? extends Array> arrayClass) {
        return arrayClass.cast(array).read(index);
    }

    @Specialization(replaces = "doCached")
    int doDefault(Array array, int index) {
        return array.read(index);
    }
}

実装を部分的に評価するという問題を解決しましたが、このソリューションでは、定数のストライドと開始インデックス最適化のための特別な特殊化を表現する方法がありません。

これまでに発見/解決した内容は次のとおりです。

インターフェースは、Java におけるポリモーフィズムの既存のよく知られた概念です。
新しいインターフェース実装をロードして、モジュール化を有効にすることができます。
低速パスから操作を使用するための便利な方法が見つかりました。
表現タイプは、実装の詳細をカプセル化できます。

ただし、新しい問題も発生しました。

表現固有のプロファイリング/キャッシングを実行できません。
すべてのインターフェース呼び出しには、呼び出しサイトにポリモーフィッククラスキャッシュが必要です。

戦略 2 の実行可能なソースコードは、こちらにあります。

戦略 3: Truffle ライブラリ #

Truffle ライブラリは、Java インターフェースと同様に機能します。Java インターフェースの代わりに、Library クラスを拡張する抽象クラスを作成し、@GenerateLibrary でアノテーションを付けます。インターフェースと同様に抽象メソッドを作成しますが、先頭にレシーバー引数 (この場合は Object 型) を挿入します。インターフェースタイプチェックを実行する代わりに、通常は is${Type} という名前のライブラリの明示的な抽象メソッドを使用します。

これを例として実行します。

@GenerateLibrary
public abstract class ArrayLibrary extends Library {

    public boolean isArray(Object receiver) {
        return false;
    }

    public abstract int read(Object receiver, int index);
}

この ArrayLibrary は、isArray と read の 2 つのメッセージを指定します。コンパイル時に、アノテーションプロセッサはパッケージ保護されたクラス ArrayLibraryGen を生成します。生成されたノードクラスとは異なり、このクラスを参照する必要は決してありません。

Java インターフェースを実装する代わりに、表現タイプで @ExportLibrary アノテーションを使用してライブラリをエクスポートします。メッセージエクスポートは、表現のインスタンスメソッドを使用して指定されるため、ライブラリのレシーバー引数を省略できます。

この方法で最初に実装する表現は BufferArray 表現です。

@ExportLibrary(ArrayLibrary.class)
final class BufferArray {
    private int length;
    private int[] buffer;
    /*...*/
    @ExportMessage boolean isArray() {
      return true;
    }
    @ExportMessage int read(int index) {
      return buffer[index];
    }
}

この実装はインターフェース版と非常によく似ていますが、さらにisArrayメッセージを指定します。ここでも、アノテーションプロセッサがライブラリの抽象クラスを実装するボイラープレートコードを生成します。

次に、シーケンス表現を実装します。まず、開始値とストライド値の最適化を行わずに実装します。

@ExportLibrary(ArrayLibrary.class)
final class SequenceArray {
    private final int start;
    private final int stride;
    private final int length;
    /*...*/
    @ExportMessage int read(int index) {
        return start + stride * index;
    }
}

ここまではインターフェース実装と同等でしたが、Truffleライブラリを使用すると、メソッドの代わりにクラスを使用してメッセージをエクスポートすることにより、表現内で特殊化を使用できるようになります。慣例では、クラス名はエクスポートされたメッセージとまったく同じですが、最初の文字は大文字になります。

次に、このメカニズムを使用して、ストライドと開始の特殊化を実装します。

@ExportLibrary(ArrayLibrary.class)
final class SequenceArray {
    final int start;
    final int stride;
    final int length;
    /*...*/

    @ExportMessage static class Read {
        @Specialization(guards = {"seq.stride == cachedStride",
                                  "seq.start  == cachedStart"}, limit = "1")
        static int doSequenceCached(SequenceArray seq, int index,
                 @Cached("seq.start")  int cachedStart,
                 @Cached("seq.stride") int cachedStride) {
            return cachedStart + cachedStride * index;
        }

        @Specialization(replaces = "doSequenceCached")
        static int doSequence(SequenceArray seq, int index) {
            return doSequenceCached(seq, index, seq.start, seq.stride);
        }
    }
}

メッセージは内部クラスを使用して宣言されているため、レシーバー型を指定する必要があります。通常のノードと比較して、このクラスはNodeを拡張してはならず、そのメソッドはstaticである必要があります。これにより、アノテーションプロセッサがライブラリのサブクラス用の効率的なコードを生成できるようになります。

最後に、読み取り操作で配列ライブラリを使用する必要があります。ライブラリAPIは、ライブラリへのディスパッチを担当する@CachedLibraryと呼ばれるアノテーションを提供します。配列の読み取り操作は次のようになります。

@NodeChild @NodeChild
class ArrayReadNode extends ExpressionNode {
    @Specialization(guards = "arrays.isArray(array)", limit = "2")
    int doDefault(Object array, int index,
                  @CachedLibrary("array") ArrayLibrary arrays) {
        return arrays.read(array, index);
    }
}

戦略2で見た型キャッシュと同様に、ライブラリを特定の値に特殊化します。@CachedLibraryの最初の属性である"array"は、ライブラリが特殊化される値を指定します。特殊化されたライブラリは、特殊化された値に対してのみ使用できます。他の値で使用すると、フレームワークはアサーションエラーで失敗します。

パラメーター型としてArray型を使用する代わりに、ガードでisArrayメッセージを使用します。特殊化されたライブラリを使用するには、特殊化の制限を指定する必要があります。制限は、操作がライブラリのキャッシュされていないバージョンを使用するように書き換えられるまで、ライブラリの特殊化をいくつインスタンス化できるかを指定します。

配列の例では、2つの配列表現のみを実装しました。したがって、制限を超えることは不可能です。実際の配列実装では、より多くの表現を使用する可能性があります。制限は、代表的なアプリケーションで超過する可能性が低い値に設定する必要がありますが、同時に過剰なコードを生成しないようにする必要があります。

ライブラリのキャッシュされていないまたはスローパスバージョンは、特殊化の制限を超えることで到達できますが、配列操作をノードが利用できない場合に呼び出す必要がある場合など、手動で使用することもできます。これは通常、言語実装の頻繁に呼び出されない部分に当てはまります。インターフェース戦略（戦略2）では、インターフェースメソッドを呼び出すだけで配列の読み取り操作を使用できました。

Truffleライブラリでは、最初にライブラリのキャッシュされていないバージョンを検索する必要があります。@ExportLibraryを使用するたびに、キャッシュされたライブラリと、キャッシュされていない/スローパスライブラリのサブクラスが生成されます。エクスポートされたライブラリのキャッシュされていないバージョンは、@GenerateUncachedと同じセマンティクスを使用します。通常、この例のように、キャッシュされていないバージョンは自動的に導出できます。DSLは、キャッシュされていないバージョンを生成する方法に関する詳細が必要な場合はエラーを表示します。ライブラリのキャッシュされていないバージョンは、次のように呼び出すことができます。

ArrayLibrary arrays = LibraryFactory.resolve(ArrayLibrary.class).getUncached();
arrays.read(array, index);

この例の冗長さを減らすために、ライブラリクラスは次のオプションの静的ユーティリティを提供することをお勧めします。

@GenerateLibrary
public abstract class ArrayLibrary extends Library {
    /*...*/
    public static LibraryFactory<ArrayLibrary> getFactory() {
        return FACTORY;
    }

    public static ArrayLibrary getUncached() {
        return FACTORY.getUncached();
    }

    private static final LibraryFactory<ArrayLibrary> FACTORY =
               LibraryFactory.resolve(ArrayLibrary.class);
}

上記の冗長な例は、次のように簡略化できます。

ArrayLibrary.getUncached().readArray(array, index);

戦略3の実行可能なソースコードは、こちらにあります。

結論 #

このチュートリアルでは、Truffleライブラリを使用すると、表現ごとの特殊化を作成することによって表現型のモジュール性を損なう必要がなくなり（戦略1）、インターフェース呼び出しによってプロファイリングがブロックされなくなる（戦略2）ことを学びました。Truffleライブラリを使用すると、型カプセル化によるポリモーフィックディスパッチがサポートされるようになりましたが、表現型でプロファイリング/キャッシュ技術を使用する機能は失われません。

次に何をすべきか？ #

すべての例を実行してデバッグしてくださいこちら。
Truffleライブラリの使用例として、相互運用性の移行ガイドを読んでくださいこちら。
Truffleライブラリの参照ドキュメントを読んでくださいこちら。

FAQ #

既知の制限はありますか？

ライブラリのエクスポートは現在、super実装を明示的に呼び出すことはできません。これにより、リフレクティブな実装は現在実行不可能になります。例については、こちらを参照してください。
戻り値のボクシング除去は現在サポートされていません。メッセージは1つの汎用的な戻り型しか持つことができません。これのサポートが計画されています。
Libraryクラスへの静的依存関係のないリフレクションは、現在サポートされていません。完全な動的リフレクションのサポートが計画されています。

Truffleライブラリはいつ使用する必要がありますか？

いつ使用するか？

表現がモジュール式であり、操作に対して列挙できない場合（例：Truffle相互運用性）。
型の表現が複数あり、いずれかの表現でプロファイリング/キャッシュが必要な場合（例：動機付けとなる例を参照）。
言語のすべての値をプロキシする方法が必要な場合（例：動的な汚染追跡の場合）。

いつ使用しないか？

表現が1つしかない基本型の場合。
インタープリターを高速化するためにボクシング除去が必要なプリミティブ表現の場合。ボクシング除去は、現時点ではTruffleライブラリではサポートされていません。

言語固有の型を抽象化するためにTruffleライブラリを使用することにしました。それらは他の言語やツールに公開する必要がありますか？

すべてのライブラリは、ReflectionLibraryを介して他の言語やツールからアクセスできます。言語実装のドキュメントでは、どのライブラリとメッセージが外部で使用されることを目的としているか、およびどのライブラリとメッセージが破壊的な変更の対象となる可能性があるかを指定することをお勧めします。

ライブラリに新しいメソッドが追加されたが、動的にロードされた実装が更新されていない場合はどうなりますか？

ライブラリメソッドがabstractと指定されている場合は、AbstractMethodErrorがスローされます。それ以外の場合は、ライブラリメソッド本体で指定されたデフォルトの実装が呼び出されます。これにより、抽象メソッドが使用された場合にエラーをカスタマイズできます。たとえば、Truffle相互運用性の場合、AbstractMethodErrorの代わりにUnsupportedMessageExceptionをスローすることがよくあります。