ActiveSpecializerを使用したASTの処理

イントロ

ActiveSpecializerは、JVMのためにコードを自動的に最適化して、それをかなりより速くします軽量ライブラリです.従来のコンパイラ最適化手法とは異なり、クラスインスタンスのランタイム情報を使用して、実行時にバイトコードを書き換えることの代替概念に依存します.すべてのクラスフィールドを静的クラスフィールドに変換し、すべての仮想メソッド呼び出しを非仮想化し、静的メソッド呼び出しで置き換えます.
特に木のような構造になると、それは本当に強力なツールです.ユースケースを見てみましょう.
ActiveSpecializerを使用して、式解析の後に受信するASTを変換します.記事の最後に、ActiveSpecializerがどのように問題に対処したかを見るためにいくつかのベンチマークを作ります.始めましょう!

ASTに方程式を解析する

このチュートリアルはParsec calculator tutorialに基づいています.しかし、それは重要な区別があります.オリジナルチュートリアルでは、parsecは式を二重値に解析します:

Parser<Double> parser = new OperatorTable<Double>()
    .infixl(op("+", (l, r) -> l + r), 10)
    .infixl(op("-", (l, r) -> l - r), 10)
    .infixl(Parsers.or(term("*"), WHITESPACE_MUL).retn((l, r) -> l * r), 20)
    .infixl(op("/", (l, r) -> l / r), 20)
    .prefix(op("-", v -> -v), 30)
    .build(unit);

代わりに、式をASTに解析します.

private static final Parser<CalculatorExpression> EXPRESSION = new OperatorTable<CalculatorExpression>()
        .infixl(DELIMITERS.token("+").retn(Sum::new), 10)
        .infixl(DELIMITERS.token("-").retn(Sub::new), 10)
        .infixl(DELIMITERS.token("*").retn(Mul::new), 20)
        .infixl(DELIMITERS.token("/").retn(Div::new), 20)
        .infixl(DELIMITERS.token("%").retn(Mod::new), 20)
        .prefix(DELIMITERS.token("-").retn(Neg::new), 30)
        .infixr(DELIMITERS.token("^").retn(Pow::new), 40)
        .build(ATOM);

たとえば、2 - 4 * 6は以下のようにパースされます:

以下の式をASTに解析します.
ActiveSpecializerは、与えられた式の値に焼き付きの静的な最終クラスのセットに、受信ASTを変換します.実行中にJITは大幅に最適化し、これらのクラスをインラインします.その結果、最適化された再利用式のインスタンスを受け取ります.
ActiveSpecializerを使用するために必要なのは以下の通りです.

public static final Parser<CalculatorExpression> PARSER = EXPRESSION.from(LEXER, IGNORED);

private static final Specializer SPECIALIZER = Specializer.create(Thread.currentThread().getContextClassLoader());

public static void main(String[] args) {
    double x = -1;

    CalculatorExpression expression = PARSER.parse("((2 + 2 * 2) * -x) + 5 + 1024 / (100 + 58) * 50 * 37 - 100 + 2 * x ^ 2 % 3");
    CalculatorExpression specialized = SPECIALIZER.specialize(expression);
    System.out.println(specialized.evaluate(x));
}

ベンチマーク

いくつかのベンチマークのための時間です.前述の式を3つの異なる方法で処理し、パフォーマンスを比較します.

String source = "((2 + 2 * 2) * -x) + 5 + 1024 / (100 + 58) * 50 * 37 - 100 + 2 * x ^ 2 % 3";

manual = x -> ((2.0 + 2.0 * 2.0) * -x) + 5.0 + 1024.0 / (100.0 + 58.0) * 50.0 * 37.0 - 100.0 + 2.0 * (Math.pow(x, 2.0)) % 3.0;
ast = SpecializerCalculatorExample.PARSER.parse(source);
specialized = SPECIALIZER.specialize(ast);

は手動で方程式

に入ります

はASTに方程式を解析して、専門化

なしでそれを評価します

は、方程式をASTに解析して、特殊化

でそれを評価します
我々は、ベンチマークツールとしてavaragetimeモードでJMHを使用しました.すべての結果は、動作あたりナノ秒として表されます.

Benchmark                        Mode  Cnt    Score   Error  Units
CalculatorBenchmark.ast          avgt   10  828.924 ± 8.369  ns/op
CalculatorBenchmark.manual       avgt   10  115.985 ± 1.009  ns/op
CalculatorBenchmark.specialized  avgt   10  117.635 ± 1.500  ns/op

ご覧のように、特殊なASTは手動で入力された方程式と同じくらい速く処理されました、一方、非専門のASTは8回遅く処理されました.ActiveSpecializerは、その実質的な効率を証明しました!