37 replies to this topic

[ApochPiQ]

"Premature optimization" is the wrong warning phrase. I said as much.


In any case, I strongly disagree that people should be (in general) left to decide whether or not to reinvent a wheel. Unless you are exceptionally good, or have very sound evidence that you can do better, existing solutions are almost always the right thing to use.

[phantom]

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.

And yet, in this thread where you moan about it, the first person to use the term goes on to explain why.... so, what was your point again?

[L. Spiro]

And yet, in this thread where you moan about it, the first person to use the term goes on to explain why.... so, what was your point again?

While I have had a beef with that phrase for a long while, perhaps the reason this thread was the thread that broke my back is because, as rightly mentioned in this article, memory managers are not something you can just one day realize you need and then add them.
It is a mature optimization, in that if you ever need one, you need one from the very start.

Since the needs of each person vary, it is not in our place to say he does not need a memory manager. And the frank fact is if we say he doesn’t, but later down the road he does, we have done a huge disservice, as there is no recovery from that situation.


Yes, he explained why he said that. And in doing so he suggested that you wait until the memory system proves itself to be a bottleneck (#1), trivialized the gains in performance you could potentially get (#2), and suggested that the problem is higher-level (#3).
#1: Again perpetuating the flawed view many programmers have of the meaning of the phrase. No, you most certainly do not wait until your memory system proves itself to be a bottleneck.
#2: The gains can be huge. Not only in performance but in added debugging.
#3: It certainly could be a higher-level problem. But custom memory managers exist and are widely use for a reason. The simple fact is that improving your overall engine design might actually give you even more of a reason to come up with a custom memory manager. You can add features that help your overall engine design, and again this needs to be something you lay down early in the project, not later.



One of my early game engines was slow partially because I didn’t have a custom memory manager. I didn’t have the ability to exploit certain features that would have been a huge gain to my overall performance, and I had to design around that.
On a later project I realized this problem and one of the first things I did was make a custom memory manager that met the needs of a superior engine design. It proved to be one of the most essential parts of my engine.

That is my point.


L. Spiro

[ApochPiQ]

"Memory manager" is a terrible term and I hereby propose that anyone who uses it henceforth in this thread deserves a swift kick in the face.


Writing a wrapper around an existing allocation system - or, better, deploying specialized allocation schemes instead of dumping everything on a general-purpose heap allocator - is a fine and dandy goal. I would go so far as to say that if you aren't mindful of allocation patterns to the point where you are controlling them via smarter allocation schemes, you're doing it wrong (on non-trivial projects at least; don't forget that plenty of games can run on modern hardware without being stupidly optimal).

If you write your own heap allocator in hopes of improving everything, you're also doing it wrong. If you write a heap allocator without first deploying better allocation schemes in general, you're... well, to keep it politically correct, you've got a hell of a lot to learn.


Advocating smarter allocation schemes is good, and I support this. For 99.9% of programmers, this means using existing allocation scheme libraries - which, generally speaking, also get you access to debug instrumentation and inspection tools, which solves basically all of the problem.

Advocating custom heap allocators is bad, and I do not support it in any way, shape, or form - especially when the advocate is working with precisely zero information on the nature of the program and its allocation patterns in the first place.


Yes, a little bit of pre-emptive consideration can save you a lot of pain down the road. But deploying complex allocation strategy frameworks is not always a foregone necessity. If you're writing PacMan or a Zelda clone for the contemporary PC, you have no need to waste your time on such things. If you're working on a mobile device or writing the next Halo, then yeah, you'd be silly not to do some memory planning up front.



Sometimes, the "right tool for the job" means not dropping a bomb on a village just to eradicate a couple of mice.



Carelessly broad generalizations are for people who are incapable of thinking for themselves.

[SiCrane]

Advocating custom heap allocators is bad, and I do not support it in any way, shape, or form....

Before I begin to violently disagree with you, could you clarify what you mean by "custom heap allocators?"

[ApochPiQ]

Hand-rolling a general-purpose heap allocator by yourself.

There do exist a few general-purpose heap allocation implementations that are very, very good - and I use them. (dlmalloc comes to mind readily, for instance.)

I should have been clearer: I'm not against replacing heap allocators if there is a need for it (and on many platforms, especially when pushing the limits of the system, there is a definite need). I'm against the average programmer striking out to reinvent that particular wheel, because it's bloody hard and I've seen far more horrifically bad attempts at it than good ones.

[SiCrane]

Ok, that makes a lot more sense than the first sentence.

[VReality]

"Premature optimization" is the wrong warning phrase.

I recognize that you have other, very valid, concerns about this as well, but the P.O. objection is perfectly valid.

Granted, it's possible to deploy a custom heap without introducing any custom requirements about how it's used, such that most engineers can proceed as usual without even being aware of it, and most existing code just works with it without modification. I've never seen one end up quite that clean in practice though. But I concede that, as opposed to the general case of premature optimization, replacing a heap allocator is likely to add relatively little complication to the rest of development.

More significantly, I've never seen a performance problem, whose root cause involved dynamic memory allocation, that wasn't addressed far more effectively with a little careful consideration of resource usage strategies. In other words, when allocation related performance problems do arise, improving heap allocation performance is rarely necessary or sufficient. Spending time and effort to improve it speculatively is, by definition... well, you get the idea.

[Triangles-PCT]

I"m sure a heap manager is very useful on consoles and any other systems with terrible default allocators..

But testing nedmalloc, using the C++ tests it supplies..


Speed test:
vector<unsigned int>:
Appending each of 10,000,000 elements: 85.200315ms
Clearing 5,000,000 elements: 0.000769ms
Assigning 5,000,000 elements: 8.873440ms
Appending block of 5,000,000 elements: 36.902473ms
Popping 4,999,999 elements: 10.842796ms
Overallocation wastage: 56.249992%
Total time: 141.819793ms

vector<UIntish>:
Appending each of 10,000,000 elements: 94.803858ms
Clearing 5,000,000 elements: 0.000000ms
Assigning 5,000,000 elements: 13.504598ms
Appending block of 5,000,000 elements: 42.104648ms
Popping 4,999,999 elements: 10.760179ms
Overallocation wastage: 56.249992%
Total time: 161.173283ms

nedallocatorise<vector, UIntish, nedpolicy::typeIsPOD<true>>:
Appending each of 10,000,000 elements: 105.057961ms
Clearing 5,000,000 elements: 0.000384ms
Assigning 5,000,000 elements: 13.207177ms
Appending block of 5,000,000 elements: 46.086399ms
Popping 4,999,999 elements: 10.768633ms
Overallocation wastage: 56.249992%
Total time: 175.120553ms


The vector using the default allocator was the fastest.

[Neilo]

I'm strongly against "Not Invented Here" syndrome which is what rolling your own allocation system is, as many posters have suggested.

I'm a pretty competent programmer and in toy projects have tinkered with memory allocation, but when it comes to getting work done, I'd much rather abstract allocations, or resource loading or whatever somewhat and plug in a proven third party library than roll my own. If it becomes a problem when profiling then it's worth revisiting, but other than that, why bother?

Perhaps premature optimization is the wrong term. Maybe obsessive compulsive optimization is more fitting? So many developers seem to lose sight of the point, making things go and using all the resources at their disposal to do so, instead, they worry about edge cases and optimizations that may or may not be required.

Surely the true skill is coding in such a way that you don't wait yourself into a corner if you do decide you need to write your own DDS loader or memory allocator?

[Antheus]

I"m sure a heap manager is very useful on consoles and any other systems with terrible default allocators..

But testing nedmalloc, using the C++ tests it supplies..

This test performs roughly 24 allocation total, per allocator (vector grows by a factor of two and doesn't release storage).

Default allocators begin to break down when doing tens of thousands of allocations per frame.

[L. Spiro]

Surely the true skill is coding in such a way that you don't wait yourself into a corner if you do decide you need to write your own DDS loader or memory allocator?

This is obviously aimed at me, and is intended to imply that because I chose to write a custom memory allocator and new DXT compression routine (to be documented on my blog in the following hours) that I don’t have true coding skill.

People made it a strong point to mention that you should figure out the decision-making process and/or motives of a person before issuing advice to said person. Without knowing why I did these things, you have made quite a blanket statement.


If you need to know why I have done these things, it is because my current project is a next-generation engine which I intend to use not only to pull out every ounce of power from your CPU that I can, but also to start my own middleware company in the future. Perhaps with this little bit of light shed on the discussion you could better appreciate my personal motives for strongly pursuing these “trivial” gains in performance and quality.

In your thinking, it is sufficient to have a latent-filled allocator as long as it is applied to an intelligent system-wide design for allocations.
In my thinking, a high-speed allocator and an intelligent system-wide design for allocations must be applied. Contrary to your suggestion that my ignorance necessitated the need for improved allocator performance, I am in fact merging the best of both worlds to form formidable technology.

As a result of my lack of “true” coding skills, my product maintains higher performance and higher-quality DXT images which are also faster to create (reduced offline compiling).


L. Spiro

[Neilo]

It's not really aimed at you, I just mentioned it because DDS loaders were brought up previously in the thread.

I don't really know how to respond to the rest of your over defensive post. My point is not that one should never reinvent the wheel, but that they should reinvent if if they need to. You're right, I have no idea how you came to the conclusion that you needed to roll your own, and to be honest, I don't care.

My point is in the interest of getting things done, it's better to not invent the wheel but use what's at your disposal in such a way that swapping things out later isn't a massive pain in the neck!

Your own progress with a next generation engine sort of proves my point too. Your blog doesn't show that much progress despite your quest for the mother of all DDS loaders!

[L. Spiro]

I simply don’t understand why saying things as they are, factually, comes off as being defensive. Even if you had intended to insult me, it would never make an impact on my emotional state; I carried the same tone in that post as with any other. Though since others seem to agree with you, I suppose an apology for appearing to be defensive is in order (and given).

Once again you are extrapolating in order to try your best to make a point. Once again I am simply stating this as an observation.
Here are the facts about the progress of my engine:
#1: I just started it this year.
#2: I maintain 2 jobs, one of which (CTO of a game company) is full-time and the other of which (acting on Japanese TV and movies) varies. When filming for a movie, it gets virtually as busy as my full-time job. Also accounting for the 2-5 daily hours I spend at the piano, the Stanford AI class, an active dating/social life, and time I simply need to spend relaxing with a game or movie, frankly I don’t exactly have a lot of time to work on the engine.
#3: There is a lot more progress than what you can see. I even stated so in the recent update.

Given #2 (lack of time) and #3 (the progress you don’t know is there), it is clearly irrational to conclude that the progress I have made indicates I have wasted time on useless features such as a custom DXT compressor (which in fact has only taken 2 days of my time so far anyway).

Calm down and don’t try so hard to make your point.


The more on-topic point is about reinventing wheels.
Is it not enough to justify as a “need” simply to say, “I want the experience”?
If I am working in an office and have deadlines, obviously that excuse will fall flat, but if you are making your own hobby project, would you not consider that gaining experience from that project is more important than just making the end result by slapping together a few libraries and adding your own little layer on top?

Finishing projects is important as well, if you want to show them to employers, but only a handful of projects need to get that far, and frankly they still won’t be that impressive if every time the employer asks you, “So did you make this feature from scratch?”, and you keep replying, “No, I used X library for that.”
Finally you reach the end of the interview and the last question is, “So you can’t make a sound module, you can’t make a graphics module, or physics, or collision, or scene manager, or script system… What exactly can you do?”
“Well, um, I can put together a bunch of things other people made…”

I have recently been browsing job postings at various game companies in Tokyo.
Square Enix is building a new next-generation in-house engine, and they have postings for people who can build a graphics library. They want to make a new scripting language, so they have a posting for people skilled enough to invent a new scripting language (as in, not using a scripting language).
They want someone who can make an IK system, not someone who can search online for an existing solution and try to mash it into their code base.
David Helgason told me a nice little story about how some guy made an IK plug-in for Unity 3D, and they were so impressed with it they hired him. I.e. people who can make things get hired.


Do you understand now?

My point is in the interest of getting things done…

And what about the interest in learning? Gaining skills?
Don’t you see?
Even if my engine takes longer to make—even if it never gets finished—each feature I add manually rather than via some online library is a new skill I bring to a company when I go to my next job.
How much you learn on any given project has little to do with how quickly it was finished. It has only to do with how much you actually did on the project.

“Getting things done” is fine for you.
Meanwhile, I will be over here, growing, becoming more valuable to my current and future employers.


L. Spiro

[Christuff]

There is a lot of answer posted here and I agree to some point with both kind ( "premature optimisation", and still usefull to roll your own, even if only for learning purpose )

From a production perspective, what i can advice you :

Think carefully your allocators ( frame allocator, temporary allocator, heap etc ... ) and redefine them using the new / delete or malloc / free.
No need for now to really care about it, use their redefinition for debug purpose, to have only one "memory manager" ( i personally hate to have thousands of different memory manager for each lib i use )
And that it, spend your time to implement nice feature, and if you find memory management / alignement is a bottleneck, you just have to implement the allocation managment in the "memory manager" rather than trying to search through all your codebase to manage all your new / delete and other kind of allocation.

My two cents.

[mhagain]

Far as I'm concerned there are two main reasons to write a custom memory manager:

- Optimization
- Functionality

I'm not entirely convinced that the optimization reason is valid all of the time, but the one thing I am convinced of is that the functionality reason tends to get drowned out in the cries of "don't do it, it's premature optimization!" People who avoid doing this for the "premature optimization" (a phrase that rankles some with me too) reason may risk losing out on a lot of useful functionality.

Let's look at optimization first. There are a few things you can do to make the stock allocators run faster, with the most important being trading in lots of small allocations in favour of doing a few large allocations. That alone is often enough to solve any performance problems you may be noticing with allocation, and doesn't really require your own custom allocators.

Often things that seem like slow allocation performance may have an entirely different root cause. You might have a heavyweight constructor and all of your performance is going on that rather than on the allocation itself. That's why profiling is important - if calling "new MyObject" takes too long you need to know if the overhead is in the allocation or in the constructor. It shouldn't have even been necessary to have had to say that....

(If your language of choice uses lazy constructors this is of course not relevant.)

Functionality is the one huge advantage that tends to get lost. L Spiro mentioned trashable heaps as one functional bonus, and this one is HUGE. As soon as you get trashable heaps your code suddenly becomes a lot cleaner. You no longer need to track individual allocations, you no longer need to painstakingly ensure that you free everything, you can just throw out all of the memory used for the operation or event that's just ended and start at a clean state, all in one fell swoop.

The other big one that was mentioned upthread is debugging. Memory usage stats is also incredibly useful - you can see fairly easily that maybe your resource loader is a memory pig, you can track how much memory you're allocating/releasing per frame, you can find out what your upper limits for particles, textures, game objects, the entire current level, etc are. If you don't have this kind of info you're really flying blind; you don't know what the memory requirement patterns of your program are and everything is guesswork.

You can get the functionality requirement without necessarily having to shoot for the optimization requirement here; a custom memory manager does not necessarily have to give you both. That on it's own should be enough to demonstrate that the "premature optimization" argument against is bogus.

[L. Spiro]

For anyone interested, I have finally published my DXTn algorithm.
http://lspiroengine.com/?p=260
It took so long because I found a bug while I was trying to publish it before. I sorted that out and it turns out that it was also causing those “edge” cases I mentioned earlier.
The finished algorithm never generated results poorer than NVidia’s in any of my test material, and was always similar in speed or faster.


L. Spiro

[ill]

I'm strongly against "Not Invented Here" syndrome which is what rolling your own allocation system is, as many posters have suggested.

Yeah this is why I'd much prefer to use a library.

There have been times when I think, why even make a game engine. Why not just use Unreal 3 or something. I really want to make a game and not have to worry about reimplementing things that professionals have already done. Well now I'm also doing this for my masters project so there's a point. Also saves on license fees.

I definitely agree with watching out for premature optimization though. You really need to look at reasons for doing the optimization. Sometimes a premature optimization can actually make things less efficient. Sometimes it's worth saving for later. Sometimes it's a plain stupid idea that will actually make things worse and be a waste of time.

It's better to spend time thinking about the high level details and write things the easy and inefficient way first. Then go in and optimize areas that probably need it and see the performance increase. You'd never even know if what you are writing is faster with the optimization if you never had it written the other way. I got the renderer actually working and giving correct results before refactoring the horrible code I had written. Would've been a nightmare to not use OpenGL immediate mode while experimenting with stuff...

Worrying about optimization is a low level detail. Worry about the high level details first and then the low level or else it's too much to think about all at once. I usually write in my code, "TODO: this code sucks, optimize later" or something so if team mates come along and see my code they'll know that's not final. I won't have people coming to me saying, bro, you suck at programming, see that code you wrote? Also I won't have teammates looking at code for examples on how to code their task and think the inefficient code I wrote is the right way to do it.

I definitely wouldn't recommend worrying about heap management for the average project. The engine is at a point now where it's being used for pretty much a AAA title in the future so I'm starting to worry about details like build configuration and deployment and heap management and all that...