next »

[Ivan]

Yeah, but say you have some sort of engine-level scene graph system that creates and keeps track of scene objects or something like that. That shouldn't be limited and should all be dynamically allocated.

And what about abstract base classes? A lot of the time you have patterns that track things by their base class with no knowledge of how large the actual subclass is. There is no notion of MAX_WHATEVER in these situations.

[Zaphos]

FWIW, there have been recent threads on the gdalgorithms list, and a lot of people still recommend using _static_ allocation for games, so all the "dynamic everything" talk should be taken with a grain of salt.

I think there's some difference of philosophy here ... if you're just learning SDL, you probably don't need to worry about this kind of optimization for a while.  There's some merit to doing what's easiest to get working code when you're starting out.

Also, you can overload new and make it correspond to static allocation (grabbing memory from a pool) if you want, I think.

[Mikademus]

when programming C++ correctly you'll actually very seldom use dynamic memory allocation (new and delete). When studying C++ make a point of reading up on references and if you ever need to dynamically allocate an object with new, always store that pointer in a smart pointer or at least an auto_ptr.

What? I don't agree with any of this. Most if not all applications allocate objects dynamically - If they don't, you're doing it wrong. You're not supposed to know everything at compile time, you're supposed to load object definitions from scripts to have them easily editable without recompilation.

Also, what's with the smart pointers? If you have any idea what you're doing you can do a much better job manually deallocating your stuff.

Yeah i don't know what that was all about. Dynamic memory allocation is the center of any real application. The point is that STL is there for a reason and unless you're confident in your ability to make more optimized containers, you should use STL's.

Thank you for your replies. I'm glad you're interested in the topic. Dynamic allocation is indeed integral to using techniques as f.i. polymorphism. Dynamic allocations in itself isn't evil. However, the normal pattern of allocating into naked pointers and deallocating "when done" or at scope end etc is dangerous and bug-prone.

Before efficient code (in the sense of squeezing out every little CPU cycle) you should have stable and maintainable code, and the habit of using naked pointers will lead to memory leaks. Using naked pointers will lead to code not exception-safe. Also, storing new'd pointers in STL containers is a bad idea that generally exacerbate both these problems. Passing pointers as parameters will risk passing invalid or null pointers. Using references, and especially const references, will allow the compiler to optimise code and avoid the unnecessary "if (!ptr)" test. Since GC isn't very suitable to performance-sensitive games, storing naked dynamic memory in smart pointers is a solution that allows RIAA, ensures proper deallocation, less code management, scope control, exception safety and transparent copying and storage in STL containers. It is also good habit of using static allocation as often as possible, since that will allow the compiler to pre-allocate space, determine memory use beforehand, and avoid the dynamic allocation overhead.

[raigan]

Yeah, but say you have some sort of engine-level scene graph system that creates and keeps track of scene objects or something like that. That shouldn't be limited and should all be dynamically allocated.

You can establish a max number of nodes, allocate them all up-front and then pool them at runtime.

And what about abstract base classes? A lot of the time you have patterns that track things by their base class with no knowledge of how large the actual subclass is. There is no notion of MAX_WHATEVER in these situations.

This is one of the first things I asked, and apparently home-made polymorphism is a common solution. So, no pointers, instead you'd use a handle (which contains hidden inside it, i.e accessed only by the "manager", the concrete type of the entity it referred to).

When you want a pointer to an object, you ask the manager for one, passing in a handle. Given a handle, the manager can use the it to decide (a) which list the entity was in (if you have one list per concrete/implementing class) or (b) which type of entity to cast to (if you have one list per interface -- and each element is the size of the largest implementing class and you use placement new to init an instance). Then the manager can pass back a pointer to whoever requested it.

There are probably lots of other ways to manage this sort of thing, (a) and (b) are just two that were specifically mentioned.

Probably this is only a big deal on consoles, and in fact there was a large debate between people who used STL and dynamic allocation heavily on consoles and those who preferred to allocate everything up front, so definitely both are possible -- I just wanted to point out that there are many different options and it really depends on what fits the game best.

For instance, in a Super Mario Bros type game, you'd never need to dynamically allocate anything -- entities never "die", they're simply put in a "dead" state. So at load time you know the exact number and type of all entities needed for the level; "dynamic" stuff (for instance, the fire ball Mario might be able to shoot) can be allocated up front based on established limits -- for instance, only two fireballs are allowed on screen at once, so given the number of Marios in the level you know the max number of fireballs needed.

That's probably the best-case game for pre-allocation; I'm sure that streaming open-world stuff is better suited to dynamically managing things.

[Zaphos]

This is one of the first things I asked

Is the discussion archived online anywhere you could link to?  It sounds interesting!

[hexageek]

Yeah, but say you have some sort of engine-level scene graph system that creates and keeps track of scene objects or something like that. That shouldn't be limited and should all be dynamically allocated.

You can establish a max number of nodes, allocate them all up-front and then pool them at runtime.

And use much more memory then it should all the time?

Why would someone statically allocate memory for a dynamic tree?
I'm not sure there will be any problem in any kind of computer with this (pc, console...)

[Alex May]

Yeah, but say you have some sort of engine-level scene graph system that creates and keeps track of scene objects or something like that. That shouldn't be limited and should all be dynamically allocated.

You can establish a max number of nodes, allocate them all up-front and then pool them at runtime.

And use much more memory then it should all the time?

And use as much memory as it will in the worst case all the time.

Kind of upsetting for a user to get to level 13 and then run out of memory without warning.

[hexageek]

Yeah, but say you have some sort of engine-level scene graph system that creates and keeps track of scene objects or something like that. That shouldn't be limited and should all be dynamically allocated.

You can establish a max number of nodes, allocate them all up-front and then pool them at runtime.

And use much more memory then it should all the time?

And use as much memory as it will in the worst case all the time.

Kind of upsetting for a user to get to level 13 and then run out of memory without warning.

that is absurd. from your logic, player can't even start the game since statically allocating it to the worst case (level 13) would fill the memory form the start.

filling up the memory is not so easy. and memory leaks are is easy to prevent or fix if you know what you're doing. (tools like http://valgrind.org/ are very handy)

I find it funny to compare dynamic and static memory allocation. 2 very different things with their own uses. Avoiding one to use another is simply a bad programming practice.

EDIT: Also, realistically thinking, no body in here should worry about dynamic memory allocation overhead.

[Zaphos]

I think Alex's point was that the memory use can't grow arbitrarily in a game, and if you write your code as if it could you're more likely to run into the problems that creates.  Nothing to do with memory leaks.

Optimizing the 'worst case' in a game does make sense.  I'm not sure why 'no body in here' should worry about optimizing their programs.

[hexageek]

I think Alex's point was that the memory use can't grow arbitrarily in a game, and if you write your code as if it could you're more likely to run into the problems that creates.  Nothing to do with memory leaks.

Of course it can. who decides how many times player will fire his weapon? which results in bullet/fire/smoke sprites/particles. Also it's possible to have gameplay which relies on player interaction for creating new game objects. In that case it's impossible to predict a worst case scenario that won't be too big. I really don't know how can you call "statically allocating a dynamic tree" optimization. Scenegraphs are dynamic by design.

Optimizing the 'worst case' in a game does make sense.  I'm not sure why 'no body in here' should worry about optimizing their programs.

Because it's not optimizing. Somehow you convinced yourself that optimizing is only about runtime overhead which is not true. There are 2 conditions that we talk about here.
1- Implementing a static scenegraph according to worst case scenario.
CONS: Uses more memory than it should except when the worst case scenario is true.
2- Implementing a dynamic scenegraph.
CONS: Runtime overhead

So according to you spending more memory beats runtime overhead?
Show me *one* example where runtime overhead caused by dynamic memory allocation affects gameplay?

The optimum solution to implement a scenegraph is using dynamic memory allocation. In fact I'm not sure you can do it statically.

[raigan]

This is one of the first things I asked

Is the discussion archived online anywhere you could link to?  It sounds interesting!

Sadly not -- gdalgorithms archive _is_ open, but looking through my mail the actual discussion is from Sweng-Gamedev which isn't. But AFAIK it's not hard to sign up, they let _me_ in anyway

https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com

I think Alex's point was that the memory use can't grow arbitrarily in a game

Of course it can. who decides how many times player will fire his weapon? which results in bullet/fire/smoke sprites/particles.

Particles are easy: you allocate MAX_NUM_PARTICLES in a ring buffer and use those, or each particle system has its own ring buffer. You can't be claiming that your particle system can handle 10^10 simultaneous particles on-screen, right? That means there's a practical limit.

Similarly, you just need to give the player (or better, the gun) a max number of simultaneous bullets in a static cyclical buffer. Unless your game features infinite terrain in all directions, there is going to be an upper limit on the number of bullets that can be alive at once, determined by the rate of fire of the gun, the speed of the bullets, the size of the world, etc. -- or simply by an arbitrary game-designer-imposed limit as in Super Mario Bros, Asteroids, Space Invaders, etc.

Note that limits don't need to be constant, you could pre-allocate different sized buffers per level (for instance if level 1 has tons of A objects but few B, while level two has many B but few A); dev builds can use huge limits and log the max occupancy of the lists, so that you have a ballpark figure for what the actual size should be in the release build.

The optimum solution to implement a scenegraph is using dynamic memory allocation. In fact I'm not sure you can do it statically.

Ignoring for a moment that scene graphs are evil http://tinyurl.com/a9j58v, if you statically allocate nodes then you get excellent cache coherency when traversing, since the nodes are all located in the same contiguous chunk of memory. You can absolutely implement graphs statically using a fixed-size pool of nodes.. unless your use case is an infinitely large world. In which case you're going to run out of memory regardless of how you structure memory management!


My intention wasn't to start a religious war about different memory management philosophies, I just wanted to point out an alternate viewpoint that was under-represented in this thread. FYI _many_ AAA console games are using static per-level allocation, so you can't dismiss this approach offhand -- if your platform doesn't have virtual memory you do need to know exactly how memory will be used and account for the worst case.

[Zaphos]

Sadly not -- gdalgorithms archive _is_ open, but looking through my mail the actual discussion is from Sweng-Gamedev which isn't. But AFAIK it's not hard to sign up, they let _me_ in anyway

https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com

Thanks!

I imagine this stuff does make some sense for PC as well; calls to new and delete are pretty slow (if they're not overridden, since they talk to the OS?) and even though virtual memory is there, it's slow!  At least, I know some people doing real time finite element simulation stuff who were talking about avoiding allocating new stuff in the simulation loop for this sort of reason.

[Mikademus]

Never got an answer from Ivan or Core XII, which I guess mean they were convinced by my post. Either that or they disconnected before losing so as not to ruin their stats

[Impossible]

The static allocation stuff is spot on.  Dynamic allocation is not necessary for most games. You are possibly wasting memory, but you will not run out of memory either, because in you have a built in finite cap on how many objects of a specific type you can have.

That said, dynamic allocation is often convenient, and in practice you usually won't have  issues with it as long as you don't abuse it.

[Ivan]

Never got an answer from Ivan or Core XII, which I guess mean they were convinced by my post. Either that or they disconnected before losing so as not to ruin their stats

I was not convinced by anything, because there is nothing to be convinced about. The argument against dynamic allocation is completely pointless and misplaced, in my opinion. There is absolutely nothing wrong with dynamic allocation if you know what you are doing and know when not to use it, because, yes, there are times when static allocation is preferable.

Regarding your post about smart pointers. Once again, they may have their place, but I don't use them and don't really know anyone who does and everyone makes out just super, so if you like them, thats great, but I don't think they should be some golden standard.

I guess my point is that I don't see the point in this argument. You can use both static and dynamic allocation and if you use it well, you won't have any problems, just like you can use or not use smart pointers. These things are preferences of style, not dogma, and arguing about programming style is pretty pointless.

[Important]

The graphs are evil article was interesting (and definitely true) but it didn't suggest anything better? Scene graphs work very nicely for limiting what's to be rendered. I'd be interested to hear of any other data structures that are in use.

[Zaphos]

The point wasn't against graphs in general, just the idea of a scene graph that does everything.  Here's a more detailed discussion on the topic: https://mollyrocket.com/forums/viewtopic.php?t=738 ... and here's a reply to a similar question: http://www.gamedev.net/community/forums/topic.asp?topic_id=464464&whichpage=1&#3060576

[Mikademus]

Regarding your post about smart pointers. Once again, they may have their place, but I don't use them and don't really know anyone who does and everyone makes out just super, so if you like them, thats great, but I don't think they should be some golden standard. ... You can use both static and dynamic allocation and if you use it well, you won't have any problems, just like you can use or not use smart pointers. These things are preferences of style, not dogma, and arguing about programming style is pretty pointless.

I take it your argument boils down to you defending your comfort zone, which is human and understandable. However, at the core of successful programming and, borrowing Alexandrescu's (2001) term, modern C++ design, is robustness and reusability. Sure, if your program is in the range of a few hundred to thousand LoC perhaps in one or a few files, then you can get away with anything, but when you get into real software design (<-- intentionally provocative phrasing) you need solid design habits and good practices. Software design is about creating robust and efficient programs, where robust means stable with as few bugs and side effects as possible and efficient means performing with as little unnecessary overhead as possible; and where robustness > efficiency.

Let me reiterate: dynamic and static allocation are techniques. Techniques are employed. Techniques are ethically neutral. Techniques are employed in practices. Some practices statistically speaking tend to result in a higher bug count than others. Some practices entail negative (usually unintended) consequences (one example is that "Object *p = new Object; ... delete p;" is not exception-safe). Consistent practices constitute patterns. It follows that some usage patterns are thus bad practice and lead to poor software robustness, reliability and/or reusability.

If you think this sounds dull and want to believe that programming is like art, then bear in mind that the truly great artists were (are?) usually also great artisans.

[David Pittman]

The graphs are evil article was interesting (and definitely true) but it didn't suggest anything better? Scene graphs work very nicely for limiting what's to be rendered. I'd be interested to hear of any other data structures that are in use.

Forsyth mentions other rendering-related data structures like BSP trees, octrees, portal graphs, etc. His point, as I understand it, is that all of these things provide unique benefits and can't be easily replaced by just a scene graph (or anything else).

Maybe you want all your static world geometry to be rendered front-to-back (employing the z-buffer to reject occluded pixels for performance). That's a classic use case for BSP trees with surfaces in the leaf nodes (although they were traversed back-to-front in the days before the GPU and z-buffers). But small pieces of geometry can quickly generate a lot of BSP branches, and moving your dynamic entities around a complex BSP tree isn't very efficient. Then you might want to double up your spatial partitioning with a simpler portal graph, so you only have to consider entities in the context of large rooms and the windows between them. That's a much smaller graph than the BSP tree. But then once you've gathered a list of renderable entities, perhaps you want to sort them according to properties like shared materials or skeletons (to reduce state changes pushed to the GPU). These are the kinds of considerations you need to make when building an efficient engine, and a single tree structure like a scene graph isn't flexible enough to handle all these needs.

And just so this post is remotely on-topic, I'm going to agree with Toastie here. Dynamic allocation is absolutely acceptable as long as you're smart about it. Don't do it more than necessary, but don't avoid it to the detriment of code usability. For example, if you choose to not use dynamic allocation, at least be proactive in developing data structures which used pooled memory and offer the same interfaces we expect from STL containers. I once worked on a project which would assert if you tried to allocate memory at runtime and which had no templated static pooled memory lists or vectors available. It sucked.

[Ivan]

I am a big believer in the ability of an intelligent person to make their own decisions about how to do their work. I think imposed patterns of any sort are dangerous and inhibitive of critical thinking. I agree that you need solid design habits and good practices, but they need to be YOUR solid design habits, not someone else's. While there are definitely useful patterns to be adapted and shared, they constitute but a fraction of what is ultimately your own way of coming up with solutions to problems.

I do believe that programming is like art, but I believe it not because I think that it gives you an excuse not to study, but because it is a great exercise for creative thinking and critical analysis.

There is a reason some people still use C over C++. With every safeguard you place, you take something away from the awareness you, as a programmer, have of what is actually going on in your code. I may use bare pointers, but I know exactly where, when and how my objects are cleaned.

I appreciate your constant condescension, though, Mikademus.