Java-Gaming.org Hi !
Featured games (90)
games approved by the League of Dukes
Games in Showcase (773)
Games in Android Showcase (230)
games submitted by our members
Games in WIP (856)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Iterator and LinkedList  (Read 4002 times)
0 Members and 1 Guest are viewing this topic.
Offline Marvin Fröhlich

Senior Devvie




May the 4th, be with you...


« Posted 2007-02-03 23:35:54 »

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
Offline biggeruniverse

Senior Newbie




That's just peanuts to space.


« Reply #1 - Posted 2007-02-04 03:59:37 »

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
Offline ryanm

Senior Devvie


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #2 - Posted 2007-02-04 11:36:56 »

Iterating a LinkedList through an Iterator is done in someting like O(n squared) time in Java, which is not good.

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?
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Marvin Fröhlich

Senior Devvie




May the 4th, be with you...


« Reply #3 - Posted 2007-02-04 12:10:34 »

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?

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
Offline irrisor

Junior Devvie





« Reply #4 - Posted 2007-02-04 20:12:46 »

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 Sad ).
Offline Marvin Fröhlich

Senior Devvie




May the 4th, be with you...


« Reply #5 - Posted 2007-02-04 20:24:17 »

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
Offline t_larkworthy

Senior Devvie


Medals: 1
Projects: 1


Google App Engine Rocks!


« Reply #6 - Posted 2007-02-05 09:17:26 »

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

Runesketch: an Online CCG built on Google App Engine where players draw their cards and trade. Fight, draw or trade yourself to success.
Offline Marvin Fröhlich

Senior Devvie




May the 4th, be with you...


« Reply #7 - Posted 2007-02-05 13:56:25 »

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.

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
Offline biggeruniverse

Senior Newbie




That's just peanuts to space.


« Reply #8 - Posted 2007-02-05 18:59:29 »

For which Vectors are best. Come on everyone! Let's join the cascade! Tongue
Offline Marvin Fröhlich

Senior Devvie




May the 4th, be with you...


« Reply #9 - Posted 2007-02-05 20:35:29 »

For which Vectors are best. Come on everyone! Let's join the cascade! Tongue

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
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline t_larkworthy

Senior Devvie


Medals: 1
Projects: 1


Google App Engine Rocks!


« Reply #10 - Posted 2007-02-06 10:19:15 »

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

Runesketch: an Online CCG built on Google App Engine where players draw their cards and trade. Fight, draw or trade yourself to success.
Pages: [1]
  ignore  |  Print  
 
 

 
EgonOlsen (1853 views)
2018-06-10 19:43:48

EgonOlsen (1882 views)
2018-06-10 19:43:44

EgonOlsen (1249 views)
2018-06-10 19:43:20

DesertCoockie (1681 views)
2018-05-13 18:23:11

nelsongames (1348 views)
2018-04-24 18:15:36

nelsongames (1966 views)
2018-04-24 18:14:32

ivj94 (2737 views)
2018-03-24 14:47:39

ivj94 (1940 views)
2018-03-24 14:46:31

ivj94 (3030 views)
2018-03-24 14:43:53

Solater (1080 views)
2018-03-17 05:04:08
Deployment and Packaging
by mudlee
2018-08-22 18:09:50

Java Gaming Resources
by gouessej
2018-08-22 08:19:41

Deployment and Packaging
by gouessej
2018-08-22 08:04:08

Deployment and Packaging
by gouessej
2018-08-22 08:03:45

Deployment and Packaging
by philfrei
2018-08-20 02:33:38

Deployment and Packaging
by philfrei
2018-08-20 02:29:55

Deployment and Packaging
by philfrei
2018-08-19 23:56:20

Deployment and Packaging
by philfrei
2018-08-19 23:54:46
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!