Sign in to follow this  
Basiror

Memorypool implementation *suggestions*

Recommended Posts

Hi a few friends and me are working on a server project in our sparetime and we need to implement memory pools to avoid memory fragmentation we don t want to use boost so we write our own memorypool implementations Thats what we came up with: In the CNodePool we store the number of objects, number of free instances and object flags(one integer for 32 objects) we need them to find free objects within blocks of 32 objects the memorypool class stores a list of nodes
emplate<class T>
class CNodePool
{
public:
        CNodePool(){};
        CNodePool(unsigned int iInstances)
        {
                m_uiFreeInstances = iInstances;
                m_uiInstanceCount = iInstances;
                m_InstanceFlags = new unsigned int[(unsigned int)(iInstances/32)+ iInstances%32];
                m_Instances = new T[iInstances];
        };
        unsigned int    m_uiFreeInstances;
        unsigned int    m_uiInstanceCount;
        unsigned int    *m_InstanceFlags;
        T               *m_Instances;
};

template<class T>
class CMemoryPool
{
public:
        CMemoryPool(unsigned int iInstances)
        {
        };

        T* alloc2()
        {
                return NULL;
        };
private:
        CNodePool<T>*           m_NodeList;
};
[/SOURCE]
So do you have any suggestion for use on how to improve our pool concept? Maybe some nifty tricks, or some more elegant solutions? We really appreciate your help cya

Share this post


Link to post
Share on other sites
if your not going to use boost pool library (why not?) then at least read the concepts page as it has useful information.

Also i suggest you separate allocation/deallocation & construction/destruction as what your currently doing with your dynamic array of T is naive. If you are not sure how to do that then it works like this, allocate a chunk of uninitialized memory then some where later on when needed you construct elements using placement new operator. Placement new does not allocate memory all it does is construct/initializes memory given the address of it. Later on when needed you destroy elements by explicitly invoking the destructor which you must do when using placement new for NON pod-types with NON trivial destructors (you can use type traits and compile-type type dispatching where in the case of POD-types you do nothing). Then at the very end you deallocate that chunk of memory, e.g. in code:


#include <new> // placement new

foo* buf = static_cast<foo*>(::operator new(sizeof(foo) * N)); // allocates only
//...
new(&buf[0]) foo(...); // constructs first element only
//....
buf[0].~foo(); // destroys the first element only
//...
::operator delete(buf); // deallocates memory only.


Note that the standard library provides variants of the generic algorithms that work with uninitialized memory and there is special iterator (std::raw_storage_iterator) that lets you work with the normal generic algorithms using uninitialized memory.

You can use malloc/free to allocate/deallocate uninitialized memory aswell but you need to use placement new.

Also prefer std::size_t over unsigned int, its a type alias defined in header cstddef. It is an unsigned integral type used as a standard way to refer to sizes (its the return type of sizeof operator) and indexing/subcripts etc.

Share this post


Link to post
Share on other sites
Ah I see, your way could clear the previously allocated object once you released it and reallocate it

Means a little bit more work to be done but hopefully this pays back

thx

Share this post


Link to post
Share on other sites
Quote:
Original post by Basiror
Ah I see, your way could clear the previously allocated object once you released it and reallocate it

Means a little bit more work to be done but hopefully this pays back


The main point is you can allocate/deallocate chunks of uninitialized memory once but you can construct/destroy elements as many times as you like you just need to track what elements are currently uninitialized/initialized (make it work like a stack). The previous method is naive because in general not only does it allocate/deallocate memory it will construct/destroy memory aswell at the same time which is redundant overhead.

Share this post


Link to post
Share on other sites
Quote:
Original post by Basiror
Maybe some nifty tricks

With pleasure >;)

If you've heard about slab allocator, used in linux kernel, they explicitly use power-of-2 sized chunks, aligned to that power. That way you can instantly get the chunk, having an object from that chunk (only by and-ing the pointer).

I've implemented that kind of chunks for MSVC using VirtualAlloc (64kB alignment), and gcc(linux) using mmap (4kB alignment). Only several lines of code each.


Another thing, instead of using bitfields, you could be using free lists, where pointer to the next object is explicitly in first sizeof(void*) bytes of each object's raw memory. When an object is free, we can write on it's memory as we wish, don't we?

Cheers.
/def

Share this post


Link to post
Share on other sites
thx that are some great tipps

all you need is a pointer to the chunk
and a pointer to the first free element of the list

and you have O(1) when trying to find a single free element of this chunk
and O(n) for traversing the chunk list

i think i will implement it that way thx

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