Gaming Your Way

May contain nuts.

Object pooling without all the ins and outs

I've been meaning to write this up for a while now, so before we start it's going to be a long one ( And I'm not going to make it even longer with a "That's what she said..." comment.. damn it, already ) and could end up being a little dry in places ( "That's..." )


Ok, we all get object pooling, any mention of optimisation includes the term like some sort of crazed mantra, so I know what it is, you know what it is, let's actually start from there.


Until recently I did it like this:

//Fill our pools    
    this.activeParticles=new Array();
    this.particlesPool=new Array();
    var particle;
    var cnt=-1;
    var len=numberOfParticlesWeWant;
    while(++cnt!=len){
        particle=new ParticleInstance();
        this.particlesPool.push(particle);
    }

The pool would be pre-filled to it's max length, I don't understand all this growing pools thing in a game, when you're getting an object from the pool it's because your game is doing tons of stuff anyway, why make it run even slower.
The main loop would then be:
  var particle;
  var cnt=-1;
  var len=this.activeParticles.length;
  while(++cnt<len){
    particle=this.activeParticles[cnt];
    if(particle.mainloop()=="dead"){
      this.activeParticles.splice(cnt,1);
      this.particlesPool.push(particle);
      len--;
      cnt--;
    };
  }

I'm just showing this for the general gist of things, two arrays, an active particle array and the pool array, when a particle stops being active you remove it from the active one and put it back into the pool.

The thing I've changed recently, which I've seen really improve performance, is the whole array access part. Every time you use pretty much any Array method, such as splice, it returns the new array. That's handy, but if you're not doing anything with it's just floating around waiting for the GC to spot it and kill it off for us. This is happening 60 times a second and when the GC kicks in is anyones guess, 1 second, 5 seconds ? Either way it's a lot of junk data just sitting around ready to be cleaned up.
Also you're no longer working with fixed length arrays, which is another strain as they shrink and grow.

The new way I've moved over to is having both a pool of objects as normal, and an offset table.
    var len=48;
    this.bloodParticle_poolOffsetTablelength=len;  
    this.bloodParticle_poolOffsetTablelength4=len/4;
    var buffer=new ArrayBuffer(len);
    this.bloodParticle_poolOffsetTable=new Int8Array(buffer);
    this.bloodParticlePool=new Array(len);
    var cnt=-1;
    while(++cnt!=len){
        this.bloodParticle_poolOffsetTable[cnt]=cnt;
        this.bloodParticlePool[cnt]=new BloodParticle(cnt);
    }

That's code directly lifted from Rot, I may love you but not enough to write new example code for you.
So there we use the len/4 for loop unrolling later on ( So all our pool lengths have to be divisible by 4, but you can go with 2 or 8 or whatever you can face ).
The one "What's that now?" thing may be the Int8Array. Basically it is what is says, an array which can only hold 8bit ints. It's much quicker than a normal array and all we're doing is storing numbers in it anyway, the table is just a list of offsets to our pool array.

When we request an object from the pool we loop through out table offsets, looking for a valid number:
ParticleHandler.prototype._getBloodFromPool = function() {
    var offset=-1;
    var cnt=-1;
    var len=this.bloodParticle_poolOffsetTablelength4;
    var table=this.bloodParticle_poolOffsetTable;
    var pool=this.bloodParticlePool;
    
    while(++cnt!=len){
        offset=table[cnt];
        if(offset!=-1){
            table[cnt]=-1;
            return pool[offset];
        }
        offset=table[cnt+12];
        if(offset!=-1){
            table[cnt+12]=-1;
            return pool[offset];
        }
        offset=table[cnt+24];
        if(offset!=-1){
            table[cnt+24]=-1;
            return pool[offset];
        }
        offset=table[cnt+36];
        if(offset!=-1){
            table[cnt+36]=-1;
            return pool[offset];
        }
    }
    return false;
};

If the offset isn't -1 then it's valid and we can claim it, so then set it to -1 and return the object. That's it, we've got our object ready to init() and no arrays were slapped around for it.
( Also you can see where our loop unrolling comes in to it )

Right, we've created our pools, got an object from them, how to do we run each object ?
    var len=this.bloodParticle_poolOffsetTablelength4;
    var table=this.bloodParticle_poolOffsetTable;
    var pool=this.bloodParticlePool;
//Sorry about the broken indenting here, it bugs me too        
        cnt=-1;
        while(++cnt!=len){
            if(table[cnt]==-1){
                if(pool[cnt].mainloop()=="dead"){
                    table[cnt]=cnt;
                }
            }
            if(table[cnt+12]==-1){
                if(pool[cnt+12].mainloop()=="dead"){
                    table[cnt+12]=cnt+12;
                }
            }
            if(table[cnt+24]==-1){
                if(pool[cnt+24].mainloop()=="dead"){
                    table[cnt+24]=cnt+24;
                }
            }
            if(table[cnt+36]==-1){
                if(pool[cnt+36].mainloop()=="dead"){
                    table[cnt+36]=cnt+36;
                }
            }
        }

Pretty much the same as requests the object from out pool, if the object is dead we just put it's value back in the offset table again.

Break the bad news to me gently doc.

You may have noticed the downside, which is in our main loop. In our original way we took the active particles array length and worked through that, so if there were only 5 objects running then it only looped 5 times. It doesn't really allow for loop unrolling, but it's always just doing the correct number.
In our table offset approach we have to check every object every time. That's less than optimal.

But...

Say your game needs up to 20 explosions running at once. Firstly, cool game. Secondly, that's the worst case scenario and because we're already checking all our objects every frame we pretty much know the game can cope with that worst case.
Also you can set flags to see if certain loops even need testing ( I removed those checks from my pasted code just for ease of reading ). Your explosions aren't going to be happening every frame ( If so, again, cool game ) so you can do a simple test to see if any are running, if not skip the loop entirely, if so run the loop and keep a running total of how many objects are actually running, if it drops back to zero clear your test flag again.

I'm sure all of you reading this have your own ways of pooling, everyone does, and I'm sure some of you will be able to pick holes in this, good, please do so in the comments so that information is shared, but I've found not altering the arrays has had a large performance boost on mobile which more than cancels out the overheads involved.

K, I've got a freeze gun to finish adding to Rot, so that's me spent.

Squize.

Object Pooling, nice and simple

I promised to write an article for a mate over a year ago now about object pooling. As you can see, I'm a little late ( And with apologies to Michael, I don't mean to be shit, I just am ).

Ok, pooling. To sum it up it's a way of re-using objects. Creating new objects is costly, so rather than killing them off we just store them away until we need them again. Pooling is perfect for things like baddies, bullets, particles etc.

Let's get down to it.

In our baddie class we have the following,

public var type:String="Baddie1";

Just a simple identifier, obviously the number reflects it's ID.

We'll come back to that.

In our BaddieHandler class we have the following,

//---------------------------------------------------------------------------------------
		private function createBaddie1(data:Array):void{
			var baddie:Baddie;
			if(baddie1Pool.length!=0){
				baddie=baddie1Pool[0];
				baddie1Pool.shift();
			} else {
				baddie=new Baddie1();
			}
			baddie.init(data[1],data[2]);
			activeBaddies.push(baddie);
		}

That's straight forward ? Ignore the data:Array and the init, that's just passing the x,y positions to it.
So we check baddie1Pool ( In this case its a Vector, an array does the same job ). If there's a baddie object in there we grab it and use it. If not we create a new instance.

Let's go back to the baddie class, when we declare it dead we simply do this,

return "dead";

Back again to our BaddieHandler class ( I've structured this well haven't I ), in our mainloop we have,

//---------------------------------------------------------------------------------------
		private function mainloop_normal():void {
			var baddie:Baddie;
			var cnt:int=0;
			
			for each (baddie in activeBaddies){
				if(baddie.mainloop()=="dead"){
					activeBaddies.splice(cnt,1);
//We can live with defining vars in a loop, as it should only be needed once per loop
					var type:String=baddie["type"];
					if(type!="DontPool"){
						var functionCall:Function=this["returnToPool_"+type];
						functionCall(baddie);
					}
				}
				cnt++;
			}	
		}

So we loop through the active baddies array, running the mainloop for each baddie. If we get returned "dead" as a string we know we've got to put him back in the pool. This is where that identifier from the start of the post comes back into it.

Finally we have a simple method for putting it back into the pool itself, eg

//---------------------------------------------------------------------------------------
		private function returnToPool_Baddie1(baddie:Baddie):void{
			baddie1Pool.unshift(baddie);
		}

The nice part is the use of identifier and the dynamic function in the mainloop, see how we create this["returnToPool_"+type] and then just call it, no messing around with any conditionals to see which pool we should
put the object back into.

And that's how simple pooling is. If you want you can pre-populate your pool ( ie create 30 baddies right at the start of the game, so there's no slow down as you slowly fill the pool to its maximum level ), I just find it easier on my brain to create the instances as I go.

Squize.