Processing AST with ActiveSpecializer
Tags: java, performance
Published: 2020-11-05 17:42:41


## Intro
[**ActiveSpecializer**](https://specializer.activej.io) is a lightweight library that automagically optimizes your code for JVM and makes it significantly faster. Unlike traditional compiler optimization techniques, it relies on an alternative concept of using runtime information of classes instances, rewriting the bytecode in runtime. It transforms all class fields into static class fields, and de-virtualizes all virtual methods calls, replaces them with static method calls.

It is a really powerful tool, particularly when it comes to tree-like structures. Let's take a look at a use case.
We will use **ActiveSpecializer** for transforming ASTs that we'll receive after equation parsing. In the end of the article we'll make some benchmarks to see how **ActiveSpecializer** coped with the problem. Let's get started!

## Parsing Equation to AST
This tutorial is based on the [Parsec calculator tutorial](https://github.com/jparsec/jparsec/wiki/Tutorial). Yet, it has an important distinction. In the original tutorial Parsec parses expressions to double values:

```java
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);
```

Instead, we will parse the expressions to an AST:

```java
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);
```

For example, `2 - 4 * 6` will be parsed like this:

![unnamed](https://dev-to-uploads.s3.amazonaws.com/i/sk12wbnqrnsgmhy2e7g5.png)
 

We will parse to an AST the following equation: `((2 + 2 * 2) * -x) + 5 + 1024 / (100 + 58) * 50 * 37 - 100 + 2 * x ^ 2 % 3`.

**ActiveSpecializer** will transforms the received AST to a set of static final classes with baked-in values of the provided equation. During runtime JIT significantly optimizes and inlines these classes. As a result, we will receive an optimized reusable expression instance.

All you need to do to use **ActiveSpecializer** is:

```java
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));
}
```
## Benchmarks
It’s time for some benchmarks. We will process the aforementioned equation in three different ways and compare the performance:

```java
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);
```

* manually enter the equation
* parse the equation to an AST and evaluate it without specialization
* parse the equation to an AST and evaluate it with specialization

We used JMH in AvarageTime mode as a benchmark tool. All the results are represented as nanoseconds per operation.
```
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
```

As you can see, specialized AST was processed just as fast as a a manually typed equation, while non-specialized AST was processed 8 times slower. **ActiveSpecializer** proved its substantial efficiency!