Java collections good for gaming?

Engines, Libraries and Tools Tools Discussion
#61

Well I haven’t tested it but I remember Riven said for-each is bad since it creates an Iterator. What’s the point of having unnecessary object creation within the game loop? After all, performance is the key right, that’s the whole point of Bag… :wink:

onyx: ok, yeah I fluffed up the ArrayList loop. But it is in loops like that where ArrayList sucks & Bag should really shine - its certainly the first place I’ll switch over to Bag.

bleb: true that indexOf() isn’t really necessary. But the problem of disappearing indexes happens with ArrayList too, but it still has indexOf(). So why remove functionality? Anyway, its not a big deal.

I can’t wait to try out this Bag, the ultimate Collection!

Efforts like this are what is going to make open-source java so good - many hands make light work.

Keith

#62

I see this so often…

First one guy makes something ultra fast, then everybody jumps on it, ‘improves’ it, makes it compatible to just about anything, implementing interfaces and utility-like methods that do stuff the way we’re used to do things. <-- that’s wrong.

If you need a Bag, get yourself a bag, and interact with it with Bags:

bag.add(Object)
bag.contains(Object)
bag.remove(Object)
bag.addAll(Bag) <—
bag.containsAll(Bag) <—
bag.containsAny(Bag) <—
bag.removeAll(Bag) <–
bag.clear();

No java.util.* please :’( What’s next? a synchronized version? :stuck_out_tongue:

bag.indexOf(Object) is pretty useless, but bag.get(int) is a must-have to squeeze out every bit of performance (Iterators are ~slow)

#63

gotta agree with Riven there, however Collections Bag isnt’ a bad thing, maybe its time to split into two versions

Bag <-- just the normal light version
FatBag <-- with Collections implemented

#64

It seems like people are concerned about creating Iterators being slow, but people want to have the use of Iterators because it’s easier to have bug-free code.

Why not have both? I see a way it can be done, but it would make it a bad idea to use the java.util interfaces because iteration would be changed.

The idea is basically to save iterators after using them so that no object creation need to be done. You could do something like:

BagIterator bagIterator = bag.iterator();

//a bunch of code that uses bagIterator, resetting it each time with a "BagIterator.reset" method (which would have to be written)

There is, however, a problem with that. If the Bag is changed to a new Bag, the BagIterator would no longer be valid. So long as this doesn’t happen, it would work (since resetting the iterator is just a matter of changing its index). But there’s a better way.

Store the BagIterator within the Bag.

Create a BagIterator class that does NOT extend Iterator (because that would confuse people). It would add only one method: dispose. Dispose does 2 things: reset the BagIterator and record that the BagIterator is ready for use.

The dispose method works closely with the iterator() method (which probably should be renamed to getBagIterator() or something to avoid confusion with java.util). The dispose method would be as follows:

//in class BagIterator
public void dispose() {
   nextIndex = 0;
   Bag.this.lastIterator = this;
}

The code for the getBagIterator method would be as follows:

//in class Bag
public BagIterator getBagIterator() {
   if(lastIterator == null)
      return new BagIterator();
   else
      return lastIterator;
}

The return type is changed because the calling class needs access to the dispose method. Also, it’s important that lastIterator is stored by dispose, not by getBagIterator. This is so that the iterator is stored only when it’s not in use.

Only one variable “BagIterator lastIterator = null;” would need to be added. It’s just a single variable instead of an array/ArrayList/Bag of BagIterators because storing a whole extra array would be a little over the top, especially if someone never disposes the BagIterators.

This way, the iterator need only be created once unless you’re iterating over the same Bag more than once at the same time. Does anyone see any problems with this?

I haven’t actually tested this. I wanted to see what the response was first because my code was read but not used previously. If I have time later today, I’ll test this myself for performance. If this has decent performance, the get(int) and remove(int) methods could be made private.

Also, it would be possible to create our own faster version of java.util if we wrote a bunch more classes like this. Array (the faster version of ArrayList) could just extend Bag and have a different remove method. There’s already people who have done this (as was mentioned earlier in this topic), so that might not be all that useful.

#65

Sooo… has anyone ever seen ArrayList or any other collection class becomming prominent in their profiling? I hate to be cynical but this whole thread seems like one massive case of premature optimisation. I’ve certainly never seen any collections class anywhere near relevent when profiling, but maybe I’m just doing things differently.

#66

When performance is really critical - I just work with bare arrays.

It really matters, when milliseconds are an eternity for your algorithm.

You can double the speed of an algorithm, by making tiny adjustments (not even talking about Collection -> array)

Anyway, I’ve got some benchmark-results (after the VM warmed up):

Bag had 1024 Objects in it, and we’re iterating over it, in 4 ways:


// CLIENT VM 1.5

array:           50ms
get:             35ms <-- get always seems to be faster than direct-array access...
iterator:        353ms
cached-iterator: 372ms



// CLIENT VM 1.6

array:           46ms
get:             38ms
iterator:        396ms
cached-iterator: 404ms

Anyone wants iterators?

All code:


public class Bag
{
   public static class MyInt
   {
      public MyInt(int value)
      {
         this.value = value;
      }
      
      public int value;
   }
   
   public static void main(String[] args)
   {
      for (int i = 0; i < 8; i++)
      {
         int loops = 8 * 1024;

         MyInt sum = new MyInt(0);
         
         Bag bag = new Bag(1024);
         for (int j = 0; j < 1024; j++)
            bag.add(new MyInt(j));

         long t_1 = System.nanoTime();
         for (int j = 0; j < loops; j++)
         {
            int count = bag.size;
            for (int k = 0; k < count; k++)
               sum.value += bag.array[k].value;
         }
         long t0 = System.nanoTime();
         for (int j = 0; j < loops; j++)
         {
            int count = bag.size;
            for (int k = 0; k < count; k++)
               sum.value += bag.get(k).value;
         }
         long t1 = System.nanoTime();
         for (int j = 0; j < loops; j++)
         {
            BagIterator it = bag.new BagIterator();
            while (it.hasNext())
               sum.value += it.next().value;
         }
         long t2 = System.nanoTime();
         BagIterator it = bag.new BagIterator();
         for (int j = 0; j < loops; j++)
         {
            while (it.hasNext())
               sum.value += it.next().value;
            it.reset();
         }
         long t3 = System.nanoTime();

         System.out.println("hmppfffs:        " + sum.value);
         System.out.println("array:           " + (t0 - t_1) / 1000000 + "ms");
         System.out.println("get:             " + (t1 - t0) / 1000000 + "ms");
         System.out.println("iterator:        " + (t2 - t1) / 1000000 + "ms");
         System.out.println("cached-iterator: " + (t3 - t2) / 1000000 + "ms");
         System.out.println();
      }
   }

   public Bag(int capacity)
   {
      array = new MyInt[capacity];
      size = 0;
   }

   private MyInt[] array;
   private int      size;

   public final void add(MyInt o)
   {
      array[size++] = o;
   }

   public final MyInt get(int i)
   {
      return array[i];
   }

   public final int size()
   {
      return size;
   }

   public class BagIterator
   {
      private MyInt[] localArray;
      private int      localSize;

      private BagIterator()
      {
         localSize = Bag.this.size;
         localArray = Bag.this.array;
      }

      int index;

      public final boolean hasNext()
      {
         return index < localSize;
      }

      public final MyInt next()
      {
         return localArray[index++];
      }

      public final void reset()
      {
         index = 0;
      }
   }
}

The whole ‘sum’ stuff is to prevent the VM from optimising the loops away (for the for-loops)

#67

strange that get() is faster than direct access, ran into the same results myself, was rather puzzled by that, must be some jre optimisation.

#68

Taking d-tour is shorter than the distance between two points.

Space and time are indeed relative! Einstein got it right all along! :o

#69

Well, with 1.5.0_06 and earlier direct access is about 25% faster. In my own tests it was about the same (>1.5.0_06). And running your’s (Riven’s) I get similar results (get() is faster than direct), which is sorta odd imo. At most it should be equally fast, shouldnt it?

My only guess is that it has to do something with the scope and that that tiny get() method gets inlined away with 1.5.0_07 and up.

edit: If the order of get and array is switched… array becomes the faster one. So, I would say that they are indeed about equally fast after warmup (as soon as the get() gets inlined away).

#70

according to that benchmark direct access looks like its slower than method access, which is odd, should be at least the same

a quick benchmark to see it its true reveals that its true :o

public class ArrayMethod {
    
    int[] numbers = new int[10000];
    
    
    public ArrayMethod() {
        
        long start;
        int temp;
        
        // initiate array
        for (int i = 0; i < numbers.length; i++) {
            numbers[i] = (int)(Math.random()*1000);
        }
        
        
        start = System.nanoTime();
        
        for (int i = 0; i < numbers.length; i++) {
            temp = numbers[i];
        }
        
        System.out.println("Direct " + (System.nanoTime() - start));
        
        
        start = System.nanoTime();
        
        for (int i = 0; i < numbers.length; i++) {
            temp = get(i);
        }
        
        System.out.println("Method " + (System.nanoTime() - start));
        
    }
    
    public int get(int i) {
        return numbers[i];
    }
    
    public static void main(String[] args) {
        new ArrayMethod();
    }
}

however switching them round so method is tested first then direct access gives different results, no idea why its like that, maybe some sort of array caching. ;D

#71

What i find strange is the ‘get’ being inlined but the Bag class isn’t final.

#72

Personally no, but oNyx’s 60 fps to 80fps improvement is compelling. In any case, I think there’s a space for a Collection where you don’t care about list or set properties. Hell, they’re mentioned right there in the second paragraph of the Collection interface docs, does anyone know why the implementation is missing?

Now that ``` ( bag instanceof Collection ) == true ``` we can just use ``` Bag synchroBag = Collections.synchronizedCollection( bag ) ```

But seriously, why no love for the java.util? For the cost(?) of some additional methods, it seems to offer a cornucopia of interoperability deliciousness…

As to the direct access/get() microbenchmarks, it looks like the VM has gotten complex enough that, like certain deities, it works in mysterious ways…
41 letters in 4 consecutive words? Damn I’m good! Maybe I should have thrown “internationalisation” in there for good measure…

#73

IIRC the server JVM will inline all methods untill it finds out it cannot, at which point it rolls the optimisation back. This post mentions it.

#74

Except that that’s clearly an extreme case - 1600 bullets/objects in one collection is not the norm. In that particular case a write-once solution would only take a few minutes, and you wouldn’t have to worry about writing a robust Bag class.

#75

Final or not doesnt make a difference since ages. Its a sorta dated tweak.

Anyways… order matters:

public class BagTest{
	private static final int size=4096;
	private static final int runs=10000;
	private static final int repeats=10;
	private static final int GET_FIRST  =0;
	private static final int ARRAY_FIRST=1;
	private static final int GET_ONLY   =2;
	private static final int ARRAY_ONLY =3;
	private Bag bag1=new Bag(size);
	private Bag bag2=new Bag(size);
	public BagTest(int which){
		fill();
		switch(which){
			case GET_FIRST:
				benchGF();
				break;
			case ARRAY_FIRST:
				benchAF();
				break;
			case GET_ONLY:
				benchGet();
				break;
			case ARRAY_ONLY:
				benchArray();
				break;
		}
	}
	private void fill(){
		for(int i=0;i<size;i++){
			Integer in=new Integer(i);
			bag1.add(i);
			bag2.add(i);
		}
	}
	private void benchGF(){
		long start,stop;
		for(int repeat=0;repeat<repeats;repeat++){
			start=System.nanoTime();
			for(int run=0;run<runs;run++){
				Object o;
				for(int i=bag1.size-1;i>=0;--i){
					o=bag1.get(i);
				}
			}
			stop=System.nanoTime();
			System.out.println("[1]get:  "+((stop-start)/1000000)+"ms");

			start=System.nanoTime();
			for(int run=0;run<runs;run++){
				Object o;
				for(int i=bag2.size-1;i>=0;--i){
					o=bag2.data[i];
				}
			}
			stop=System.nanoTime();
			System.out.println("[2]array:"+((stop-start)/1000000)+"ms");
		}
	}
	private void benchAF(){
		long start,stop;
		for(int repeat=0;repeat<repeats;repeat++){
			start=System.nanoTime();
			for(int run=0;run<runs;run++){
				Object o;
				for(int i=bag2.size-1;i>=0;--i){
					o=bag2.data[i];
				}
			}
			stop=System.nanoTime();
			System.out.println("[1]array:"+((stop-start)/1000000)+"ms");

			start=System.nanoTime();
			for(int run=0;run<runs;run++){
				Object o;
				for(int i=bag1.size-1;i>=0;--i){
					o=bag1.get(i);
				}
			}
			stop=System.nanoTime();
			System.out.println("[2]get:  "+((stop-start)/1000000)+"ms");
		}
	}
	private void benchGet(){
		long start,stop;
		for(int repeat=0;repeat<repeats;repeat++){
			start=System.nanoTime();
			for(int run=0;run<runs;run++){
				Object o;
				for(int i=bag1.size-1;i>=0;--i){
					o=bag1.get(i);
				}
			}
			stop=System.nanoTime();
			System.out.println("get:  "+((stop-start)/1000000)+"ms");
		}
	}
	private void benchArray(){
		long start,stop;
		for(int repeat=0;repeat<repeats;repeat++){
			start=System.nanoTime();
			for(int run=0;run<runs;run++){
				Object o;
				for(int i=bag2.size-1;i>=0;--i){
					o=bag2.data[i];
				}
			}
			stop=System.nanoTime();
			System.out.println("array:"+((stop-start)/1000000)+"ms");
		}
	}
	public static void main(String[]args){
		if(args.length==1&&args[0].equals("-gf"))
			new BagTest(GET_FIRST);
		else if(args.length==1&&args[0].equals("-af"))
			new BagTest(ARRAY_FIRST);
		else if(args.length==1&&args[0].equals("-go"))
			new BagTest(GET_ONLY);
		else if(args.length==1&&args[0].equals("-ao"))
			new BagTest(ARRAY_ONLY);
		else{
			System.out.println("usage BagTest <-gf>|<-af>|<-go>|<-ao>\n\t-gf=get first\n\t-af=array first\n\t-go=get only\n\t-ao=array only");
			System.exit(1);
		}
	}
}

D:\java\test>java BagTest
usage BagTest <-gf>|<-af>|<-go>|<-ao
        -gf=get first
        -af=array first
        -go=get only
        -ao=array only

D:\java\test>java BagTest -gf
[1]get:  708ms
[2]array:463ms
[1]get:  643ms
[2]array:442ms
[1]get:  682ms
[2]array:389ms
[1]get:  663ms
[2]array:434ms
[1]get:  640ms
[2]array:390ms
[1]get:  612ms
[2]array:450ms
[1]get:  656ms
[2]array:444ms
[1]get:  613ms
[2]array:388ms
[1]get:  591ms
[2]array:488ms
[1]get:  640ms
[2]array:390ms

D:\java\test>java BagTest -af
[1]array:628ms
[2]get:  461ms
[1]array:605ms
[2]get:  431ms
[1]array:634ms
[2]get:  418ms
[1]array:616ms
[2]get:  378ms
[1]array:602ms
[2]get:  369ms
[1]array:634ms
[2]get:  371ms
[1]array:622ms
[2]get:  373ms
[1]array:595ms
[2]get:  431ms
[1]array:613ms
[2]get:  371ms
[1]array:594ms
[2]get:  375ms

D:\java\test>java BagTest -go
get:  610ms
get:  691ms
get:  638ms
get:  623ms
get:  632ms
get:  682ms
get:  601ms
get:  686ms
get:  598ms
get:  692ms

D:\java\test>java BagTest -ao
array:635ms
array:681ms
array:646ms
array:608ms
array:640ms
array:626ms
array:613ms
array:602ms
array:700ms
array:594ms

So they are indeed about equally fast (with 1.5.0_07+ client).

Except that that’s clearly an extreme case - 1600 bullets/objects in one collection is not the norm.

Mh. Sort of. Well, you have that amount of bullets in danmaku (bullet hell) games. And outside of that genre you can easily use that many kind of bullet-alike objects… for particle effects.

[…]and you wouldn’t have to worry about writing a robust Bag class.

I like my simple one. Its already good the way it is (clear() is missing, but other than that its already perfect).

I for one dont believe in generics :wink:

#76

Actually I should try slotting the original Bag into my (much neglected) scrolly shooter and see how it fares. I still think it’s a special case though - not only the number but the rapid insert/remove cycle is much more heavy duty than anything else. Particle effects I think need separate attention and are best handled via fixed size arrays.

Personally I’d have stuck with ArrayList eveywhere, and only wheeled out the original Bag (quirks and all) for bottlenecks and other extreme situations.

#77

By the way, I just insert a lil’ question in the discussion : what is the difference between vector and arraylist ? vector is shorter to write so I often use it (almost always)… is there any performance difference, storage diff, or whatever ? when should I use one or the other…

#78

Vector is synchronized, which is nice, but deadslow.

#79

Now that you mention Vector, that one actually showed up as a hotspot during profiling not so long ago. Vector#get and Vector#size where the bottleneck in my code :slight_smile: I replaced that particular bit with direct array access and saw a nice drop in cpu usage.

[quote=“Riven,post:78,topic:28392”]
Vector is synchronized, but it’s rarely the type of synchronization you actually need. I personally always use ArrayList and handle the synchronization myself where needed.

#80

don’t lead yourself into thinking that there is some silver bullet. every datastructure supplies a solution for a certain need. may you be looking among the axis of access speed, time to add something, time to add a collection to a collection, memory foodprint, etc. There are mathemetical/theoretical fundations for datastructures which are guidelines(but implementations can differ in efficiency; I rember something with ArrayList vs LinkedList) I think a combination between the theoretical and a profiler will due.

the use of this bag is the same of any of the other Collections perhaps more trival then others(to implement) but it’s still error prone to write trival stuff then to reuse, every minute saved I’ll take.