Static Memory Pool Viability

  • (2 Pages)
  • +
  • 1
  • 2

19 Replies - 1365 Views - Last Post: 10 July 2013 - 08:38 AM Rate Topic: -----

#1 raspinudo  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 61
  • View blog
  • Posts: 232
  • Joined: 19-September 11

Static Memory Pool Viability

Posted 02 July 2013 - 09:43 AM

Hey All,

I began working on a static memory pool class for a game I'm currently
working on, and I have hit a bit of an interesting point. I'm finding that
constant calls to malloc are performing just as well as my pool. While
I'm sure I could optimize my design, I thought I should ask: is malloc()
so optimized now that memory pools aren't as useful? I will be moving this
game to mobile at some point, so malloc's may hurt a lot more there.

As for my current design, it is basically as follows.

There are raw memory handles which are simply a pointer and a boolean
to designate whether or not they are currently in use. The pool takes
in the size of the object upon which it will be based. I did this to simplify
the design, as it takes out the complexity of having to find the
right sized block. From there, it is basically a vector of these memory
handles which point to sections of the raw memory which is allocated with
malloc at initialization.

By my account, lookup for a free ptr should be O(n) where n is the length of the vector.
Free'ing a ptr should be O(1). By these, I feel it should be performing well, but
around 100,000 alloc's with some free's interspersed are talking roughly 12s.

If interested, here is the current source code:

Header
#ifndef MEMORY_H
#define MEMORY_H

#include <vector>
#include <deque>
#include <cstdlib>
#include <iostream>
using std::vector;

namespace MM 
{
    /*
     * A simple class which encapsulates a pointer
     * to raw memory (allocated with malloc()), along
     * with a boolean to signify its current usage state.
     */
    class RawMemHandle
	{
		public:
			RawMemHandle(unsigned char* rawMemPtr);
            ~RawMemHandle();
			unsigned char* getPtr();
			bool freeToUse();
			void setUsageState(bool parity);

            //disable copies
            RawMemHandle& operator=(const RawMemHandle&) = delete;
            RawMemHandle(const RawMemHandle&) = delete;

		private:
			unsigned char* m_rawMemHandle;
			bool m_freeToUse;
	};

    /*
     * A class which allocates a static memory pool
     * for a particular object type. Useful for items
     * such as ships which will be continually alloc'd
     * and dealloc'd throughout a level.
     */
	class StaticObjectPool
	{
		public:
			StaticObjectPool(size_t numBlocks, size_t blockSize);
			~StaticObjectPool();
			RawMemHandle* requestBlock();
			void freeBlock(RawMemHandle* memHandle);
            
            //disable costly operations(copy, assignment)
            StaticObjectPool& operator=(const StaticObjectPool&) = delete;
            StaticObjectPool(const StaticObjectPool&) = delete;

		private:
            vector<RawMemHandle*> m_memoryMap;
            size_t m_numBlocksFree;
			unsigned char* m_rawMemPtr;
	};
}

#endif //MEMORY_H




Implementation
#include "../include/memory.h"

using namespace MM;
using namespace std;

RawMemHandle::RawMemHandle(unsigned char* rawMemHandle)
{
	m_rawMemHandle = rawMemHandle;
	m_freeToUse = true;
}

RawMemHandle::~RawMemHandle()
{
	m_rawMemHandle = nullptr;
}

unsigned char* RawMemHandle::getPtr()
{
	m_freeToUse = false;
	return m_rawMemHandle;
}

void RawMemHandle::setUsageState(bool parity)
{
	m_freeToUse = parity;
}

bool RawMemHandle::freeToUse()
{
	return m_freeToUse;
}

StaticObjectPool::StaticObjectPool(size_t numBlocks, size_t blockSize)
{
	m_rawMemPtr = (unsigned char*) malloc(numBlocks*blockSize);
	m_numBlocksFree = numBlocks;
	
	for(size_t iter = 0; iter < numBlocks; iter++)
	{
		m_memoryMap.push_back(new RawMemHandle(m_rawMemPtr+(iter*blockSize)));	
	}

}

StaticObjectPool::~StaticObjectPool()
{
	for(const auto handle : m_memoryMap)
	{
		delete handle;	
	}	
	
	m_memoryMap.clear();
	free(m_rawMemPtr);
    m_rawMemPtr = nullptr;
}

RawMemHandle* StaticObjectPool::requestBlock()
{
	if(m_numBlocksFree > 0)
	{
		m_numBlocksFree--;
		for(const auto elt : m_memoryMap)
		{
			if(elt->freeToUse())
				return elt;
		} 
	}	
 
	return nullptr;
}

void StaticObjectPool::freeBlock(RawMemHandle* memHandle)
{
	memHandle->setUsageState(true);
	m_numBlocksFree++;
}




Really not sure why it isn't performing like I believe it should, any advice would
be appreciated.


EDIT: Probably should have placed this in general C++, if so, I apologize.

This post has been edited by raspinudo: 02 July 2013 - 09:47 AM


Is This A Good Question/Topic? 0
  • +

Replies To: Static Memory Pool Viability

#2 jimblumberg  Icon User is offline

  • member icon


Reputation: 4100
  • View blog
  • Posts: 12,695
  • Joined: 25-December 09

Re: Static Memory Pool Viability

Posted 02 July 2013 - 09:54 AM

Why are you using malloc in a C++ program?

Jim
Was This Post Helpful? 2
  • +
  • -

#3 raspinudo  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 61
  • View blog
  • Posts: 232
  • Joined: 19-September 11

Re: Static Memory Pool Viability

Posted 02 July 2013 - 09:57 AM

I guess I did it out of bad habits, I suppose I should replace the allocation as

m_rawMemPtr = new unsigned char[numBlocks*blockSize];


Was This Post Helpful? 0
  • +
  • -

#4 jimblumberg  Icon User is offline

  • member icon


Reputation: 4100
  • View blog
  • Posts: 12,695
  • Joined: 25-December 09

Re: Static Memory Pool Viability

Posted 02 July 2013 - 10:00 AM

Don't forget to delete instead of free as well.

Also how are you handling fragmentation?

Jim
Was This Post Helpful? 1
  • +
  • -

#5 raspinudo  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 61
  • View blog
  • Posts: 232
  • Joined: 19-September 11

Re: Static Memory Pool Viability

Posted 02 July 2013 - 10:05 AM

I haven't implemented anything for it yet, but I have some ideas. I suppose I could
to a sort of the vector every so often in this way:

before sort
--used--
--used--
--not--
--used--
--not--
--used--

after sort
--used--
--used--
--used--
--used--
--not--
--not--



Such that there are two main sections of the vector. I also replaced my free call with
delete. I guess old habits are the hardest to break.
Was This Post Helpful? 0
  • +
  • -

#6 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3590
  • View blog
  • Posts: 11,166
  • Joined: 05-May 12

Re: Static Memory Pool Viability

Posted 02 July 2013 - 10:25 AM

View Postraspinudo, on 02 July 2013 - 12:43 PM, said:

I'm finding that constant calls to malloc are performing just as well as my pool. While
I'm sure I could optimize my design, I thought I should ask: is malloc()
so optimized now that memory pools aren't as useful? I will be moving this
game to mobile at some point, so malloc's may hurt a lot more there.


It depends on the runtime library.

If you look at Game Programming Gems, a game company has implemented their own memory pool because the runtime for their target system was too slow. In the process they managed to get some optimizations because: they know the size of the objects they will be allocating; and they know their allocation/deallocation patterns.

In general though, modern runtime libaries have taken a lot of what was learned back in the 80's when it was the vogue to write your own memory allocator, and implement the various optimizations directly into the runtime library. Part of the reason for this being implemented by the compiler companies was that there was a war on who had the most efficient memory allocator. In the end, we all won due to that constant market pressure.
Was This Post Helpful? 1
  • +
  • -

#7 raspinudo  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 61
  • View blog
  • Posts: 232
  • Joined: 19-September 11

Re: Static Memory Pool Viability

Posted 02 July 2013 - 10:49 AM

View PostSkydiver, on 02 July 2013 - 10:25 AM, said:

View Postraspinudo, on 02 July 2013 - 12:43 PM, said:

I'm finding that constant calls to malloc are performing just as well as my pool. While
I'm sure I could optimize my design, I thought I should ask: is malloc()
so optimized now that memory pools aren't as useful? I will be moving this
game to mobile at some point, so malloc's may hurt a lot more there.


It depends on the runtime library.

If you look at Game Programming Gems, a game company has implemented their own memory pool because the runtime for their target system was too slow. In the process they managed to get some optimizations because: they know the size of the objects they will be allocating; and they know their allocation/deallocation patterns.

In general though, modern runtime libaries have taken a lot of what was learned back in the 80's when it was the vogue to write your own memory allocator, and implement the various optimizations directly into the runtime library. Part of the reason for this being implemented by the compiler companies was that there was a war on who had the most efficient memory allocator. In the end, we all won due to that constant market pressure.


That is good to hear. It is surprising that many articles discussing custom memory pools are
so recent. I suppose the more limited architectures, like ps3 and other embedded systems, lend
themselves to such an implementation than on a modern desktop. Since I am planning this game
for mobile, would it still be worth my time to improve my implementation(first by accounting
for fragmentation) given the lesser capability of the hardware target?

This post has been edited by raspinudo: 02 July 2013 - 10:50 AM

Was This Post Helpful? 0
  • +
  • -

#8 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5848
  • View blog
  • Posts: 12,707
  • Joined: 16-October 07

Re: Static Memory Pool Viability

Posted 02 July 2013 - 01:15 PM

You can't sort anything. Once you give out memory, you're guaranteed it is available.


The RawMemHandle is confusing to me. Try to envision how you'd use your StaticObjectPool.

I'd start with something like:
class StaticObjectPool {
public:
	StaticObjectPool(size_t numBlocks, size_t blockSize = 64);
	~StaticObjectPool();
	void *request(size_t);
	void free(void *);
private:
	size_t numBlocks, blockSize;
	struct Block {
		size_t sizeInBlocks;
		bool used;
		Block() : sizeInBlocks(0), used(false) { }
		Block(size_t sz, bool u) : sizeInBlocks(sz), used(u) { }
	};
	unsigned char *storage;
	std::map<void *, Block> blocks;
	//disable costly operations(copy, assignment)
	StaticObjectPool& operator=(const StaticObjectPool&) {}
	StaticObjectPool(const StaticObjectPool&) {}
};


Was This Post Helpful? 0
  • +
  • -

#9 raspinudo  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 61
  • View blog
  • Posts: 232
  • Joined: 19-September 11

Re: Static Memory Pool Viability

Posted 02 July 2013 - 02:49 PM

I think it would work. If I have a vector of RawMemHandles, I can sort them by which ones
are currently being used, but they will still point to the same memory location.

Something like this:

Posted Image

General use case would be something along these lines:

Also, sorry, I should've mentioned that my code has been working(seemingly, definitely need to test more),
I am just trying to figure out the performance problems. Here is an example of said performance:

void MemoryTest::test10000()
{
    for(int i = 0; i < 100000; i++)
    {
        //100k allocs
        DummyObject* dmo =
            (DummyObject*) objectPool.requestBlock()->getPtr();

        dmo3->a = i;

        //some interspersed deallocs
        if(i%3 == 0)
            objectPool.freeBlock((RawMemHandle*) dmo);
    }
}

$ time ./bin/osx_main   
./bin/osx_main  4.97s 

$ time ./bin/gnu_main
./bin/gnu_main 13.13s 



One last edit, here is a more indicative general use case

#include "../include/memorytest.h"

#include <iostream>
using namespace std;

int main()
{
    StaticObjectPool so(4, sizeof(int));
    int* a = (int*) so.requestBlock()->getPtr();
    int* b = (int*) so.requestBlock()->getPtr();
    int* c = (int*) so.requestBlock()->getPtr();
    int* d = (int*) so.requestBlock()->getPtr();

    if(so.blocksAvailable())
        int* e = (int*) so.requestBlock()->getPtr();
    else
        cout << "NO MORE MONEY LEFT SCROOGE" << endl;

}




Update: before I go study for my final tomorrow, I thought I'd play around with a quick
function for sorting the vector. It was another excuse to try out lambas again!

void StaticObjectPool::defragmentSort()
{
	auto comp = [] (RawMemHandle* ra, RawMemHandle* rb) ->bool { return ra->freeToUse() ;}; 
	sort(m_memoryMap.begin(), m_memoryMap.end(), comp);		
}
~



They really are very handy for use as comparators.

I will note that, I'm not entirely certain as to whether this function will be incredibly helpful.
Due to the random nature of allocs and deallocs, I would assume that the vector would be pretty
interspersed with free spots on average, but I suppose it will be good to have it around to perform
a cleaning every so often to increase access times.

This post has been edited by raspinudo: 02 July 2013 - 06:16 PM

Was This Post Helpful? 0
  • +
  • -

#10 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5848
  • View blog
  • Posts: 12,707
  • Joined: 16-October 07

Re: Static Memory Pool Viability

Posted 03 July 2013 - 05:28 AM

View Postraspinudo, on 02 July 2013 - 05:49 PM, said:

I can sort them by which ones are currently being used, but they will still point to the same memory location.


Sure. Why? ( Nice graphic, btw. )

Interesting. That makes it easier; actually want to lock down type.

Perhaps:
template<typename T>
class StaticObjectPool {
public:
	StaticObjectPool(size_t size);
	~StaticObjectPool();
	T *request();
	bool free(T *);
private:
	size_t size;
	T *storage;
	std::vector<T *> memTaken, memFree;
	//disable costly operations(copy, assignment)
	StaticObjectPool& operator=(const StaticObjectPool&) {}
	StaticObjectPool(const StaticObjectPool&) {}
};

#define test(x) x = so.request(); if (x==NULL) { std::cout << "Failed at " << #x << "\n"; } else { std::cout << "Allocated " << #x << "\n"; }

int main() {
	StaticObjectPool<int> so(4);
	int *a, *b, *c, *d, *e, *f, *g;
	test(a); test(B)/>/>; test(c); test(d); test(e); test(f);
	so.free(a);
	test(g);
	return 0;
}



Alternately, sans STL:
template<typename T>
class StaticObjectPool {
public:
	StaticObjectPool(size_t size);
	~StaticObjectPool() { }
	T *request();
	bool free(T *);
private:
	size_t size;
	struct Block {
		T item;
		bool used;
	};
	Block *blocks;
	StaticObjectPool& operator=(const StaticObjectPool&) {}
	StaticObjectPool(const StaticObjectPool&) {}
};



Though, honestly, it all seems overkill. Just a std::vector<T> would be fine.

This post has been edited by baavgai: 03 July 2013 - 05:29 AM

Was This Post Helpful? 1
  • +
  • -

#11 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3590
  • View blog
  • Posts: 11,166
  • Joined: 05-May 12

Re: Static Memory Pool Viability

Posted 03 July 2013 - 05:52 AM

Yes, you can sort the handles, but that still doesn't fix your fragmentation of allocated blocks.

Or did you mean for the handles to stay stable, and the blocks of memory they point to be move around. If that's the case, then you are setting up a memory handle system just like described in Game Programming Gems Book x. My books are packed away right now so I can't tell you which book exactly, but it's in one of the the "General Programming" sections of one of the books in series.
Was This Post Helpful? 0
  • +
  • -

#12 raspinudo  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 61
  • View blog
  • Posts: 232
  • Joined: 19-September 11

Re: Static Memory Pool Viability

Posted 03 July 2013 - 06:06 AM

View Postbaavgai, on 03 July 2013 - 05:28 AM, said:

View Postraspinudo, on 02 July 2013 - 05:49 PM, said:

I can sort them by which ones are currently being used, but they will still point to the same memory location.


Sure. Why? ( Nice graphic, btw. )

Interesting. That makes it easier; actually want to lock down type.

Perhaps:
template<typename T>
class StaticObjectPool {
public:
	StaticObjectPool(size_t size);
	~StaticObjectPool();
	T *request();
	bool free(T *);
private:
	size_t size;
	T *storage;
	std::vector<T *> memTaken, memFree;
	//disable costly operations(copy, assignment)
	StaticObjectPool& operator=(const StaticObjectPool&) {}
	StaticObjectPool(const StaticObjectPool&) {}
};

#define test(x) x = so.request(); if (x==NULL) { std::cout << "Failed at " << #x << "\n"; } else { std::cout << "Allocated " << #x << "\n"; }

int main() {
	StaticObjectPool<int> so(4);
	int *a, *b, *c, *d, *e, *f, *g;
	test(a); test(B)/>/>/>; test(c); test(d); test(e); test(f);
	so.free(a);
	test(g);
	return 0;
}



Alternately, sans STL:
template<typename T>
class StaticObjectPool {
public:
	StaticObjectPool(size_t size);
	~StaticObjectPool() { }
	T *request();
	bool free(T *);
private:
	size_t size;
	struct Block {
		T item;
		bool used;
	};
	Block *blocks;
	StaticObjectPool& operator=(const StaticObjectPool&) {}
	StaticObjectPool(const StaticObjectPool&) {}
};



Though, honestly, it all seems overkill. Just a std::vector<T> would be fine.


I agree; I believe my initial over complication was due to the way I was helping myself
conceptualize the problem. I will attempt to simplify my code later today.

View PostSkydiver, on 03 July 2013 - 05:52 AM, said:

Yes, you can sort the handles, but that still doesn't fix your fragmentation of allocated blocks.

Or did you mean for the handles to stay stable, and the blocks of memory they point to be move around. If that's the case, then you are setting up a memory handle system just like described in Game Programming Gems Book x. My books are packed away right now so I can't tell you which book exactly, but it's in one of the the "General Programming" sections of one of the books in series.


Since all of the objects in the pool are of the same size, will fragmentation occur? Perhaps
I am misunderstanding, but I dont there will ever be a case of an " unusable piece".
Was This Post Helpful? 0
  • +
  • -

#13 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3590
  • View blog
  • Posts: 11,166
  • Joined: 05-May 12

Re: Static Memory Pool Viability

Posted 03 July 2013 - 07:03 AM

Yes, you are right. If they are all the same sized blocks then there shouldn't be any fragmentation.

But then what's the point of compacting the handles other than perhaps getting better locality of reference while trying to find the next free handle. If you were using a "linked list" like system where each free handle pointed to the next free handle, even after you compact, you would still need to retain that linked list for the cases when you don't have time to compact this. I find it adding too much complexity if you have two "modes" on accessing free handles like an array if recently compacted and nothing has been freed, and then accessing like a linked list once something has been freed. It maybe simpler to just scan through the handles looking for unused handles.
Was This Post Helpful? 0
  • +
  • -

#14 raspinudo  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 61
  • View blog
  • Posts: 232
  • Joined: 19-September 11

Re: Static Memory Pool Viability

Posted 03 July 2013 - 01:36 PM

View PostSkydiver, on 03 July 2013 - 07:03 AM, said:

Yes, you are right. If they are all the same sized blocks then there shouldn't be any fragmentation.

But then what's the point of compacting the handles other than perhaps getting better locality of reference while trying to find the next free handle. If you were using a "linked list" like system where each free handle pointed to the next free handle, even after you compact, you would still need to retain that linked list for the cases when you don't have time to compact this. I find it adding too much complexity if you have two "modes" on accessing free handles like an array if recently compacted and nothing has been freed, and then accessing like a linked list once something has been freed. It maybe simpler to just scan through the handles looking for unused handles.


I agree completely. I finally had time to test it after my final this morning and the sorting
actually hindered performance which confirms my initial thought that the sparsity of the
data structure will provide good enough look up time, probably something along the lines of
O(sqrt(n)) if I had to guess. I will be working on a simplified approach later today,
then I will post the results/performance marks to further the discussion.

This post has been edited by raspinudo: 03 July 2013 - 01:47 PM

Was This Post Helpful? 0
  • +
  • -

#15 raspinudo  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 61
  • View blog
  • Posts: 232
  • Joined: 19-September 11

Re: Static Memory Pool Viability

Posted 03 July 2013 - 06:54 PM

Quote

Though, honestly, it all seems overkill. Just a std::vector<T> would be fine.


In most cases I'd agree, but the more I read the apple developer docs pertaining to
iOS, it really seems to recommend one time allocation for good performance across its
platforms.

I'm currently at a decent point with the code. I won't say I'm happy with the cleanliness
of the usage. As is, I am returning a RawMemHandle* from alloc(). This is because, when
calling free, you need to pass a RawMemHandle so that the function can set the handles
boolean member to true so that the pointer is up for use again. I'm gonna contemplate some
ways to clean this up tonight, any suggestions are welcome. Also, let me take this opportunity
to thank you all for your input thus far, it is greatly appreciated.

#ifndef MEMORY_H
#define MEMORY_H

#include <vector>
using namespace std;

namespace MM 
{
    /*
     * A simple struct which encapsulates a pointer
     * to raw memory (allocated with malloc()), along
     * with a boolean to signify its current usage state.
     */
    struct RawMemHandle
	{
	    RawMemHandle(unsigned char* rawMemPtr)
        :
            m_rawMemPtr(rawMemPtr),
            m_freeToUse(true)
        {}

        unsigned char* m_rawMemPtr;
        bool m_freeToUse;
	};

    /*
     * A class which allocates a static memory pool
     * for a particular object type. Useful for items
     * such as ships which will be continually alloc'd
     * and dealloc'd throughout a level.
     */
    template <typename T>
	class StaticObjectPool
	{
		public:
			StaticObjectPool(size_t numBlocks)
            {
                m_rawMemPtr = new unsigned char [numBlocks*sizeof(T)];
                m_numBlocksFree = numBlocks;
	
	            for(size_t iter = 0; iter < numBlocks; iter++)
	            {
		            m_memoryMap.push_back(new RawMemHandle(m_rawMemPtr+(iter*sizeof(T))));	
	            }
            }

			~StaticObjectPool()
            {
                for(const auto handle : m_memoryMap)
	                delete handle;	
	
                m_memoryMap.clear();
	            delete[] m_rawMemPtr;
                m_rawMemPtr = nullptr;
            }

			RawMemHandle* alloc()
            {
                if(m_numBlocksFree > 0)
                {
		            m_numBlocksFree--;
		            for(const auto elt : m_memoryMap)
		            {
			            if(elt->m_freeToUse)
			            {	
				            elt->m_freeToUse = false;
				            return elt;
			            }
		            } 
	            }   	
 
	            return nullptr;
            }

			void free(RawMemHandle* memHandle)
            {
                memHandle->m_freeToUse = true;
                m_numBlocksFree++;
            }

			bool blocksAvailable()
            {
                return m_numBlocksFree > 0;
            }
						             
            //disable costly operations(copy, assignment)
            StaticObjectPool& operator=(const StaticObjectPool&) = delete;
            StaticObjectPool(const StaticObjectPool&) = delete;

		private:
            vector<RawMemHandle*> m_memoryMap;
			unsigned char* m_rawMemPtr;
	        size_t m_numBlocksFree;
    };
}
#endif //MEMORY_H


Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2