Heap Management

I wouldn’t say the release of that code is recent; I read that comment in the SDK at least 5 or 6 years ago, and I always considered that my own memory manager, written much later, should consider that the standard to beat.
My best case is about 30 times faster so I don’t beat them there but my average is a bit higher, so I call it about even. Except in 64-bit machines, where my average is 20 times faster. I don’t know why that is except that malloc() and free() must really suck on 64-bit machines.


How important is it? It depends on your needs.
While many AAA games are released using STL and default allocators, hardware is still limiting the potential of games.
In order to reduce those limitations, serious game makers tend to squeeze every ounce of performance out of their engines as humanly possible.

Consider the method Frostbite 2 uses for frustum culling.
“Standard” frustum culling has also been used in many AAA games for many years. Why did Frostbite 2 use their own approach with reduced branching? Because performance is just that important to them.

Advantages:
#1: Faster allocations. Your allocations can’t possibly be slower than those provided by Microsoft.
#2: Trashable heaps. Free everything in a single call. This can be emulated without a custom memory manager, but it can cause some problems doing it that way. Namely in regards to debug output.
#3: Better debug options and output. Able to track files and lines of every allocation (or almost) and later print debug information for allocations not released. This is where it becomes more essential to use a custom memory manager when working with trashable heaps.
#4: More alignment options. Alignments help you perform parallelism. You can’t SSE on data not aligned to 16-byte boundaries.

Disadvantages:
#1: You actually have to write it.
#2: It won’t be stable for a long time. A year later you might find one super-rare case that causes your manager to break. It took about 2 years for me to find that last edge case.


It doesn’t have a lot to do with STL. You could still use STL the way you normally do.
If you use your own manager, of course you will be overloading global new and delete. On Windows, some subsystems are still allowed to allocate directly through malloc() or via the Win32 heap allocators, meaning your allocators have no interference.
On iOS, the system will be using your allocators as well. Be mindful, but not afraid, of that.


Rewriting STL is not as scary as it sounds and comes with a lot of its own benefits.
Again, AAA games may use STL sometimes, but if your goal is performance, or game-ready customizations of the templates, you are better off writing your own.
Again, this will give you a bit more power geared specifically for games. You can make your templates work nicely with trashable heaps, add per-instance allocation rules (as apposed to one allocator that governs all vectors, for example), etc.
You can make them behave one way on PC and another way—more memory-conservative—on embedded devices and consoles.
You can add features to give you more control over how memory is used. For example, my vector template has Reset(), which frees all resources used by the vector, and ResetNoDealloc(), which obviously resets the vector, but does not release its memory back to the system. It can then be used again and it won’t perform any allocations at all until the left-over buffer is exceeded.


Rewriting STL does not mean rewriting the entire STL. Obviously the first thing you will rewrite are vectors.
Then sets and maps, multi-maps, linked lists, and strings. After that? Nothing. At least I haven’t had a use for the rest yet. If I do, I will make them when I need them. And that is just how it goes.
Make them when you need them.


In the end it just depends on how needy you are in the performance department vs. how much time you have on the project.
If time is short, that may be a problem, not because there is a lot to write, but because there is a lot that could go wrong in your memory manager and it may take a long time to find all the issues.
It may not break for you but once a million people are using it, it may just crumble for a lot of people.


L. Spiro

You don't need to use a replacement for the standard memory allocation routines, but it obviously does have it's benefits for large projects.
Regarding performance, as always, you shouldn't fret too much unless you actually see a non-trivial percentage of your CPU time being spent inside malloc/new.
Every commercial project I've worked on has had it's own memory systems -- but often valued for the debugging features, just as much as for performance, etc.
On console games where your memory requirements are very strict, you might find that you have to use a custom memory system in order to maintain your RAM budgets -- simply so you can tell how much RAM each part of your game is using.
If you're doing ok without these kinds of features, it might be that you don't need them, yet ;)

If you don't have the time/expertise to write this kind of thing, you can always buy an existing one.

Yeah one of the biggest advantages is definitely the debugging. What kinds of things do I actually need to worry about when I write a heap manager? Do I just allocate a huge chunk of memory and write stuff to it, and if I'm low on memory allocate more? How would I handle fragmentation? I read about Doom's Zone memory system and how it kept a linked list of free memory locations. I also remember something like that from Operating Systems class. Are there better ways to do that kind of thing now?

So once I have this heap manager does EVERYTHING in the game that would normally call new or malloc now use the heap manager? Is there ever a time where I just use the standard library memory allocation functions? Is it a good idea to have multiple heap managers rather than just one global one for any reason? I'm also going to have multiple threads for sound and rendering tasks and whatever else I need. Do those usually need mini heaps of their own?

I can probably start writing this and as I work on it, look at the Doom 3 source code for ideas. There aren't very many great tutorials that talk about all the crazy optimizations that would go into making this kind of thing.

Not sure how much I believe that comment. I've downloaded and tested various so-called fast allocators(Nedmalloc etc.) claiming that they outperform microsofts, and every time I actually tested it, the MS allocator was the fastest.

The OS seemed to matter somewhat here, as MS allocator under XP didn't always win, but under Vista/Windows 7 it fairly well destroyed the others(I believe the default under Vista+ is low frag).

Not sure how much I believe that comment. I've downloaded and tested various so-called fast allocators(Nedmalloc etc.) claiming that they outperform microsofts, and every time I actually tested it, the MS allocator was the fastest.

The OS seemed to matter somewhat here, as MS allocator under XP didn't always win, but under Vista/Windows 7 it fairly well destroyed the others(I believe the default under Vista+ is low frag).

I benchmark my own quite often, and it definitely does outperform Microsoft’s. I didn’t think that was too special but if you say so.
And as I mentioned, while my manager is designed to work on whatever the native address size of the operating system, I did no other special optimizations for 64-bit machines.
I don’t know about 32-bit Windows 7 but my 64-bit Windows 7 is at least 20 times slower than my memory manager.
As I mentioned, I didn’t do anything special so I attribute that to poor managers by Microsoft.

What kinds of things do I actually need to worry about when I write a heap manager?

Stability first. This thing will provide memory for the rest of your entire engine and game. It absolutely must be reliable.
Otherwise there is litte need for “worry”.

Do I just allocate a huge chunk of memory and write stuff to it, and if I'm low on memory allocate more?

Basically. One big allocation from the operating system, assign a heap manager to it (which itself could be placed at the start of the heap it is to manage), and keep a linked list of these managers.
The big manager maintains the linked list and searches over the heap managers trying to find one that can handle the allocation or free operation.
The heap managers will typically keep track of which areas are free and not free via linked lists, one for free stores and one for used stores.
Updating these linked lists correctly is the tricky part. It just has to be done carefully.

How would I handle fragmentation?

Fragmentation is not really the job of the memory manager itself, but there are things it can do to reduce it, and increase the efficiency of its use of the heap.
If speed is your only goal, you will return the first free block of memory you find when an allocation is requested.
To decrease fragmentation, you should search a little more for a free block that fits the requested allocation size exactly.

Fragmentation, however, is more of an issue with the overall design of the engine. Trashable heaps are one way to eliminate them.
In my engine, each part of a game (main menu, options menu, gameplay screen, bonus area, etc.) are all “states”, and the engine is designed to keep states completely separate from each other (although while making your game you do have the ability to add some glue between them if you think it is necessary).
If each state correctly releases its resources when destroyed, then in theory the heap will look exactly the same before and after the state was executed.
This basically means fragmentation is never an issue, and I can also use this design to alert the user to potential memory leaks.

Are there better ways to do that kind of thing now?

Linked lists are still commonplace. It is more a matter of how you distribute your buckets for fast searching.
Other tactics include making a second type of allocator for small sizes. Since every allocation has some book-keeping overhead, small allocations tend to be the most wasteful.
You ask for 4 bytes but another 16 bytes are added for internal book-keeping.

So for small allocations a different method is used.
That method has an array of 256 pools. The sizes of the data in each pool are known, so you don’t need to keep that type of book-keeping information with every allocation.
Instead, pool 0 has a size of 1 byte, pool 1 data are all 2 bytes, etc. So if I ask for 16 bytes, the size is below 256 so it goes to the secondary manager, which goes to pool #15 and finds an entry there that is unused.

I don’t know if I have just described the “zone” method Doom uses; I basically got this idea on my own and I don’t know what their method is.

So once I have this heap manager does EVERYTHING in the game that would normally call new or malloc now use the heap manager?

Yes.
Anything not managed by your manager is a risk. Your manager can only print the leaks that came out of heaps it was managing.
If someone leaks a malloc() you will never know.
And remember, once you override new and delete, regular calls to new and delete will be routed to your manager, and new/delete are preferred in C++ over malloc() and free() anyway.

Is there ever a time where I just use the standard library memory allocation functions?

Only if there is no alternative. I rewrote any classes that would force me into that situation.

Is it a good idea to have multiple heap managers rather than just one global one for any reason?

Certainly. This is how trashable heaps work.
The managers should all be instances. The default manager is nothing but an instance that happens to be a global.
new and delete are overridden to direct to this one.

Then from that one you can request another manager instance. In my engine, each master model (not model instances) has its own manager. It uses that for all of its allocations, so when the model is destroyed it can simply trash the heap and be done.
Mind you this cannot be done carelessly. Even if you plan to throw away an entire heap at once you still need to call destructors etc.
How my system works is that each trashable object has a Trash() function, which basically tells them they can freely let go of their resources without deallocating them. Just set the pointers to NULL.
When the destructors come around, the pointers are NULL and nothing happens.

My vector classes are custom-made and support this functionality. If you trash a vector, it will then call Trash() on each object in its list and then set its pointers to NULL.

You would call Trash() on your custom memory manager instance as well so that it does not print a ton of debug messages related to leaks.

I'm also going to have multiple threads for sound and rendering tasks and whatever else I need. Do those usually need mini heaps of their own?

Up to you. It could help with fragmentation reduction, but those managers are not typically the major contributors to fragmentation.


L. Spiro

Sounds good... The only problem is Doom 3 doesn't really take advantage of multithreading so I can't learn too much from their source about how to handle threads and tasks. I might find more info later or experiment with it...

The only thing I had to do related to threading was to make the managers thread-safe.
This just means a critical section or a mutex at the highest-level calls (malloc, realloc, and free).

If you make a manager instance for your models as I have done you don’t need this overhead at all since you could guarantee that only your model class will be using the manager instance, and only on one thread.
That is unless you plan to load using multiple threads.


L. Spiro

Regarding performance, as always, you shouldn't fret too much unless you actually see a non-trivial percentage of your CPU time being spent inside malloc/new.
Every commercial project I've worked on has had it's own memory systems -- but often valued for the debugging features, just as much as for performance, etc.
On console games where your memory requirements are very strict, you might find that you have to use a custom memory system in order to maintain your RAM budgets -- simply so you can tell how much RAM each part of your game is using.

Just curious, but how exactly do you write a custom allocator?

When you say Model are you talking about like Model view controller Model?

The way you write an allocator is you basically allocate a huge chunk of memory with standard malloc or new or whatever. Then when you need some memory allocated you allocate from a chunk of your massive memory block instead of from the OS with malloc.

You have to keep track of which blocks in your memory are free.

Just curious, but how exactly do you write a custom allocator?

http://bitsquid.blog...ation-in-c.html
Should give you a good idea.

You don't have to. Just use a decent replacement that's well proven to work. Like nedmalloc or Hoard.

Nevertheless, you'll probably want to overload your new & delete routines for debugging purposes and other higher-level memory management.

On 11/26/2011 at 11:16 AM, ill said:

So basically, how important is this kind of thing?

In the most general, high level terms, writing your own heap manager is almost always an instance of "premature optimization". In other words, you should really only be doing it if:

• you've developed an engine/game which turns out to "over-use" heap allocations to the point that the profiler has identified them as a performance bottleneck,
• you only need that little boost that you think you can get from a custom heap manager, and
• you can't find a (probably much more effective) higher level solution to the problem.

In other words, almost never.

As for memory corruption and leak debugging tools, stock heap managers (e.g., Microsoft's) generally provide them, and the first thing a custom manager does is break those tools, costing you development time on your own. In fact, there's enough value in the built-in debugging tools, that even if you were to write your own manager, you'd probably want it disabled during development, and only swapped in for whatever performance boost it can give you, in release builds.

When you say Model are you talking about like Model view controller Model?

No, I mean a 3D model.

writing your own heap manager is almost always an instance of "premature optimization".

I really get very tired of seeing this.
Everyone everywhere says everything is a premature optimization.
If we lived by that rule every code we ever wrote would be a sluggish pile of slop.

When you know (or can be sure within reasonable doubt) that something you are about to make will be faster than the alternative, why would you not make it?
Because it didn’t prove to be a bottleneck?

What is the sense in that?
If you waited around for every part of the engine to prove itself as being a bottleneck, you will ultimately find yourself overloaded with bottlenecks, or you won’t be able to find bottlenecks at all because you won’t have a good basis for comparison. Everything will be slow, thereby making nothing seem like a specific bottleneck.



The only reason to claim “premature optimization” is when either of the following is true:
#1: You aren’t even sure it will work, and you are already trying to make it optimized. This falls under the “make it work, then make it fast” mantra.
#2: You aren’t sure that the end result will be faster than the alternative.


There is no reason to claim premature optimization here.
#1 is easy to handle. Just keep a backup system on the side that allows you to go back to the OS allocators while you are trying to sort out the bugs in your custom one.
I already warned him of how much of a hassle it can be to make it stable, and he seems to be willing to undergo the challenge.
#2 seems unlikely. As I mentioned, I don’t consider that I did anything with my own managers that others cannot do, and mine is around 4 times faster, sometimes 20-25 times faster. Never slower.
I am fairly confident that it is not a risky undertaking as far as performance is concerned.


L. Spiro

You make the crucial mistake of assuming everyone is skilled enough to deal with the intricacies of writing a heap allocator. This is a patently false assumption.

Most programmers are not going to be able to produce a heap allocator that is more robust, faster, and better-tooled than existing allocators. For those programmers, "premature optimization" perhaps is the wrong warning phrase, so "horribly bad idea" might capture the sentiment a bit better.


I've seen memory managers written by people who were not highly skilled in memory allocation algorithms and/or were not well-versed in the low-level concerns that make memory management a sticky game. I would never drop one of their managers into any software, especially not a game that requires performance, long-term stability, consistency, and debuggability.

There are maybe three or four allocators I've ever seen (in the C/C++ world at least) that I would use in a serious project. And only a very, very serious project calls for custom memory management logic. Tooling is good on the out-of-the-box stuff, and performance is more than enough if you aren't sloppy with your allocation patterns to begin with.


I'd go so far as to say that anything more than wrapping OS heap management with some debugging/arena/pool features is a vicious waste of time; not because it won't gain you anything, but because the typical programmer will spend many orders of magnitude more time trying to figure out all the bizarre bugs they've created than getting any real benefit from the memory manager.

And if all you need is some debug info and arena/pool style features, well, there's excellent libraries for that already.


From a business perspective, if I hired a programmer who a priori of rigorous and desperate profiling thought it was worth his time to write a heap allocator instead of getting real features done... well, in the spirit of the season, he'd get a nice little pink envelope in his stocking, if you know what I mean.

On 11/28/2011 at 5:40 PM, L. Spiro said:

When you know (or can be sure within reasonable doubt) that something you are about to make will be faster than the alternative, why would you not make it?

Because chances are you don't need it.

In general, there shouldn't be enough dynamic allocation going on that gaining a speed increase over a stock memory manager should make an appreciable difference to overall performance. When one's use of a stock memory manager becomes a performance bottleneck, they've made some fairly serious higher level design blunders. And in general addressing issues in higher level technical design will produce far greater performance improvements.

On 11/28/2011 at 5:40 PM, L. Spiro said:

If you waited around for every part of the engine to prove itself as being a bottleneck, you will ultimately find yourself overloaded with bottlenecks, or you won’t be able to find bottlenecks at all because you won’t have a good basis for comparison. Everything will be slow, thereby making nothing seem like a specific bottleneck.

And yet a profiler will still give you your best targets for performance improvement. You should always develop with performance in mind of course, but the "performance" of the vast majority of your code just won't matter to actual overall engine/game performance.

The idea isn't to use the slowest approach until it proves a problem, it's to avoid unnecessary work until it proves necessary.

On 11/28/2011 at 5:40 PM, L. Spiro said:

The only reason to claim “premature optimization” is when either of the following is true:
#1: You aren’t even sure it will work, and you are already trying to make it optimized. This falls under the “make it work, then make it fast” mantra.
#2: You aren’t sure that the end result will be faster than the alternative.

If either of those are true, then you probably can't call it an optimization at all.

The marks of premature optimization are that the anticipated enhancement hasn't proven necessary to success, or that its implementation hinders development. Creating a custom heap meets both conditions, to different degrees (depending on the approach and the scope of the work).

On 11/29/2011 at 12:16 PM, ApochPiQ said:

Most programmers are not going to be able to produce a heap allocator that is more robust, faster, and better-tooled than existing allocators.

Back in the day, this wasn't such a big deal. Operating systems (and their heap managers) were relatively newly multi-threaded, and game engines were not. It wasn't too big a challenge to make a heap allocator that used the same basic allocation, block joining, and error detection schemes without the multi-threading overhead. But in the end, it still proved unnecessary.

Anyway, my point isn't that you should never write your own high performance custom heap manager. It's that if you never do, you'll most likely never end up missing it. The stock managers work, and work well. Your time is probably better spent elsewhere. But it is your time.

I've been working on my engine for a while but I can't say for sure if memory allocation is a bottle neck yet. I have had cases where there was some lag after a particle system gets created which I'm guessing is due to all the new particles being allocated. I might also make my engine work on next gen consoles sometime in the future. Many AAA game engines use their own memory manager so I'm guessing this is a bottle neck for them and it would be a bottleneck for me also. Then again many people say it might not be a bottleneck.

The crazy memory debugging features in this heap manager would only be enabled if a macro is true. That way the debug build would use it and maybe if I want to make a release build but still have memory profiling on for some testing. I can still do memory debugging without a custom heap manager by just wrapping around the new calls and tracking my allocations with a debug build. I've used memory tools like Valgrind and Visual Leak Detector but that only let's me know if all memory allocated is free by the end of the program. I'd like to know if memory I allocated between levels is properly freed, or memory that was allocated for an entity is freed when it's destroyed. There's also the resource manager caching my resources so those things shouldn't be freed between levels. A regular memory profiling tool can't differentiate between those two kinds of memory allocations.

I'll check out those libraries you guys suggested and if they don't require some license fee I'll use them. Otherwise I'll hold off on this whole heap manager thing for a while.

On 11/29/2011 at 2:25 PM, ill said:

I have had cases where there was some lag after a particle system gets created which I'm guessing is due to all the new particles being allocated.

If you were able to implement a heap manager with better performance, the result would be reduced "lag" in those cases. Allocations would still be somewhat expensive, and if you were doing too many of them before, you still would be.

In other words, better allocation performance wouldn't actually solve the problem. It seems like you probably need to re-think how the particle system handles its resources. ...that is, after finding out for certain what's causing the hitch.

On 11/29/2011 at 2:25 PM, ill said:

I'd like to know if memory I allocated between levels is properly freed, or memory that was allocated for an entity is freed when it's destroyed. There's also the resource manager caching my resources so those things shouldn't be freed between levels. A regular memory profiling tool can't differentiate between those two kinds of memory allocations.

These debugging features can be implemented in a system that wraps the stock heap manager and delegates actual heap management to it. You don't necessarily need to re-implement heap management for this.

Anyway, my point isn't that you should never write your own high performance custom heap manager. It's that if you never do, you'll most likely never end up missing it. The stock managers work, and work well. Your time is probably better spent elsewhere. But it is your time.

Then I can safely assume you have never written one.
I consider the features and speed of my own invaluable. It has detected for me some of the trickiest of leaks and helps me guarantee the leak-free state of my engine.
Its improved performance does not decrease my attention to higher-level memory-managing design. In other words, I get the best of both worlds.

You make the crucial mistake of assuming everyone is skilled enough to deal with the intricacies of writing a heap allocator. This is a patently false assumption.

I feel that I warned him thoroughly about how difficult it is. He seemed to still be willing to try, so beyond that, I am not willing to decide for others what they should or should not do.



This is where “premature optimization” claims bug me.
It has been a few days so I don’t remember the situation of the original poster, but in general it seems that people assume everyone is in a corporate setting, has time restrictions, or has skill limitations.
You must admit to one of these when making such a claim. If someone had infinite skill or infinite time (or both), would you still make such a claim?
If you knew a person had infinite skill, you would probably expect that person to write a memory manager far beyond existing ones, and of course that would be no premature optimization.
On a more realistic level, if someone is doing this as a hobby project or as a learning tool, time has much less meaning.


“Premature optimization” is a way of saying you don’t think it is worth the time of someone else. Contrarily, I prefer to simply state that such a task is non-trivial, one can expect X number of hardships along the way, and these are the benefits of accomplishing said task. I let the other person decide the value of his or her time spent on said task. I don’t think I have ever claimed “premature optimization” because I don’t think it is appropriate to decide for others what that constitutes, and I think such claims can do more damage than good (while sometimes they can also do more good than damage, admittedly).



If I had come this board and asked about making my own DDS file maker, I have a feeling I would have been greeted with questions along the line of, “Why would you do that? There are already great tools that do it. Use the NVidia converter,” etc.
“That is a waste of time. You won’t get better quality than what is produced by the NVidia or S3 converters.”
Luckily I did not ask around. I just dove in and made a converter. And the results are better than both NVidia’s and S3’s, except in a few cases which I know how to detect and am currently thinking about how to handle. If I figure something out for those cases, I will have a method that beats NVidia and S3 in all cases.
(I do plan to publish my results and method by the way.)
This is something I could easily see others prematurely claiming to be a “premature optimization” (or similar). Or more accurately, a case in which others would have attempted to make my decision for me, and thus prevent progress.
This is why I reiterate: Let people decide for themselves. Give them the facts about a task (difficulty, expected skill level for success, etc.) and let them decide for themselves whether or not to go through with it.
I think it is always a premature optimization to claim “premature optimization” to someone else.


L. Spiro


[EDIT]
This is what I was trying to say in my previous post.
As correctly pointed out, “premature optimization” is a term that is too loosely tossed about due too a misunderstanding of what it really means.
I gave an example in which you would forgo most optimizations with the end result being a whole heap of slop-slow code and an overwhelming amount of changes laying in front you. The author of that article correctly reiterated that point.

With how often this term is used, new programmers mistakenly get the idea that no code should be made fast until it proves to be a bottleneck. They interpret it as “Early optimization is evil”.

You have to be more careful about when and where you use this expression. I have never seen a situation in which there was nothing better to say than “it is premature optimization”.
Rule of thumb: When you feel the need to claim “premature optimization”, there is usually a better way to explain why you feel someone should not undergo said task.
[/EDIT]

If you had rocked up and said 'I want to make my own DDS maker, how do I do it?' then yes, you would have quite rightly been pointed at existing solutions because from that small snippet you wouldn't have given enough information to be pointed in any other direction and thus making your own would have looked like a waste of time.

If you had rocked up and said 'the NV DDS compressor isn't fast enough, how can I make my own?' then you would have been likely greated firstly with questions of 'really? how much time are you wasting? are you doing it on load or in the pipeline?' and other such things to ensure that the solution was right for your use case.

If you had rocked up and said 'the NV DDS compressor isn't giving the quality I want, how cna I make my own?' then you might have got some suggestions about tweaking it and probably some pointers to existing implimentations/papers on how to improve on DXTn/BCn compression systems (because plenty of people have already looked into the problem).

The point is WITHOUT a significant use case blindly going 'huhuhuh I can make it better for I r the bestest!' IS more than likely going to be a waste of time. Heap management is one such area; unless you have a known need then doing anything is likely to be a waste of time for most people. Heck, you even need to known certain non-trivial things such as, iirc, the memory allocation performance changes if you run the app from VS REGARDLESS of if you are in debug mode or not when compared to running it externally.

(On the DDS charge I would firstly question if the quality is currently an issue and then suggest a caching asset build system to reduce your build times instead of spending time and effort on something which is unlikely to make a huge amount of difference. We have the latter where I work which cuts down build time, in fact most of the build time is spent either working out dependancies or building non-texture assets and the build system is fully distrubuted, and the former is subjective as none of the artist where I have worked have complained as yet about texture issues quality wise coming from NV's compiler thus, in our case, rolling your own would have been a waste of time.)

So, yes, when no details as to WHY someone would want to do something has been presented calling them out on just WHY they would want to do something and then questioning if it is premature, and their time better spent else where, is a GOOD thing.

Maybe you like to swan off and 'fix' things which for most people aren't broken, or at least not broken enough to warrent 'fixing' but not everyone can do it and more importantly if they want to get something else done not everyone SHOULD do it either.