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.

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.

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).

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.

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?

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:



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]

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.

Is it safe to do this:



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?

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}

Interesting stuff. Thanks, ToohrVyk.