Java collections good for gaming?

[zingbat]

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

[fletchergames]

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.

[kappa]

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.

Games published by our own members! Check 'em out!

[Riven]

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)

[cylab]

If you stick to use collections you can maybe get a speedboost by using Trove

[zingbat]

"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.

[kappa]

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.

[Mr_Light]

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.

[fletchergames]

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.

[blahblahblahh]

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.

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.

Games published by our own members! Check 'em out!

[Riven]

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.

[kappa]

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.

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.

[Riven]

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.

[Mr_Light]

A List implementation that is optimised for fast insertions and removals at any index in the list.

This list implementation utilises a tree structure internally to ensure that all insertions and removals are O(log n). This provides much faster performance than both an ArrayList and a LinkedList where elements are inserted and removed repeatedly from anywhere in the list.

The following relative performance statistics are indicative of this class:

              get  add  insert  iterate  remove
 TreeList       3    5       1       2       1
 ArrayList      1    1      40       1      40
 LinkedList  5800    1     350       2     325
 

ArrayList is a good general purpose list implementation. It is faster than TreeList for most operations except inserting and removing in the middle of the list. ArrayList also uses less memory as TreeList uses one object per entry.

LinkedList is rarely a good choice of implementation. TreeList is almost always a good replacement for it, although it does use sligtly more memory.

but commons collections doesn't support genetrics afaik. I haven't used this but I just bumbed into it then I saw this discussion.

[Torquemada]

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.

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?

[fletchergames]

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.

[Riven]

Often you want the order of your List (!!) to be kept. It's not a Set where you don't really care.

[Mr_Light]

Yeah that would be great, the whole 'orderness' wich the it implies to have (it's a List) would be lost.

[darkprophet]

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

[Mr_Light]

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.

[Riven]

Having (performance-critical) paths controlled by throwing/catching Exceptions is one of the worst anti-patterns around.

[kappa]

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.

didn't realise that removing objects caused such a performance hit for ArrayLists, so if you need to remove an object on a list where order doesn't matter with a lower performance hit, how would you do it?

here my attempt not sure if its right

1   2   3   4   5

int index; // index of entity that needs removing int last = myArrayList.size() - 1; // index of last entity in the list myArrayList.set(index, myArrayList.get(last)); myArrayList.remove(last);

is that how you'd do it or is there another way?

[darkprophet]

Having (performance-critical) paths controlled by throwing/catching Exceptions is one of the worst anti-patterns around.

Thats not the case here; this is because if I was to do if (index >= internalList.size()) {...} that would simply add another bound checking statement ontop of what the JVM does already...

Benchmark it, you'll see...

DP

[shawnkendall]

We (IMI) broke down and switched just about everything over to http://javolution.org/ collections.

I'll never look back :-) </knock wood>

[darkprophet]

My collection buffer/list/map thing was rather specialised; so it didn't warrant moving everything to javolution although I have heard a few good things about it.

It doesn't matter now anyway, I literally have a flat GC profile with yourkit.com; the list grows exponentially to start off with, but once it settles down, its fine....

DP

[oNyx]

Horrible on so many levels, but its fast

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26   27   28   29   30   31   32   33   34   35   36   37   38   39   40   41   42   43   44   45   46   47   48   49   50   51   52   53   54   55   56   57   58   59   60   61

public class Bag{    private int capacity;    public Object []data;    public int size=0;    public Bag(){       this(10);    }    public Bag(int capacity){       this.capacity=capacity;       data=new Object[capacity];    }    public Object remove(int i){       Object o=data[i];       data[i]=data[--size];       data[size]=null;//kev was right... it really should be there for being dynamic n stuff      return o;    }    public void add(Object o){       size++;       if(size>capacity){          capacity=(capacity * 3)/2 + 1;          Object []oldData=data;          data=new Object[capacity];          System.arraycopy(oldData, 0, data, 0, oldData.length);       }       data[size-1]=o;    }    public static void main(String[]args){       Bag b=new Bag();       for(int i=0;i<5;i++)          b.add(new Integer(i));       System.out.println("\nbag contains:");       for(int i=0;i<b.size;i++)          System.out.println(b.data[i]);       for(int i=0;i<b.size;i++){          int k=((Integer)b.data[i]).intValue();          if(k%2==0){             System.out.println("remove:"+i+" -> "+b.data[i]);             b.remove(i--);          }else{             System.out.println("keep:"+i+" -> "+b.data[i]);          }       }       System.out.println("\nbag contains:");       for(int i=0;i<b.size;i++)          System.out.println(b.data[i]);       for(int i=0;i<b.size;i++){          int k=((Integer)b.data[i]).intValue();          if(k%2==1){             System.out.println("remove:"+i+" -> "+b.data[i]);             b.remove(i--);          }else{             System.out.println("keep:"+i+" -> "+b.data[i]);          }       }       System.out.println("\nbag contains:");       for(int i=0;i<b.size;i++)          System.out.println(b.data[i]);    } }

[oNyx]

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26   27   28   29   30   31   32   33   34   35   36   37   38   39   40   41   42   43   44   45   46   47   48   49   50   51   52   53   54   55   56   57   58   59   60   61   62   63   64   65   66   67   68   69   70   71   72   73   74   75   76   77   78   79   80   81   82   83   84   85   86   87   88   89   90   91   92   93   94   95   96   97   98   99   100   101   102   103   104   105   106   107   108   109   110   111   112   113   114   115   116   117   118   119   120   121   122   123   124   125   126   127   128   129

import java.util.*; public class ListWalk3{    ArrayList al=new ArrayList();    LinkedList ll=new LinkedList();    Bag bag=new Bag();    int numberOfElements=5000;    private void fill(){       System.out.println("filling");       for(int i=0;i<numberOfElements;i++){          Integer in=new Integer(i*10);          al.add(in);          ll.add(in);          bag.add(in);       }       System.out.println("done");    }    private void test(){       int repeat=5;       int runs=50000;       int iruns=10000;       long start,stop;       double[]sums=new double[3];       for(int r=0;r<repeat;r++){          start=System.currentTimeMillis();          for(int r2=0;r2<iruns;r2++){             for(int i=al.size()-1;i>=0;--i){                Object o=al.get(i);             }          }          stop=System.currentTimeMillis();          System.out.println("iterate[ArrayList backward]      "+(double)(stop-start)/1000.0+" seconds");          sums[0]+=(double)(stop-start)/1000.0;          start=System.currentTimeMillis();          for(int r2=0;r2<iruns;r2++){             ListIterator itr=ll.listIterator();             while(itr.hasNext()){                Object o=itr.next();             }          }          stop=System.currentTimeMillis();          System.out.println("iterate[LinkedList listIterator] "+(double)(stop-start)/1000.0+" seconds");          sums[1]+=(double)(stop-start)/1000.0;          start=System.currentTimeMillis();          for(int r2=0;r2<iruns;r2++){             for(int i=bag.size-1;i>=0;--i){                Object o=bag.data[i];             }          }          stop=System.currentTimeMillis();          System.out.println("iterate[Bag]                     "+(double)(stop-start)/1000.0+" seconds");          sums[2]+=(double)(stop-start)/1000.0;       }       double[]sums2=new double[3];       double[]sums3=new double[3];       Integer in=new Integer(23);       for(int r=0;r<repeat;r++){          //add          start=System.currentTimeMillis();          for(int r2=0;r2<runs;r2++)             al.add(in);          stop=System.currentTimeMillis();          System.out.println("add[ArrayList]  "+(double)(stop-start)/1000.0+" seconds");          sums2[0]+=(double)(stop-start)/1000.0;          start=System.currentTimeMillis();          for(int r2=0;r2<runs;r2++)             ll.add(in);          stop=System.currentTimeMillis();          System.out.println("add[LinkedList] "+(double)(stop-start)/1000.0+" seconds");          sums2[1]+=(double)(stop-start)/1000.0;          start=System.currentTimeMillis();          for(int r2=0;r2<runs;r2++)             bag.add(in);          stop=System.currentTimeMillis();          System.out.println("add[Bag]        "+(double)(stop-start)/1000.0+" seconds");          sums2[2]+=(double)(stop-start)/1000.0;          //rem          start=System.currentTimeMillis();          for(int r2=0;r2<runs;r2++)             al.remove(0);          stop=System.currentTimeMillis();          System.out.println("rem[ArrayList]  "+(double)(stop-start)/1000.0+" seconds");          sums3[0]+=(double)(stop-start)/1000.0;          start=System.currentTimeMillis();          for(int r2=0;r2<runs;r2++)             ll.remove(0);          stop=System.currentTimeMillis();          System.out.println("rem[LinkedList] "+(double)(stop-start)/1000.0+" seconds");          sums3[1]+=(double)(stop-start)/1000.0;          start=System.currentTimeMillis();          for(int r2=0;r2<runs;r2++)             bag.remove(0);          stop=System.currentTimeMillis();          System.out.println("rem[Bag]        "+(double)(stop-start)/1000.0+" seconds");          sums3[2]+=(double)(stop-start)/1000.0;       }       String []labels={          "ArrayList :",          "LinkedList:",          "Bag       :"};       System.out.println("\n\n"+numberOfElements+" elements\n");       System.out.println("\niterate "+iruns+" times");       for(int i=0;i<3;i++)          System.out.println(labels[i]+(sums[i]/repeat));       System.out.println("\nadd "+runs+" times");       for(int i=0;i<3;i++)          System.out.println(labels[i]+(sums2[i]/repeat));       System.out.println("\nrem "+runs+" times");       for(int i=0;i<3;i++)          System.out.println(labels[i]+(sums3[i]/repeat));       System.out.println("\nsum");       for(int i=0;i<3;i++)          System.out.println(labels[i]+" "+((sums[i]+sums2[i]+sums3[i])/repeat));    }    public static void main(String[]args){       ListWalk3 lw=new ListWalk3();       lw.fill();       lw.test();    } }

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19

iterate 10000 times ArrayList :3.3147999999999995 LinkedList:6.014799999999999 Bag       :0.7909999999999999 add 50000 times ArrayList :0.01 LinkedList:0.13200000000000003 Bag       :0.0062 rem 50000 times ArrayList :15.0418 LinkedList:0.016 Bag       :0.01 sum ArrayList : 18.3666 LinkedList: 6.162799999999999 Bag       : 0.8071999999999999

Couldnt be arsed to use bigger values for add/remove (for more meaningful results), since AL's remove took bloody ages.

[oNyx]

I wanted to know what this would mean in reality... so I took my (opengl accelerated) fuzetsu prototype and replaced the ArrayLists with Bag. With about 1600 bullets I got 80fps instead of 60fps (on a 500mhz machine!).

Really awesome

edit: Btw with 1.5.0_07 and up using a get() wrap for the direct array acess is about equally fast. With 1.5.0_06 and earlier its about 30% slower.

[kappa]

this Bag class is really good and fast for gaming, totally blows ArrayList away for performance, gonna swap over from ArrayList to Bag

[blahblahblahh]

I wanted to know what this would mean in reality... so I took my (opengl accelerated) fuzetsu prototype and replaced the ArrayLists with Bag. With about 1600 bullets I got 80fps instead of 60fps (on a 500mhz machine!).

Really awesome

edit: Btw with 1.5.0_07 and up using a get() wrap for the direct array acess is about equally fast. With 1.5.0_06 and earlier its about 30% slower.

Mem usage difference?