Sign in to follow this  

How to use a memory pool?

This topic is 4686 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 want to allocate memory for 200 objects of type T at the begining of the game. Not create the objects, just allocate the memory! Then, when the game starts, I do not have to allocate/deallocate, I just construct/destroy when needed (this takes a lot of time less). Now, could someone tell me how to do this with STL? ;) I've read through the documentation and as far as I could understand I need to use a raw_storage_iterator. Could someone give me an example, or point me to a web site with an example how this should be done? Thanks, Csaba

Share this post


Link to post
Share on other sites
As far as I know you can tell std::vector and std::deque to reserve space for later use, though Im not certain. I'll post a link as soon as I find one.

EDIT: Found it.
You can use std::vector::reserve (I assume std::deque has it too).
You can do the same by passing a number to the constructor, so:

std::vector<int> vec1(10);
std::vector<int> vec2;
vec2.reserve(10);


Both vec1 and vec2 now have enough space for 10 ints allocated.
Check your favourite STL reference for more details or try looking here.

EDIT 2: Ah, Ok, thanks Trap. So it seems that even though it reserves space, it does not reserve uninitialized memory.
Though I cant see why this matters in this case... I guess my C++ knowledge still needs some work ;-)

EDIT 3: Quick look at SGI's STL docs reveals this:
Quote:

The main reason for using reserve() is efficiency: if you know the capacity to which your vector must eventually grow, then it is usually more efficient to allocate that memory all at once rather than relying on the automatic reallocation scheme.


[Edited by - issch on February 12, 2005 3:02:07 PM]

Share this post


Link to post
Share on other sites
Containers like vector reserve space, that is correct. But they do it by creating 1 object and copying it to every reserved space. They don't reserve uninitialized memory.

Share this post


Link to post
Share on other sites
Quote:
Original post by Trap
But they do it by creating 1 object and copying it to every reserved space. They don't reserve uninitialized memory.


Actaully std::vector::reserve allocates uninitialized memory only, std::vector::resize will allocate & then copy construct initialize its elements. STL allocator concept separates allocation/de-allocation & construction/destruction.

Share this post


Link to post
Share on other sites
Quote:
Original post by gcsaba2
I've read through the documentation and as far as I could understand I need to use a raw_storage_iterator.


You don't need to, STL provide a special class of iterators & algorithms that deal with uninitialized memory if you need the facilities your not required to use them, in order to give a pooling scheme for STL containers you write an STL compliant allocator type, all STL allocators are parameterized by allocator type as already been said the boost library have a couple of STL compliant allocator types both pooled allocators good for small objects.

Quote:
Original post by gcsaba2
Could someone give me an example


Sure, first choose your memory model/scheme, write a memory manager, the loki library has a small object allocator so i'll use that and wrap it up in an STL compliant allocator type:


#include <cstddef>
#include <Singleton.h>
#include <SmallObj.h>
#include <new>

template<
typename Tp,
std::size_t chunkSize = DEFAULT_CHUNK_SIZE,
std::size_t maxSmallObjectSize = MAX_SMALL_OBJECT_SIZE
>
class loki_pool_allocator {

struct loki_pool_alloc : public Loki::SmallObjAllocator {
loki_pool_alloc(): Loki::SmallObjAllocator(chunkSize, maxSmallObjectSize) {}
};

typedef Loki::SingletonHolder< loki_pool_alloc > alloc_type;

public:

typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef Tp* pointer;
typedef const Tp* const_pointer;
typedef Tp& reference;
typedef const Tp& const_reference;
typedef Tp value_type;

template< typename Tp1 > struct rebind { typedef loki_pool_allocator<Tp1> other; };

loki_pool_allocator() throw() { }

loki_pool_allocator(const loki_pool_allocator&) throw() { }

template<typename Tp1>
loki_pool_allocator(const loki_pool_allocator<Tp1>&) throw() { }

~loki_pool_allocator() throw() { }

pointer
address(reference x) const { return &x; }

const_pointer
address(const_reference x) const { return &x; }

pointer
allocate(size_type n, const void* = 0)
{ return static_cast<Tp*>(alloc_type::Instance().Allocate(n)); }

void
deallocate(pointer p, size_type n)
{ alloc_type::Instance().Deallocate(p, n); }

size_type
max_size() const throw()
{ return maxSmallObjectSize; }

void
construct(pointer p, const Tp& val)
{ ::new(p) Tp(val); }

void
destroy(pointer p) { p->~Tp(); }
};

template<
typename Tp,
std::size_t chunkSize,
std::size_t maxSmallObjectSize
>
inline bool
operator==( const loki_pool_allocator< Tp, chunkSize, maxSmallObjectSize >&,
const loki_pool_allocator< Tp, chunkSize, maxSmallObjectSize >&) { return true; }

template<
typename Tp,
std::size_t chunkSize,
std::size_t maxSmallObjectSize
>
inline bool
operator!=(const loki_pool_allocator< Tp, chunkSize, maxSmallObjectSize >&,
const loki_pool_allocator< Tp, chunkSize, maxSmallObjectSize >&) { return false; }

#include <cmath>
#include <algorithm>
#include <iterator>
#include <vector>
#include <iostream>

int main() {

typedef std::vector<int, ::loki_pool_allocator<int> > cust_vec;
const cust_vec::size_type N = 30;
cust_vec v;

v.reserve(N);

std::generate_n(std::back_inserter(v), N, std::rand);

std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, ", "));

}


Share this post


Link to post
Share on other sites
Hmm, not good. Although the vector thingie seems to be just what I need when it comes to memory usage, I actually want to use lists, not static vectors. The deque may have been okay, but it doesn't support reserve() as it is said in the documentation. Neither does list.

I mean I could in theory do the whole thing without using STL, but I hoped there was an easy way for this. What I want is actually the following:
1) I have a memory space enough to contain 200 objects with 2 pointers each (for having a double-linked list)
2) At first the memory is only allocated, but it is not initialized
example: T *MemSpace = (T*)(malloc(200 * (sizeof(T) + 2*sizeof(void*)));  

3) When I create a new instance, I point to a memory address, write there whatever I want, create the necessary pointers to simulate a list, and that's it
4) I'm not sure how to do the deleting part. Perhaps the two pointers should always exist, even if an object is not initialized? Then, when something is thrown out, the second pointer of the last element in the list will point to its address, so it will effectively be placed at the end of the list
5) When the program ends, the entire memory space is freed.

Here's an example program. I KNOW it's damn complicated, and I'm wondering if doing all this pointer arithmetic will actually save me time compared to simply allocating memory. An alternative to this complex solution would be to add a new bool field which will be true if the object is used and false if it isn't.

struct T
{
char name[10];
};

int main()
{
T *Instance;
int *Pointer, *Position;

// allocate the memory for 200 objects with 2 pointers each
T *MemSpace = (T*)(malloc(200 * (sizeof(T) + 2*sizeof(void*))));

Instance = MemSpace; // instance points to the begining address of MemSpace
strcpy(Instance->name,"First"); // we write something to that address
Position = (int*)Instance; // we save the position
Instance++; // lets move to the next address
Pointer = (int*)Position; // Pointer will point to that address
*Pointer = (int)Position; // and it will hold the address of Instance
Pointer++; // lets move to the second pointer
Position = Pointer;
Position++; // move to the address of the following instance of T
*Pointer = (int)Position; // point to that address
Instance = (T*)Position; // lets create another instance
strcpy(Instance->name,"Second"); // we copy something into it
Instance++; // move to the address of the first pointer
Pointer = (int*)Instance; // save that position
Instance--; // go back
Instance--; // go back again
Position = (int*)Instance; // take the address
Position--; // go back
Position--; // go back
*Pointer = (int)Position; // get the address of the previous element
Pointer++; // move to second pointer
*Pointer = 0; // point to NULL

free(MemSpace); // at the end of the program

return 0;
}


Here's a code that is more understandable. In fact, this is similar to what I wanted to do in the first place. However, this way I won't be using STL, but instead I'll have to make my own double-linked list :(
struct SList
{
char name[10];
bool empty;
SList *back,*forward;
};

int main()
{
SList *MyList = 0; // this list will hold 200 elements
SList *Tmp, *Position;

Position = MyList;

for (int i=0; i<200; i++)
{
Tmp = new(SList);
Tmp->back = Position;
Tmp->empty = true;
if (Position != 0) Position->forward = Tmp;
if (MyList == 0) MyList = Position; // the first element
Position = Tmp;
}
Position->forward = 0; // the last element

// now lets insert something here
Position = MyList;
while ( (Position->forward != 0) && (!Position->empty) )
{
Position = Position->forward;
}
Position->empty = false;
strcpy(Position->name,"Blahblah");

// now lets delete some item
Position = MyList;
while ( (Position != 0) && (strcmp(Position->name,"Searched string") != 0) )
{
Position = Position->forward;
}
if (Position != 0) // found
{
Position->empty = true;
Tmp = Position;
while (Tmp->forward != 0) // lets find the last element in the list
{
Tmp = Tmp->forward;
}
// lets throw out the searched items
if (Position->back != 0) Position->back->forward = Position->forward;
if (Position->forward != 0) Position->forward->back = Position->back;
Position->back = Tmp;
Tmp->forward = Position;
}

// finally, lets deallocate all that memory
while (MyList != 0)
{
Tmp = MyList;
MyList = MyList->forward;
delete Tmp;
}
return 0;
}


So now I hope you understand what exactly I want to do here ;)
Can this be done with STL list? Or can this whole process be simplified by using allocators or raw_storage_iterator?

Share this post


Link to post
Share on other sites
Im sorry, Im a bit tired right now.. but why do you need to do it that way with two pointers?
I guess I just don't really know why someone would choose a list over a vector. I mean, moving forward can esily be done:

indec++;
foo = vec[index];

In fact, if I really wanted to do something like this, Id w
rite a wrapper class that has something along the lines of:

template <class T>
class veclist
{
private:
int index;
std::vector<T> vec;
public:
void forward ()
{
index++;
}
void backward ()
{
index--;
}
T get ()
{
return vec[index];
}
// And so on...
};


Or perhaps store "next" and "previous" links in the vector (as an index or as iterators), maybe by doing something like:

struct blah
{
ObjectToStore o;
int nextindex; // could use iterators here
int previndex;
};
std::vector<blah> vec;
...



I dunno, like I said, Im tired. Im probably not thinking clearly so feel free to ignore or flame me.

Share this post


Link to post
Share on other sites
Well, the main problem with vectors is that if I throw out an element from it, then there's going to be a "hole" there, which will cause various problems. With lists I don't have holes, but instead when I throw out an element I place it at the back of the list. In vectors an element with the index 5 will remain with the index 5, while a list is more dynamic.

struct blah

{

ObjectToStore o;

int nextindex; // could use iterators here

int previndex;

};
Are you saying I could simulate a list using iterators? Okay, let's say I have a vector of five elements, and they _should_ be connected like this:
0 <-> 3 <-> 2 <-> 4 <-> 1
So when iterator->index == 0, then ++iterator->index == 3
Also, when iterator->index == 4, then --iterator->index == 2

Can this be done? How?

Share this post


Link to post
Share on other sites

This topic is 4686 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