Iterator and LinkedList

Game Mechanics
#1

Hi, Tom

I saw your changes in World. You used a LinkedList for the Listeners and an Interator to iterate them. Both is not a good idea at this point.

Iterating a LinkedList through an Iterator is done in someting like O(n squared) time in Java, which is not good. So a LinkedList should be avoided if iterated (at least in perfomance critical sections).

Using an Iterator or the Java 5 loops (which are backed by an Iterator) in performance critical sections cases additional GC and should be avoided.

We had to realize this in Xith3D, too. And we had to convert all uses of an Iterator or Java 5 loops in performance critical sections by the conventional for (int i …) loops.

If this is done in any other critical section in the code, you should replace them all by for (int i …) loops. It will save a lot of GC time.

Marvin

#2

I also noticed this when refactoring for static variable use, but mostly left it alone. I think though, that we should discuss it on the joode-dev mailing list:

http://sourceforge.net/mailarchive/forum.php?forum_id=51541

#3

Really? A quick look at the source (at least in 1.6) suggests that iteration is performed in a non-brain-damaged way i.e. O(n). It would be a spectacular oversight on Sun’s part to be iterating a linked list in O(n2).
Do you have any benchmarks that demonstrate this?

#4

No, I don’t have any benchmarks. I just read the 1.6er sourcecode. But it seems, that I had a look at the wrong Iterator implementation. iterating a LinkedList through the Iterator is dome in O(n). So, sorry for the false alarm.

The the GC expensiveness stays for the Iterator.

Marvin

#5

err, iterating in O(n^2) is certainly not the case, as any other list in the jdk it iterates in O(n), of course. This also applies to ArrayList, obviously. But that’s not the point. The rest of Marvins concerns is still valid: iterators and linked lists in general are not gc friendly. The foreach is backed by an iterator, though it seems to be faster in some cases. Still it is unknown to me if the bycode optimization is capable of reducing the gc overhead (instrumented byte code doesn’t help in finding that out :frowning: ).

#6

We used YourKit to find the most expensive sections in the Xith code. The Iterators produced a lot of GC, which YourKit reported. After we converted (almost) all of them, we had a lot less GC overhead, which was visible in the YourKit results and which lead to a smooth camera flight in our Q3 benchmark.

Marvin

#7

Okay. I choose to use the Iterator to avoid the n^2 problem. I did not think about the gc though. I will update it.

Tom

#8

Well, maybe you could get away from the LinkedLists at all. In most cases an ArrayList is as good for the job a LinkedList is good for. As long as you don’t want to extensively add objects at the top of the list. And getting away from the Iterator at all in critical sections is worth it. GC overhead can cause annoying hicks in your app. But I saw, you already started to convert some iterator loops to simple int ones.

Marvin

#9

For which Vectors are best. Come on everyone! Let’s join the cascade! :stuck_out_tongue:

#10

Do you mean, we all could help in replacing the Iterator loops?

Sometimes a Vector is a little bit overkill, since it is synchronized. If we don’t need this feature, we could simply use ArrayList. Please look into either Vector’s or ArrayList’s JavaDoc. The difference is explained there. Please tell us, what you prefer.

Marvin

#11

Yeah. Vectors are not useful to us. The engine has no provision for concurrancy (static tmp variables for example), so there is no need to use Vectors. ArrayLists are what we should be using