Sign in to follow this  
Aardvajk

Pool allocators and polymorphic types

Recommended Posts

I just wondered if anyone had any thoughts on strategies to provide more efficient systems of allocation for polymorphic game objects. I understand how to create a pool allocation scheme for types that are guaranteed to be the same size in a way that would be more efficient than just using new and delete but my games tend to be structured with game objects being derived from a common base that the engine manipulates via a list of base class pointers. Obviously I can see the potential performance hit in using new and delete to create and destroy such objects on a frame-by-frame basis (although to be honest I've never actually witnessed any performance penalties - it is more something that I feel should have a performance hit [smile]) but I can't quite get my head around how I could write an allocater that could more efficiently provide memory for a hierachy of polymorphic objects whose sizes would be different. I can imagine sort of re-implementing the a standard memory manager as employed by the run-time with a pre-allocated chunk of memory and chains of free space and so on but I guess that wouldn't be much of an improvement on standard new/delete (probably worse if I wrote it) plus would suffer from the same issues as standard allocation strategies like fragmentation or non-constant time searching for free blocks and so on. Sorry if the above is not too clear. I hope I've explained what I mean well enough for someone to give me some input. Thanks in advance.

Share this post


Link to post
Share on other sites
Well, there are still different strategies available for generic memory management that have their own trade-offs. For example, you could always allocate at the end of your generic memory buffer, which will be a constant operation, and then do a compaction on the buffer only when you run out of room. .NET's garbage collection does something similar to this (I was thinking of this specifically because of this article). You have to worry about the less frequent but time-intensive compaction process, and have to worry about either having double pointers or readjusting pointers when you do a compaction, but your allocations and deallocations are very quick.

Share this post


Link to post
Share on other sites
I use pool allocators for the most frequent sizes used. For instance, I use sizes 8, 16, 32, 64. When I allocate an object, I look for the smallest pool in which the object can fit and get the memory from there (returning it to that pool when the object is destroyed). Sizes above 64 are allocated using good old new, but it should obviously not happen often.

Of course, 8/16/32/64 are abritrary examples. You should examine what the size distribution of your objects is, and choose the pool sizes based on this (the formula for computing the average memory wasted by padding is quite simple).

Share this post


Link to post
Share on other sites
Thanks for the input people. It's appreciated.

ToohrVyk - that's a good idea. Thinking about it, I remember reading that the Windows HeapAlloc function uses a similar system and I reckon that could be ideal for what I want.

I guess if I had a virtual member return the size of the object, I could write a system that uses this approach that could select the correct allocator to take the memory from just using the base class interface.

I suppose there isn't really a simpler solution to this problem. Guess I better brush up on my placement new and explicit destructor calling. Never really used all that before.

Thanks again.

Share this post


Link to post
Share on other sites
Quote:
I guess if I had a virtual member return the size of the object, I could write a system that uses this approach that could select the correct allocator to take the memory from just using the base class interface.

I suppose there isn't really a simpler solution to this problem. Guess I better brush up on my placement new and explicit destructor calling. Never really used all that before.


Member new/delete operators for the base class, with a singleton memory pool allocator?

Share this post


Link to post
Share on other sites
Cor. That sounds like a nice idea. I've actually never written any custom new and delete operators before, but I'm sure I could google some information.

I'm guessing I could write an operator new and delete function in the base class that used a polymorphic GetSize() member and returned the memory from an allocator? Where would I call the placement new? I'm guessing that would have to be done in the derived class since a constructor can't be virtual, or have I got the wrong end of the stick?

Sorry to be asking questions that google can probably answer. I'll have a look into it tonight when I get in. Definatley sounds like the plan though.

Ta.

[NESTED EDIT] - Was typing edit below when you replied Toohrvyk. Sorry [smile]

[EDIT] Sorry - I think I get it. I don't need placement new etc if I am providing operator new/delete. I've just tried this:


#include <stdio.h> // sorry! don't have stl at work

int mem[10]; int mp=0;

class X
{
public:
X(int v) : V(v) { }

static void *operator new(size_t sz);
static void operator delete(void *d);

int V;
};

void *X::operator new(size_t sz)
{
printf("operator new called\n");

return (void*)(&(mem[mp++]));

return 0;
}

void X::operator delete(void *d)
{
printf("operator delete called\n");

(*(int*)(d))=-1;
}

void out()
{
for(int i=0;i<10;++i) printf("%d ",mem[i]);
printf("\n");
}

X *x[5];

int main()
{
out();

for(int i=0;i<5;++i) x[i]=new X(i*10);

out();

for(int i=0;i<5;++i) delete x[i];

out();
}





This seems to produce the output I would expect. Am I on the right track, and are there any potential gotchas anyone would like to warn me about once I start trying to apply this to a polymorphic hierachy? I appreciate that my "allocation strategy" with the array and the mp variable suck but it was just as an example.

Cheers.

[Edited by - EasilyConfused on October 5, 2006 10:59:41 AM]

Share this post


Link to post
Share on other sites

class Base {
public:
static void* operator new (std::size_t);
static void operator delete (void*);
};

class Derived: public Base {};

Base* b = new Derived();
delete b;


This code would call Base::operator new(sizeof(Derived)), so it can fetch the memory from a pool allocator and return it. Then, it would call Base::operator delete(b), which should use some clever tactics to return the data to the correct pool allocator. Various techniques are possible depending on what you do, from the polymorphic sizeof method to a pointer-to-pool stored at index -1 in the memory buffer returned by operator new.

Share this post


Link to post
Share on other sites
Is it safe to do this:


class X
{
public:
// ...
static void operator delete(void *d);

virtual size_t get_size(){ return sizeof(X); }
};

void X::operator delete(void *d)
{
X *x=static_cast<X*>(d);

IdentifyPoolWith(x->get_size());

// etc
}

class Y : public X
{
public:
// ...

size_t get_size(){ return sizeof(Y); }
};

int main()
{
X *x=new Y();

// ...

delete x;
}




Seems to produce the output I'd expect on my trivial example but we are well into bounds where my understanding is a bit limited. Is there anything above that looks like a horrible accident waiting to happen? The static_cast concerns me a bit, but I can't dynamic_cast the void* pointer, can I?

Share this post


Link to post
Share on other sites
Reading through the standard, I found:

Quote:
12.5§5[class.free]
When a delete-expression is executed, the selected deallocation function shall be called with the address of the block of storage to be reclaimed as its first argument and (if the two-parameter style is used) the size of the block as its second argument.


This means that, as long as you have a virtual destructor, you can write:

void X::operator delete(void *d,size_t size)
{
IdentifyPoolWith(size);

// etc
}

Share this post


Link to post
Share on other sites
If you use it correctly and don't derive from "pool-allocated" classes, or make derived pool-allocated classes also pool-allocated, then you can use a plain pool-allocator. (sorry for that sentence :D)

My implementation looks like this:


#define PA_ALIGN 4
inline void* pa_malloc( size_t size ) { return malloc(size); }
inline void pa_free( void* ptr, size_t size ) { free( ptr ); }

/**
* Pool Allocator Implementation
**/

struct PoolAllocator {
std::vector<unsigned char*> pools;
size_t elemsize, slotsize, nelements;
size_t nextfree;
std::queue<unsigned char*> freelist;
PoolAllocator( size_t elemsize, size_t nelements ) : elemsize(elemsize), nelements(nelements), nextfree(0), slotsize(elemsize) {
if( slotsize % PA_ALIGN ) slotsize += PA_ALIGN - (slotsize % PA_ALIGN);
pools.push_back( (unsigned char*)pa_malloc( slotsize * nelements ) );
}
~PoolAllocator() {
for( std::vector<unsigned char*>::iterator i=pools.begin(); i!=pools.end(); ++i )
pa_free( *i, slotsize*nelements );
}
void* allocate( size_t s ) {
// try free slot
if( freelist.size() ) {
unsigned char* slot = freelist.front();
freelist.pop();
return slot;
}
if( nextfree >= nelements ) {
// create new pool
pools.push_back( (unsigned char*)pa_malloc( slotsize * nelements ) );
nextfree = 0;
}
unsigned char* slot = pools.back() + slotsize * nextfree;
nextfree ++;
return slot;
}
void deallocate( void* p, size_t s ) {
unsigned char* px = (unsigned char*)p;
freelist.push( px );
}
};

/**
* example usage:
* class SceneGraphNode : public PoolAllocatorMixin<SceneGraphNode,2000>
**/

template < typename T, size_t poolsize=5000 >
class PoolAllocatorMixin {
static PoolAllocator ms_PoolAllocator;
public:
void *operator new( size_t s ) { return ms_PoolAllocator.allocate(s); }
void operator delete( void* p, size_t s ) { return ms_PoolAllocator.deallocate(p,s); }
};


// class static pool allocator instance
template < typename T, size_t poolsize >
PoolAllocator PoolAllocatorMixin<T,poolsize>::ms_PoolAllocator( sizeof(T), poolsize );





And you may use it like this:


class Base : public PoolAllocatorMixin<Base,2000> {
...
};

class Derived : public Base, public PoolAllocatorMixin<Derived,2000> {
...
};




Never tested the mixin on derived classes, but should work - theorethically.

Is completely transparent to the user, and there would be two separate pools: Base::ms_PoolAllocator and Derived::ms_PoolAllocator.

EDIT:

You may never forget to override the pool allocator on derived classes. Else it will crash. So, its not very useful for a library.

Example to override a derived class with default allocator:

class Derived : public Base {
...
public:
// override with std allocator
void *operator new( size_t s ) { return malloc(s); }
void operator delete( void* p, size_t s ) { free(p); }
};


Share this post


Link to post
Share on other sites
Quote:
Original post by Robert Frunzke
If you use it correctly and don't derive from "pool-allocated" classes, or make derived pool-allocated classes also pool-allocated, then you can use a plain pool-allocator. (sorry for that sentence :D)


Classic [grin].

Cheers for that Robert. I'd like to roll out my own pool allocator really for the experience but I'll keep your code above to hand to refer to.

Paul

Share this post


Link to post
Share on other sites

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