Excessive garbage collection in arithmetic evaluator

Question

I'm attempting to create an Android app which graphs simple mathematical functions that the user inputs (essentially a graphing calculator). Every onDraw call requires hundreds of arithmetic evaluations per second (which are plotted on screen to produce the graph). When my code evaluates the expression the program slows down considerably, when the inbuilt methods evaluate the expression, the app runs with no issue.

According to 'LogCat', garbage collection occurs about 12 times per second, each time pausing the app for roughly 15 milliseconds, resulting in a few hundred milliseconds worth of freezes every second. I think this is the problem.

Here is a distilled version of my evaluator function. The expression to be evaluated is named "postfixEquation", the String ArrayList "list" holds the final answer at the end of the process. There are also two String arrays titled "digits" and "operators" which store the numbers and signs which are able to be used:

String evaluate(String[] postfixEquation) {

    list.clear();

    for (int i = 0; i < postfixEquation.length; i++) {

        symbol = postfixEquation[i];

        // If the first character of our symbol is a digit, our symbol is a numeral
        if (Arrays.asList(digits).contains(Character.toString(symbol.charAt(0)))) {

            list.add(symbol);

            } else if (Arrays.asList(operators).contains(symbol))  {

                // There must be at least 2 numerals to operate on
                if (list.size() < 2) {
                    return "Error, Incorrect operator usage.";
                }

                // Operates on the top two numerals of the list, then removes them 
                // Adds the answer of the operation to the list
                firstItem = Double.parseDouble(list.get(list.size() - 1));
                secondItem = Double.parseDouble(list.get(list.size() - 2));
                list.remove(list.size() - 1);
                list.remove(list.size() - 1);

                if (symbol.equals(operators[0])){ 
                    list.add( Double.toString(secondItem - firstItem) );  
                } else if (symbol.equals(operators[1])) {
                    list.add( Double.toString(secondItem + firstItem) );
                } else if (symbol.equals(operators[2])) {
                    list.add( Double.toString(secondItem * firstItem) );
                } else if (symbol.equals(operators[3])) {
                    if (firstItem != 0) {
                        list.add( Double.toString(secondItem / firstItem) );
                    } else {
                        return "Error, Dividing by 0 is undefined.";
                    }
                } else {
                    return "Error, Unknown symbol '" + symbol + "'.";
                }
            }
        }

    // The list should contain a single item, the final answer 
    if (list.size() != 1) {
        return "Error, " + list has " + list.size() + " items left instead of 1.";
    }

    // All is fine, return the final answer
    return list.get(0);
}

The numerals used in the operations are all Strings, as I was unsure if it was possible to hold multiple types within one array (i.e. Strings and Doubles), hence the rampant "Double.parseDouble" and "Double.toString" calls.

How would I go about reducing the amount of garbage collection that occurs here?

If it's of any help, I have been using these steps to evaluate my postfix expression: http://scriptasylum.com/tutorials/infix_postfix/algorithms/postfix-evaluation/index.htm. I have been unable to get past this issue for weeks and weeks. Any help would be appreciated. Thanks.

Answer 1

The rule for tight loops in Java is don't allocate anything. The fact that you're seeing such frequent GC collections is proof of this.

You appear to be doing calculations with Double, then converting to a String. Don't do that, it's terrible for performance because you create tons and tons of strings then throw them out (plus you are converting back and forth between strings and doubles a lot). Just maintain an ArrayDeque<Double> and use it as a stack -- this also saves you from doing the array resizes that are probably also killing performance.

Precompile the input equations. Convert all the input operations to enum instances -- they are faster to compare (just takes a switch statement), and may even use less memory. If you need to handle doubles, either use a generic Object container and instanceof, or a container class that contains both an operation enum and a double. Precompiling saves you from having to do expensive tests in your tight loop.

If you do these things, your loop should positively fly.

Answer 2

Probably your list manipulation is the source of this problem. Lists internally have arrays, which are expanded/shrunk depending on how much data is on the list. So doing lots of add and removes randomly will heavily require garbage collection.

A solution to avoid this is using the right List implementation for your problem, allocate enough space to the list at the beginning to avoid resizing the internal array and to mark unused elements instead of removing them

The freezing symptoms are because you're doing your calculations in your UIThread. If you don't want your app to freeze, you might want to check AsyncTask to do calculations on a separate thread.

PS: also looks like you're doing some useless operations in there... why parseDouble() secondItem?

Answer 3

The 15ms pauses are not occurring in your UI thread, so they should not be affecting performance to much. If your UI is pausing while your method is executing, consider running it on another thread (with AsyncTask)

To reduce your garbage collection you need to reduce the amount of memory allocated within the loop.

I would suggest looking at:

1. Performing the Arrays.asList functions outside the loop (ideally somewhere that is only executed once such as your constructor or a static constructor)
2. If your list is a LinkedList, consider changing it to an ArrayList
3. If your List is an ArrayList, make sure you initialise it with enough capacity so it won't need to be resized
4. Consider making your List store Objects rather than Strings, then you can store both your symbols and Doubles in it, and don't need to convert back and forward from Double to String as much
5. Consider writing a proper parser (but this is a'lot more work)

Answer 4

However, you are using a lot of strings. While this may not be the case, it's always one of those things you can check out because Java does funky stuff with String. If you are having to convert the string to double as you are outputting, then there's quite a bit of overhead going on.

Do you need to store the data as String? (Note that the answer may actually be yes) Heavy use of temporary strings can actually cause the garbage collector to get fired off often.

Be careful about premature optimization. Profilers and running through the function line-by-line can help