Are java.util collections good enough for gaming or is there something better and free?
I mean if theres much unnecessary garbage being created, data structures too nested (too much dereferencing), too many interfaces, etc
For the most part, they’re fine. Arrays are an acceptable alternative too.
If your game is running slow, it’s probably not from the Collection code.
i’ve found that ArrayLists are really good for java gaming, they’re fast and easy to use, much nicer than using arrays.
P.S. another thing that i’ve found is that ArrayLists are almost always faster than LinkedLists.
primitive-maps are completely useless for anything performance-related. Auto-boxing only makes it worse.
I made a code-generator that spits out all combinations of classes:
IntIntMap
IntCharMap
CharShortMap
CharByteMap
etc etc etc
Same for sets. Sometimes you just long for C++ templates :-[
Also, using:
for(Object obj: objs)
is much slower than
for(int i=0; i<objs.length; i++)
Object obj = objs[ i ];
as it creates an Iterator and well… iterates over it.
If you can afford the hassle of working with arrays instead of lists, i’d highly recommend it, as you most likely get a 10-20% boost (if it’s your bottleneck, ofcourse)
“If you can afford the hassle of working with arrays instead of lists, i’d highly recommend it, as you most likely get a 10-20% boost (if it’s your bottleneck, ofcourse)”
Its allways a bottleneck when we use something like a scenegraph, for example, and to deal with big sets of data. However in the later case we can also use buffers i supose.
“If you stick to use collections you can maybe get a speedboost by using Trove”
Looks great. From the overview it supports primitive collections and addresses some performance issues i didn’t even know about it.
i’d recommend you do a quick benchmark of your own when choosing a collection other than the one with the offical jre,
last time i tried a different collection FastList from http://javolution.org/ although according to the website the benchmarks for FastList are better than ArrayList, my own tests showed otherwise.
Optimisations are always taking place here and there with every new release of java release. I’ve found java collection to be pretty sufficient perfomance wise and you should only be worried if it becomes a bottle neck as mentioned above.
and there is http://jakarta.apache.org/commons/collections/
indentify a bottleneck first and retest after changes, as sugjested above, to actually see if there was an improvement.
I looked at Trove, and it doesn’t support generics. It has special maps for mapping primitives, but there’s no way to to create a THashMap with generics like you would do with a HashMap.
An article I read on the Internet indicates that Trove is faster and uses less memory, but it doesn’t use generics.
Completely the opposite of my experience. Which I only mention in order to say “YMMV”, and “quotes like the above which have no explanation are useless information, you need to go away and look at the documentation and make an informed decision for yourself - whether by benchmarking or algorithm or code analysis”.
For an example: Java 1.4.2 and perhaps 1.5 too (can’t remember) ArrayList collapses completely if you go to large data sets (more than a few thousand entries in a single list). Performance drops by orders of magnitude.
We’d need a LinkedArrayList in such situations, where several ArrayLists are Linked together, to prevent MASSIVE ‘shifting’ of data to the ‘left’ or ‘right’.
Doesn’t sound too hard to implement.
most game types won’t need to have more than a few hundred entities at anyone time anyway, so i doubt you’d run into the data set too large thing you mention. Besides entities you finish with can easily be removed. Only thing i can think of that’d require massive amount of entities is a particle manager for which you shouldn’t need to use an arraylist anyway, for which a normal array should suffice.
The problem with ArrayLists is removing of Objects, as all objects right of it, must be shifted to the left.
If you’re doing that (adding/inserting/removing) very often per frame it can very well become a bottleneck.
but commons collections doesn’t support genetrics afaik. I haven’t used this but I just bumbed into it then I saw this discussion.
So surely you can copy the last element of your arraylist to the position of the element to be removed, and simply remove the last element of the arraylist? Wouldn’t that just be a reference copy and then a removal with no shifting?
That would work unless the order the elements are in matters.
Often you want the order of your List (!!) to be kept. It’s not a Set where you don’t really care.
Yeah that would be great, the whole ‘orderness’ wich the it implies to have (it’s a List) would be lost.
yeah, like they said, the integrity of the List will be gone…
Speaking of lists and performance; last night, i made a class (aptly named OverwriteList) that is half Map, half List, half Buffer. It implements List<MutableEntry<K, V>>, encapsulates List<MutableEntry<K, V>> and holds an index counter, on add(…), the counter would be increased, then you could try to get from the MutableEntry<K, V> from the list, if an IndexOutOfBoundsException is thrown, then you just use the encapsulated list’s add(…) method, if not, then you you get the MutableEntry<K, V> at that index, and set the key and value of the current entry to the one that you want to add. A clear() would be simply resetting the index back to 0.
Extremely useful when you want to have a 1 - 1 relationship between two objects (sorta like a hashmap) and need minimum garbage creation (renderbins anyone? )
I can post the code for it if you guys need it…
DP
oi didn’t see the 2nd page or a lot of ppl posted at the same time. now it just looks harsh, sorry about that anyways datastructures are intesting.