Sign in to follow this  

How do you manage object pools in your engine/game?

This topic is 1181 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I would like to know how do you manage object pools in your engines/games and how do you access them. I have some ideas:

  1. For each entity manually add a static member that will be the ObjectPool managing this entity type. One problem here is how and when the pool should be inited. In my egine almost all objects initialization are made in an init() method that is called after construction. So I would have to init the static instance somehow.

  2. Have a Pool Manager acting like something like a Plugable Factory where entities are registered and a Pool are created for this entity type. Something like this:

    PoolManager.RegisterEntity<Ogre>(preAllocationCount, maxSize);
    PoolManager.RegisterEntity<Orc>(preAllocationCount, maxSize);
    Ogre* ogre=PoolManager.Create<Ogre>();
    ogre->init(...);
    PoolManager.Delete(ogre);

Don't know if this is something overengeniered. But seems something I like because transfer the entity creation to just a system in the game. The PoolManager.

 

What do you think? Could you expose more ideas around this subject?

 

Thanks in advance.

 

Share this post


Link to post
Share on other sites

I like to keep things simple and use the new and delete operators most of the time and don't worry that much about allocation. I'm confident that the implementation of new/delete doesn't do anything terribly stupid and that I would have to work really hard to do something better performance-wise. If I need to track objects I put them into an std::vector or sometimes a std::map. There are some cases where I have groups of large numbers of very small objects, and for those I instead use the operator new[] and delete[].

Share this post


Link to post
Share on other sites

Hi,

 

Thanks for the answer. Well with this aproach moving to a simple placement new will improve performance greatly. Let's here some more options ;).

 

Cheers.

Share this post


Link to post
Share on other sites

Option two, there is no need to store extra member variables inside the object and it seems easier to maintain. Having it as a fully separated system makes it easier to benchmark and/or build usage stats without having to link unrelated system together. I use something similar to keep objects of the same type in a coherent chunk of memory to make looping over them cache friendly.

 

As to new and delete they usually use mallac and free, both are know to slow down when they start fighting memory defragmentation. So if your code allocates and destroys a lot of objects, gets used in long game sessions or some sort of server you might start running in to performance issues (random time spikes) when creating/destroying objects.  When people talk about object pools they usually need them to avoid those random spikes to gain more stable frame times.

 

Edit: Memory defrag is not the only reason new/delete and malloc/free have unreliable timing, there are some platform depended reasons as well.

Edited by Nemo Persona

Share this post


Link to post
Share on other sites

Option two, there is no need to store extra member variables inside the object and it seems easier to mentain. Having it as a fully seperated system makes it easyer to benchmark and/or build useage stats without having to link unrelated system together. I use something similair to keep objects of the same type in a coherent chunk of memory to make looping over them more cache friendly.

 

As to new and delete they usualy use mallac and free, both are know to slow down when they start fighting memory defragmentation. So if your code allocates and destroys alot of objects, gets used in long game sessions or some sort of server you might start running in to performance isseus (random time spikes) when creating/destroying objects.  When people talk about object pools they usualy need them to avoide those random spikes to gain more stable frame times.

I'm inclined to move that to an external system instead of putting in the related class type.

 

Could you explain a bit how your system work? I was thinking about implementing something simple based on std::vector. I mean allocating for example vectors of 10 or 20 objects on demand. This way I would not  get too deep into this difficult subject and would get rid of reallocation problems ivalidating all previously created pointers.

 

Cheers.

Share this post


Link to post
Share on other sites

What Nemo Persona says, constantly newing and deleting objects is a bad idea if your game should be running for a longer period of time. Each new usually translates into a context switch from application/user mode into kernel mode for the OS, which then needs to allocate the requested amount of memory, and then switch back to user mode, which might take a long time depending on fragmentation and platform specifics.

 

ObjectPools are usually used to avoid new and delete for most of your use cases. You allocate a large memory buffer (either with new or malloc), and then manually hand out that memory to the rest of your application. That way you limit yourself to a low number of memory allocations, and instead only care about memory initialization (with placement new, for example).

 

The simplest way to make an ObjectPool is to use a vector for your planned type (i.e. std::vector<Ogre>), make a simple wrapper class that tracks which indices were "allocated" (more like requested to be used), and that's it. If you know for sure you will never need more than X amound of your objects, you can even just use an array (Ogre[1000]), and keep the same wrapper interface, without the user of that interface being none the wiser, except the fact that it won't be able to allocate more than 1000 Ogres.

Share this post


Link to post
Share on other sites

What Nemo Persona says, constantly newing and deleting objects is a bad idea if your game should be running for a longer period of time. Each new usually translates into a context switch from application/user mode into kernel mode for the OS, which then needs to allocate the requested amount of memory, and then switch back to user mode, which might take a long time depending on fragmentation and platform specifics.

 

ObjectPools are usually used to avoid new and delete for most of your use cases. You allocate a large memory buffer (either with new or malloc), and then manually hand out that memory to the rest of your application. That way you limit yourself to a low number of memory allocations, and instead only care about memory initialization (with placement new, for example).

 

The simplest way to make an ObjectPool is to use a vector for your planned type (i.e. std::vector<Ogre>), make a simple wrapper class that tracks which indices were "allocated" (more like requested to be used), and that's it. If you know for sure you will never need more than X amound of your objects, you can even just use an array (Ogre[1000]), and keep the same wrapper interface, without the user of that interface being none the wiser, except the fact that it won't be able to allocate more than 1000 Ogres.

Thanks, good answer.

 

More or less this is the way I was explaining. The problem with a single vector is reallocation handling. This is why I suggested to use an array of pools. This way reallocs of vectors won't be proced.

 

Cheers.

Share this post


Link to post
Share on other sites

We have multiple memory pools knocking about, it's something I am very familiar with as it often goes wrong when people don't use it properly, but a good memory pool system can speed up your game massively.

 

To give you a few examples.

 

Scratchpad

     INCREDIBLY DANAGEROUS!!!  but incredibly fast.

 

     We use a scratchpad when we just need a block of memory within a subroutine. an example pseudo code would be

void init(int size)
{
    base = maloc(size);
}

void * alloc(size)
{
      oldptr = base;
      base+=size;
      return oldptr;
}

void free(int size)
{
     base-=size;
}

You can see why it is so dangerous smile.png

Used correctly it is about as fast as you can get.

 

 

Simple pool

 

   A simple pool is much safer, but can suffer from fragmentation.  It is a double linked list of memory fragments.

   This produces an overhead on each memory allocation, you attach a header to each allocation. So each alloc consumes requested memory + header size bytes of memory.

   When you free a block of memory, you look at the last and next blocks. If either of those is free you join this allocation to it... kind of hard to explain.

 

   I'll try a diagram. F is a free block, A is an allocated block. So if you start off with this structure

 

   A1 A2 F1 A3 A4 F2     

 

   Then free A2 you end up with F1 growing into the newly available space and end up with this structure

 

   A1 F1 A3 A4 F2

 

   If you then free A3 , F1 grows again... in the other direction

 

   A1 F1 A4 F2

 

   Finally freeing A4 not only grows F1 a third time, but merges F1 and F2

 

   A1 F1

 

 

The last type of allocator we typically use is a block based system. This is used when we know we would get fragmentation and we have a good idea of the size of each allocation

 

We just allocate an array of blocks of memory and mark them as free. When you ask for an allocation you are just given the first free one.

 

This can never fragment, and is very fast, but it is also very wasteful. Say you decide that 4K is a valid block size, every block will be 4K, so if you only need 3K , you have wasted 1K of ram.

 

 

This is just a walk through of the basic structure of the sorts of memory allocators we use and why, as usual the real world code gets more complex. Fallbacks, error handling, and a million other things that people add because they had a bug and made it general case instead of situational... but that's lfe I guess.

 

Hope this helps you come up with a plan.

Share this post


Link to post
Share on other sites

 

What Nemo Persona says, constantly newing and deleting objects is a bad idea if your game should be running for a longer period of time. Each new usually translates into a context switch from application/user mode into kernel mode for the OS, which then needs to allocate the requested amount of memory, and then switch back to user mode, which might take a long time depending on fragmentation and platform specifics.

 

ObjectPools are usually used to avoid new and delete for most of your use cases. You allocate a large memory buffer (either with new or malloc), and then manually hand out that memory to the rest of your application. That way you limit yourself to a low number of memory allocations, and instead only care about memory initialization (with placement new, for example).

 

The simplest way to make an ObjectPool is to use a vector for your planned type (i.e. std::vector<Ogre>), make a simple wrapper class that tracks which indices were "allocated" (more like requested to be used), and that's it. If you know for sure you will never need more than X amound of your objects, you can even just use an array (Ogre[1000]), and keep the same wrapper interface, without the user of that interface being none the wiser, except the fact that it won't be able to allocate more than 1000 Ogres.

Thanks, good answer.

 

More or less this is the way I was explaining. The problem with a single vector is reallocation handling. This is why I suggested to use an array of pools. This way reallocs of vectors won't be proced.

 

Cheers.

 

 

You should note that if you reference the objects in the pool by index within the vector, than you don't need to care about the vector moving the data around in memory. This is the strength of indices, with the small drawback of one additional indirection to actually get the data.

 

And the usage of these pools should also be as simple as possible. If you need a pool for Ogres, make an instance if ObjectPool<Ogre> m_ogrePool in your game class, or some other logical place. Don't make the pools static, nor singletons, as you lock yourself from being able to make different pools for different levels or maps.

Share this post


Link to post
Share on other sites

 

Could you explain a bit how your system work?

 

My object pool allocates a data block using malloc(sizeof(Type) * count) and then it uses the return pointer as a standard array or objects. Using malloc avoids the constructor calls, sins you are working with a object pool you usually implement init/create/delete methods to reset the object and that makes the constructor/destructor obsolete in most cases.

 

As for invalidating pointers, keeping the memory block coherent does invalidate them but sins I'm using a data oriented design I don't rely on the pointer as a id to a object. To id specific objects every object pool has a secondary array with id's that is kept in sync with the data array, kinda like a key value pair. This works because I almost never access the 'objects' based on there id due to the data oriented design, if you do access objects based on id the look ups would be to slow.

 

As mentioned before std::vector reallocate objects and invalidate pointers as well, you can get around this by using a vector of pointers to objects, std::vector<Object*> will do the trick and keep things simple.

 

ps. damm spell checker why you disabled >.<

Edited by Nemo Persona

Share this post


Link to post
Share on other sites

The object pool pattern is about re-using objects by putting back wasted objects into the pool (perhaps up to an upper limit) instead of deleting them. So sub-sequent allocations are fed from the pool until those is depleted. The pool may be preset with a minimum of objects.

 

The pool allocation scheme is a concept where (usually fixed size) objects are allocated from a pre-allocated block of memory. Its purpose is to avoid the costs of generic new/delete or malloc/free operations in situations where the memory usage pattern is known.

 

Both concepts are independent; they can even be combined.

Share this post


Link to post
Share on other sites

the old school way:

 

a statically allocated array of structs.  each struct has an "active" field (boolean).

 

allocate: findfirst inactive, return index, use it.

 

deallocate: active=0;

 

there is one array for active entities, and a second for active projectiles.

 

very clean code.  runs very fast.

 

runtime memory allocations are limited to local variables created on the stack, and perhaps one explicit malloc and free of a huge buffer for reading in the exe file and calculating a checkcsum.

Share this post


Link to post
Share on other sites

The only thing I'm using object pools for are my particles. I have a list of 10,000 that I keep up with. I keep up with the nextParticleIndex and when I need a particle, I use that guy and advance the counter. I setup the particle with the appropriate position, color, rotation, etc. Each particle also has an Active flag and sets this to false after the particle's duration has elapsed.  

 

I don't bother looking for the first inactive particle, I just keep using the next guy assuming he's completed. If I have 10,000 active particles and overwrite one, I don't think any of my players will notice. :)

 

For everything else, I just new up and delete as needed. I doubt it will ever be an issue. If it ever is, that's when I'll look into profiling where the problem is and optimizing it then.

 

- Eck

Share this post


Link to post
Share on other sites

Question (C++ specific) to those using init methods in lieu of constructors: Why not use placement new/delete instead of methods that init your object?

Edited by CDProp

Share this post


Link to post
Share on other sites

Question (C++ specific) to those using init methods in lieu of constructors: Why not use placement new/delete instead of methods that init your object?

 

In a lot of cases I don't actually call the init method, usually when I know required values are build in next code block thus avoiding unneeded constructor/method call and/or stack allocation for temp values to pass on to constructor/method. This could still be achieved with placement but then it becomes obfuscated and less obvious when reading true the code months later, so boils down to personal preference I guess. (Pod objects only, for objects with resources that require to be managed following RAII is a must in my mind and placement seems like a nice option.)

Edited by Nemo Persona

Share this post


Link to post
Share on other sites

A simple pool is much safer, but can suffer from fragmentation. It is a double linked list of memory fragments.
This produces an overhead on each memory allocation, you attach a header to each allocation. So each alloc consumes requested memory + header size bytes of memory.
When you free a block of memory, you look at the last and next blocks. If either of those is free you join this allocation to it... kind of hard to explain.


Note that the memory overhead caused by link pointers can be safely eliminated through the proper use of unions and type punning.

Share this post


Link to post
Share on other sites

This topic is 1181 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this