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.