Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Perfomance penalty of java.util.Stack #28

Closed
dktcoding opened this issue Jan 20, 2015 · 5 comments
Closed

Perfomance penalty of java.util.Stack #28

dktcoding opened this issue Jan 20, 2015 · 5 comments

Comments

@dktcoding
Copy link

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.

@fasseg
Copy link
Owner

fasseg commented Jan 20, 2015

Nice!
I always wanted to look into different Stack impls for the algo, but never got to it. Unfortunately I'm very short on time at the moment and will probably not be able to take a look at it until the weekend. Im sorry about that but please don't feel discouraged either (see #26). I very much like what you have done.

@dktcoding
Copy link
Author

No problem, I've been using exp4j for a while now, and I'm glad to contribute.

fasseg added a commit that referenced this issue Jan 27, 2015
@fasseg
Copy link
Owner

fasseg commented Jan 27, 2015

Cherry picked this into master.

@fasseg
Copy link
Owner

fasseg commented Jan 27, 2015

@dktcoding
I added you as a contributor to the exp4j's pom after adding your ArrayStack to master. Please let me know if the information in the pom is accurate and if you agree to have this info published on the exp4j maven project page at http://objecthunter.net/exp4j/team-list.html.

https://github.com/fasseg/exp4j/blob/master/pom.xml#L63

@dktcoding
Copy link
Author

@fasseg yes, the information is accurate. Thanks!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants