Comments on: Alternatives to malloc and new [...] • Управление памятью: есть ли альтернативы для malloc и new? Рассказ с иллюстрациями. [...] [...] • Управление памятью: есть ли альтернативы для malloc и new? Рассказ с иллюстрациями. [...]

]]>
By: links for 2011-07-26 « Bloggitation/2011/02/12/alternatives-to-malloc-and-new/#comment-6403 links for 2011-07-26 « Bloggitation Wed, 27 Jul 2011 06:08:18 +0000 [...] there was a popular reddit post today arguing against overuse of malloc, the C equivalent of heap [...] [...] there was a popular reddit post today arguing against overuse of malloc, the C equivalent of heap [...]

]]>
By: Tweets that mention Alternatives to malloc and new » #AltDevBlogADay -- Topsy.com/2011/02/12/alternatives-to-malloc-and-new/#comment-772 Tweets that mention Alternatives to malloc and new » #AltDevBlogADay -- Topsy.com Tue, 15 Feb 2011 00:10:21 +0000 Alternatives to malloc and new [...]

]]>
By: Steven Tovey/2011/02/12/alternatives-to-malloc-and-new/#comment-769 Steven Tovey Mon, 14 Feb 2011 11:35:10 +0000 Thanks for your kind words, the question you ask is incredibly hard to answer without a lot more additional information, but I will have a crack as best I can, :) I'd probably start by checking out what types of enemies you're going to have. Are they all the same type? When you have a mass of them are they all the same or different types? This type of information is important to know. Also, how different is the behavior of each enemy type and how different is the data you're storing for each type? You need to look carefully at the data transformation you're applying for the enemy type and tailor separation of the data to this, it might end up that you only have a small amount of per-instance state. This type of analysis is pretty important to carry out before you start making calls on memory budgets and figuring out how much you're going to be wasting. Let's assume we have one type that spawns a whole bunch of instances at one particular point, but then spawns a very minimal amount later on. You could handle this in a few ways. You could go for malloc and free, this has all the drawbacks I mentioned, and will actually waste a great deal more memory in the long run due to fragmentation. The approach I would most likely advocate is to have as slim a state structure as possible for per-instance data for your enemies (of course pointing at the per-type data is implied for all the instances of this type). Then I'd probably have a static area of memory which I'd manage as a ring buffer (you just need to allocate whatever amount of enemies you require from a ring buffer, sorry I didn't cover these, maybe in the future I will). This may appear wasteful and I guess to some extent it is (depending on just how slim you were able to make that state data), but let's look at a little deeper here at the impact of this approach versus the other approach using dynamic memory. With a static memory buffer you always know just how much memory it will use at all times and you also know that it will never fail because it is unable to make an allocation, you also know where the memory is in relation to other memory for objects of the same type (with the ring buffer management scheme I mentioned you know it's actually linear, with the exception of the wrap around case, which plays nicely with caches and DMA). You don't have any of these assurances with dynamic memory allocation. In addition you have all the drawbacks associated with heap fragmentation from making many smallish allocations at run-time from your global heap. To say that dynamic memory allocation saves you memory, I think in the long run, is simply untrue it is far more likely to end up costing you as it will piss plenty through fragmentation. If you were really that worried, you could lump all the memory for your enemies into one big pool and allocate chunks capable of holding a whole bunch of enemies, that way you get bursts of local contiguity as well as not having to make that explicit division between your enemy types, within blocks you could manage the allocations linearly. The amounts will likely change during the course of development as you rebalance the needs of the game with what you physically have available to you in hardware, yes, and as TomF rightly points out in his comment the memory guy will definitely be poking around in there at the end of the project. If you don't want to do manual re-balancing, then it's perfectly possible to make all this stuff data-driven if you like (you don't just have to settle for a bunch of #define) and even have tools to visualise and design your heap offline, I have just such tools for personal projects. In addition, you can also insert tracking code into your allocators to see what levels they reach during play throughs, graphing this over time can be a very illuminating thing to do. This can be important to identify potential over-allocation in static buffers and make vital savings later on, again this stuff can all be visualised nicely (and in real-time if you so desire). For my money, it's fairly unlikely that a general purpose allocator (or indeed anything) will ever out perform a smart programmer thinking about the problems at hand and taking advantage of knowledge that he or she has in that context. If you need more sophistocated methods to make allocations then I would really try to justify them to myself before I went ahead with it. From my experience, the amount wasted from these type of approaches doesn't tend to impact things that greatly and can actually free up your content creators to do more with the resources.... And if it does start to have an impact, just have one of your artists down-res that 2048x2048 texture they used for the door knob over there ;). Thanks for your kind words, the question you ask is incredibly hard to answer without a lot more additional information, but I will have a crack as best I can, :)

I’d probably start by checking out what types of enemies you’re going to have. Are they all the same type? When you have a mass of them are they all the same or different types? This type of information is important to know. Also, how different is the behavior of each enemy type and how different is the data you’re storing for each type? You need to look carefully at the data transformation you’re applying for the enemy type and tailor separation of the data to this, it might end up that you only have a small amount of per-instance state. This type of analysis is pretty important to carry out before you start making calls on memory budgets and figuring out how much you’re going to be wasting.

Let’s assume we have one type that spawns a whole bunch of instances at one particular point, but then spawns a very minimal amount later on. You could handle this in a few ways. You could go for malloc and free, this has all the drawbacks I mentioned, and will actually waste a great deal more memory in the long run due to fragmentation. The approach I would most likely advocate is to have as slim a state structure as possible for per-instance data for your enemies (of course pointing at the per-type data is implied for all the instances of this type). Then I’d probably have a static area of memory which I’d manage as a ring buffer (you just need to allocate whatever amount of enemies you require from a ring buffer, sorry I didn’t cover these, maybe in the future I will). This may appear wasteful and I guess to some extent it is (depending on just how slim you were able to make that state data), but let’s look at a little deeper here at the impact of this approach versus the other approach using dynamic memory.

With a static memory buffer you always know just how much memory it will use at all times and you also know that it will never fail because it is unable to make an allocation, you also know where the memory is in relation to other memory for objects of the same type (with the ring buffer management scheme I mentioned you know it’s actually linear, with the exception of the wrap around case, which plays nicely with caches and DMA). You don’t have any of these assurances with dynamic memory allocation. In addition you have all the drawbacks associated with heap fragmentation from making many smallish allocations at run-time from your global heap. To say that dynamic memory allocation saves you memory, I think in the long run, is simply untrue it is far more likely to end up costing you as it will piss plenty through fragmentation. If you were really that worried, you could lump all the memory for your enemies into one big pool and allocate chunks capable of holding a whole bunch of enemies, that way you get bursts of local contiguity as well as not having to make that explicit division between your enemy types, within blocks you could manage the allocations linearly.

The amounts will likely change during the course of development as you rebalance the needs of the game with what you physically have available to you in hardware, yes, and as TomF rightly points out in his comment the memory guy will definitely be poking around in there at the end of the project. If you don’t want to do manual re-balancing, then it’s perfectly possible to make all this stuff data-driven if you like (you don’t just have to settle for a bunch of #define) and even have tools to visualise and design your heap offline, I have just such tools for personal projects. In addition, you can also insert tracking code into your allocators to see what levels they reach during play throughs, graphing this over time can be a very illuminating thing to do. This can be important to identify potential over-allocation in static buffers and make vital savings later on, again this stuff can all be visualised nicely (and in real-time if you so desire).

For my money, it’s fairly unlikely that a general purpose allocator (or indeed anything) will ever out perform a smart programmer thinking about the problems at hand and taking advantage of knowledge that he or she has in that context. If you need more sophistocated methods to make allocations then I would really try to justify them to myself before I went ahead with it.

From my experience, the amount wasted from these type of approaches doesn’t tend to impact things that greatly and can actually free up your content creators to do more with the resources…. And if it does start to have an impact, just have one of your artists down-res that 2048×2048 texture they used for the door knob over there ;).

]]>
By: anon/2011/02/12/alternatives-to-malloc-and-new/#comment-762 anon Mon, 14 Feb 2011 07:53:40 +0000 What do you mean by "assert-recover" especially with the "recover" part? What do you mean by “assert-recover” especially with the “recover” part?

]]>
By: Steven Tovey/2011/02/12/alternatives-to-malloc-and-new/#comment-748 Steven Tovey Sun, 13 Feb 2011 19:40:00 +0000 My gut feeling is, that by taking away malloc and new and restricting memory allocation to a set of allocators as presented by Steven, the programmer is forced to think about lifetime and scope of data. Flexibility is taken away so "only" simple and robust solutions become doable. What a positive side effect (at least on the engine side of games)! My gut feeling is, that by taking away malloc and new and restricting memory allocation to a set of allocators as presented by Steven, the programmer is forced to think about lifetime and scope of data. Flexibility is taken away so “only” simple and robust solutions become doable. What a positive side effect (at least on the engine side of games)!

]]>
By: Bjoern Knafla/2011/02/12/alternatives-to-malloc-and-new/#comment-746 Bjoern Knafla Sun, 13 Feb 2011 18:28:13 +0000 I think the two most important things about memory management are to realize that any decision you make now will probably need to be changed later, and it will need to be changed by someone else. That someone else is usually going to be the "memory tzar" who, near the end of the project, will get in there and tune the memory system like crazy and re-examine 90% of the memory system. They will need to change allocation schemes a lot, fiddle with every setting, and merge or split schemes (e.g. I've done things like merging a 28-byte and a 32-byte fixed-size-block system into a single 32-byte-block system).That means that every alloc/free needs to be wrapped in some way from day 1 (even if at the start, they just trivially call alloc() and free()!), and that you need to be pretty careful about supplying hints. For example, even if you "know" you're using a pool system, it's still good practice to call Free() on each block when you stop using it. If it really ends up being a pool system in the final game, those calls won't do anything (except in debug mode they fill with 0xDEADBEEF, etc). But if later someone needs to change it to some other scheme, the calls are there. Similarly grabbing from fixed-size heaps - if you really do only need 23 bytes in a 32-byte-chunk-heap, say so. Worse case the system ignores that data. But it helps monitor internal fragmentation, and later that single heap might be split into two separate heaps. I think the two most important things about memory management are to realize that any decision you make now will probably need to be changed later, and it will need to be changed by someone else. That someone else is usually going to be the “memory tzar” who, near the end of the project, will get in there and tune the memory system like crazy and re-examine 90% of the memory system. They will need to change allocation schemes a lot, fiddle with every setting, and merge or split schemes (e.g. I’ve done things like merging a 28-byte and a 32-byte fixed-size-block system into a single 32-byte-block system).That means that every alloc/free needs to be wrapped in some way from day 1 (even if at the start, they just trivially call alloc() and free()!), and that you need to be pretty careful about supplying hints. For example, even if you “know” you’re using a pool system, it’s still good practice to call Free() on each block when you stop using it. If it really ends up being a pool system in the final game, those calls won’t do anything (except in debug mode they fill with 0xDEADBEEF, etc). But if later someone needs to change it to some other scheme, the calls are there. Similarly grabbing from fixed-size heaps – if you really do only need 23 bytes in a 32-byte-chunk-heap, say so. Worse case the system ignores that data. But it helps monitor internal fragmentation, and later that single heap might be split into two separate heaps.

]]>
By: Steven Tovey/2011/02/12/alternatives-to-malloc-and-new/#comment-738 Steven Tovey Sat, 12 Feb 2011 13:13:29 +0000 Great article, Ste! I've seen too many instances of developers not understanding the true costs and implications of using malloc & friends.And yes.. alloca() or other can be more effective for temporary allocations - but if you're using these while developing libraries (internal, middleware, etc..) then quite often it's worth thinking again. Or if you're doing alloca()-style calls in threads. Or if you're in a callback/interrupt handler. In these situations stack space is not necessary plentiful or the amount of stack you run with is not under your control - so extra care should be taken. And yeah, what Tony said.. It's nice to see SCEI's coding standard affecting your brace style.. ;-) Great article, Ste! I’ve seen too many instances of developers not understanding the true costs and implications of using malloc & friends.And yes.. alloca() or other can be more effective for temporary allocations – but if you’re using these while developing libraries (internal, middleware, etc..) then quite often it’s worth thinking again. Or if you’re doing alloca()-style calls in threads. Or if you’re in a callback/interrupt handler. In these situations stack space is not necessary plentiful or the amount of stack you run with is not under your control – so extra care should be taken. And yeah, what Tony said.. It’s nice to see SCEI’s coding standard affecting your brace style.. ;-)

]]>
By: James Podesta/2011/02/12/alternatives-to-malloc-and-new/#comment-736 James Podesta Sat, 12 Feb 2011 11:57:26 +0000 Very good article, breaks down the information nicely! I am pretty sure many do know about this as well, but i will link it for related info : Great stuff Steven. In addition to the fragmentation caused by over use of allocation there is another drawback. Performance. Standard new and malloc (even dlmalloc) are slow and cN have a dramatic performance impact. Linear allocators are perfect for many cases where fast allocation is required. Kudos on providing code too. Although all your curly brackets are on the wrong line. Great stuff Steven. In addition to the fragmentation caused by over use of allocation there is another drawback. Performance. Standard new and malloc (even dlmalloc) are slow and cN have a dramatic performance impact. Linear allocators are perfect for many cases where fast allocation is required. Kudos on providing code too. Although all your curly brackets are on the wrong line.

]]>
By: Julien Hamaide/2011/02/12/alternatives-to-malloc-and-new/#comment-733 Julien Hamaide Sat, 12 Feb 2011 09:50:16 +0000 Instead of using "alloca", some compilers provide "malloca", which allocates space on the stack below a certain size threshold, and on the heap otherwise. And if the compiler does not provide it, it is trivial to implement. That's one more conditional jump though. Instead of using “alloca”, some compilers provide “malloca”, which allocates space on the stack below a certain size threshold, and on the heap otherwise. And if the compiler does not provide it, it is trivial to implement. That’s one more conditional jump though.

]]>
By: grrussel/2011/02/12/alternatives-to-malloc-and-new/#comment-731 grrussel Sat, 12 Feb 2011 09:25:28 +0000 may be a performance win for little effort.Another technique is simply to reduce the number of heap allocations for dynamic data structures by using containers that allocate up to N elements internally, before using heap allocated storage e.g.
If you have your own implementation of malloc/new it is also helpful to be able to manage multiple heaps with different scope and lifetime. Even something as simple as a separate heap or stack allocators for short lived temporaries can help a lot to avoid polluting and fragmenting your heap.To go further on those topic, there is an excellent presentation by Andreas Fredriksson of DICE titled “Scope Stack Allocation” that you can find on their publication website. @Chris, I wanted to provide code, I was inspired by the research takes better with source post on this very blog. Great point re: variable length arrays, thanks for linking to it :) C99-coders represent! :)@Dylan, I think you're right, the only problem is that no matter what you expose malloc and new to in terms of metadata about the allocation there could always be a better allocation scheme devised by an individual in the know w.r.t the system at large. It's basically the same argument about asm vs. higher-level languages. I think the keyword in your summary is "fairly", i.e: it probably could be made to work with the majority of allocations in a more or less sane fashion. @Chris, I wanted to provide code, I was inspired by the research takes better with source post on this very blog. Great point re: variable length arrays, thanks for linking to it :) C99-coders represent! :)@Dylan, I think you’re right, the only problem is that no matter what you expose malloc and new to in terms of metadata about the allocation there could always be a better allocation scheme devised by an individual in the know w.r.t the system at large. It’s basically the same argument about asm vs. higher-level languages. I think the keyword in your summary is “fairly”, i.e: it probably could be made to work with the majority of allocations in a more or less sane fashion.

]]>
By: Dylan Cuthbert/2011/02/12/alternatives-to-malloc-and-new/#comment-288 Dylan Cuthbert Sat, 12 Feb 2011 02:51:31 +0000 Great article! Love that there’s code, too :)One tiny addition on stack-based allocation, C99 also provides variable-length arrays: