#170298 - Jesse - Wed Sep 16, 2009 7:29 am
I'm running extremely tight on memory in my app and I suffer from fragmentation issues. The problem is that I keep tabs of all allocations and there shouldn't be any that could cause this. Running the app in my PC testbed where I written nice memory tracking tools gives me nothing, so I suspect that there is some low-level DS allocation that messes things up.
On PC I'm using the _CrtMem toolset to create hooks in the memory manager. Is there something similar available on the DS, allowing me to log individual memory allocations?
_________________
http://www.collectingsmiles.com/colors & http://www.collectingsmiles.com/hyena
#170303 - Dwedit - Wed Sep 16, 2009 1:43 pm
My experience is that malloc on the ds royally sucks, and basically never frees anything until everything after it is freed as well.
I saw the case where you allocate a big buffer, then a small object, then free the big buffer never relinquished the memory until you also freed the small object.
If there's a way you can change the order of your memory allocations, then try that.
_________________
"We are merely sprites that dance at the beck and call of our button pressing overlord."
#170306 - kusma - Wed Sep 16, 2009 2:52 pm
You could try to replace stdlib's allocator with something like nedmalloc...
#170307 - Miked0801 - Wed Sep 16, 2009 2:58 pm
Lol. Dwedit, you just described memory fragmentation :)
Yes, the memory is freed, but it is in small little chunks and cannot be used. There are many ways to fight fragmentation:
1. Pre-allocate memory pools for like sized, like lifetime objects. If you have 100, 256 byte structures that come in and out of memory all the time, allocate a pool for them once and let them idle instead of freeing - or create a seperate malloc pool just for them.
2. Allocate based on lifetime. If something lives for a whole level, allocate it first. If something jumps in and out of memory all the time, allocate it last. The exception to this is 1 shot, large buffers (such as decompression buffers). They may need to be allocated earlier while memory is still available, just don't allocate anything else while they still live or you ruin memory.
3. Allocate in smaller chunks. It's a lot easier to fit 10 50k chunks in memory than 1 500k chunk. There is a little overhead associated with this, but better to spend an extra 9 32 byte headers and some extra search time than to run out of space.
If all else fails, trace yoru malloc tree and see where the fragmentation exists. It could just be a single, small object that you think is dying, but never goes away. Or my favorite, a Vector or other STL container this is cleared of all objects, but still leaves behind a few bytes of overhaed polution that must be swap tricked away.
On the PC, this is all hidden from you...
#170315 - Jesse - Wed Sep 16, 2009 4:20 pm
Thanks for all the responses.
| Miked0801 wrote: |
| On the PC, this is all hidden from you... |
No, not really. I've hooked in to the memory manager and keep good track of every little allocation (like the std::string thing that I had to hit with a hammer multiple times for it to release it's memory).
| Miked0801 wrote: |
| Yes, the memory is freed, but it is in small little chunks and cannot be used. |
Exactly. I can track both "free memory" and "biggest free block" on the DS, and it's the second one I have problem with.
| kusma wrote: |
| You could try to replace stdlib's allocator with something like nedmalloc... |
Thanks. I'll look into that. If nothing else, with compiling the source manually, I should be able to log some things as well.
| Miked0801 wrote: |
| If all else fails, trace yoru malloc tree and see where the fragmentation exists |
This is what I was looking for. How is this done?
_________________
http://www.collectingsmiles.com/colors & http://www.collectingsmiles.com/hyena
#170321 - Miked0801 - Wed Sep 16, 2009 6:25 pm
Ok, you have a clue then :)
Most malloc implementations I've seen are linked lists. They usually have a free list and a used list. You can grab a debugger and start manually walking the free list to see where the gaps appear in your memory. You can also walk the used list to see where (and if you have some sort of debug tag what) things are resident.
Or write a utility to do this for you and output a list of all available contiguous blocks of RAM off a button press or out of memory assert. This type of functionality is key to decent embedded system memory management. I'm a little surprised that your canned malloc doesn't have something like this already.
Also, keep track of your biggest and largest blocks to see exactly when they are getting hosed. This can point to what the culprit is. A break point in malloc and free with a notebook to write down addresses and sizes is tedious, but is the best way to exactly trace memory usage if you don't have a tracing system already built.
#170333 - Jesse - Thu Sep 17, 2009 3:19 am
| Miked0801 wrote: |
| You can grab a debugger and start manually walking the free list to see where the gaps appear in your memory. |
I don't really have a debugger (which I sort of enjoy in a kind of perverted way). :)
| Miked0801 wrote: |
| You can also walk the used list to see where things are resident. |
Ok. Dumping that info to disc and do diff's on a couple of those should hopefully help (and that's basically what I've been doing on the PC). I still don't really have a starting point for where to look for how the memory blocks are defined on the DS (to be able to step through the memory block list and know their sizes), but I'll start with digging through the malloc headers.
_________________
http://www.collectingsmiles.com/colors & http://www.collectingsmiles.com/hyena
#170336 - Miked0801 - Thu Sep 17, 2009 7:10 am
Yep - check your malloc implementation. I'm willing to bet it is just a linked list or two.
#170342 - Dwedit - Thu Sep 17, 2009 2:27 pm
Isn't it just the Newlib malloc?
_________________
"We are merely sprites that dance at the beck and call of our button pressing overlord."
#170367 - headspin - Sat Sep 19, 2009 2:24 pm
Something else to consider when developing on the DS is using compression. I recommend adpcm compression for samples, lz77 for graphics (these are both supported by hardware decompression) and for other types of data it's worth taking a look at ndszlib.
Compression can save alot of space, for example a game Flash is working on at the moment using zlib compressed xm's saved 0.63 MB of RAM which is quite substancial for the DS.
Also consider having set buffer sizes rather than malloc'ing and "new"ing data all the time or make sure you only "new" objects once at the start of your game.
_________________
Warhawk DS | Manic Miner: The Lost Levels | The Detective Game
#170372 - wintermute - Sun Sep 20, 2009 3:22 am
| headspin wrote: |
Something else to consider when developing on the DS is using compression. I recommend adpcm compression for samples, lz77 for graphics (these are both supported by hardware decompression) and for other types of data it's worth taking a look at ndszlib.
|
Not really sure how compression relates to malloc logging and memory fragmentation tbh. I'm also confused by the existence of something called ndszlib when zlib compiles OOB with devkitARM
| Miked0801 wrote: |
| Or my favorite, a Vector or other STL container this is cleared of all objects, but still leaves behind a few bytes of overhaed polution that must be swap tricked away. |
Do you have any examples of that, Mike? That sounds rather interesting.
devkitARM uses the standard dlmalloc found in Newlib. See http://gee.cs.oswego.edu/dl/html/malloc.html for design details. There's also a link to a malloc tracer from the Doug's main page at http://g.oswego.edu/dl/
_________________
devkitPro - professional toolchains at amateur prices
devkitPro IRC support
Personal Blog
#170385 - Miked0801 - Sun Sep 20, 2009 7:18 pm
I can show you what I have to fight when trying to kill fragmentation with STL stuff indirectly:
Allocate a bunch of memory. Create an empty Vector and check your memory. Add a few objects to it. Remove them. Now, go ahead and clear the vector so that it releases its memory. You will find a few bytes left behind in memory. This has been well documented. The only way that I've heard of fixing this is to use the STL swap function to swap a brand new empty vector for the older one. This frees the memory completely. I'm not at a point where I can place direct source to show this in detail, but if you google 'C++ swap trick', you'll get the idea.
#170387 - sajiimori - Sun Sep 20, 2009 8:00 pm
Every STL implementation I've seen just destructs the objects when clearing a vector, and only frees memory in the container's destructor. This is better than freeing memory opportunistically because it allows the programmer to choose when the memory is freed, rather than freeing it anytime the number of elements happens to drop to zero.
Dwedit, if you can prove that freeing a large buffer doesn't actually relinquish its memory, you should report it as a bug: the memory should absolutely be available to you immediately. If it's just that you have a 1 byte allocation in the middle of the heap, then yeah, obviously you cut your largest contiguous block in half. This has nothing to do with the quality of malloc and everything to do with your own decisions. Malloc can't force you not to do that.
That said, the best approach is to design your programs so it doesn't matter if there's a byte in the middle of your heap. Minimize your need for large contiguous blocks, and make special accomodations (such as preallocation) for those you can't eliminate. General-purpose allocations should be kept under 10k, at which point fragmentation is unlikely to be very important.
Edit: In practical terms, anytime you allocate 100k, you should be asking: How can I guarantee, now and forever, that this allocation can't fail, no matter what kind of pathalogical fragmentation is going on in the general-purpose heap?
(Or rather, if it fails, then it's just because the assets are too large, as opposed to a technical problem. Print a nice error message in that case.)
#170395 - sverx - Mon Sep 21, 2009 9:30 am
| sajiimori wrote: |
| In practical terms, anytime you allocate 100k, you should be asking: How can I guarantee, now and forever, that this allocation can't fail, no matter what kind of pathalogical fragmentation is going on in the general-purpose heap? |
Yes... so that's why I allocate those big buffers right in the beginning and never deallocate them if I know I'll need them again...