How to Make an Object Pool

The goal of a pool is to avoid memory churn by reusing objects instead of allocating and freeing them, thus improving performance.

Object pools maintain a collection of reusable objects and track their usage. As you will see, object pools are easy to build and only require a few modifications to your existing objects’ classes.

As the chapter demo source code demonstrates, using a pool is pretty straightforward and doesn’t call for a lot of changes:

//
// Our step function called on each Request Animation Frame (RAF)
//
 
// in this step we recycle our particle
demo.recyclingStep = function( particles ) {
 
    var i;
 
    for (i = 0; i < demo.settings.rate; i++) {
 
        var min = -10,
            max = 10,
            velx = min + Math.random() * (max - min),
            vely = min + Math.random() * (max - min),
            w = demo.settings.size,
            h = demo.settings.size,
            life = demo.settings.life;
 
        particles.getFree()
            .setup( demo.settings.width * 0.5, demo.settings.height * 0.5, w, h, life )
            .setVel( velx, vely );
    }
 
    for (i = 0; i < particles.elements.length; i++) {
 
        var particle = particles.elements[i];
 
        if( particle.allocated === true ){
 
            if( particle.life === 0 )
                particles.free( particle );
 
            else if(demo.settings.cull === true && demo.isInBounds(particle) === false)
                particles.free( particle );
 
            else
                demo.integrate( particle );
 
            particle.life--;
        }
    }
 
    if( demo.settings.render === true )
        demo.draw( demo.particles.elements );
};
 
// in this step we create new particles instead of recycling them
demo.notRecyclingStep = function( particles ) {
 
    var i;
 
    for (i = 0; i < demo.settings.rate; i++) {
 
        var min = -10,
                max = 10,
                velx = min + Math.random() * (max - min),
                vely = min + Math.random() * (max - min),
                x = demo.settings.width * 0.5,
                y = demo.settings.height * 0.5,
                w = demo.settings.size,
                h = demo.settings.size,
                life = demo.settings.life;
 
        // continuously pushing new objects in an array cause high memory churn and should be avoided
        particles.push( new demo.Particle( x, y, w, h, life ).setVel( velx, vely ) );
    }
 
    for (i = 0; i < particles.length; i++) {
 
        var particle = particles[i];
 
        if( particle.life === 0 ){
            // splicing like pushing should be avoided
            particles.splice(i, 1);
            i--;
        }
 
        else if(demo.settings.cull === true && demo.isInBounds(particle) === false){
            // splicing like pushing should be avoided
            particles.splice(i, 1);
            i--;
        }
 
        else
            demo.integrate( particle );
 
        particle.life--;
    }
 
    if( demo.settings.render === true )
        demo.draw( demo.particles );
};

demo.ParticlePool = function(){
this.elements = [];     // will be filled with particles
this.freeElements = new DoublyLinkedList();//hold free particles indices
      // Fill the pool
      this.grow();
};

// Recyclable particle
demo.RecyclableParticle = function(poolindex) {
    this._poolindex = poolindex; // used by the pool
    this.allocated = false;      // true means alive, false means dead
}

demo.ParticlePool.prototype.grow = function( growth ){
    growth = growth || demo.settings.rate * 130;
 
    var oldsize = this.elements.length, // previous array size
        newsize = oldsize + growth;     // size after growth
 
    // Resize our elements array
    this.elements.length = newsize;
 
    for( var i = oldsize; i < newsize; i++ ){
 
        // Add a new element to our pool
        this.elements[i] = new demo.Particle( i );
 
        // Add its index to the free elements array
        this.freeElements.push( i );
    }
 
    console.log( 'Pool grown from ' + oldsize + ' to ' + newsize + ' particles.' );
};

RecyclableParticle.prototype.reset = function() {
    this.setup( 0, 0, 0, 0, 0 ); // reset size and position
    this.setVel( 0, 0 );         // reset velocity
    this.acc.x  = 0;             // reset acceleration x
    this.acc.y  = 0;             // reset acceleration y
    return this;                 // so our particle API is chainable
}

demo.ParticlePool.prototype.getFree = function(){
            if( this.freeElements.length === 0 ){
                // no free particles left, grow the pool
                this.grow()
            }
            // get and remove head from freeElements linked-list
            var index = this.freeElements.remove(0);
            // retrieve the particle from the elements array
            var particle = this.elements[index];
            // mark the particle allocated so we use it when iterating on the pool
            particle.allocated = true;
 
            // reset particle position, velocity etc.
            particle.reset();
 
            // done
            return particle;
        };

demo.ParticlePool.prototype.free = function( particle ){
    if( particle.allocated === true ){
        // mark the particle as not allocated
        particle.allocated = false
 
        // add the particle's index to the free elements array
        this.freeElements.push( particle._poolindex )
    }
};

Iterating on a Pool

After a while, your pool will look like the one shown in Listing 3-5. You can see here the benefit of both having an array of free indexes and embedding in each object its own index; otherwise, you would have to iterate over the objects array to get objects from the pool as well as to free them.

Listing 3-5. Your Pool after Many Requests and Returns

In the demo, you loop over the pool objects array twice, first to move particles around, in the physics step, then to render them. In the loops the particles are processed only if their allocated flag is set to true, so you ignore unallocated particles instead of discarding them. In this way, you are holding references to the unallocated particles rather than generating garbage, as you would if you were not using a pool (see Listing 3-6).

Listing 3-6. Looping over Only Allocated Objects

for (i = 0; i < particles.elements.length; i++) {
 
    var particle = particles.elements[i];
 
    if( particle.allocated === true ){
 
        if( particle.life === 0 )
            particles.free( particle );
 
        else
            demo.integrate( particle );
 
        particle.life--;
    }
}

Using an Object Pool

As in real life, filling a pool takes time and can be expensive. You must avoid having the object pools fill while the player is playing your game by preallocating the necessary number of objects during the initialization of the game, effectively moving the cost of creating objects up front.

You may also prefer not to allow some of your pools to grow. For instance, you may want to have only a fixed number of particles in your game. In this case, when you need to display a particle, and there is no free one left, you can choose not to spawn a particle at all or to remove the oldest one to spawn it in a new place. Do you remember trying to write your name with bullet holes in Half-Life, and the ones you shot first disappeared as you were writing? Well, now you know what was happening.

During the development process, you should monitor your pool usages to determine the levels at which your pools should initially be filled.

For more information on static memory JavaScript and object pools, you may want to consult HTML5Rocks.com (www.html5rocks.com/en/tutorials/speed/static-mem-pools).

Culling for Simulation

Discarding particles as soon as they are offscreen is the simplest task in the demo. Figure 3-4 shows a drop in CPU usage when culling is turned on.

In your loop, you call the following function and discard the particle if it returns false:

isInBounds = function( particle ){
          var x = particle.pos.x,
                y = particle.pos.y,
                w = particle.size.y,
                h = particle.size.x,
                areaW = demo.settings.width,
                areaH  = demo.settings.height;
 
           return !(x > areaW || x + w < 0 || y > areaH || y + h < 0);
     }

Not exactly rocket science, and that’s the point. This function must be cheap to be worth it, as it will be used as many times as there are live particles in the pool.

Discarding objects as soon as you can is the easiest way to save performance. It is far more time-consuming to optimize a physics engine so that it becomes 10 percent faster than it is to discard 10 percent of your objects. By not discarding objects, you are not only making the game perform worse than it should, but also wasting user CPU time and battery life.

Culling for Rendering

Chances are that, the demo notwithstanding, you may actually care about offscreen objects. For instance, if your hero were moving freely on a large map, you wouldn’t discard enemies as soon as they were offscreen. In this case, you would use boundaries that are much larger than the viewable area.

If your game boundaries are larger than the viewable area (see Figure 3-5), you should check during the rendering loop that each object is effectively in the viewable area before trying to render it. Otherwise, you will overdraw (draw more than necessary) and end up burning precious graphics processing unit (GPU) power.

Note that if you use a framework, you should check to see if it does the culling for you.

Your Code Will Be Compiled and Optimized on the Fly

What happens to your JavaScript code is rather fascinating: first it is compiled in machine language in order to run on the CPU, and then it may be compiled again, but in a more optimized way if the browser’s JavaScript engine judges this necessary and possible.

The initial compilation generates slow code, then the following compilations generate fast, optimized code, and whereas on desktop, compilation time is unnoticeable, on mobile, slowdowns are occurring as optimizations are made and tested by the JavaScript engine.

Your code will run fast only when optimized, and only the functions that are called many times will be optimized (the engine marks these as hot and optimizes them).

The consequence of this approach is that the JavaScript engine will make optimizations while your game is running.

Deoptimizations

Optimizations performed by the compiler are speculative; they are made under the assumption that the JavaScript state is stable. If the state changes, then the compiler changes the evaluation of your function, which can cause a deoptimization to occur (called a global deopt).

You can also get deoptimizations if there’s some specific part of your function that invalidates the optimization process, such as a try/catch block (called a local deopt). The engine will continue to attempt to optimize to a specific threshold and then will give up. Until that time, you can get a plethora of optimize/deopt combos every frame as the engine tries to understand itself and find a local minimum of execution.

Finding and fixing all this is madness and varies from engine to engine. I suggest that you check out the literature for each virtual machine (VM) if you see that deopts are causing performance issues (for more information, see the section “Digging Deeper.”)

Rev Up the Engine

To have your game running at a steady 60FPS from the start, your code will have to be optimized before the start. Or, to put it differently, the player shouldn’t be able to play before the JavaScript engine has optimized your game.

The obvious solution is to have a warm-up phase while the game is loading or displaying a menu. During this phase, you would run your game in the background so that its code is optimized before the user starts playing.

If you run only a subset of the game during the warm-up phase, only the JavaScript engine will optimize this subset. Sometimes, it may be enough to call only the most expensive functions, for example, a physics simulation, at a fast rate during the warm-up phase. But, I would say that the best warm-up is to run the entire game at a fast rate; however, it may be impractical to do so.

Figure 3-6 displays how Foxes and Shotguns (www.foxesandshotguns.com) warms up behind the scenes while loading assets.

Instead of generating spaced platforms, platforms are lined up, and the hero jumps and shoots randomly. Meanwhile, the loading screen is displayed. None of this is rendered, and the user will see only the loading scene. The result for this particular game is a silky smooth frame rate right from the start, instead of a rate punctuated by random slowdowns caused by JavaScript engine optimizations times.

As you can see, the warm-up phase depends on your game. Creating a special level to be used only for that purpose may be an easy way to move the compilation time up front.

Benchmarking

There’s no direct way of knowing when the browser JavaScript engine is done optimizing a function, and although using a warm-up phase is good, warming up longer than necessary makes the user wait longer than is desirable.

The only way to get a hint from your code about what’s going on is to measure the execution time of your loop, like so:

var t = window.performance.now();
function tick() {
        requestAnimationFrame( tick );
     
      var n = window.performance.now(),
          raf_delta = n - t,
          current_fps = 1000 / raf_delta;
      t = n;
 
        // read input, move things, render them
        game.step()
 
       // use step_duration to guess if the game code has been optimized
        var step_duration = window.performance.now() - t;
}

As you can see, the time it takes the loop to execute step_duration decreases and stabilizes after a while. By benchmarking your loop on various devices, you’ll get a good sense of the minimum execution time your loop should target to be to be considered good enough to exit the warm-up phase. However, keep in mind that you cannot assume a fixed number of iterations for your code to be optimized, as the heuristics used are nondeterministic and vary from browser to browser.

Now, it’s up to you to use your benchmark data to decide the best course of action for your game. For instance, you could employ a dynamic solution that uses average execution times on the fly, or a short, special level that runs for a fixed number of frames, and check the elapsed time to determine if your code has been optimized by reaching a target execution time.

Digging Deeper

To get a glimpse of what’s happening behind the scenes, you can run Chrome or Chromium with flags to print out when functions are optimized, as follows:

chrome.exe --no-sandbox --js-flags="--trace-opt --trace-deopt" -user-data-dir=<empty dir path> http://localhost/awesomegame.html

This will output in the console optimizations as they are happening, as pictured in this screenshot. Hopefully, you’ll get a better idea of what the browser is doing to make your code run fast, and maybe you’ll start optimizing your most demanding functions for V8 or find out what prevents some part of your code from being optimized. But, beware that this is a time-consuming process and probably of no value unless you find out that deopt code is a bottleneck.

For more on V8, visit https://docs.google.com/document/d/1hOaE7vbwdLLXWj3C8hTnnkpE0qSa2P--dtDvwXXEeD0/pub.

For more on optimizing for V8, check out: http://floitsch.blogspot.de//search/label/V8-optimizations.