Question - Iterating through an ArrayList

Newbie & Debugging Questions
#1

Hello

I was looking for the bottlenect in my game and I find it at a strange place and I wonder why.

So the game is basically a lag test in which I have n circle. The bottleneck was iterating through a small (between 1 and 5 elements) ArrayList n*n time. I was using this code to iterate :

for(int i : list){
              //Do something
        }

I fix it by using this code :

for(int i=0; i<list.size(); i++){
              //Do something
        }

So my question is why does it fix it. Is it because with for(int i : list) it creates an Iterator object and that’s what take more time?

#2

enhanced for loop over int[]


// YOUR code

int[] array = ...;
for(int item: array)
   // stuff



// REAL code

int[] array = ...;
for(int i=0; i<array.length; i++)
   int item = array[i]; // stuff

enhanced for loop over List


// YOUR code

List<Integer> list = ...;
for(int item: list)
   // stuff



// REAL code

List<Integer> list= ...;
Iterator it = list.iterator();
while(it.hasNext());
   int item = ((Integer)it.next()).intValue(); // stuff
#3

I would have thought the first method to be the fastest actually.

Switching the i++ to read ++i might speed things up somewhat as well believe it or not :smiley:

// Json

#4

Don’t forget that iterator.hasNext() and iterator.next() must both perform exactly the same bounds checks.

#5

Of course you can optimise it some more as well.


final int size = list.size();

for(int i = 0; ++i < size;) {
    //Do something
}

No need to call the size() method every time :smiley:

// Json

#6

My point is that these are very different beasts:

`for(int item: array)
// stuff

for(int item: list)
// stuff`

#7

The second was nearly 2 times faster in my case.

#8

It was 2 ArrayList. (but I guess it still apply)

#9

How was the ArrayList declared if I may ask?

// Json

#10

this is something that may happend when you program at a “too high level”, like in this one you dont tell to the processor/computer what kind of variables/objects that bunch of code will use so the code is very “Generics” but very slow too…

[quote]Switching the i++ to read ++i might speed things up somewhat as well believe it or not
[/quote]
? i++ & ++i are both using “negligable” cpu in comparaison of others instructions in the loop

#11

When I create the object containing the ArrayList at the begin of the game. That’s the exact line :

protected ArrayList<Integer> positionLevel = new ArrayList<Integer>();
#12

The first example will be less efficient because it requires an implicit conversion between Integer and int, due to autoboxing. You might find it performs better like this:

for(Integer i : list){
              //Do something
        }

However, “i” will still probably require conversion to int (either implicitly or explicitly) for it to be useful in your code.

#13

@davidc I tried it but it doesn’t seems to affect the speed.

#14

Why not put your ints in an int[]

#15

You might be doing an implicit conversion inside the loop itself, which affects the performance in the same way.

That’s what I would do if performance was the top priority and the code was being called often enough to warrant it. You lose the flexibility of an array list but avoid autoboxing altogether. If it comes down to it, you can create an array of fixed size and then reallocate if it needs to be bigger. This is fine if you know what the maximum size will be.

#16

You could try Primative collections for Java? There’s a bunch of collections written in the same api style but specifically coded to only deal with one type of primitive at a time. That should give you the flexibility of a resizable array but without the overhead of iterators or autoboxing.

#17

Then there is also the javolution libraries for performance.

http://javolution.org/

// Json