princec
« League of Dukes » JGO Kernel  Posts: 8076 Medals: 91
Eh? Who? What? ... Me?
|
 |
«
Reply #60 on:
2012-01-05 08:49:40 » |
|
No, generally speaking, it creates almost no garbage at all. Unless you create 10,000 bullets every single frame. This does not happen  Cas |
|
|
|
Damocles
Sr. Member  Posts: 264 Medals: 14
|
|
«
Reply #61 on:
2012-01-05 08:49:59 » |
|
I think that depends on the size of your game.
In a smaller game an array is fine, but in a larger Project its not a good choice as it is potentially more error-prone
due to wrong use.
|
|
|
|
princec
« League of Dukes » JGO Kernel Posts: 8076 Medals: 91
Eh? Who? What? ... Me?
|
|
«
Reply #62 on:
2012-01-05 08:51:32 » |
|
I use ArrayLists rather than arrays with current size var because... well, that's what OOP was invented for. So you didn't have to keep doing that sort of crap everywhere. The VM optimises it to the point where it won't make a great deal of difference and as Damocles says, it'll just lead to more errors, duplicated code, and yucky looking code. Cas |
|
|
|
Games published by our own members! Go get 'em! 
|
|
nsigma
Sr. Member Posts: 342 Medals: 18
|
|
«
Reply #63 on:
2012-01-05 09:03:50 » |
|
I use ArrayLists rather than arrays with current size var because... well, that's what OOP was invented for. So you didn't have to keep doing that sort of crap everywhere. The VM optimises it to the point where it won't make a great deal of difference and as Damocles says, it'll just lead to more errors, duplicated code, and yucky looking code.
+1. Use arrays and you'll slowly start writing your own ArrayList, and probably a suboptimal one at that! One possible performance improvement, inspired by @theagentd's comment (or maybe exactly what he means?), would be a list that didn't null everything on clear(), just resets the counter, and has a separate cleanup() method that nulls everything past the counter value. Obviously, you call cleanup() every now and again to GC, but if the size of the list remains fairly constant, that should only need to null a few references rather than iterating through everything on every frame. And it'll be a PITA to implement, and you'll probably gain next to nothing!  |
|
|
|
Grunnt
Jr. Member Posts: 50 Medals: 3
|
|
«
Reply #64 on:
2012-01-05 09:49:18 » |
|
Okay then, these are all good points! I guess I haven't worked on a sufficiently-sized project yet to encounter these problems. I'm open to the idea of doing this 1% less efficiënt to make it 10% less error prone Thanks for the advice, I'll have a good long look at the other approaches described here. |
|
|
|
theagentd
JGO Wizard Posts: 1391 Medals: 88
|
|
«
Reply #65 on:
2012-01-05 10:18:35 » |
|
One possible performance improvement, inspired by @theagentd's comment (or maybe exactly what he means?), would be a list that didn't null everything on clear(), just resets the counter, and has a separate cleanup() method that nulls everything past the counter value. Obviously, you call cleanup() every now and again to GC, but if the size of the list remains fairly constant, that should only need to null a few references rather than iterating through everything on every frame. And it'll be a PITA to implement, and you'll probably gain next to nothing! Exactly what I meant. I claim that one! =S |
There is no god.
|
|
|
princec
« League of Dukes » JGO Kernel Posts: 8076 Medals: 91
Eh? Who? What? ... Me?
|
|
«
Reply #66 on:
2012-01-05 10:50:47 » |
|
The speed of clearing that list to null is incredibly fast. I mean, really, incredibly fast. Even if the list is really, really big. And who knows what benefits it will have on the garbage collector. Probably only positive ones. Premature optimisation ftw! Cas |
|
|
|
theagentd
JGO Wizard Posts: 1391 Medals: 88
|
|
«
Reply #67 on:
2012-01-05 13:25:20 » |
|
What about just nulling out the elements that did not get overwritten after the last buffer migration? GC win plus less nulls. I might write a small class for this one day...
|
There is no god.
|
|
|
ra4king
JGO Kernel Posts: 3149 Medals: 196
I'm the King!
|
|
«
Reply #68 on:
2012-01-05 13:27:02 » |
|
How about (as I pointed out earlier), nulling out the index when removing it, then removing all nulls after the loop ends?
|
|
|
|
nsigma
Sr. Member Posts: 342 Medals: 18
|
|
«
Reply #69 on:
2012-01-05 13:55:24 » |
|
What about just nulling out the elements that did not get overwritten after the last buffer migration? GC win plus less nulls. I might write a small class for this one day...
Knock yourself out, but I'm with princec - I think it's a lot of work for no gain. It's probably not even premature optimisation - you might just be jumping straight to premature evil.  How about (as I pointed out earlier), nulling out the index when removing it, then removing all nulls after the loop ends?
Isn't your suggestion just premature deoptimization! Aren't you just forcing yourself to iterate an extra time, and doing more in the process? |
|
|
|
Games published by our own members! Go get 'em! 
|
|
miga
JGO n00b Posts: 40
|
|
«
Reply #70 on:
2012-01-07 13:49:53 » |
|
I will go with double buffered ArrayList. I'm implementing that on my code right now. It works well so far. I'm gonna test around.
I learned several new things from this topic. Very interesting to hear others' opinions. I have to look more into GC to understand better.
In my case, I believe double buffered ArrayList would be more efficient than Bag. Like I said above, I think keeping entities in spawned order is more appropriate. If I was to use Bag to hold entities, I would be looping backwards to enable removing and not missing any element while iterating. If I need a structure to hold static number of things, then I would just go with array or the most simple.
Thanks a lot guys.
|
|
|
|
Bukky
JGO n00b Posts: 3
|
|
«
Reply #71 on:
2012-02-09 01:50:59 » |
|
May I ask someone to explain the purpose of the temp ArrayList in princec's code example? Setting entities1 = temp right before you .clear() it seems unnecessary, though I'm sure there is a reason for doing so. Is this done to help java's garbage collector?
Thank you,
-Bukky
|
|
|
|
|
ra4king
JGO Kernel Posts: 3149 Medals: 196
I'm the King!
|
|
«
Reply #72 on:
2012-02-09 02:12:36 » |
|
May I ask someone to explain the purpose of the temp ArrayList in princec's code example? Setting entities1 = temp right before you .clear() it seems unnecessary, though I'm sure there is a reason for doing so. Is this done to help java's garbage collector?
Thank you,
-Bukky
The temp ArrayList is used so that you can switch the references of entities0 and entities1. Then you clear entities1 so you can re-add entities then next time the for loop is executed. It is true you could have just done "entities1 = new ArrayList<Entity>()" but why waste memory? Btw, welcome to JGO |
|
|
|
Bukky
JGO n00b Posts: 3
|
|
«
Reply #73 on:
2012-02-09 04:27:27 » |
|
The temp ArrayList is used so that you can switch the references of entities0 and entities1. Then you clear entities1 so you can re-add entities then next time the for loop is executed. It is true you could have just done "entities1 = new ArrayList<Entity>()" but why waste memory? why can't you just do this 1
2
| entities0 = entities1;
entities1.clear(); |
wouldn't that accomplish the same thing? what am I missing here? WHY AM I SO DUMB    Btw, welcome to JGO Thanks! |
|
|
|
|
theagentd
JGO Wizard Posts: 1391 Medals: 88
|
|
«
Reply #74 on:
2012-02-09 04:41:50 » |
|
The temp ArrayList is used so that you can switch the references of entities0 and entities1. Then you clear entities1 so you can re-add entities then next time the for loop is executed. It is true you could have just done "entities1 = new ArrayList<Entity>()" but why waste memory? why can't you just do this 1
2
| entities0 = entities1;
entities1.clear(); |
wouldn't that accomplish the same thing? what am I missing here? WHY AM I SO DUMB Btw, welcome to JGO Thanks! You're probably mixing up references and instances. In this case we have two instances of ArrayList. We also have two references, each pointing to one of the ArrayList instances. With your code you'd set both references to point to the same instance, and one of the ArrayList instances will be forever unreachable and garbage collected. Picture yourself holding two apples (instances), one in each hand (reference). How do you switch apples between your hands? You can't hold two apples in one hand, so you'll have to put one apple down on a table (the temp ArrayList reference), then move the other apple to the first hand and finally pick up the first apple from the table with your other hand. I may have just overcomplicated it a lot, but I hope you understand... xD |
There is no god.
|
|
|
ra4king
JGO Kernel Posts: 3149 Medals: 196
I'm the King!
|
|
«
Reply #75 on:
2012-02-09 14:31:13 » |
|
Also you gotta remember that a variable (of class types) only references the object. Here, both entities0 and entities1 refer to the same object This calls the clear() method of the object referenced by entities1, the same object referenced by entities0. Before all this, entities0 and entities1 referred to 2 different objects and, as theagentd explained, we simply switched the references and cleared one. |
|
|
|
Bukky
JGO n00b Posts: 3
|
|
«
Reply #76 on:
2012-02-09 20:58:16 » |
|
I may have just overcomplicated it a lot, but I hope you understand... xD
No, that was a beauteous metaphor. Before all this, entities0 and entities1 referred to 2 different objects and, as theagentd explained, we simply switched the references and cleared one.
Thank you both theagentd and ra4king, I understand now! |
|
|
|
|
kaffiene
Sr. Member Posts: 418 Medals: 1
|
|
«
Reply #77 on:
2012-02-09 21:30:34 » |
|
Just one side note I would like to make: there is almost no situation in existence, ever, that you would want to use a LinkedList. It exists mostly as a curiosity for computer science degrees as an example of a data structure that has no practical application, like the infamous bubble sorting algorithm. Cas Linked lists are the building blocks for structures like B* trees which are your basic database index structure. |
|
|
|
|
kaffiene
Sr. Member Posts: 418 Medals: 1
|
|
«
Reply #78 on:
2012-02-09 21:33:38 » |
|
Sun...ehrm...Oracle did an amazing job of forcing us to write our own collections for performance.
That's no different to any other language. C++ game developers don't naively use every container in STL either, you know. |
|
|
|
|
kaffiene
Sr. Member Posts: 418 Medals: 1
|
|
«
Reply #79 on:
2012-02-09 21:40:20 » |
|
Could someone post the source code for that Bag collection? The link Appel supplied is broken.
Thx!
|
|
|
|
|
ra4king
JGO Kernel Posts: 3149 Medals: 196
I'm the King!
|
|
«
Reply #80 on:
2012-02-09 22:18:12 » |
|
This is my Bag implementation, which just extends ArrayList and overrides the remove method. Note that this class only sets indices to null, this is to avoid getting a ConcurrentModificationException while looping through with a for-each loop. After your foreach loop ends, just call remove(null) and all the nulls will removed from the list.
|
|
|
|
Riven
« League of Dukes » JGO Kernel Posts: 5866 Medals: 255
Hand over your head.
|
|
«
Reply #81 on:
2012-02-10 03:27:57 » |
|
This is my Bag implementation, which just extends ArrayList and overrides the remove method. Note that this class only sets indices to null, this is to avoid getting a ConcurrentModificationException while looping through with a for-each loop. After your foreach loop ends, just call remove(null) and all the nulls will removed from the list. You're using recursion to remove nulls from the collection. Calling indexOf(null) for every null element in your list adds insult to injury as it will remove the first null element from the list, resulting in moving a lot of (null) elements around in the backing array. Not only is that significantly slower than using iteration, but what if you just removed >10K of items, you'd end up with a StackOverflowError. |
Hi, appreciate more people! Σ ♥ = ¾ Learn how to award medals... and work your way up the social rankings |
|
|
ra4king
JGO Kernel Posts: 3149 Medals: 196
I'm the King!
|
|
«
Reply #82 on:
2012-02-10 03:35:15 » |
|
This is my Bag implementation, which just extends ArrayList and overrides the remove method. Note that this class only sets indices to null, this is to avoid getting a ConcurrentModificationException while looping through with a for-each loop. After your foreach loop ends, just call remove(null) and all the nulls will removed from the list. You're using recursion to remove nulls from the collection. Not only is that significantly slower than using iteration, but what if you just removed >10K of items, you'd end up with a StackOverflowError. The bigger question here: why exactly are you removing >10K items?!  And how much slower is recursion than iteration? |
|
|
|
Riven
« League of Dukes » JGO Kernel Posts: 5866 Medals: 255
Hand over your head.
|
|
«
Reply #83 on:
2012-02-10 03:52:55 » |
|
I updated the previous post. Seeing as how the Bag collection is purely meant for performance, you most likely made it perform only slightly faster than your regular ArrayList. This is my (outdated) Bag class: http://riven8192.blogspot.com/2009/08/bag-unordered-list-fast-remove.htmlThe bigger question here: why exactly are you removing >10K items?! And how much slower is recursion than iteration? That's not the bigger question at all, it's not even relevant. You created a collection that is known to fail under normal conditions and has disappointing performance. |
Hi, appreciate more people! Σ ♥ = ¾ Learn how to award medals... and work your way up the social rankings |
|
|
princec
« League of Dukes » JGO Kernel Posts: 8076 Medals: 91
Eh? Who? What? ... Me?
|
|
«
Reply #84 on:
2012-02-10 04:28:58 » |
|
Linked lists are the building blocks for structures like B* trees which are your basic database index structure.
Maybe on disk but in memory... I can only see disadvantages. ArrayList ftw! Cas |
|
|
|
Riven
« League of Dukes » JGO Kernel Posts: 5866 Medals: 255
Hand over your head.
|
|
«
Reply #85 on:
2012-02-10 04:37:20 » |
|
Linked lists are the building blocks for structures like B* trees which are your basic database index structure.
Maybe on disk but in memory... I can only see disadvantages. ArrayList ftw! When I put my tin foil hat on, I like to imagine the superiour performance of LinkedList<ArrayList<T>> in some odd usecase. |
Hi, appreciate more people! Σ ♥ = ¾ Learn how to award medals... and work your way up the social rankings |
|
|
ReBirth
JGO Wizard Posts: 1271 Medals: 19
|
|
«
Reply #86 on:
2012-02-10 06:51:39 » |
|
Really, I still use ArrayList only |
|
|
|
theagentd
JGO Wizard Posts: 1391 Medals: 88
|
|
«
Reply #87 on:
2012-02-10 09:52:00 » |
|
Size is known: Arrays
Size is unknown: ArrayLists
Size is huge --> Probably vertex or other GPU data, so obviously just keep it in a ByteBuffer/FloatBuffer or MappedObjects
Well, that's how I do it at the moment. xD
|
There is no god.
|
|
|
Ultroman
JGO n00b Posts: 32 Medals: 2
|
|
«
Reply #88 on:
2012-02-10 16:58:41 » |
|
Wow, this is the BEST thread about lists I've ever read!  So many good ideas here! My 2 cents: I tend to use ArrayList. Their 'sense' of order appeases me. I'd like to add, for the OP: Whichever you use (Bag, ArrayList, etc.), you probably wont see a noticable difference, until you're working with the big boys on some voluminous project. But I must admit I share your enthusiasm for optimizing |
|
|
|
|
kaffiene
Sr. Member Posts: 418 Medals: 1
|
|
«
Reply #89 on:
2012-02-11 01:04:15 » |
|
Linked lists are the building blocks for structures like B* trees which are your basic database index structure.
Maybe on disk but in memory... I can only see disadvantages. ArrayList ftw! Cas :) Yes, that's true :o) |
|
|
|
|
|
