Sign in to follow this  
OleKaiwalker

Memory Management

Recommended Posts

Hey, What would be the smarter thing to do, when designing a memory manager for a game (or just a framework)? 1) Allocate a big chunk and then do some tag boundary allocations. Fx every block has a header, saying whether it's free or not, it's size and maybe a pointer to next block. This design can eventually be expanded to a free list or something like that (to speed up the allocation procedure). On of the great advantages with this design will be the low internal fragmentation, due to the coalescence process. But that process do also cause a more time comsuming freeing process - something I don't think a game will appreciate? 2) It can also be done with a design, where numerous pools are allocated in the beginning, each containong blocks of a specific size. Fx one pool with 2 bytes sized blocks and another with 4 bytes sized blocks. When an allocation is called, the first block in the free list, that containes the requested size, is taken (simply removed from the free list). When it has to be deallocated agian, the block does simply get inserted as the first element in the right free list again. This design will perform fast and safe, but may result in some heavy internal fragmentation. What design would you use? Do you have a better one?

Share this post


Link to post
Share on other sites
To pick the right one, you'd have to how the program you use it for is going to behave. If it will be allocating zillions of little blocks the second one is preferable, if it is allocating rather big chunks of different sizes the first one works better. What I am currently doing for my own project is keep a bunch of 'pools' (as in your second approach) for small blocks (8, 12 and 16 bytes), and just call the standard operator new when asked for bigger chunks.

Share this post


Link to post
Share on other sites
Go with number 1. If you really have an algorithm somewhere in your game that needs fast memory allocation and deallocation you'd write a fixed size pool allocator anyway.
I wrote a memoy manager which doesn't use boundary tags but it allocates a bunch of "boundary tags" at its initialization, this limits your application to a fixed size of free and used blocks but it improves locality for the allocation and deallocation algorithms alot.

Share this post


Link to post
Share on other sites
I use a hybrid aproach. I create multiple pools on startup (using Doug Lea's malloc) to keep "alike" allocations together (ex. textures are allocated from the same pool, sounds, etc). Each pool then returns the requested amount of memory from its "chunk" and updates its internal state for every allocation. All allocations are aligned, and the way memory is "freed" dramatically reduces fragmentation. When memory is allocated a header stating the block's size and pool it came from is added just before the actual memory. When it is freed, the block is added to the top of a list and a pointer to the previous block replaces the pool variable in the header. The pool itself will use these freed blocks first, joining and splitting free blocks as necessary.

Personally, I think this is the best allocator I have programmed to date. I cant wait until I get my program up and running so I can spend more time tweaking it and testing the fragmentation numbers after a few days of continous allocations.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
I also wrote my memory manager pretty similar to what the previous poster wrote.
Allocating big blocks/pools of memory. And once an allocation is done by the user, it will just return a piece of memory inside those blocks instead of doing an actualy malloc.
Each allocation has a header in front of it and the memory address returned can be aligned by a value specified by the user that does the allocation.
Also it is possible to group specific allocation types together. For example I group all strings together in the same pools. This makes it more efficient, otherwise you can end up having big blocks that are empty after some temparory memory was allocated etc.

I made a macro that works like this:


class Vertex
{
DECLARE_MEMORYOBJECT(Vertex, 16, MEMCATEGORY_MESHDATA)
//.....
};


This will automatically create the operators new and delete. So when you do "new Vertex" it will automatically be managed by the memory manager.

Deleting memory is pretty fast. However allocating isn't so fast as the standard malloc. This is because I store no free list. What I do is search for free places inside the blocks and find the best fitting memory hole to minimize fragmentation. This is speed up by introducing cached searches. It is very likely that there is still a free piece of memory in the last block where an allocation has been made in. This gives a very big speedup in allocation. Also I cache some other stuff.

Re-allocating data, like realloc is done by trying to simply change the header of the given allocation so that it registers more memory. This doesn't involve any allocation or so. So it will most likely return the same memory location as it already had initially. Unless the resizing of the allocation won't fit, in that case it will delete the allocation and allocate it again in another block. Also it pre-allocates some extra data for dynamic data, to speedup incremental resizing for things such as dynamic arrays.

Allocations that are above a given size will get their own private memory blocks so will basically be done with a traditional malloc, but allow alignment etc.

I can generate per category statistics and global memory statistics. This is very useful to see how much memory your mesh data actualy uses for example.
Also it can report things such as memory overhead due to alignment, block overhead per allocation, etc.

Last but not least it automatically shows all possible memory leaks when you shutdown your application, and it will clean up those allocations afterwards, so that at least all memory has been released again.

When you get a huge number of allocations, the allocation process can become quite slow though compared to using just a malloc. This is some area that I still need to improve.

Cheers,
- John / http://www.emotionfx.com

Share this post


Link to post
Share on other sites
I simply override the global new and delete operators to make integration with the memory manager transparent to the application. This also lets me compare the memory manager speed up by simply commenting out the overides and testing.

BTW, searching for the best fit is not a good way to prevent long term fragmentation. Your allocations will gradually become more spread out using that method because you are searching for a best fit and using that address as the starting point for the next search. And so on and so on.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
No, I'm not using that address as a starting point for the next allocation. This way I minimize the amount of small memory holes, so that bigger allocations will have less chance to not fit inside the smaller holes. This reduces the memory fragmentation more as opposed to just using the first fit.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Also, overriding global new and delete might cause problems when different libraries being used all do this.
But there are also some advantages of it of course. But in my library I only want to count the memory used by the library, and if the user allocates custom objects, it shouldn't add those to the memory statistics of the library.

Share this post


Link to post
Share on other sites
Most big games (especially on consoles where memory management is a critical part of the code) use several memory allocation schemes. Each scheme is tailored to solve a particular problem, and deciding which allocator to use depends on how the memory is going to be used.

Rather than re-inventing the wheel, look up how the various existing memory allocation schemes work. Chances are somebody has already implemented something like what you are considering and figured out all the advantages and disadvantages.

[Edited by - JohnBolton on July 7, 2004 5:14:36 PM]

Share this post


Link to post
Share on other sites
I totally agree with JohnBolton. There is no allocator that will match each problem field well. Different memory needs and usage patterns require different allocation schemes if you want optimal memory management. Implementing various types of allocator systems will make the project a bit more complex, but will payout better performance wise. Also as was mentioned before there are some pretty robust allocators out there you might want to look at. Charles Bloom for example has some niffty allocation schemes implemented inside Galaxy3 . You also must take into consideration caching when designing/implementing allocators/memory managers.

Also on hybrid approaches. One thing I learnt about hybrid approaches from personal experience is that they tend to get over-engineered, and usually add no performance gain or even can become the bottleneck. A few robust allocation schemes applied at the right places will give you an edge over hybrid generalized solutions (plus note they are much easier to implement robustly).

Share this post


Link to post
Share on other sites
I've never coded a memory management system of my own. Is such a thing really necessary for most applications that run for an extended amount of time, or is this only advisable for games ad other apps that do a lot of new/deletes? And does the builtin OS-memory management suck so bad it can't be trusted with this task at all?

Share this post


Link to post
Share on other sites
No,
I did this mostly for the purpose of selfeducation and to see if my allocator would be more efficient. I also like the ability to easily retrieve memory allocation statistics and to catch memory leaks and other memory related errors.

Share this post


Link to post
Share on other sites
Memory intensive programs will eventually run out of memory or suffer performance issues using the normal new and delete functions. Writing custom managers will allow the application to system memory more efficiently so that the program can run faster longer.

Share this post


Link to post
Share on other sites
90% of the time, on a computer with paged virtual memory (such as your PC), the standard memory manager is all you need.

Before you decide to implement your own memory manager, you should make sure that memory management is really a bottleneck, and that your memory manager will perform better than the standard, and that it doesn't create more problems than it solves.

Share this post


Link to post
Share on other sites
I trying to make my mm with design #1, but I ran into some complications. To insure that my mm isn't fixed-size, I want to make it possible for the mm to create an extra heap, when no fitting free blocks are found. But when 2 or more heaps are inserted, it becomes complicated to find the one, in which deallocated should inserted.

One solution is to do a linear search through every heap, and eventually the right memory location will come up.

That is of course a very stupid and time consuming way of doing it.

Another solution could be to see which heap, that contains the address, and therefor can all the other time consuming calculations be left out, simply be seach every heap, intill a heap matches this statment.

if (heap->addr <= block && block > (heap->addr + heap->nBlocks))

Now my question is... Is there a better way? Some other way to manages the heaps?

And last, can the previous statment be optimized some way?

Share this post


Link to post
Share on other sites
Right, I've just been reading Stroustrup on allocators, and if I'm getting what he wrote correctly, then allocators basically are ... hmm ... memory management systems kind of, is that correct? So if one wants to write his own memory management, would it make sense to make your own allocator? Has anyone actually done this?

Also, can someone point me to a VERY simple tutorial on allocators. I'd like to think I'm a fairly decent C++ programmer, but reading Stroustrup has got my head steaming.

Share this post


Link to post
Share on other sites
There's an allocator template in <memory>. You can build your own allocator with this and instantiate standard containers with your new allocator.
For more indepth information read The C++ Programming Language, by Stroustrup :)

Overriding global new and delete is different though since the allocator template is a special purpose allocator (when it's not implemented via global new and delete as it is by default).
Global new and delete will have to manage the whole freestore that your application uses.

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