#166733 - Schala - Mon Feb 16, 2009 4:36 am
I know for PC programming, it's better to use the stack for simple data and the heap for complex structures and what not. However, for GBA programming, I'm rather concerned about using the heap for such stuff. Is it okay to use the heap for structure/class instances on GBA?
#166735 - Dwedit - Mon Feb 16, 2009 5:50 am
The stack is inside IWRAM, which is 32KB total to be shared among the stack, global variables, and high performance code intentionally placed in IWRAM.
The heap is inside EWRAM, which is 256KB total. If your game is a Multiboot game which runs without a cartridge, then it is shared with your code. Otherwise, it's all free for any heap use, or you can also statically allocate variables there using special declarations.
The only problem with the heap is that malloc and free suck. It's sensitive to the order things are allocated and freed. If you allocate something big, then allocate something tiny, then free something big, your memory doesn't come back until you've freed the tiny thing. Horrible fragmentation issues there.
_________________
"We are merely sprites that dance at the beck and call of our button pressing overlord."
#166736 - Schala - Mon Feb 16, 2009 6:02 am
So I should use EWRAM for instantiation as opposed to malloc/free?
#166739 - elwing - Mon Feb 16, 2009 9:24 am
never looked at memory fragmentation, but if malloc/free are really so bad on the GBA someone surelly wrote a new memory allocator, no?
#166745 - Pete_Lockwood - Mon Feb 16, 2009 1:26 pm
By default, malloc and free have the potential to be bad. Libraries exist which do their best to improve things (recommended reading: http://g.oswego.edu/dl/html/malloc.html and it's possible something similar is used by devKitPro) or if you're using malloc and free a lot and know the dynamics of your program well enough you can usually optimize allocations for your specific case.
_________________
It's not an illusion, it just looks like one.
#166747 - elwing - Mon Feb 16, 2009 2:21 pm
quite interesting article, I've read something looking like that in game programming gems7 trough they only use bins for small allocation and work using tree for bigger allocation, now my question underneath was not how to program an allocator, but is there a good one floating around?
#166750 - gauauu - Mon Feb 16, 2009 4:17 pm
For relatively simple games, I've found that it's often easier to allocate big hunks of memory up front, and doing your own custom memory management from those hunks.
Simple example:
In my game, you can have at most 40 "character" objects at once. So up front, I allocate an array of 40 character objects. I then manage which ones are active, and when a new one is needed, return one of the inactive ones. I never need to allocate more memory for them, and I never need to free the big hunk of memory (since the game never really exits)
This only works in fairly simple programs, where you're not needing to allocate/free tons of different objects all over the place.
#166752 - sgeos - Mon Feb 16, 2009 4:25 pm
Even for games of medium complexity you can make multiple game state structs that contain large numbers of arrays for various things. I suppose you could even make a union of game state structs, or a game state struct that contains unions (or both) and manage things that way.
#166763 - Schala - Tue Feb 17, 2009 1:40 am
So... what? malloc/free is okay to use for large games?
#166765 - gauauu - Tue Feb 17, 2009 2:54 am
| Schala wrote: |
| So... what? malloc/free is okay to use for large games? |
It's "okay" to use anywhere. But avoiding the performance hits, unpredictability, or hassle of normal memory management often makes it worth finding other solutions. Those other solutions are simpler in simpler projects.
With any size project, you'll want to think through how you want to manage memory, and implement it with whatever method seems the best.
#166766 - Schala - Tue Feb 17, 2009 3:01 am
Well, you mentioned EWRAM/IWRAM. Any method for those?
#166768 - sgeos - Tue Feb 17, 2009 4:22 am
| Schala wrote: |
| So... what? malloc/free is okay to use for large games? |
On a portable where malloc can fail, I'd say avoid it whenever you can. When can't avoid it, tred with extreme caution (and always, always check the return status of malloc). Memory related bugs are often strange and hard to track down.
#166770 - eKid - Tue Feb 17, 2009 4:33 am
You don't really need to worry about malloc unless you're allocating very large buffers, or large arrays of objects. I got away with using malloc/free everywhere in my gba game, which was a multiboot game with only 16-32k of ewram remaining.
#166771 - sajiimori - Tue Feb 17, 2009 5:51 am
We use tons of heap allocation on our DS games. We don't check the results of memory allocations; we assert inside the allocator.
Since assets have to be copied to main RAM on the DS, it's not uncommon to be left with little more than 256K of general-purpose working memory, just like we'd have on GBA.
Our memory optimizations are rarely in the form of "pre-allocate an array of X character structs" and usually more like "aggressively destroy off-screen objects".
#166793 - sgeos - Wed Feb 18, 2009 9:07 am
| sajiimori wrote: |
| We use tons of heap allocation on our DS games. We don't check the results of memory allocations; we assert inside the allocator. |
I'm under the impression you are using custom memory allocation routines. Either way, you need to be sure you actually get memory the memory you ask for.
#166805 - Miked0801 - Wed Feb 18, 2009 6:00 pm
Umm, all memory allocation routines are pretty much custom on the DS/GBA right? :)
And if you don't get memory you ask for, your screwed in just about every case. When we create a system where memory allocation is a maybe, we set aside a special pool or heap just for that memory and have special case fail code only for it, otherwise just assert fatal and find the memory leak. Memory allocation is already one of our slower tasks, no need to burden it further if there is no need.
#166810 - sajiimori - Wed Feb 18, 2009 10:39 pm
There's only one way to guarantee that you always get the memory you ask for: Never ask for memory that isn't available! ;)
#166812 - sgeos - Thu Feb 19, 2009 3:30 am
You can ask for memory that is available, but not in a continuous block. Ie, fragmentation can be a killer. Hence the statically allocated arrays some people use. Either you get the memory every time, or you do not ever get it.
IIRC, some of the old NES games failed to spawn things if there were already too many objects in play. This solution could be used even yet, although there certainly are other uses for dynamically allocated memory that can not just fail.
#166813 - elwing - Thu Feb 19, 2009 9:40 am
hum, so there is no "bins" based allocator as the one described by Dimitar lazarov in game programming gems7 in the abstract "High Performance Heap allocator"? looks like something interesting to write...
#166825 - Miked0801 - Thu Feb 19, 2009 6:26 pm
Again, you can ask for a large, contiguous chunk of memory, but if you're doing things that fragment ram, you had better ask for them early before they get gobbled. Then you are indeed getting into a bin type system.
Anyways, iff one is a little bit careful, you can usually avoid massive memory fragmentation. Swap trick your stl containers when done or not in use, try to allocate and free stuff in without other allocs in the middle, etc.
Or, just try not to code things that take contiguous memory. It's a lot easier to find space in a somewhat fragmented heap for 10x20k blocks than 1 200k block. I find myself doing optimizations like this more than preallocate and pray.
#166841 - sajiimori - Fri Feb 20, 2009 3:40 am
Exactly. "Don't ask for memory that isn't available" can mean "make more memory available" or "don't ask for so much."
I hate being super careful everywhere, under threat of failed allocation. I'd much rather ask for less contiguous memory, and make special accomodations for large allocations that would otherwise be at risk of failure.
Those "special accomodations" are pretty much always for assets, so it's not even an issue on GBA. A single general-purpose heap is all I would use on GBA.
If you have super large C++ objects (over 5k or so), by all means, split them up! Hold some data members by reference, and allocate them separately. There's no need to require so much contiguous memory.
If you still get a failed allocation, even when your objects are small, then either you're truly out of memory, or you have a sadistic fragmentation problem the likes of which I've never seen.
And if you're truly out of memory, you would have ran out much sooner using preallocated buckets, because preallocation is inherently wasteful -- it's basically a way to "pay off" the fragmentation troll to make it go away.
Edit: That's not to say I never pay off the fragmentation troll. I opt to waste memory on a large music heap, which is always partially unused, because I don't want to think about whether a particular song is going to use too much memory and cause some other allocation to fail. I want to pay for music and forget about it.
#167235 - keldon - Fri Mar 06, 2009 6:07 pm
I've written some [basic] memory management algorithms with the following properties:
| Code: |
/*
*
* \brief The DYNAMIC_IDX_ALLOCATOR allocates 'offsets' with an associated
* size very much the same way that <code>malloc</code> will allocate
* a pointer. This class can be used an implementation for dynamically
* allocating memory.
*
* The DYNAMIC_IDX_ALLOCATOR preallocates all operational memory,
* providing it with predictable space and time requirements.
* Allocating operates in O(N) and deallocating memory operates in O(1) time.
*
* The implementation allows a limited number of allocations set at
* compile time though the SIZE template argument. The allocations can
* span any space using those allocations, for example a 2GB space
* could [in theory] be managed by an implementation that only allows
* 128 allocations.
*
* The template implementation takes three parameters; the SIZE
* determines the maximum number of allocations, OFFSET_TYPE
* is the data type returned for allocations of offsets, whilst
* the IDX_TYPE is the type used to reference the internal
* allocations. IDX_TYPE must be able to represent SIZE, whilst
* OFFSET_TYPE must be able to represent the size specified in either
* the constructor or <code>init_memory_space()</code>.
*
* sizeof(DYNAMIC_IDX_ALLOCATOR<SIZE,OFFSET_TYPE, IDX_TYPE>) can be calculated as
* such:
* - sizeof(MEMORY_BLOCK[SIZE]) + sizeof(ALLOCATOR) + sizeof(size_t)
* > sizeof(MEMORY_BLOCK) == sizeof(OFFSET_TYPE)*2
* > sizeof(ALLOCATOR) == sizeof(IDX_TYPE)*(SIZE+3)
* - Which is an accumulation of:
* > sizeof(OFFSET_TYPE[SIZE*2]) ## MEMORY_BLOCK
* > sizeof(IDX_TYPE[SIZE+3]) ## ALLOCATOR
* > sizeof(size_t) ## size
* - Which is equal to:
* > sizeof(OFFSET_TYPE[SIZE * 2]) + sizeof(IDX_TYPE[SIZE + 3]) + sizeof(SIZE_T)*/ |
I've not long updated my algo to use a partitioned set that is iterable so the commenting is very out of date (well, non existant now <_<). I use it for allocating sprite/bg names - it does take up a fair amount of space, but its predictable and preallocated!
Recently moved home and haven't sorted out my own connection just yet, but if anyone is interested ... I may upload it.
Edit: correct wrong description of deallocation speed.