Project

General

Profile

Actions

Perfomance penalty of java.util.Stack

This is copy of the original #26 discussion

I've been profiling exp4j in particular Expression.evaluate(), from the profiling I gathered the following data (using Netbeans profiler):

Using Stack                 100.00%

evaluate()         19633    100.00%     
 Total Stack       10900     55.52%     
  Stack.pop()       5219     26.58%  
  Stack.push()      3361     17.12%
  Double.valueOf()  2320     11.82%  
 HashMap.get()      1479      7.53%
-----------------------------------
Using LinkedList             85.48%

evaluate()         16782    100.00%
 Total LinkedList   8938     53.26%
  LinkedList.push() 3670     21.87%
  LinkedList.pop()  2705     16.12%
  Double.valueOf()  2563     15.27%
 HashMap.get()      1493      8.90%
-----------------------------------
Using ArrayStack             46.45%

evaluate()          9120    100.00%
 Total ArrayStack    971     10.65%
  ArrayStack.push()  590      6.47%
  ArrayStack.pop()   381      4.18%
 HashMap.get()      1452     15.92%

The results show that most of the time used by Expression.evaluate() is wasted on the use of java.util.Stack which is backed by java.util.Vector.
I tested again using java.util.LinkedList which can be used as a drop in replacement for java.util.stack, it shows some improvements (~15%) but the boxing/unboxing process still takes up a lot of time.
Finally I've created a simple ArrayStack class that works with an array of doubles directly and doesn't need to box/unbox nor to adapt the methods from java.util.Vector to push() and pop(). The final result is that the Expression.evaluate() uses less than 50% of the time.

About the table:
The second column of the table is the total time in ms used by the method in 1M excecutions.

The profiled code was:

public class Test {
    static final String EXPRESSION = "log(x) - y * sqrt(x^cos(y)) "
                                   + "+ 43 / 9 * sin(x) - 3 ^ (-3)";
    public static void main(String[] args) {
        final Expression expression = new ExpressionBuilder(EXPRESSION)
                .variables("x", "y")
                .build();
        Random rnd = new Random();
        double val = 0;
        int count = 0;
        while (count < 1000000) {
            expression.setVariable("x", rnd.nextDouble());
            expression.setVariable("y", rnd.nextDouble());
            val += expression.evaluate();
            count++;
        }
        System.out.println(val);
    }
}

Looking forward now most of the time seems to be used retrieving the variable values.

Updated by Federico Vera almost 3 years ago · 2 revisions

Go to top