Sign in to follow this  

Memory Pooling/Operator New

This topic is 4653 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have written the following code into my sprite class to override the operator new so that it creates a memory pool for 100 sprites.
void *cOBJ_Sprite::operator new(size_t size) throw()
{
  if(size != sizeof(cOBJ_Sprite))
  {
    return ::operator new(size);
  }
  
  cOBJ_Sprite *ptr = m_begin;
  
  // If the memory has already been allocated return the first
  // pointer on the list, if not then allocate the memory needed.
  if(ptr)
  {
    m_begin = ptr->m_next;
  }
  else
  {
    new_handler golbalHandler = std::set_new_handler(m_newHandler);
    
    // Allocate sizeof(cOBJ_Sprite) * OBJ_TOTALSPRITES bytes
    cOBJ_Sprite *block;
    try 
    {
      block = static_cast<cOBJ_Sprite*>(::operator new(
        sizeof(cOBJ_Sprite) * OBJ_TOTALSPRITES));
    }
    catch(std::bad_alloc&)
    {
      std::set_new_handler(golbalHandler);
      throw;
    }
    std::set_new_handler(golbalHandler);
    
    // Link the memory together starting with 1 because we will
    // return the zeroith pointer to the calling object.
    for(int i = 1; i < OBJ_TOTALSPRITES-1; i++)
    {
      block[i].m_next = &block[i+1];
    }
    block[OBJ_TOTALSPRITES-1].m_next = 0;
    
    ptr = block;
    
    m_begin = &block[1];
  }
  
  return ptr;
} // operator new

There are several classes in my project to which I would like to add this feature but I am unable to find a way to generalize... -- If a template is used (i.e. template<class T>) then the linked list structure will fail because objects of type T must have a m_next member variable -- If an abstact class is used for inheritance then the size of the derived classes will vary from the size of the base and the correct amount of memory will not be allocated. Does anyone have any suggestions about creating a "Memory Pool" class that would use the above process?

Share this post


Link to post
Share on other sites
Well, I dont recomment what you did as it is, but thats because I just generally avoid overloading new / delete. Why not use some sort of factory method, the class which holds these factory methods maintains the behavior for creation. Then you could say mySprite->addLink(ResourceManager::CreateSprite()); or something like that. You could parameterize the factory class so that you could implement other schemes as well without changing every single class. Ohh, and FYI boost::smart_ptr's break with an overloaded new from what I hear, thats just the word on the street but I havent confirmed it.

Share this post


Link to post
Share on other sites
If you take a look in _Effective C++_ by Scott Meyers (or was it _More Effective C++_ ? I think the first...), you'll find a hint where he does almost what you're doing.

However, if I recall correctly, there was no need for a m_next member, even though he used the first four bytes (or similar) of the object as the m_next pointer. It would work because you only need m_next while it is still in the list of unallocated (ie, uninstanced) objects; when you create a new instance, it's removed from the list and so the pseudo m_next member gets obliterated. So it may be templateable -- I haven't tried myself.

Sorry, I don't have my copy of the book here, otherwise I'd give ya the page # or example code... I'll check the thread later if you're still looking for a reference; I think we have the book at work.

Share this post


Link to post
Share on other sites
Quote:
Original post by JClayton
-- If a template is used (i.e. template<class T>) then the linked list structure will fail because objects of type T must have a m_next member variable


Use a non intrusive list like the standard library list (you can provide a custom allocator types for standard library containers).

Quote:
Original post by JClayton
-- If an abstact class is used for inheritance then the size of the derived classes will vary from the size of the base and the correct amount of memory will not be allocated.


If you overload operators new/delete for a base class the compiler will give the correct size of sub-types to operator new, don't use sizeof(cOBJ_Sprite) use the size passed to new/delete.

Also there is a special overload for operator delete for classes where there is an extra parameter that the compiler also gives you the correct size automatically to:


struct foo {
....
void operator delete(void* p, size_t n) { .... }
};



Quote:
Original post by JClayton
Does anyone have any suggestions about creating a "Memory Pool" class that would use the above process?


Don't bother so much, its only worth doing for small objects, larger ones just forward to operator new/delete. Loki library has a small object allocator you can use for your class hierarchies, boost library has pooled allocators you can use including an STL compliant allocator type (soon to have per-class allocators but simple to write you own out of the existing library).

Really it sounds like you just want a dead/alive list and/or object ownership management than a custom allocator which is a lower-level abstraction.

Quote:
Original post by The Reindeer Effect
Ohh, and FYI boost::smart_ptr's break with an overloaded new from what I hear, thats just the word on the street but I havent confirmed it.


That is when you redefine global operators new/delete not the case when you overload them.

boost::shared_ptr internally dynamically allocates the reference counter which generally use global operators new/delete sending it into an infinite recusion if you redefine global operators new/delete and use shared_ptr inside there.

How ever when i checked out the implementation there is a choice of allocators to use you just define the macro of interest and it uses another allocation scheme but all of them use global new in the end [smile] so i write a patch that allowed the selection of malloc/free allocator via macro like the others and works happily, i should probably submit the patch to boost but i don't know if that goes under bugs or new features.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster


If you are going to do something like this , you should probably do a validation on the size parameter to make sure its a positive multiple of your object size.



Ive always done this kind of thing via a seperate getfreenode() routine (and not overloading new) .....

Share this post


Link to post
Share on other sites
Microsoft's GDI+ does something similar. YOu almost never want to overload the global operator new so they make a base class that over loads new/delete and their array counter parts.

THey then derive all their classes from it. Very neat concept.

It allows you to create your own memory pools and drill right down to analyze their memory usage. It also allows you to put your code in a dll and have people create and delete them from any other dll because you handle the deletion, no more create memory in one dll and release it in aother errors:)

It also allows you to slip in cusmtom memory allocators much easier since all your objects go to the same place to get allocated.

Its really a very cunning strategy. Microsoft really does have some smart people working for them. DOn't listen to the /. crowd:)

Cheers
CHris

Share this post


Link to post
Share on other sites
Quote:
Original post by snk_kid
Quote:
Original post by The Reindeer Effect
Ohh, and FYI boost::smart_ptr's break with an overloaded new from what I hear, thats just the word on the street but I havent confirmed it.


That is when you redefine global operators new/delete not the case when you overload them.


Ahh that was you, thanks for clearing that up.

Share this post


Link to post
Share on other sites
Quote:
Original post by snk_kid


Quote:
Original post by JClayton
-- If an abstact class is used for inheritance then the size of the derived classes will vary from the size of the base and the correct amount of memory will not be allocated.


If you overload operators new/delete for a base class the compiler will give the correct size of sub-types to operator new, don't use sizeof(cOBJ_Sprite) use the size passed to new/delete.


That solves the allocation problem, however that introduces another problem with the formation of the linked list. When the memory is allocated a pointer to the first "element" is defined here:

block = static_cast<cOBJ_Sprite*>(::operator new(size * OBJ_TOTALSPRITES));

However when you attempt to index an array of type cOBJ_Sprite that points to a memory block of different size "elements" then it breaks, thus this no longer works:

for(int i = 1; i < OBJ_TOTALSPRITES-1; i++)
{
block[i].m_next = &block[i+1];
}

Share this post


Link to post
Share on other sites
Quote:
Original post by JClayton
That solves the allocation problem, however that introduces another problem with the formation of the linked list. When the memory is allocated a pointer to the first "element" is defined here:

block = static_cast<cOBJ_Sprite*>(::operator new(size * OBJ_TOTALSPRITES));

However when you attempt to index an array of type cOBJ_Sprite that points to a memory block of different size "elements" then it breaks, thus this no longer works:

for(int i = 1; i < OBJ_TOTALSPRITES-1; i++)
{
block[i].m_next = &block[i+1];
}


Think about it don't have one list of different sizes, you have multiple lists each of which are for a particular size, use something like a hash map that maps sizes to lists or something simillar.

For example boost::pool are for pools of a particular size or type, there is no per-class allocator as of yet that will work with a class hierarchy (i think) so as an example i've written one that uses an STL hash_map that maps size to boost::pool this gives amortized constant time look-up on size.

They was one problem boost::pool cannot be stored in STL containers directly so boost::shared_ptr is used. Also i've used the loki library's singleton package you don't need to use that you can use your own singleton or just a class/static member:


#include <loki/Singleton.h>

#include <boost/pool/pool.hpp>
#include <boost/pool/pool_alloc.hpp>
#include <boost/shared_ptr.hpp>

#include <cstddef>
#include <hash_map>

class Object {

typedef size_t size_type;
typedef boost::pool< > pool_type;
typedef boost::shared_ptr<pool_type> pool_ptr;
typedef std::pair<const size_type, pool_ptr> pool_pair;
typedef boost::fast_pool_allocator<pool_pair> pool_alloc;

typedef stdext::hash_map<
size_type, pool_ptr,
stdext::hash_compare<size_t>,
pool_alloc
> mmap;

typedef Loki::SingletonHolder< mmap, Loki::CreateStatic, Loki::PhoenixSingleton > PoolMap;

public:

void* operator new(size_t n) {
mmap& m = PoolMap::Instance();

mmap::const_iterator itr = m.find(n);

if(itr != m.end())
return itr->second->ordered_malloc();
else {
pool_ptr pp(new pool_type(n));
m[n] = pp;
return pp->ordered_malloc();
}
}

void operator delete(void* p, size_t n) {

mmap& m = PoolMap::Instance();

mmap::const_iterator itr = m.find(n);

if(itr == m.end())
return ;

if(!itr->second->is_from(p))
return ;

itr->second->ordered_free(p);
}
};



sample code:


struct foo : public Object {
int i;
foo(int j): i(j) {}
};

#include <string>

struct bar : public Object {

typedef std::basic_string<
char,
std::char_traits<char>,
boost::pool_allocator<char>

> string_type;

string_type s;

bar(const string_type& s_ = string_type()): s(s_) {}
};

#include <iostream>

int main() {

for(int i = 0; i < 1000000; ++i) {
foo* f = new foo(i);
delete f;
}

bar* b = new bar("hello");
bar* b2 = new bar("goobye");

delete b; delete b2;

}



Note that even the hash map uses a pooled allocator type! [grin]

boost::pool ordered member functions are used instead of non-ordered version to minimize memory fragmentation which can actually hinder performance, the code is very fast compared to the generic memory manager profile it for your self and see! if you want to use the above by redefining global operators new/delete instead you need to make minor modifications otherwise the code will go into an infinite recusion just ask if you want a hand with that.

Also note that hash_map is currently an STL extension not part of the standard library but most compiler comes with it. They are not equal on each compiler most follow SGI's interface, VC++ 7.1 and above diverge a little and the above was written and compiles on VC++ 7.1 and above.

Share this post


Link to post
Share on other sites
(Late reply): I was able to write the module without the use of 3rd party libraries (mostly for the expierence). Note that the memory pool sacrifices virtual memory (pointers in the linked list) for both CPU speed and safety. This code may be used for individual projects as long as the proper citation is given.

#ifndef __MEM_Pool_h__
#define __MEM_Pool_h__

/*
* Name: cPool class
* Author: "The Jeff"
* Date: 20/03/05 23:46
* Description: Allocates a pool of memory and interacts with said pool via a
* linked list. The memory is allocated when the cPool constructor is called
* and de-allocated when the destructor is called. A call to Alloc returns
* a pointer to the next available slot in memory and Free returns a block
* of memory back to the pool. Once all objects have been freed the pool is
* de-allocated. The cSafePool class provides a base class for objects that will
* become pool types. The safe pool is type-safe and ensures that the correct forms
* of operator new and delete are called.
*
* Declared within the namespace whileone
*
*
* Changes: None
*/


namespace whileOne {

typedef unsigned char uchar;

class cPool {
public:
cPool(size_t size, int n)
{
m_topNode = new sNode();


// Attempt to allocate memory equal to sizeof(object type) * number of objects
// in pool. If allocation fails the standard new exception is thrown.
try
{
m_topNode->memory = static_cast<uchar*>(::operator new(size * n));
}
catch(std::bad_alloc &)
{
throw;
}

sNode *node = m_topNode;
for(int i = 1; i < n+1; i++)
{
sNode *next = new sNode();

// Once a pointer has been established to the first block of memory, the function
// will loop until n is reached. Pointers will be assigned to each block of memory
// at an offset to the original pointer. The offset is equal to (i * object size)
next->memory = m_topNode->memory + (i * size);
next->prev = node;
node->next = next;
node = node->next;
}

m_curNode = m_topNode;
}

~cPool()
{
sNode *next = m_topNode;
sNode *dead;

while(next)
{
dead = next;
next = next->next;
::operator delete(dead->memory);
delete dead;
}
}

// Returns NULL if no more memory is available
void *Alloc(size_t size) throw()
{
// No more memory available so attempt to allocate some more
if(m_curNode->next == NULL)
{
sNode *node = new sNode();

try
{
node->memory = static_cast<uchar*>(::operator new(size));
}
catch(std::bad_alloc &)
{
throw;
}

node->prev = m_curNode;
m_curNode->next = node;
m_curNode = m_curNode->next;

return static_cast<void*>(node->memory);
}

void *memory = static_cast<void*>(m_curNode->memory);

if(m_curNode->next != NULL)
m_curNode = m_curNode->next;

return memory;
}

inline void Free(void *ptr, size_t size)
{
m_curNode = m_curNode->prev;

// Once the last object has been freed the constructor is called
// (subject to change)
if(m_curNode == m_topNode)
delete this;
}

private:
typedef struct sNode {
sNode *next;
sNode *prev;
uchar *memory;

sNode() : next(NULL), prev(NULL), memory(NULL) { }
~sNode() { }
}sNode;

sNode *m_topNode;
sNode *m_curNode;

cPool(const cPool &);
cPool &operator=(const cPool &);
};

/*
* This version of the Pool class is strongly typed so it can only be used on objects
* of derived classes. SafePool's operator new returns a pointer to already existing
* memory so its use does not contradict the memory pool design. Operator delete ensures
* that the pointer is merely returned to the pool and the memory remains un-deleted.
*/

template <class T, int U>
class cSafePool {
public:
cSafePool() { }

virtual ~cSafePool() { }

static void *operator new(size_t size)
{ return Pool().Alloc(size); }

static void operator delete(void *p, size_t size)
{ Pool().Free(p, size); }

private:
cSafePool(const cSafePool &);
cSafePool &operator=(const cSafePool &);

// Singleton pattern accessor: returns a reference to a pool object. Note the
// relationship between SafePool and Pool: SafePool is-implemented-as a pool.
static cPool &Pool()
{
static cPool pool(sizeof(T), U);

return pool;
}
};

}

#endif // __MEM_Pool_h__





And thanks everyone for the help :)

[Edited by - JClayton on March 21, 2005 2:55:33 AM]

Share this post


Link to post
Share on other sites

This topic is 4653 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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