An Even Faster Java Expression Evaluator

i’ve been reading the how to write one of the fastest expression evaluators in java article (also published over at jcg ) and thought to myself – there is an even faster way!

thus i whipped up a caliper benchmark which you can check out on my github account .

the benchmark compiles the performance of the following libraries:

• parsii
• jeval
• jeplite
• matheval
• expr
• janino expressionevaluator
• a hand-rolled solution based on janino

before getting into the results, a couple of general words about the state of (open source) expression evaluator libraries in java (i couldn’t test closed source ones because they impose restrictions – like “only 15 expressions evaluated” – which make it impossible to benchmark them):

• none of them are in maven central (or even in maven for that matter – with the exception of janino, but there you still need a different repo to get the latest version)
• their development is mostly stalled
• they are lacking in features and/or are buggy

the benchmark consist in evaluating the 2 + (7-5) * 3.14159 * x + sin(0) expression (similar to the original article). unfortunately the exponentiation part had to be eliminated because not all libraries support it. also, x had to be fixed to 0 because parsii erroneously always considers it zero.

most of the libraries (jeplite and matheval being the exception) separate the idea of “compiling” and “evaluating” the expression. this can be very useful if we wish to evaluate the same expression for a multitude of values of the contained variable. thus the benchmark tests two cases: compile + evaluate and only evaluate (depending on your usecase one or the other is more relevant). also, jeval is by default excluded from the benchmark since it performs so poorly that it eclipses all the other results. if you wish to see just how poorly it performs, uncomment the relevant methods from benchmarkexpressionevaluation.

without further ado, here are the results (smaller is better):

as you can see, the custom implementation beats parsii by a factor of 10x! so how does it work? you can always check out the source code , but i will also explain: it uses janino to compile a class of the form:

import static java.lang.math.*; // to get sin, cos, etc

public static final class janinocompiledfastexpr1234 implements unarydoublefunction {
    public double evaluate(double x) {
        return (/* your expression here */);
    }
}

which you can later invoke. the advantages of this approach are:

• raw speed – as you can see from the benchmark, the java parser / compiler is very well optimized and hard to beat, even when rolling your own parser for a subset of cases
• raw speed the second time – the jit helps us immensely and gives optimizations like constant folding or vectorization for “free”
• brevity – the whole proof of concept is implemented in 60 lines, probably less lines than this article contains
• “garbage free” – after the initial compilation no allocations are made in the heap, but rather all parameters are passed on the stack (since they are primitives)

of course the solutions is not without its drawbacks:

• depending on the source of the expression we could be compiling and executing arbitrary java code sent to us by a malicious user . not a pretty prospect. we try to mitigate this in two ways:
  • whitelist the set of characters allowed in the expression
  • execute all expressions under a special classloader which uses a protectiondomain that has no permissions
• the above isn’t wholly satisfactory however:
  • the compiler itself can have bugs (it has happened in the past )
  • neither of the safety measures efficiently prevent the potential denial of service conditions (like creating infinite loops or consuming all the memory)
• also, this is just a proof of concept – for a more complete solution one would need to add more interfaces (like binarydoublefunction, ternarydoublefunction and also unarylongfunction, etc) as well as some settings related to the naming of the parameters.

still, this is a great example as to the power of the java ecosystem and what can be achieved by thinking  a little outside of the box.

if you run the benchmark for yourself, you might find a couple of interesting things:

• the “janino” test continuously warns about recompilation. this is expected if you think a little bit about it – since at every invocation it “compiles” the expression. the same is true for janinofastexpr
• both janino and janinoprecompiled complain about excessive garbage collection. this is because they use auto-boxing (varargs) to pass the parameters which isn’t very efficient (generates a lot of garbage)

this is it folks, enjoy the source code and hopefully this will inspire people to find better solutions to their problems!