Trying to design some object pooling

[ColbyCheeze]

I've done some reading and it seems like using object pooling for creation of many objects is ideal in many ways.

I am trying to design object pooling for creating the different types of projectiles in my game and am having some trouble deciding how to do it.

1. I've never created any kind of pooling before...
2. I'm trying to decide how to design the actual projectile class. Obviously there will be diff types like: Missle, Plasma, Laser etc...

Everything can derive from "AProjectile" which extends my "MovingEntity" class...however something im struggling with is:

Should I create multiple pools for different types of projectiles? (obviously a Missle can't be a Laser) or is there some way I could design an object that can mold to fit any type of projectile thus allowing me to derive all from the base projectile class and therefore have one pool of projectiles...

Also thought I'd see if anyone has some thoughts / examples of how to actually create some object pooling, as I am new to the concept.

Hopefully that all made sense! Love to see what you guys can come up with. Thanks :P

[newblack]

you won't be able to "apply" a type to an already created instance of a different (or ancestor) type.

In terms of pooling implementation, you can quite simply create a desired number of every type you'll be using in your application. You could map Class to a pool of that type in a Dictionary object to constrain your pool access to a single method. Offer another method to return an object you're done with to the pool. The pooling management class can identify the Class dynamically and return it to the appropriate pool.

[691175002]

The chances are that its unlikely that object pooling is really the best solution.

Except in extreme cases, object creation and collection is not going to be a massive performance bottleneck. Object pooling is moderately complex for what you get, and has the risk of the overhead being greater than simply creating objects on demand. Not only that, but the many potential types of objects that need to be pooled sticks a lot of excess complexity in there.

I assume that your goal is performance in using large quantities of objects.
There are alternatives to object pooling that may be more appropriate such as the flyweight pattern (http://en.wikipedia.org/wiki/Flyweight_pattern).

It is far faster to manage creation and deletion of coordinates (Numbers/ints) than complete objects, and opens the possibility for more optimization on top of that (Manually inlining method calls from the flyweight class).

Pools are far more suited to things like threads where creation may take orders of magnitude more time than the calculations being done. The example provided in the flyweight pattern (Characters being displayed in word processors) is really far more appropriate for bullets, there is many of them, they vary only in coordinates, it is impractical to have each one be an object in itself...

[newblack]

Instantiation is a pretty decent bottlenecker... and in the case where you're creating loads of objects like you might with projectiles in a game (or game framework if i remember correctly? where it would give the user an option to pool?) it's certainly worth looking into.

Joa Ebert talks about the huge impact it had on pooling tween objects:
http://blog.je2050.de/2008/05/07/twe...-object-pools/

[VENGEANCE MX]

I would create multiple pools; one for each type of projectile. I don't see that it'd be any slower than making one unified pool, and it makes the thinking a lot easier. Using a unified pool would probably mean that you need to put more code into instantiating each object, I think? I can see that slowing it down. Besides, the way both me and webgeek used when experimenting with pooling was to create one pool per object type. He understands OOP (and coding in general) far better than me, so I'm guessing that if there was any merit in using a single pool, he would've written it that way instead.

If you need any help, I can post my sloppily implemented pooling method. It's actually pretty simple (depending on how your engine's currently set to operate), only maybe 8 lines of code per pool, and can be slipped in and out of the engine pretty tidily. Webgeek has a better implementation (does the same thing in the same way, but with less code on your part - just two function calls per pool, I think), but I never figured out how to use it (although that can be attributed to me being useless at working in OOP).

[newblack]

I wrote this generic pooler real quickly- use should be self explanatory:

package
{
    
    import flash.utils.Dictionary;
    import flash.utils.getDefinitionByName;
    import flash.utils.getQualifiedClassName;
    
    public class PoolingManager
    {
        
        private var _poolMap:Dictionary;
        
        public function PoolingManager()
        {
            _poolMap = new Dictionary();
        }
        
        public function getElementFromPool( type:Class, autoFillAmt:int = 0 ) : Object
        {
            var pool:Array = _poolMap[ type ];
            if( autoFillAmt > 0 )
            {
                if( !pool || !pool.length )
                {
                    createPool( type, autoFillAmt );
                    pool = _poolMap[ type ];
                } 
            }
            return pool.pop();
        }
        
        public function getNumElementsInPool( type:Class ) : int
        {
            var pool:Array = _poolMap[ type ];
            if( pool ) return pool.length;
            return 0;
        }
        
        public function returnElementToPool( element:Object ) : void
        {
            var type:Class = getClass( element );
            var pool:Array = _poolMap[ type ];
            pool.push( element );
        }
        
        public function createPool( type:Class, numMembers:int = 100 ) : void
        {
            
            if( !_poolMap[ type ] ) _poolMap[ type ] = new Array();
            var pool:Array = _poolMap[ type ];
            
            while( --numMembers > -1 )
            {
                pool.push( new type() );
            }
            
        }
        
        public function removePool( type:Class ) : void
        {
            _poolMap[ type ] = null;
        }
        
        private function getClass( instance:Object ) : Class
        {
            var name:String = getQualifiedClassName( instance );
            return Class( getDefinitionByName( name ) );
        }

    }
} 

[ColbyCheeze]

Thanks for the replies. Yea I saw that example from Joa...that was one of the reasons I decided to take that route.

I suppose it would be best to just create multiple pools then...currently my game is structured as follows (the engine anyways) : http:http://www.cheezeworld.com/files/spa...MunsterUML.png

So basically what I could do is have a pool for the same "renderer" object, in which case i'd be using BitmapClipRenderer and all I'd have to do is swap the BitmapClip depending on what "type" of projectile im rendering.

As far as the projectiles I suppose I'll have to create multiple pools for each type of projectile I decide to make...the other solution would to give the "AProjectile" class all the properties than any projectile would need and attach an "actions" class which just has a set of static functions that can be called based on the parameter passed in...( Actions.projectileAction("type", parameters...); )

That would give me a max of 2 pools for the projectiles however it might end up being messy as all of the actions are being stored in one function...and also it would slow things down because I am now calling an extra function withing each projectiles update()...

What do you guys think? Just create multiple pools for multiple types of entities or do the "action" approach?

[newblack]

Maybe it's not apparent, but what I posted handles all the type separate pool creation for you...

it differentiates at the necessary level (Class), which means it only implements logic you'd have to anyway with multiple pool objects. And it keeps everything type safe (which could be painstaking if you need tons of different pools as you'd have to write a different class for each pool type).

lastly, definitely avoid the "action" approach. it breaks a lot of OOP law imo.

[ColbyCheeze]

definitely avoid the "action" approach. it breaks a lot of OOP law imo.

Yea I agree...it was just a thought I had while writing the reply. NE-ways I looked at your code it looks pretty simple and a good implementation too!

If you need any help, I can post my sloppily implemented pooling method

If you wouldn't mind I'd like to see yours and webgeeks version? Just to get an idea of some different options to try.

[JerryScript]

Except in extreme cases, object creation and collection is not going to be a massive performance bottleneck.

Try a simple loop test with sufficient iterations, do one test that creates new geom objects (rectangles, points, etc), and do another one that uses object pooling. I think you'll find that object creation with some of Flash's native classes can be a very big bottleneck.

One special case in the originator's game is the lasers. Generally speaking, a laser will be virtually instantaneous from origin to target. Due to this, you can use a simple pooling method that only has to loop from numberDestroyed to numberCreated, rather than having to rearrange a linked list based on destruction. For bullets and missles this won't work due to some objects being destroyed out of the creation order.

[VENGEANCE MX]

Here's a trimmed-down version of one of my Invasion tests, then. Put this script on your main frame (told you it's sloppy):

stage.scaleMode = "noScale";
stage.quality = "LOW";

var infSheetBMP:infSheet = new infSheet();
var troops:Sprite = new Sprite();
var troopPool:Array = new Array();

var frameRate:int=31;
var lowest:int=frameRate;
var checkCounter:int = checkRate = 8;
var startTime = getTimer();
var lowestResetCnt=frameRate*5;
var fps:int = 31;

var tI:int = 0;
var t;

var te:TextField = new TextField();
te.text = "FPS: 31\nTroops: 0";
te.autoSize = TextFieldAutoSize.LEFT;
addChild(te);

function createTroop(tr:Number):void {
    if (troopPool.length>0) {
        myTroop = troops.addChild(troopPool[0]);
        troopPool.splice(0, 1);
    } else {
        var myTroop:Infantry = new Infantry(this);
        var infSprite:Bitmap = new Bitmap(infSheetBMP);
        myTroop.addChild(infSprite);
        troops.addChild(myTroop);
    }
    myTroop.init();
}

stage.addEventListener(Event.ENTER_FRAME, EnterFrame);
function EnterFrame(event:Event):void {
    createTroop();
    
    tI = troops.numChildren;
    while (tI--) {
        t = troops.getChildAt(tI);
        t.eF();
    }
    if(--checkCounter==0) {
        fr = checkRate/((getTimer() - startTime)/1000);
        fps = int(fr*10)/10;
        if (fps<=lowest){
            powest=fps;
        } else {
            if(fps>frameRate){
                fps=frameRate;
            }
        }
        startTime = getTimer();
        checkCounter = checkRate;
    }
    if (--lowestResetCnt==0){
        lowestResetCnt=frameRate;
        lowest=frameRate;
    }
    te.text = "FPS: "+String(fps)+"\nMCs: "+String(troops.numChildren);
} 

You'll need to download and put this into your Library:



And Export it for ActionScript with a Linkage Identifier of infSheet.

Finally, you'll need an Infantry.as in your project folder saying this:

package {
    import flash.display.Sprite;
    import flash.display.Bitmap;
    import flash.display.BitmapData;
    import flash.geom.Rectangle;

    public class Infantry extends Sprite {
        public var _root;
        public var speed:int;
        public var frame:int;
        public var objMode:String;
        public var cond:Boolean;
        public var inc:int;
        
        public var obj:String = "Inf";
        
        public var WIDTH:int = 35;
        public var HEIGHT:int = 54;
        public var FRAMES:int = 17;
        
        public var rect:Rectangle;
        
        public function Infantry(mr:Object) {
            _root = mr;
            cacheAsBitmap = true;
            scrollRect = new Rectangle(0,0, WIDTH, HEIGHT);
            draw();
        }
        public function draw():void {
            rect = scrollRect;
            rect.x = frame * WIDTH;
            scrollRect = rect;
        }
        public function init():void {
            y = Math.floor(245-Math.random()*12)
            x = -50-Math.random()*20;
            frame = 0;
            speed = 3;
            objMode  = "Walk";
            cond = true;
            inc = Math.round(Math.random()*5);
            WIDTH = 35;
            HEIGHT = 54;
            FRAMES = 17;
            scrollRect = new Rectangle(0,0, WIDTH, HEIGHT);
        }
        public function eF():void {
            if (x <= 300) {
                x-=-speed;
            } else if (x>300) {
                x -= 21 ;
                y -= -10;
                objMode = "Die";
                frame = 0;
                FRAMES = 19;
                WIDTH = 54;
                HEIGHT = 44;
                scrollRect = new Rectangle(0, 121, WIDTH, HEIGHT);
            }
            draw();
            frame++;
            if (objMode=="Die") {
                if (frame==FRAMES) {
                    _root.troops.removeChildAt(_root.tI);
                    _root.troopPool.push(this);
                }
            } else {
                if (frame==FRAMES) {
                    frame = 0;
                }
            }
        }
    }
} 

Sorry if it doesn't work; I haven't tested that, so I might've removed some unnecessary stuff. I'd compile it all for you, but Flash 9 doesn't run on my Intel Mac. As for webgeek's version... you'd need to ask him for that.

Oh, bear in mind that while object pooling does get rid of the bottleneck of object instantiation, you can still create a far faster entity engine using copyPixels(). My non-pooling copyPixels() engine runs about 20 times faster than this. Comparison:

Pooling sprites (FPS capped at 31, so note that this isn't a very fair benchmark):
http://www.birchlabs.co.uk/Invasion5F9.swf
copyPixels():
http://www.birchlabs.co.uk/Invasion_5.html

[Squize]

V, pooling isn't limited to sprites mate.

I'm sure we've spoken about this before, you can still use bobs with pooling rather than just sprites.

Squize.

[VENGEANCE MX]

I know it's not limited to sprites. But if the engine can handle 7,000 bobs (or 2,000 with collision detection) fine without pooling, you don't really need to go to the extra length of pooling it. The bobs in my copyPixels() engine only have the properties x,y,frame,HP and objMode, so object instantiation isn't a pressing overhead.

Nevertheless, I'm going to try pooling my copyPixels() engine in a few weeks, once my GCSEs have finished, and see if it makes any significant difference.

[691175002]

My point is simply that even for something like lasers, as Vengeance said, you can drop a bit of the OOP fluff and make something both fast and simple.

A copyPixels engine is really quite similar to a flyweight pattern as you have a single object representing many with data being swapped in through arrays.

While object instantiation compared with reuse or pools in a simple for loop will show major performance gains, toss in a reasonably sized copyPixels or draw operation in the loop and the difference suddenly becomes much smaller. Considering each object may draw itself 30+ times during its lifetime I feel the following test is far more telling:

 Results of test:
Constant Reinstantiation: 551
Reuse: 537

var bd:BitmapData = new BitmapData(800,600);
var cpy:BitmapData = new BitmapData(200,200);
bd.lock();

var p:Point = new Point (0,0);
var r:Rectangle = new Rectangle (0,0,40,40);


var n:Number = getTimer();
var pp:Point;
var rr:Rectangle;
for (var i:int = 0; i < 10000; i++) {
	// A basic bullet symbolized by a point and rectangle
	pp = new Point();
	rr = new Rectangle();
	for (var j:int = 0; j < 30; j++) {
		bd.copyPixels(cpy,r,p);
	}
}
trace ("Constant Reinstantiation: " + (getTimer() - n));

n = getTimer();
for (i = 0; i < 10000; i++) {
	// A basic bullet symbolized by a point and rectangle
	pp.x = 0;
	pp.y = 0;
	rr.x = 0;
	rr.y = 0;
	rr.width = 0;
	rr.height = 0;
	for (j = 0; j < 30; j++) {
		bd.copyPixels(cpy,r,p);
	}
}
trace ("Reuse: " + (getTimer() - n));

You will notice that even when two completely new objects are being created each iteration, there is less than a 3% speed difference as soon as you throw in some realistic operations. This isn't even being compared to a pool, just reusing the same two objects.


I generally try to design out situations that involve hundreds or thousands of objects cycling each frame to begin with. The cases where an object pool is truly necessary (And better than the many alternatives) are far between.

[VENGEANCE MX]

Thank you, 691175002. Was hoping for some evidence along those lines. Webgeek said (if I recall correctly) that object pooling is only necessary when you're instantiating big objects that inherit loads of methods and properties, which is why the Sprite example benefits from it (inherits DisplayObject, which is massive). Point() and Rectangle() don't seem to be too intensive, but they still have a not insignificant number of properties and methods in them. A typical bob object might have even less overhead than one of these.

I'd be interested in seeing the speed difference between a Point being created, and a Sprite.

[691175002]

Here is the same test, changed to sprites:

Constant Reinstantiation: 636
Reuse: 549

A little more of a difference, but considering how heavy a sprite is, on top of the fact that a sprite will probably live longer than 30 frames, make me still think that there are better alternatives.

As well, on this scale a pool with both a hashtable lookup as well as a push/pop will have overhead.

[JerryScript]

I think there are a couple of problems with your test for reinstantiation, but I could be thinking about it the wrong way, so please correct me if I'm wrong here.

The rectangle and point objects used in your copy pixel call are not the ones created. This may not make a difference, but should be fixed.

            bd.copyPixels(cpy,r,p);

// should be

        bd.copyPixels(cpy,rr,pp); 

The second issue is that you are in fact using object pooling in both tests, due to the fact that you reuse the same rectangle and point objects in the second loop of each test. This should be done in the reuse test, but not in the reinstantiation test if you want results with no pooling. Perhaps remove the second loop and instead use more objects. That or:

for (var i:int = 0; i < 10000; i++) {
    // A basic bullet symbolized by a point and rectangle
    for (var j:int = 0; j < 30; j++) {
        pp = new Point();
        rr = new Rectangle();
        bd.copyPixels(cpy,rr,pp);
    }
}
trace ("Constant Reinstantiation: " + (getTimer() - n));

n = getTimer();
for (i = 0; i < 10000; i++) {
    // A basic bullet symbolized by a point and rectangle
    for (j = 0; j < 30; j++) {
        pp.x = 0;
        pp.y = 0;
        rr.x = 0;
        rr.y = 0;
        rr.width = 0;
        rr.height = 0;
        bd.copyPixels(cpy,rr,pp);
    }
}
trace ("Reuse: " + (getTimer() - n)); 

Either way, the results of your tests show reuse (pooling) to be faster, so why argue against it?

[691175002]

You misunderstand what is being tested.

The first test works like follows:
I assume that someone is creating a set of lightweight object, keeping each one for thirty frames (Each frame performing a single copypixel operation) then discarding it.
In the inner loop, the point and rectangle are kept the same, because it is assumed that each instance will have its own point and rectangle for personal use (Or an external class which handles drawing will also be reusing the same Point/Rect). The drawing is irrelevant to the test, I am simply padding the loop with plausible operations to show that in real life, perhaps 1% of execution will be spent creating new objects in comparison to what the objects are doing, even with something so short lived.

The second test is essentially the same, except that we are reusing instead of creating new Rectangles and Points.


Now, keep in mind that this is a test between Reuse and complete reinstantiation. Not a test between a pool and a flyweight. This just demonstrates that the most optimal solution, not creating or storing any new objects is less than 3% faster than the slowest possible solution with lightweight objects.

Now, if you wanted to simulate a pool you could toss in a hashtable lookup and a push/pop in an external class in each iteration, on several arrays of hundreds of entries in length. The gap starts to close.
I am quite confident that when you are using lightweight objects such as bullets, there will be no practical performance gain to a pool, and potentially a performance loss if your class is lightweight.


I still stand by my statement that in almost all cases, pools are either unnecessary or solve a problem that could have been avoided in the first place, even more so for something like bullets.

[ColbyCheeze]

Thank you for all of the data, I really appreciate it. I think perhaps just creation objects won't be so bad but I'll still use a factory for it all just in case later I can swap in some type of pooling on the backside and have it all still work fine.

I do actually create a few things each time a projectile is created so pooling would probably give some sort of gains on situations with large amounts of things flying around...however from your tests I suppose I can just focus on that later if I really feel it is even a cause of concern for performance.

I was just trying to juice as much performance out of all the small stuff as I could to make as much room for the AI / Collision once I get to that.

Overall good discussion so far though methinks! :P

[JerryScript]

Thanks for the explanation. I first used pooling with heavy object usage with good results, so I have always used it since, without taking into regard a lightweight case. One of those traps you fall into from good results.