Sign in to follow this  
Structural

Memory management

Recommended Posts

I finished my memory management prototype last night, but I'm worried that my whole strategy is not efficient. I will illustrate what my idea was. I use one big piece of memory like this: [ ........................lots of MB............................ ] Every piece of memory has a header, which looks as follows:
struct MemBlock
{
	void* loPtr;	/**< Low pointer of the available memory without header */
	void* hiPtr;	/**< High pointer of available memory */
	MemBlock* next, *prev;	/**< Links of the list */
	unsigned int size;	/**< Size of the memory (without header */
	char taken;	/**< Marks if block is ready to be used */
};
Every block of memory that is taken receives this header. It is in essence a double linked list. A block looks as follows: [ HEADER | ..... memory to be used by application .... ] After a few allocs the big memory block looks as follows: [hhh| ...... ][hhh| ..........][hhh| ... ] etc etc where "hhh" is a header I have my doubts about this whole idea of using headers. Every header is 28 bytes. With a bit of bad luck and many small objects I have more header data than actual usable data. On the other hand, this is fast. This is all pointer work. No new objects that need to be pushed down a list, no ordening of lists. Looping through the whole list is fast too. What are your opinions about this? Would it be better to adapt to a seperate list for header information? Here's the current source code. I have tested it with the basic functionality to see if allocating and freeing works. It seems to, but a real thorough test still remains to be done.
#ifndef MEMORYMANAGER_H
#define MEMORYMANAGER_H

#include <vector>
using std::vector;
#include <assert.h>
#include <stdio.h>

#define MEM_ALLOC_SIZE 1024*1024*100	// megabytes
/*
comment these defines to disable functionality
*/
//#define MEM_TRACK_ALLOCS 1	/**< Keeps track of allocations */
//#define MEM_REG_ALLOCS 1	/**< Registers all allocations to file */
#define MEM_CHECK_BOUNDS	/**< Check the bounds of a block */
/*
END
  comment these defines to disable functionality
*/


#define MEM_BOUNDS_SIZE 8
#define MEM_BOUNDS_VALUE 0xDEADBEEF
#define MEM_FNAME_SIZE 256



struct MemBlock
{
#if defined MEM_TRACK_ALLOCS | MEM_REG_ALLOCS	// guard with defines to save memory
	char file[MEM_FNAME_SIZE];
	int line;
#endif
	void* loPtr;	/**< */
	void* hiPtr;	/**< */
	MemBlock* next, *prev;
	unsigned int size;	/**< */
	char taken;
};

struct MemLog
{
	
};

class MemoryManager
{
public:
	MemoryManager()
	{

		
	}

	~MemoryManager()
	{
		
	}

	static void init()
	{
		heap = (char*)malloc(MEM_ALLOC_SIZE);
		if (heap == NULL)
		{
			assert( "COULD NOT ALLOCATE MEMORY" && false );
		}

		MemBlock* b = (MemBlock*)heap;	// move to first...
		memset(heap,0x00,sizeof(MemBlock));
		b->loPtr = (void*)&heap[sizeof(MemBlock)];
		b->hiPtr = (void*)&heap[MEM_ALLOC_SIZE - 1 - sizeof(MemBlock)];
		b->size = MEM_ALLOC_SIZE - sizeof(MemBlock);
		b->next = 0;
		b->prev = 0;
		b->taken = 0;
	}

	static void clean()
	{
		if (heap)
			free(heap);
	}

	static void* MMmalloc(int size)
	{
		MemBlock* b = (MemBlock*)heap;
		MemBlock* n;

		while (b)
		{
			if (b->taken == 0 && (b->size - sizeof(MemBlock)) > size)
				/*
				This is tricky thinking. If a new block should fit in this free block, then a new header should be added
				The size of the header should be deducted from the total available size.
				*/
			{
				n = (MemBlock*)&((char*)b->loPtr)[size];	// move the n-pointer (n stands for new) to the end of the block

				// [b]<->[b->next]
				// [b]<->[n]<->[b->next]
				n->prev = b;		
				n->next = b->next;
				b->next = n;
				if (n->next)
					n->next->prev = n;

				// [bbb|b.lo ...................... b.hi]
				// [bbb|b.lo ... b.hi][nnn|n.lo ... n.hi]
				n->loPtr = &((char*)n)[sizeof(MemBlock)];
				n->hiPtr = b->hiPtr;
				b->hiPtr = &((char*)b->loPtr)[size-1];

				n->size = b->size - size - sizeof(MemBlock);
				b->size = size;

				n->taken = 0;
				b->taken = 1;

				return b->loPtr;
				
			}
			else if (b->taken == 0 && b->size >= size)
			/*
			The block would not fit, but perhaps this is because the size of the header was just atad too much.
			Well, instead we just keep the header and put the data in this block.
			*/
			{
				b->taken = 1;
				return b->loPtr;
			}

			b = b->next;
		}

		return NULL;
	}


	static void* MMmalloc(int size, char* file, int line)
	{
		return MMmalloc(size);
	}



	static void MMfree(void* address)
	{
		MemBlock* b = (MemBlock*)heap;
		int returnFlag = 0;

		while (b)
		{
			if (address == b->loPtr)
			{
				b->taken = 0;

				//[aaa| ... ][xxx| ...... ][bbb| ... ][yyy| ......]
				//[aaa| ... ][xxx| ................. ][yyy| ......]
				if (b->prev != NULL)
				{
					if (b->prev->taken == 0)	// only xxx is free
					{
						b->prev->next = b->next;
						b->prev->hiPtr = b->hiPtr;
						if (b->next)
							b->next->prev = b->prev;
						b->prev->size += b->size + sizeof(MemBlock);

						b=b->prev;	// Adjustment: if the following statement is true, then b should point to the new header, not the old one.

						returnFlag = 1;
					}
				}

				//[xxx| ...... ][bbb| ... ][yyy| ......][zzz| ...... ]
				//[xxx| ...... ][bbb| ................ ][zzz| ...... ]
				if (b->next != NULL)
				{
					if (b->next->taken == 0)	// only yyy is free
					{
						b->size += b->next->size + sizeof(MemBlock);
						b->hiPtr = b->next->hiPtr;
						b->next = b->next->next;
						if (b->next)
							b->next->prev = b;
						

						returnFlag = 1;
					}
				}

				if (returnFlag)
					return;
			}
			
			b = b->next;
		}
	}

	static void writeMap(char* filename)
	{
		FILE* file;
		char line [ 256 ];
		int i;
		int linesize;
		int maxlinesize = 100;

		if (!filename)
			return;

		file = fopen(filename, "w");

		if (!file)
			return;

		MemBlock* b = (MemBlock*)heap;

		sprintf(line, "MEMORY MAP\n---------------------\nSize: %i bytes (%x hex)\nHeader Size: %i (%x hex)\n---------------------\n",MEM_ALLOC_SIZE, MEM_ALLOC_SIZE, sizeof(MemBlock), sizeof(MemBlock));
		fputs(line, file);

		i=0;
		while (b)
		{
			sprintf(line, "[ %i (%i) | %x ... (size %i b) %x ]\n", i, b->taken, b->loPtr, b->size, b->hiPtr);
			b = b->next;
			i++;

			fputs(line, file);
		}
	}

private:
	static char* heap;
//	static vector<MemBlock*> freeBlocks;
//	static vector<MemBlock*> takenBlocks;
//	static vector<MemBlock> blocks;
//	static vector<MemBlock> dead;

//	static vector<MemLog> log;

//	static int opCount;
//	static int missCount;
//	static int algoCount;
};



inline void* __cdecl operator new(size_t nSize, char* lpszFileName, int nLine) 
{ 
	return MemoryManager::MMmalloc(nSize, lpszFileName, nLine); 
}

inline void __cdecl operator delete(void* mem) 
{ 
	MemoryManager::MMfree(mem);
}




#define new _MEM_DEBUG_NEW_ 
#define delete _MEM_DEBUG_DELETE_

#ifndef __FILE__
#define __FILE__ "No __FILE__ define known"
#endif

#ifndef __LINE__
#define __LINE__ -1
#endif

#define _MEM_DEBUG_NEW_ new(__FILE__,__LINE__)
#define _MEM_DEBUG_DELETE_ delete

#if defined MEM_TRACK_ALLOCS || MEM_REG_ALLOCS	// Only give filename and line if debugging
	#define malloc(size) MemoryManager::MMmalloc(size, __FILE__, __LINE__); 
#else
	#define malloc(size) MemoryManager::MMmalloc(size); 
#endif

#define free(addr) MemoryManager::MMfree(addr)






#endif

Share this post


Link to post
Share on other sites
Most (not all) successful allocators use different strategies for large and small blocks. In particular, small blocks are perfect for fixed-size pools, where (say) all the 4-byte objects are stored in one block, with no need to encode size information. Alexandrescu's Modern C++ Design has a good example of this.

Share this post


Link to post
Share on other sites
Thank you for your tip. I don't have the book, but I'll try to get a hold of it.
I have applied another form of allocation as you suggested.
If the size is under the value x, then it allocates a piece of memory in a "page" of a fixed size. This page is also an item in the linked list and contains many smaller blocks of which the size is unknown. This seems much faster than the linked list solution.
[ppp| 111 | 222 | 33 | 4444 | 5 etc etc ... ]

It allocates the little pieces sequentially and it uses a pointer to the first unused address. So you can keep filling it until reach the end of the page. But when releasing you can not re-use the page untill all pieces are released (reference counter here). This is a disadvantage and it wastes memory.

I did a timing test:
-------------------------------------------------
Method:
- Release mode, VC6.0
- Sequential allocation of 5000 blocks varying from 1 to 250 bytes
- sequential deallocation of these 5000 blocks

Results:
* standard malloc/free: 4 ms
* memory manager with linked list: 700 ms
* memory manager page allocating: 2 ms
* memory manager combo 1: 100 ms
- sequential allocation below 128 bytes (page of 10KB)
- linked list above 128 bytes

Linked list method is far too slow. This method goes through the list and finds the first free block that fits the requested size. Because this block is always at the end in a sequential allocation the loop is always of the maximum size. A reveerse loop would speed this up.
-------------------------------------------------
Method:
- Sequential allocation of 20000 blocks varying from 1 to 250 bytes
- sequential deallocation of these 20000 blocks

Results:
* standard malloc/free: 20 ms
* memory manager page allocating, page size 100kb: 4 ms

Great advantage over standard methods.
-------------------------------------------------
Method:
- Sequential allocation of 100000 blocks varying from 1 to 250 bytes
- sequential deallocation of these 100000 blocks

Results:
* standard malloc/free: 100 ms
* memory manager page allocating, page size 100kb: 100 ms

The linked list method kicks in. 123 pages are used to allocate these 100000 smaller pieces. A page is another entry in the linked list.
-------------------------------------------------


I'm beginning to doubt about this sort memory management thing. Obviously the linked list is not effective, but with 5000 items to loop through in the end this is not surprising. Some quick indexing is required but I have no idea how to do this.
The page method in the manager is quite a bit faster so it seems, but it wastes memory. If an x amount of memory is released within a page it can not be re-used untill all memory in the page is released.


I made this manager to see what the gain was in pre-allocation of memory.
Obviously there is a speed gain if you can very quickly retrieve a piece of memory (see last two tests), but if you want to fill your memory efficiently you get overhead that makes things very slow. Unless you use some more advanced algorithms.
I think I'll stick to runtime allocation. The memory manager might be able to speed things up in a few situations, but making it always work requires more effort than it's really worth.

Share this post


Link to post
Share on other sites
The problem is, when you going into something specific, some general solution won't stand up long against an optimized one that was made for it. So, if you are going to allocate different sized memory blocks, why not use different memory managers that deal with them? I'll be giving a brief tutorial soon on this kind of thing, so stay tuned and good luck.

Share this post


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

struct MemBlock
{
void* loPtr; /**< Low pointer of the available memory without header */
void* hiPtr; /**< High pointer of available memory */
MemBlock* next, *prev; /**< Links of the list */
unsigned int size; /**< Size of the memory (without header */
char taken; /**< Marks if block is ready to be used */
};


You can decrease the size of the header by removing these unnecessary items:

loPtr -- Since you know the size of the header, you don't need a pointer to the start of the block.
hiPtr -- Since you store the size of the allocated block you don't need a pointer to the end of the block.
prev -- Use a singly-linked list and live with any speed penalty.
taken -- Use a separate list for free blocks.

New and improved. Only 8 bytes:
struct MemBlock
{
MemBlock* next; /**< Links of the list */
unsigned int size; /**< Size of the memory (without header */
};

Share this post


Link to post
Share on other sites
http://www.cs.umass.edu/~emery/heaplayers.html

Heaplayers has quite a few different implementations of memory managers. You might find what you need. It is also very handy to understand what is needed in a MM. Its by the same guy that made reaps.

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