CODEWITHSUNDEEP
javaperformancefor-loop
user1094607
user1094607

Reputation: 147

Exponentially increasing amounts of time to repeat a function

I've written my own math parser and for some reason it takes increasing amounts of time to parse when I tried to profile the parser.

For testing I used this input: Cmd.NUM_9,Cmd.NUM_0,Cmd.NUM_0,Cmd.DIV,Cmd.NUM_2,Cmd.ADD,Cmd.NUM_6,Cmd.MULT,Cmd.NUM_3

Single execution ~1.7ms
3000 repeats ~ 1,360ms
6000 repeats ~ 5,290ms
9000 repeats ~11,800ms

The profiler says 64% of the time was spent on this function: this is my function to allow implicit multiplications.

private void enableImplicitMultiplication(ArrayList<Cmd> input) {
    int input_size = input.size();
    if (input_size<2) return;
    for (int i=0; i<input_size; i++) {
        Cmd cmd = input.get(i);
        if (i>0) {
            Cmd last = input.get(i-1);
            // [EXPR1, EXPR2] => [EXPR1, MULT, EXPR2]
            boolean criteria1 = Cmd.exprnCmds.contains(cmd) && Cmd.exprnCmds.contains(last);
            // [CBRAC, OBRAC] => [CBRAC, MULT, OBRAC]
            // [NUM_X, OBRAC] => [NUM_X, MULT, OBRAC]
            boolean criteria2 = cmd==Cmd.OBRAC && (last==Cmd.CBRAC || Cmd.constantCmds.contains(last));
            // [CBRAC, NUM_X] => [CBRAC, MULT, NUM_X]
            boolean criteria3 = last==Cmd.CBRAC && Cmd.constantCmds.contains(cmd);
            if (criteria1 || criteria2 || criteria3) {
                input.add(i++, Cmd.MULT);
            }
        }
    }
}

What's going on here??

I executed the repeats like this:

public static void main(String[] args) {
    Cmd[] iArray = {
        Cmd.NUM_9,Cmd.NUM_0,Cmd.NUM_0,Cmd.DIV,Cmd.NUM_2,Cmd.ADD,Cmd.NUM_6,Cmd.MULT,Cmd.NUM_3
    };
    ArrayList<Cmd> inputArray = new ArrayList<Cmd>(Arrays.asList(iArray));
    DirtyExpressionParser parser = null;
    int repeat=9000;
    double starttime = System.nanoTime();
    for (int i=0; i<repeat; i++) {
         parser = new DirtyExpressionParser(inputArray);
    }
    double endtime = System.nanoTime();
    System.out.printf("Duration: %.2f ms%n",(endtime-starttime)/1000000);
    System.out.println(parser.getResult());
}

Constructor looks like this:

public DirtyExpressionParser(ArrayList<Cmd> inputArray) {
    enableImplicitMultiplication(inputArray); //executed once for each repeat
    splitOnBrackets(inputArray); //resolves inputArray into Expr objects for each bracket-group
    for (Expr expr:exprArray) {
        mergeAndSolve(expr);
    }
}

Upvotes: 0

Views: 184

Answers (1)

Marko Topolnik
Marko Topolnik

Reputation: 200158

Your microbenchmark code is altogether wrong: microbenchmarking on the JVM is a craft in its own right and is best left to dedicated tools such as jmh or Google Caliper. You don't warm up the code, don't control for GC pauses, and so on.

One detail which does come out by analyzing your code is this:

  1. you reuse the same ArrayList for all repetitions of the function call;
  2. each function call may insert an element to the list;
  3. insertion is a heavyweight operation on ArrayList: the whole contents of the list after the inserted element must be copied.

You should at least create a fresh ArrayList for each invocation, but that will not make your whole methodology correct.

From our discussion in the comments I diagnose the following issue you may have with understanding your code:

In Java there is no such thing as a variable whose value is an object. The value of the variable is a reference to the object. Therefore when you say new DirtyExpressionParser(inputArray), the constructor does not receive its own private copy of the list, but rather a reference to the one and only ArrayList you have instantiated in your main method. The next constructor call gets this same list, but now modified by the earlier invocation. This is why your list is growing all the time.

Upvotes: 3

Related Questions