Memory Allocation Strategies in c++ :

[anonymous12345]

hi,
i am trying to find a good design pattern to handle memory allocation of my objects in c++.
good = no errors , fastest.
I will post all designs i have thought.

For example we will use the following:

class creature : represents a monster than when killed it must be deleted.
class creatureManager : stores creatures / takes care of their destruction.


1) use of shared_ptr : (works without bugs)

c++ will call delete thus making c++ slower than java.
a) because delete and new will be called very often for small objects, whereas in java you do garbage collection when you "need" to, so you do garbage collection in big part of the memory.
b) because java does garbage collection in a seperate tread = no cost because of multicore cpus.
we chose c++ instead of java because of its speed, so why lose that benefit.

2) creatureManager has full ownership of its objects. with the following way.
a) creatures that are added to the creatureManager, now will belong only to
creatureManager (passByReference).
b) the class will be responsible for deleting the corresponding object when needed,
e.g when a unit dies.

However that means that the destruction phase cant be called at any time
e.g someone calls get(...) to get a creature (for temporal use e.g 1 frame), but at the same
time the creature dies, so we have an error we use an address that doesnt exist.

This dictates the following : (if there is an alternative please say)
c) the destruction phase will be called after the simulation phase (where creatures attacks,
gets killed, etc ...).

so the game loop will be :
while(true)
{
simulate();
destruction_phase();
show_graphics();
}

d)We cant use array/vector since deletition of objects will force it to resize(slow).
We cant use a linked list because iterating all elements in the list to find if its ready to be
deleted (killed) has O(n) time , and remove operation takes O(n).
This leaves us to use HashMap<String,Creature> ( O(1) insert, O(1) search, O(1) delete).
(i think hashMap is called unordered_map in c++).
So every unit will have a unique name/id, so we will know what to delete. We will keep a list
"list_that_must_be_deleted" that shows which things must be deleted (in order to delete
later), with the following command (pseudocode):

for(Creature c in list_that_must_be_deleted )
{
HashMap.remove(c.getName());
}

Questions :

1) Are there any other design patterns , that have same or better speed than 2nd design ?
2) Do you think the 2nd design its an okay/correct design pattern ?

thanks,

[GameZelda]

For 2), have you tried to use a vector?

I don't think vector will resize when you delete objects (at least until you delete a lot). And if you need to add a lot elements, you can resize() or reserve() in the vector before adding them.

[anonymous12345]

but isnt vector like an array.

when i delete a unit that it dies, i dont know if it would be in the end of the array.
If i am unlucky it will be at the start of the array = internally calls full copy constructor on all elements O(n) compexity .

[Speedo]

but isnt vector like an array.

when i delete a unit that it dies, i dont know if it would be in the end of the array.
If i am unlucky it will be at the start of the array = internally calls full copy constructor on all elements O(n) compexity .

Swap & pop. Swap the element to be deleted with the last element in the vector, then call pop_back().

As for your OP, it sounds to me like you're stressing over fairly irrelevant details. Unless you are expecting to remove dozens of units/items every frame, I don't really see much way that that's going to be a bottleneck in a game. I would probably just start with a vector or list, whichever is more appropriate (probably a list), and if profiling determines that removing units is actually a bottleneck, then start considering other container types or optimizations.

[nuzzle]

hi,
i am trying to find a good design pattern to handle memory allocation of my objects in c++.

Have you tried smart pointers?

When there's no obvious object owner, use smart pointers.

[JVene]

c++ will call delete thus making c++ slower than java.

Actually that's not accurate.

A great many of the commercial engines use a form of smart pointer, though most reject boost's shared_ptr and much of the STL for performance and compiler/platform reasons.

"Under the hood" of Java, you'll find the JVM is written in C and/or C++, and it should be obvious that what's implemented there to perform that work in alternate threads is an option in C++ itself. It couldn't be implemented in Java otherwise.

Further, the general heap is serialized. When a garbage collection engine does it's work there is a lock (or a series of lock/unlock, I don't know the specifics) on the heap while memory is returned to general storage. There are few options for optimizing memory access in threaded systems since the application developer has limited control over it.

In C++, on the other hand, one can multiplex the allocation from the heap, bringing considerable performance benefits when well applied. Considerable research shows that when memory allocation/deallocation cycles are a bottleneck, custom allocation solutions achieve orders of magnitude of gain. I have an old thread on "Custom memory allocation revisted" that discusses part of it.

because delete and new will be called very often for small objects

If this happens as the result of a character being killed, how often can this occur? The time is likely negligible overall. Depending on just what the destructor does, it's probable that at least 100s of thousands can be deleted per second, perhaps a million. If assets in the object complicated (many containers, lots of related objects for example), it is entirely possible to pass the object via shared_ptr (or similar) to an 'engine' devoted to deletion within a thread. Removal of the smart pointer from the container/manager solves the issue of the object being referenced inappropriately (even if it's destroyed later, it's gone as far as the manager/container is concerned).