do most games do a lot of dynamic memory allocation?

Started by
99 comments, last by Norman Barrows 9 years, 4 months ago

Handmade Hero (handmadehero.org) video series by Casey Muratori touches on this subject which I found very interesting.

In day 014, Casey talks about memory management and proposes a design in which the game allocates on the heap only once at startup, and then partitions the memory to various subsystems. He then goes on to talk about that games usually calls new/malloc all over the place and that this introduces a failure point at every location. Using his design the failure point is once at startup only - if the game starts at all, it never fails and never runs out of memory.

(Also worth noting based on the original post is that Jonathan Blow and Casey are friends and have worked together on The Witness.)

PS. I highly recommend everyone to check out the Handmade Hero video series if you are interested in low-level programming at all.

Advertisement


I'm intrigued as to where you have pulled this 'extra dereference' from?
A pointer to a chunk of dynamic memory and a pointer to a chunk of memory which came in with the exe are going to be the same...

please correct me if i'm wrong

if i have a static array in the data segment, i can access it with base plus index (or was it base-index-offset?) addressing, an addressing mode native to intel, amd, and motorola processor instruction sets.

an array (or anything?) on the heap adds one extra instruction to calculate the base address.

been a long time since i did this kind of stuff, things might have changed, what with a class and a struct being more or less the the same thing except for the default protection mode.

Norm Barrows

Rockland Software Productions

"Building PC games since 1989"

rocklandsoftware.net

PLAY CAVEMAN NOW!

http://rocklandsoftware.net/beta.php


you have a scratch buffer objects a placement-new'd into for ease of construction but never deleted from, the allocation pointer is just reset to the start each frame; useful for things like rendering when you need to build temp data structures).

that's how my render queue works! <g>

the queue buffer and index buffers are allocated at load time (in the data segment - of course <g> ).

to clear the queue, you just set the queue pointer and number of index entries to zero


This has nothing to do with 'asset size > ram'; this is all about keeping things clean. If I don't need that memory allocated then why hang on to it?

ok, this makes sense, i do the same sort of thing. i'll unload startup screens before loading game assests - don't need them anymore - a waste of GPU ram. and i'll allocate large temp buffers on the heap for file i/o - the heap is the only logical place to do it.

but for non-temporary data, i use the data segment, or an array in the data segment with pointers to the heap, where the heap ram is sequentially allocated and deallocated just once (asset load for a chunk / level / game). for big temporary data, i use the heap, and for small temporary data i use the stack.

i use static array implementations of doubly linked lists for pretty much everything. they tend to be simpler and faster than traditional doubly linked lists implemented on the heap. the downside is you must set the max size at compile time, instead of the limit being up to the liimits of available ram.

but as i said before, i'm not doing monster engines. i'm mostly doing basic sims with 100 targets max kinda thing. so setting sizes upfront isn't too difficult. start with MAXTGTS=100. maybe kick it to 200 before release, that kind of thing.


a very specific example where you apparently don't care about wastage or good software design (hint: global things are bad software design but having seen your code in the past this doesn't surprise me in the least...)

ah, too true! 99% of the time, the entire projectiles array is empty. heck, most of the time, the entities list is empty too! its just the player list that has anything in it. and its usually 90% empty.

as for global, yes its bad. its unsafe - easy to misuse. the safety lacking in the code syntax must be replaced with coding policies and methodologies which must be well documented, and rigorously followed with strict coder discipline to avoid problems. but its the way i started, so i'm used to it. in the long run, all i really use it for its to avoid calling setter and getter methods everywhere. i suspect that it might be possible to write a game where all data is in private modules acessable only via getter and setter methods, and then you have control code modules that call getter and setter methods and perform operations on the values. the only thing that any data module would have to know about any other module would be any custom data structure definitions used to get and set its values. the only thing controller code modules would need to know would be custom data structures used to get and set values of data modules they use. an extremely modular system. but as you can see, there would be a lot of get and set calls. granted , many might get inlined, but i just bypass them and do the assignments directly, IE:

tgt.active=1;

vs

void activate_tgt(int i)

{

tgt.active=1;

}

or

strucs tgtrec {

...

void activate()

{

active=1;

}

}; // end struct

tgt.activate();


Fixed compile time buffers are the devil; the flexibility gained from just pulling from the heap for a value pulled from a config file far outweighs anything else in the general case.

so for the general case you advocate going data driven for the sizes of such data structures, and using the heap. yes this makes perfect sense. its simply matter of scale. my current projects are small enough i can get away without it. think about it, if you were going to code breakout or galaga, or space invaders or missile command or pong right quick and dirty, you wouldn't break out unity, and start creating CES systems and whatnot - its overkill: "using a tank to squash an ant" as they used to say in design sciences. you'd load up a couple bitmaps, and declare a few variables, and go for it. especially if you'd done it dozens of times before. for me, writing these sims (other than caveman - its a whole different sort of beast) is kind of like that.

Norm Barrows

Rockland Software Productions

"Building PC games since 1989"

rocklandsoftware.net

PLAY CAVEMAN NOW!

http://rocklandsoftware.net/beta.php


not using the heap as a defensive strategy against bad coding doesn't seem like valid thinking to me.

beats me, probably true. i use data segment for non-temp stuff, stack for small temp stuff, and heap for large temp stuff. most games apparently use heap for non-temp stuff. i find the data segment to be quick, easy, and good enough to get the job done. in my case it has nothing to do with defending against bad coding.

when it comes to defending against bad coding, i believe that should all be taken care of before release, and there should not be a single machine instruction in the final code whose sole purpose is to hand hold a programmer who can't write correct code. all incorrect code should be found and fixed before release. and correct code should require NO run time checks, because its correct and doesn't make any type errors. i realize this is a hopelessly perfectionist attitude given the state of game development industry today. perhaps that's one reason why i've never gone to work for a studio. but i still try to hold myself to these standards. in the past, i've typically averaged just one bug and a couple of dialog typos per new release. i develop in release mode, use the simplest possible code and architecture, keep things as modular as possible, use printf for debugging, and timers for profiling - all old school. gpu profiling tools are about the only new thing of interest to me.


Using containers and smart pointers, thinking about exception safety and avoiding raw pointers to represent ownership achieves much the same thing.

yes, but at what cost in complexity?


But I don't think your approach has anything to recommend it more generally.

its definitely not for everyone.

when it comes to coding i have an analogy i use:

imagine you come to a deep ravine and you have to cross to the other side. the side of the ravine you're on represents point A: where you're at when you start writing code to do something. the far side of the ravine represents point B: the solution, when you have code that gets you from A to B (across the ravine). now the simplest thing to do is throw a rope across, then hand over hand, or tight rope walk across. this represents quick and dirty "get it done" code with no error checking. it'll get you from A to B, but if you slip up, your screwed. blued. and tattooed! <g>. so you can throw a couple more ropes across for hand rails and make a rope bridge (basic error checking). safer, but not fool proof. so you decide to bite the bullet, and implement a true bridge across the ravine. much better, but you can still go over the edge some how. so finally you give up and build a tunnel (suspended or otherwise) across the ravine (bulletproof safe code). now you can't fall to your death. i find it simpler to just use a single rope and learn how to hand over hand across. the point is to get from A to B, not build a tunnel. tunnels are safe, but tunnels are more work, and sometimes run slower too. another analogy is you don't need a bridge with guardrails or a tunnel if you simply teach your code to not walk over the edge! <g>. sort of an an ounce of prevention vs a pound of runtime checking cure.

Norm Barrows

Rockland Software Productions

"Building PC games since 1989"

rocklandsoftware.net

PLAY CAVEMAN NOW!

http://rocklandsoftware.net/beta.php

but as i said before, i'm not doing monster engines. i'm mostly doing basic sims with 100 targets max kinda thing. so setting sizes upfront isn't too difficult. start with MAXTGTS=100. maybe kick it to 200 before release, that kind of thing.


Maybe you aren't, but you've rocked up here questioning things as though your minor project is in some way shining a light as to The Best way when it is just one example of a specific thing done in a specific way which works for you - lets not pretend that playing the static allocation game is anything less than wasteful bad practice which just happens to work for you.


as for global, yes its bad. its unsafe - easy to misuse. the safety lacking in the code syntax must be replaced with coding policies and methodologies which must be well documented, and rigorously followed with strict coder discipline to avoid problems. but its the way i started, so i'm used to it. in the long run, all i really use it for its to avoid calling setter and getter methods everywhere. i suspect that it might be possible to write a game where all data is in private modules acessable only via getter and setter methods, and then you have control code modules that call getter and setter methods and perform operations on the values. the only thing that any data module would have to know about any other module would be any custom data structure definitions used to get and set its values. the only thing controller code modules would need to know would be custom data structures used to get and set values of data modules they use. an extremely modular system. but as you can see, there would be a lot of get and set calls.


No, what I can see is a straw man argument built up using a lot of poor examples and something which screams 'bad design' at me - a good system design does not have 'getters and setters everywhere' and does not require module after module to know about the structures or internal setup of other systems.

A good system design decouples. A good system design hides. A good system design does not vomit all over your code base which is typically the case with global objects.

Fun example: Previous place I worked had a system to manage sharing system textures/render targets. This system was global. It was written by a junior with little experience and it was a mess. I designed and wrote a system to replace it (plus do more) which was not global (because the bloody thing was only used in the renderer anyway). Once the replacement was completed it took a couple of days to unwire the old system which had gotten everywhere. The new system was faster, cleaner, had more functionality and never once had a single bug tracked back to it. Nor did it have loads of 'get and set' functions.


granted , many might get inlined, but i just bypass them and do the assignments directly, IE:


And wasn't it you who not long ago had to make a chance which required searching all over his code base to do because the thing you were changing was accessed from so many places?

think about it, if you were going to code breakout or galaga, or space invaders or missile command or pong right quick and dirty, you wouldn't break out unity, and start creating CES systems and whatnot - its overkill: "using a tank to squash an ant" as they used to say in design sciences. you'd load up a couple bitmaps, and declare a few variables, and go for it. especially if you'd done it dozens of times before. for me, writing these sims (other than caveman - its a whole different sort of beast) is kind of like that.


Just because I wouldn't use an CES system doesn't mean I'd go around hardcoding things into arrays in data segments either; no, more likely I would grab existing code to read config files... hell, with projects as trivial as that I'd probably just grab Lua and use that for the logic and just plug it into some C++ framework.

But I'm assuming your 'sims' are more detailed than the trivial examples you gave so that is again not a sane comparison nor one which is representative of the scale of things.

The point is, regardless of the scale of things I would spare some brain time to do it properly because you don't know where things are going to go and spinning a few brain cells to correctly split up code rather than vomiting out some monstrosity is the way I will do things.

By all means continue developing and coding as you've done forever... it's no skin of my nose and when I do see your code I get a wonderful amusement out of it... but at the same time don't pretend it is in any way, shape, or form 'good practise' to do things your way because it simply isn't.


YAGNI holds that it's better to not implement something until you have an actual need for it because you likely don't understand the requirements and ramifications of that which you don't yet have a pressing need for.

that's just plain old common sense engineering.

glad to hear the concepts are still out there even if folks don't necessarily follow them.


But I am (and I think the rest of us here are) trying to shoot down your misconception that static allocations are beneficial in any way -- they are exactly (or at least approaching exactly-enough to not matter) the same as a single dynamic allocation with same lifetime, but also potentially less flexible. They are no more efficient and only differently complex, not less so.

the only real benefit is it saves me a malloc at program start and a free at program end, and perhaps one machine instruction during access. on the downside , it lacks flexibility which i don't need. so for me the sum total is its a bit less work and maybe a little faster. that's why i've never switched.


The why leads directly to How the industry resolves the problem -- fewer allocations, not static allocations.

yes, it appears the common approach is to allocate some memory and manage it yourself. the industry uses the heap for flexibility. not needing such flexibility i do the same sort of thing with the data segment. target and projectile lists are an example of this.

Norm Barrows

Rockland Software Productions

"Building PC games since 1989"

rocklandsoftware.net

PLAY CAVEMAN NOW!

http://rocklandsoftware.net/beta.php


He then goes on to talk about that games usually calls new/malloc all over the place and that this introduces a failure point at every location.

this is the sort of thing that prompted my original post. that didn't seem right. perhaps games made by less experienced programmers make a lot of runtime allocations?

Norm Barrows

Rockland Software Productions

"Building PC games since 1989"

rocklandsoftware.net

PLAY CAVEMAN NOW!

http://rocklandsoftware.net/beta.php

the only real benefit is ... and perhaps one machine instruction during access. so for me the sum total is ... and maybe a little faster.


OK, so, firstly one instruction on the CPU is nothing. Less than nothing. Not worth caring about in the slightly for something like this because in fact, as I think about it, your method is possibly slower.

You are accessing a global variable to find the address you need to pull data from. That value is not fixed at compile time so will end up being accessed and pulled into a register from a memory address every time.

You have no idea where that memory address is.
You have no idea what is around it.

Chances are very very good that memory address is no where near data you've just touched so that means that memory address is not in the cache at all. Congrats, your global memory access now means a trip down the cache (at best) and probably out to memory where it will take a few thousand cycles to get it back to you stalling the CPU and meaning that your single instruction saved is worth nothing.

On the flip side, memory allocated and pulled into a class instance should, if you are thinking about it, sit somewhere near where you are going to be accessing other things, which means there is a reasonable chance that the address of your data is already sat about in the cache and even if it isn't it is no worse than the previous example.

So, lets get off the performance train eh? because I'm willing to bet in any reasonably sized system you aren't going to be winning that fight anyway.


Maybe you aren't, but you've rocked up here questioning things as though your minor project is in some way shining a light as to The Best way when it is just one example of a specific thing done in a specific way which works for you - lets not pretend that playing the static allocation game is anything less than wasteful bad practice which just happens to work for you.

didn't mean to come off that way.

this really isn't about how i do things, i tend do things differently from most folks. i don't pretend its everyone's cup of tea.

i was simply curious, as the video mentioned in the O.P., and stuff you see on the web, seemed to indicate that frequent allocations and deallocations were common in games. which didn't seem right. so i figured i'd ask.

Norm Barrows

Rockland Software Productions

"Building PC games since 1989"

rocklandsoftware.net

PLAY CAVEMAN NOW!

http://rocklandsoftware.net/beta.php


a good system design does not have 'getters and setters everywhere

i said it might be possible, not performant. <g>.

Norm Barrows

Rockland Software Productions

"Building PC games since 1989"

rocklandsoftware.net

PLAY CAVEMAN NOW!

http://rocklandsoftware.net/beta.php

This topic is closed to new replies.

Advertisement