Java-Gaming.org    
Featured games (79)
games approved by the League of Dukes
Games in Showcase (477)
Games in Android Showcase (109)
games submitted by our members
Games in WIP (537)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: 1 2 [3] 4
  ignore  |  Print  
  ArrayList, Hashtable, or ... for holding in-game-objects  (Read 15364 times)
0 Members and 1 Guest are viewing this topic.
Online princec

JGO Kernel


Medals: 343
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #60 - Posted 2012-01-05 14: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 Smiley

Cas Smiley

Offline Damocles
« Reply #61 - Posted 2012-01-05 14: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.

Online princec

JGO Kernel


Medals: 343
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #62 - Posted 2012-01-05 14: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 Smiley

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline nsigma
« Reply #63 - Posted 2012-01-05 15: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!  Smiley

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!  Grin

Praxis LIVE - open-source intermedia toolkit and live interactive visual editor
Digital Prisoners - interactive spaces and projections
Offline Grunnt

JGO Wizard


Medals: 66
Projects: 8
Exp: 5 years


Complex != complicated


« Reply #64 - Posted 2012-01-05 15: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 Grin

Thanks for the advice, I'll have a good long look at the other approaches described here.

Online theagentd
« Reply #65 - Posted 2012-01-05 16: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!  Grin
Exactly what I meant. I claim that one! =S

Myomyomyo.
Online princec

JGO Kernel


Medals: 343
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #66 - Posted 2012-01-05 16: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 Smiley

Online theagentd
« Reply #67 - Posted 2012-01-05 19: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...

Myomyomyo.
Offline ra4king

JGO Kernel


Medals: 342
Projects: 2
Exp: 5 years


I'm the King!


« Reply #68 - Posted 2012-01-05 19:27:02 »

How about (as I pointed out earlier), nulling out the index when removing it, then removing all nulls after the loop ends?

Offline nsigma
« Reply #69 - Posted 2012-01-05 19: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.  Wink

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!  Smiley  Aren't you just forcing yourself to iterate an extra time, and doing more in the process?

Praxis LIVE - open-source intermedia toolkit and live interactive visual editor
Digital Prisoners - interactive spaces and projections
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline miga

Junior Member


Medals: 2
Projects: 1



« Reply #70 - Posted 2012-01-07 19: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.

Miga's Hobby Programming - http://www.migapro.com
Offline Bukky

Junior Newbie





« Reply #71 - Posted 2012-02-09 07: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
Offline ra4king

JGO Kernel


Medals: 342
Projects: 2
Exp: 5 years


I'm the King!


« Reply #72 - Posted 2012-02-09 08: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? Wink

Btw, welcome to JGO Smiley

Offline Bukky

Junior Newbie





« Reply #73 - Posted 2012-02-09 10: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? Wink

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  Huh Undecided Emo

Btw, welcome to JGO Smiley

Thanks!
Online theagentd
« Reply #74 - Posted 2012-02-09 10: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? Wink

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  Huh Undecided Emo

Btw, welcome to JGO Smiley

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

Myomyomyo.
Offline ra4king

JGO Kernel


Medals: 342
Projects: 2
Exp: 5 years


I'm the King!


« Reply #75 - Posted 2012-02-09 20:31:13 »

Also you gotta remember that a variable (of class types) only references the object.

1  
entities0 = entities1;

Here, both entities0 and entities1 refer to the same object

1  
entities1.clear();

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.

Offline Bukky

Junior Newbie





« Reply #76 - Posted 2012-02-10 02: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!
Offline kaffiene
« Reply #77 - Posted 2012-02-10 03: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 Smiley
Linked lists are the building blocks for structures like B* trees which are your basic database index structure.
Offline kaffiene
« Reply #78 - Posted 2012-02-10 03: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.
Offline kaffiene
« Reply #79 - Posted 2012-02-10 03:40:20 »

Could someone post the source code for that Bag collection?  The link Appel supplied is broken.

Thx!
Offline ra4king

JGO Kernel


Medals: 342
Projects: 2
Exp: 5 years


I'm the King!


« Reply #80 - Posted 2012-02-10 04: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.

Offline Riven
« League of Dukes »

JGO Overlord


Medals: 757
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #81 - Posted 2012-02-10 09: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
Offline ra4king

JGO Kernel


Medals: 342
Projects: 2
Exp: 5 years


I'm the King!


« Reply #82 - Posted 2012-02-10 09: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?! Tongue
And how much slower is recursion than iteration?

Offline Riven
« League of Dukes »

JGO Overlord


Medals: 757
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #83 - Posted 2012-02-10 09: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.html


The bigger question here: why exactly are you removing >10K items?! Tongue
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
Online princec

JGO Kernel


Medals: 343
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #84 - Posted 2012-02-10 10: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 Smiley

Offline Riven
« League of Dukes »

JGO Overlord


Medals: 757
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #85 - Posted 2012-02-10 10: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
Offline ReBirth
« Reply #86 - Posted 2012-02-10 12:51:39 »

Really, I still use ArrayList only Tongue

Online theagentd
« Reply #87 - Posted 2012-02-10 15: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

Myomyomyo.
Offline Ultroman

JGO Knight


Medals: 24
Projects: 1


Snappin' at snizzes since '83


« Reply #88 - Posted 2012-02-10 22:58:41 »

Wow, this is the BEST thread about lists I've ever read!  Cheesy
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  Wink

- Jonas
Offline kaffiene
« Reply #89 - Posted 2012-02-11 07: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)
Pages: 1 2 [3] 4
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

CogWheelz (17 views)
2014-08-01 22:53:16

CogWheelz (15 views)
2014-08-01 22:51:43

CopyableCougar4 (20 views)
2014-08-01 19:37:19

CogWheelz (19 views)
2014-07-30 21:08:39

Riven (27 views)
2014-07-29 18:09:19

Riven (16 views)
2014-07-29 18:08:52

Dwinin (14 views)
2014-07-29 10:59:34

E.R. Fleming (42 views)
2014-07-29 03:07:13

E.R. Fleming (13 views)
2014-07-29 03:06:25

pw (44 views)
2014-07-24 01:59:36
Resources for WIP games
by CogWheelz
2014-08-01 18:20:17

Resources for WIP games
by CogWheelz
2014-08-01 18:19:50

List of Learning Resources
by SilverTiger
2014-07-31 18:29:50

List of Learning Resources
by SilverTiger
2014-07-31 18:26:06

List of Learning Resources
by SilverTiger
2014-07-31 13:54:12

HotSpot Options
by dleskov
2014-07-08 03:59:08

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:58:24

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:47:22
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!