Re: How to best solve fragmentation issues

["alex.mania@..." <alex.mania@...>]

On Wed Feb 20 20:30 , 'Jens Andersson' <lists@collectingsmiles.com> sent:

>I've integrated LUA into a Nintendo DS project and are starting to run into
>problems with memory fragmentation. In my application I load some very large
>images where I need big continuous blocks of memory from the ~3Mb I have
>available. LUA's dynamic memory allocation seems to be one of the
>troublemakers. I found the lua-functions where I can specify my own
>allocation routines and my current thinking is that I could make LUA use a
>separate heap. I'm not really looking forward to implement a separate
>memory-manager, but this way the LUA allocations won't interfere with the
>rest of the memory.
>
>Is there a better way to solve this?
>
>Thanks,
>
>/Jens

If there's no way you can combine smaller tables in to a larger table, there's
not too much you can do. It's normally up to the allocator to be able to cope
with fragmentation, which on most systems is fine... apparently the DS is a bit
weak there.

Building an allocator is hard work though. You would be far better off to the
search the net for C allocators, I'm sure you'd find dozens in seconds.

Failing that, I would recommend just building a small block allocator. Anything
larger then say, 2K, simply pass through to the standard C alloc. That keeps
things simple. For an example of good small block allocator, I would recommend
reading the open source fastmm docs, for Delphi. I found the readme on the net
here: http://bbs.et8.net/bbs/showthread.php?t=746596, not far down the page. It's
the fastest allocator I know of for tiny/small blocks, and doesn't suffer from
fragmentation.

Basically, it only attempts to allocate out according to a certain granularity
(eg a 5 byte alloc might be satisfied from an 8 byte block) which allows it to
keep free lists of every single block size. By always allocating large chunks of
small blocks at a time, and maintaining bit fields for which small blocks are
free inside the large chunks, quick allocation can be performed. It simply
requires checking the free list, and then performing a bit scan to find a free
block, and then finally removing the pool from the free list if it was the last
block. Freeing a block simply requires setting the bitfield, and adding the pool
to the free list if required.

Anyway, hope something in there helped.
-Alex