🔒 Locked

Memory Management

Started by OleKaiwalker Jul 7, 2004 at 3:32 AM 19 replies 2.8k views

Original Post

Jul 7, 2004 at 3:32 AM

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?

marijnh

Jul 7, 2004 at 4:00 AM

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.

Baraclese

Jul 7, 2004 at 5:17 AM

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.

Deebo

Jul 7, 2004 at 10:07 AM

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.

Deebo

Jul 7, 2004 at 11:29 AM

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.

JohnBolton

132

JohnBolton

Jul 7, 2004 at 5:14 PM

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]

weddo

Jul 7, 2004 at 6:20 PM

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).

Red Ant

Jul 8, 2004 at 6:57 AM

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?

Baraclese

Jul 8, 2004 at 8:01 AM

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.

Deebo

Jul 8, 2004 at 8:03 AM

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.

JohnBolton

132

JohnBolton

Jul 8, 2004 at 1:27 PM

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.

OleKaiwalker

Author

OleKaiwalker

Jul 8, 2004 at 4:45 PM

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?

Baraclese

Jul 8, 2004 at 5:26 PM

look here under "Wilderness Preservation":
http://g.oswego.edu/dl/html/malloc.html
I don't do that my pool size is fixed :)

OleKaiwalker

Author

OleKaiwalker

Jul 8, 2004 at 5:35 PM

I really don't see, how that is helping me...? I might just be me dont getting it?

Kelly G

Jul 8, 2004 at 5:55 PM

Curious. Why implement a memory manager? Is malloc() too slow for your app?

OleKaiwalker

Author

OleKaiwalker

Jul 9, 2004 at 2:05 AM

It's not too slow... It just leads to some heavly external fragmentation, I like to avoid...

Red Ant

Jul 10, 2004 at 2:26 PM

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.

Baraclese

Jul 10, 2004 at 2:56 PM

There's an allocator template in . 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.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.