Take the 2-minute tour ×

So I am part way through writing my first game on Android and after watching a lengthy presentation on optimising for games, I have been checking my allocations. I have managed to get rid of all in-game allocations apart from ones made my ArrayList when it creates an implicit iterator for the for(Object o : m_arrayList) convention.

There are a fair few of these iterations/allocations since all of my game objects, ai entities etc. are stored in these for their ease of use.

So what are my options?

  • I could, theoretically specify sensible upperbounds and use arrays, but I like the features of ArrayList such as exists and remove that keep code clean and simple.

  • Override ArrayList and provide my own implementation of iterator() that returns a class member rather than allocating a new iterator type each time it is used.

I would prefer to go for option 2 for ease of use, but I had a little go at this and ran into problems. Does anyone have an example of what I described in option 2 above? I was having problems inheriting from a generic class, type clashes apparently.

The second question to this then is are there any other options for avoiding these allocations?

And I guess as a bonus question, Does anyone know if ArrayList preallocates a number of memory slots for a certain amount (specified either in the ctor or as some shiftable value) and would never need to do any other allocations so long as you stay within those bounds? Even after a clear()?

Thanks in advance, sorry there is so much there but I think this information could be useful to a lot of people.

share|improve this question
I don't see any mention of testing/profiling. Is this actually a performance bottleneck? –  Thomas Dec 21 '11 at 19:50
per your bonus question, an ArrayList constructed without an initial capacity parameter allocates space for 10 objects in the list initially and grows by the initial capacity when needed. You can call trimToSize to save space. –  Pedantic Dec 21 '11 at 19:50
For the bonus question ,ArrayList allocates a capacity of 10 by default. stackoverflow.com/a/4666050/340068 –  Alok Kulkarni Dec 21 '11 at 19:52
@Thomas. Potentially, potentially not, there are occasional pauses on lower spec phones which I can only really put down to GC but cannot confirm it 100%. But I thought that if I can substitute ArrayList for some other type then this would be a quick win anyway with no negative consequences anywhere. –  makar Dec 21 '11 at 20:05
add comment

2 Answers

up vote 3 down vote accepted

Use positional iteration.

for ( int i = 0, n = arrayList.size( ); i < n; ++i )
   Object val = arrayList.get( i );

That's how it was done before Java 5.

For preallocation.

ArrayList arrayList = new ArrayList( numSlots );

or at runtime

arrayList.ensureCapacity( numSlots );

And for a bonus -> http://docs.oracle.com/javase/6/docs/api/java/util/ArrayList.html

share|improve this answer
Thanks, I did think about this method and in fact used to use something like this but was put off after doing a little research. It would appear that the get(i) function is slower for iterating through when compared with iterators. The trade off being the allocations saved I suppose.... Might have to experiment –  makar Dec 21 '11 at 19:50
@makar. Actually for ArrayLists get would be as fast or faster than using iterators. It references directly a positional element of underlying array. –  Alexander Pogrebnyak Dec 21 '11 at 19:54
it wasn't done this way before Java 5. Iterators have been around for forever in java. –  jtahlborn Dec 21 '11 at 20:01
That's interesting, I will try and find whatever made me think otherwise, if indeed I ever did. Perhaps I was thinking of some other collection. –  makar Dec 21 '11 at 20:02
@jtahlborn. You are correct! Iterators were there before Java 5, but for( Object obj : collection ) loop was not. –  Alexander Pogrebnyak Dec 21 '11 at 22:20
show 1 more comment

I'll answer the bonus question first: Yes, ArrayList does pre-allocate slots. It has a constructor that takes the desired number of slots as an argument, e.g. new ArrayList<Whatever>(1000). clear does not deallocate any slots.

Returning a shared iterator reference has a few problems. The main problem is that you have no way of knowing when the iterator should be reset to the first element. Consider the following code:

CustomArrayList<Whatever> list = ...
for (Whatever item : list) {
for (Whatever item : list) {

The CustomArrayList class has no way of knowing that its shared iterator should be reset between the two loops. If you just reset it on every call to iterator(), then you'll have a problem here:

for (Whatever first : list) {
    for (Whatever second : list) {

In this case you do not want to reset the iterator between calls.

@Alexander Progrebnyak's answer is probably the best way to iterate over a list without using an Iterator; just make sure you have fast random access (i.e. don't ever use a LinkedList).

I'd also like to point out that you are getting into some pretty heavy micro-optimization here. I'd suggest that you profile your code and find out if allocating iterators is a genuine problem before you invest much time in it. Even in games you should only optimize what needs optimizing, otherwise you can spend many, many days shaving a few milliseconds off a minute-long operation.

share|improve this answer
+1 For micro-optimization –  Alexander Pogrebnyak Dec 21 '11 at 19:56
Thanks for the detailed answer. I was aware of the associated risks of having a single instance iterator returned but was happy to abide by the rules required if it meant stopping the allocations. As to your other point, I have been quite careful all along to not do any iterations in game so seeing all of those implicit allocations spewing out is a little frustrating! I've resisted the urge to do a lot of optimisations too early but felt that if I could just swap my ArrayLists to another type then it would be a quick fix with no bearing on anything else. But point taken! –  makar Dec 21 '11 at 20:01
*not to do any allocations. not iterations. –  makar Dec 21 '11 at 20:07
add comment

Your Answer


