12

This question involves memory management in Java for performance reasons: because I am developing this program as an Android Game and memory GC's kill my performance. So I have done a large amount of work so far and it turns out that I am doing a great job of optimizing the memory usage of my game, but I have one problem: iterators!

Here is what I am doing:

  1. Start game level.
  2. Start allocation tracker (this way we ignore all of the allocations that will remain for as long as the level runs; I have many objects that only get created once at the beginning of the level and they are not the problem).
  3. Do a few things in the level and get the allocations.

My allocations are full of this:

466 24 java.util.AbstractList$SimpleListIterator 12 java.util.AbstractList iterator
465 24 java.util.AbstractList$SimpleListIterator 12 java.util.AbstractList iterator
464 24 java.util.AbstractList$SimpleListIterator 12 java.util.AbstractList iterator
463 24 java.util.AbstractList$SimpleListIterator 12 java.util.AbstractList iterator
461 24 java.util.AbstractList$SimpleListIterator 12 java.util.AbstractList iterator
456 24 java.util.ArrayList$ArrayListIterator 12 java.util.ArrayList iterator
454 24 java.util.ArrayList$ArrayListIterator 12 java.util.ArrayList iterator
453 24 java.util.ArrayList$ArrayListIterator 12 java.util.ArrayList iterator
452 24 java.util.ArrayList$ArrayListIterator 12 java.util.ArrayList iterator

So the only objects that are being allocated while my game is running are iterators! Okay, well now to fix it then...what code is causing the problem I asked...here it is:

for (Segment side : listOfSides.getSides()) {
    // do stuff
}

Yes, it turns out that for-each syntax calls iterator behind the scenes to populate each element. Which makes perfect sense and exactly what I expected it to do but I did not realise that it could build up so horribly and cause a performance problem for games. If I could get rid of this problem then it would really make my game run like lightning no matter what phone it was on. So my question is: what would you do to make it so that all of these temporary iterators were not created and then immediately discarded resulting in nasty GC runs? Bonus points for doing so in a way that does not make my code completely ugly! (And using ndk on Android is not an option)

P.S. I was thinking that for all of my ArrayLists I could start using the get(int i) function as they are arrays behind the scenes and the integer I would use to index that would be placed on the stack and not the heap. But for the other objects like a HashMap and LinkedList I am not sure what to do.

Improve this question
2
  • Your question isn't clear: have you actually profiled the performance of your application, or are you relying solely on the memory profiler? Commented Jul 15, 2012 at 7:46
  • @AndrewAylett The performance of my application is fine. Runs at 60 fps most of the time. Except occasionally when the GC hits; as it is I could just ship this version of Masters of Light (my android game). But I just want to see if I could do better with the garbage collection; for the feeling of producing good quality if nothing else. Commented Jul 15, 2012 at 7:50

3 Answers 3

Reset to default
14

ArrayList and LinkedList let you traverse the elements using get(int i) (note it might be slow for LinkedList, I don't know how get() is implemented.) This is the recommended approach to avoid allocating iterators. If you look at the source code of the platform you will notice that we try to avoid using the for-each syntax as much as possible.

For HashMap you can grab the underlying sets using entrySet() and then call toArray(Object[]) and pass a pre-allocated array big enough to hold all the values. Alternatively, see if you could use the various SparseArray classes offered by Android.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

But calling entrySet allocates a new object, and you are back where you started.
Then maybe values() and keySet()? I seem to remember that one of them didn't create new objects.
I was busy already converting my code to use ArrayList's and then to use the get(i) function but I did not know about the HashMap trick. Though I will have to take a good look at it too if what @StephenC says is correct and figure out which one does not create objects. Really good advice and it was just good to know what the Android team themselves do. Thanks Romain.
Actually, I think I'm wrong ... at least in the Oracle Java codebase. But even so, you are trading off allocating a (small) iterator object against copying a (potentially large) set of entries into an array.
Looking at our codebase it seems that entrySet() will allocate at most once, if the map is empty. The same goes for values() and keySet(). So it's safe to call these methods to avoid allocations.
1

Given the constraints you've placed, the only solutions are to use indexing and either an ArrayList or an array. And for LinkedList and HashMap, I don't think there is a practical alternative that will avoid any allocation.

But is the GC really so slow that you really need to go to the extreme of micro-optimizing like this?

Improve this answer

6 Comments

I agree with you that they seem to be my best options at the current time. And the allocations that I have recorded are occurring in a tight loop (some even more than others). It is just enough to be annoying but, most importantly, I just want to see if it can be done. So in answer to micro optimizing: Why have any lag when you could have none? Atleast that is what I am trying for. In normal circumstances I would agree with you completely; I don't have to worry about this in most apps I write.
"Why have any lag when you could have none?" - That argument is only valid if you have evidence that you have significant lag. Anyway, the classic way to reduce lag is to trigger a GC when you "know" that any lag won't be noticed.
A GC pause will typically last between 1ms all the way up to 100ms. If you are trying to render at 60fps, 1ms can be enough to make you skip a frame (which means the app goes from 60fps to 30fps, then back to 60fps, etc. It's a pretty bad experience.)
Exactly what @RomainGuy said. I almost had commented with very similar words.
He said it as a comment on the original question: "The performance of my application is fine. Runs at 60 fps most of the time. Except occasionally when the GC hits." Then he obviously used one of the tools we provide with the SDK to track down memory allocations. Those are not "micro optimizations." Getting rid of GC pauses is often a worthwile optimization (unless you can find code in your render loop that takes ~1 to 100ms...)
|
0

The foreach loop always gets the iterator when you use it with Lists. There are only two ways to make it not allocate memory; both involve uglying up your code:

  • Use it on a raw array instead of a List (the easiest approach).

  • Use it on a List or other Iterable whose iterator() function doesn't allocate memory. This gets kind of hardcore and is probably not worth it, but I have done it in cases where I really want to optimize a loop. Here's how I did it:

    1. Make your own container class that implements Iterable. (The foreach loop will work on anything at all that implements Iterable, even if it's not a subclass of List.)
    2. Make that class so it doesn't allocate memory when it returns an iterator via the iterator() function. You can do this by having a pool of iterators, grabbing one and resetting its values. You'll likely want a pool instead of just reusing a single one, because some of your code might have multiple nested loops iterating over the same collection.
    3. Spend several hours debugging the above ugly solution. All in all it's not worth it in most cases.
Improve this answer

3 Comments

How would you know when all of the other objects that you have given iterators to were done with them so that they could be returned to the pool? It would seem that you would need some kind of callback?
I didn't come up with a good solution for that actually; I had my higher-level code manually reset it. There's likely a better way but I can't really think of one. One hack would be, if you know for a fact that you'll only be using it with foreach loops, you could maybe have the iterator mark itself free when its .hasNext() returns false, since you know that's the end of a foreach loop. That would obviously be unreliable if loops exit early, or if other code calls iterator.hasNext() and then uses the iterator's current value. So the manual reset is unfortunately the best I can come up with.
Yeah, using an array is by far easier and safer. I think that is what I would do instead of the second option. The second option also breaks conventions and would confuse any new developers. But good out-of-the-box thinking though.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.