Memory Management in C/C++
Author
Hi,
I've just downloaded a delaunay triangulation program from internet and reading the source code. I stumble upon this code:
struct memorypool {
VOID **firstblock, **nowblock;
VOID *nextitem;
VOID *deaditemstack;
VOID **pathblock;
VOID *pathitem;
int alignbytes;
int itembytes;
int itemsperblock;
int itemsfirstblock;
long items, maxitems;
int unallocateditems;
int pathitemsleft;
};
it seems that the program is doing it's own memory management. I wonder why people want to do their own memory management, we have new/delete for C++ and malloc/free for C. What are the advantages/disadvantages of doing our own memory management?
Thanks.
regards,
tep
You could pre-allocate a big bunch of memory in one go, then hand it out as requred.
When new/delete or free/alloc allocate memory, the C or C++ runtime has to tag each block of memory with the information it needs to be able to deallocate it. While this is pretty trivial, if you were allocating 10,000,000 struct's, each of a size of 4 bytes, the run-time information would be as large as the data itself.
This would be a good time to implement your own memory manager that relied upon the fact that objects placed within it have a fixed size.
This is only one example.
When new/delete or free/alloc allocate memory, the C or C++ runtime has to tag each block of memory with the information it needs to be able to deallocate it. While this is pretty trivial, if you were allocating 10,000,000 struct's, each of a size of 4 bytes, the run-time information would be as large as the data itself.
This would be a good time to implement your own memory manager that relied upon the fact that objects placed within it have a fixed size.
This is only one example.
The OS memory allocators are general purpose, they know or ask nothing about the use of the memory requested and therefore use a very simplistic allocation strategy like finding the first block from the heap that meets the request size. In practice, especially in a game, you want to have more control than this. If you used the OS manager and did many allocations and frees, you would end up fragmenting the heap quite badly and this will degrade performance quite a lot over time (as the OS has to search over more locations to meet an allocation request). Therefore, commonly, you would allocate one very large chunk and manage it in a way that has more knowledge about its intended use.
Perhaps you know that you are going to be making a very large number of 16 byte allocations. You could dedicate one part of your memory space to just 16 byte allocations and this would greatly increase the speed for them as your manager needs to only know how many free slots there are and where the first available one is rather than having to go through a list of "free memory" slots and checking if each is big enough for your request.
Or perhaps you want to do some extended error handling/corruption checking. Your manager could implement its own guard bands around each allocation and check them when you free the memory rather than relying on the OS heap integrity checking functions.
Maybe you want to allocate from a particular part of memory (specifically physically-backed memory or specifically virtual memory).
This list goes on, this is by no means a large coverage of the reasons you might want to manage memory yourself. Its a large and imo geekily exciting area of game development :)
Perhaps you know that you are going to be making a very large number of 16 byte allocations. You could dedicate one part of your memory space to just 16 byte allocations and this would greatly increase the speed for them as your manager needs to only know how many free slots there are and where the first available one is rather than having to go through a list of "free memory" slots and checking if each is big enough for your request.
Or perhaps you want to do some extended error handling/corruption checking. Your manager could implement its own guard bands around each allocation and check them when you free the memory rather than relying on the OS heap integrity checking functions.
Maybe you want to allocate from a particular part of memory (specifically physically-backed memory or specifically virtual memory).
This list goes on, this is by no means a large coverage of the reasons you might want to manage memory yourself. Its a large and imo geekily exciting area of game development :)
Quote:Original post by stephanus
it seems that the program is doing it's own memory management. I wonder why people want to do their own memory management, we have new/delete for C++ and malloc/free for C. What are the advantages/disadvantages of doing our own memory management?
C++ has more than simply new and delete: it also provides several other allocators, some of which use pooling to increase performance and reduce fragmentation.
However, when you have to perform many allocation and deallocation operations, it can become necessary to handle them yourself because you know best how to optimize them.
Even then, I cannot help but feel that your source is not C++, but C++-compiler-friendly plain old C.
new/delete/free/malloc are all expensive operations. It's always a good idea to do 1 large allocation instead of many small allocations. Any good particle system, for example, will just allocate 1 large buffer for, say, 5000 particles, and then just reuse those 5000 particles in various ways without needing to allocated any more memory. Then when you shut down you just release the block of memory. You'd be surprised the amount of performance increase you can get if you implement your own memory manager, if you are indeed making many calls to new and delete normally.
Memory management is one of the few areas where micro-optimization can make a real difference since it will determine how your objects are organized in memory and thus will control how well they can be cached, which is a significant factor when dealing with a lot of data.
If you have a linked list that is constantly added to and removed from (while other things are going on, including other objects being allocated and freed on the same heap), it's likely your memory will become fragmented and the list will have elements all over the place, so iterating through the list could destroy the cache.
On the other hand, if you allocate blocks of objects at a time (say, enough to be 1MB) and link those blocks together instead (with some extra book keeping to track which 'cells' are free and which are not), you can ensure that iterating through the list generally steps to nearby elements of memory and thus that your program can take full advantage of a large part of the CPU's data cache.
The allocation algorithms in the CRT might try to control fragmentation and the like, but they have to be very general and can't be specialized on your actual usage requirements, so either they'll fragment too much or they'll run slower due to the work they do to avoid fragmentation.
Be aware that optimizing memory allocation can still be completely pointless - unless you are actually processing a lot of data, have profiled your code and found it to be too slow, and have tracked the problem to cache thrashing, you don't really need to worry about it.
If the code you found is C++, it's likely poorly designed. Allocation control can be done in a much better structured way, such as is done by boost::pool.
If you have a linked list that is constantly added to and removed from (while other things are going on, including other objects being allocated and freed on the same heap), it's likely your memory will become fragmented and the list will have elements all over the place, so iterating through the list could destroy the cache.
On the other hand, if you allocate blocks of objects at a time (say, enough to be 1MB) and link those blocks together instead (with some extra book keeping to track which 'cells' are free and which are not), you can ensure that iterating through the list generally steps to nearby elements of memory and thus that your program can take full advantage of a large part of the CPU's data cache.
The allocation algorithms in the CRT might try to control fragmentation and the like, but they have to be very general and can't be specialized on your actual usage requirements, so either they'll fragment too much or they'll run slower due to the work they do to avoid fragmentation.
Be aware that optimizing memory allocation can still be completely pointless - unless you are actually processing a lot of data, have profiled your code and found it to be too slow, and have tracked the problem to cache thrashing, you don't really need to worry about it.
If the code you found is C++, it's likely poorly designed. Allocation control can be done in a much better structured way, such as is done by boost::pool.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
