mardi 24 janvier 2017

How to cooperate Memory Pool concept into data structure (e.g. custom array)?

I have been using component-entity system.
Long time ago, I wanted to improve it to use memory pool.

Phase 1

For simplicity, here is my ancient code :-

Entity* entity      =new Entity();             
Com_Physic* comPhys =new Com_Physic();

This is a result from refactoring :-

Ptr<Entity> entity=centerPool()->createEntity();                   //use pool
Ptr<Com_Physic> comPhys=centerPool()->create<Com_Physic>(entity);  //use pool

It works really good. (time used per timestep-=10%)

Phase 2

Now I have a strong desire to adapt the memory pool concept everywhere.
However, in cases that involved some data-structures, it is hard.

Here is an example function that return all (default) physics body of a certain entity.
It is not a real complete code, but good enough to show the problematic part :-

class SystemPhysic : public basicSystem {
    //..... other function / field .....
    public: MyArray<PhysicObject*> getAllPhysicBody(Ptr<Entity> entity){
        Ptr<Com_Physic> comPhysic=entity->get<Com_Physic>();
        MyArray<PhysicObject*> allPhy=comPhysic->physicsList; 
                                   //^ #problem
        return allPhy;
    }
};

MyArray<T> is a custom array similar as std::vector. It uses its own allocator.

Here is its core:-

void reserve(int expectedSize){
    //......
    void* databaseNew=operator new [](expectedSize*sizeof(T));
    //......
}

Therefore, whenever I call MyArray<PhysicObject*>::operator=(),
... roughly speaking, operator new[] will be called. (#problem)

Memory is fragmented again.

Question

How to cooperate memory pool concept into data-structure?

More technical information

There are 2 type of problems about MyArray<T>:-

MyArray<T> as a field of Component (e.g. Com_Physic).
MyArray<T> as a temporary message that pass from a system to another system. It is created fast, delete fast. (>70% , life time = 1 time-step)

I have an idea to divide it in 2 cases, ShortLife_MyArray<T> & LongLife_MyArray<T>,
... but I think I make it too complex and far harder to maintain.

To make the problem worse, in a real game, there are also many kinds of data-structure besides MyArray<T>, e.g. MyArray<T1,T2>,MyMap<T1,T2>,MySet<T1,&FunctionPointer>, etc.

My poor solutions

Solution 1 (singleton, static)

Create a static pool field in MyArray<T>, MyArray<T1,T2>,MyMap<T1,T2>, etc.

All types data-structures have to use that static pool to allocate memory when needed.

GlobalDataStructure::staticPool=topLevel()->poolPtr; 
//called only once before everything start

Disadvantage:-

It is a static variable. (not make sense much)
It is moderately hard to find where the global-setting statement should be called.
(weak) I can use only 1 pool. (I am not sure if it is a problem.)
(weak) I have to use mutex to lock the pool if my game is multi-thread.

Solution 2 (the upper hand)

Create a non-static pool field in MyArray<T>, MyArray<T1,T2>,MyMap<T1,T2>, etc.

Whenever I want to create a new data-structure,
... I have to pass the shared pool (from top-level game logic).

MyArray<T> arr=MyArray<T>(topLevel()->poolPtr);

There can be many pools for different situation. It is probably good.

When data-structures want to allocate, it must use that pool.

Disadvantage:-

I have to refactor all codes for all types of data-structure.
I have to pass the pool.
(weak) I have to use mutex to lock the pool if my game is multi-thread.

Solution 3 (lazy way)

Don't do anything, pools for entity and component should be enough.
The others solution are over-engineering.

c++11