[opensource-dev] Script Memory Management Algorithm

Kelly Linden kelly at lindenlab.com
Mon Mar 8 09:46:44 PST 2010


We are not out to write a new malloc for mono.  What we have is a system
that throws an exception when the memory used by the script hits a certain
threshold (64k currently).  This exception is caught so we can "crash" the
script.  The future small scripts and big scripts projects will add new
functions to set and get this threshold value, allowing scripters to
effectively control how much memory is reserved for their script.  We will
continue to use mono's default memory management within the reserved memory
thresholds.  It is a much simpler problem to solve.

 - Kelly

On Sun, Mar 7, 2010 at 5:50 AM, Carlo Wood <carlo at alinoe.com> wrote:

> Lets assume that the *average* script uses
> 8 to 16 kB of real memory. LL's design allocates
> 64 kB regardless, leading to an overhead of
> 400 to 800% (meaning they need to buy 5 to
> 9 times the memory that is theoretically needed).
>
> In that light, I gave it some more thought, and
> think something as complex as my rmalloc's algorithm,
> with it's 19% overhead, isn't needed (note that
> it's both faster than gmalloc as well as three
> times more efficient; so complexity is not always
> a bad thing ;).
>
> Nevertheless, in this case, since the scripts
> use a maximum of 64 kB, you can use the
> following design:
>
> Let each allocated block be a power of 2
> kilobytes, with a maximum of 64 kB (and a
> minimum of 1 KB, or 4 if even the tiniest
> script needs that).
>
> It is easy to see that this would lead
> to an overhead of 25% on average per
> allocated block.
>
> We'd still have to deal with "holes" of a
> full 64 kB where blocks became totally
> unused, but normally scripts in objects are
> started all at once when a sim reboots, and
> only seldom stopped. The scripts that will
> most likely attribute to random starting
> and stopping of scripts will be the scripts
> in attachments. A worst case scenario would
> be one where there are 50 avies in a sim
> (during a meeting), then a new avie enters
> with some scripts which need to be allocated
> at the top of the heap; then the previous
> 50 avies leave. That would create a hole
> in the heap of the size of all the scripts
> of those 50 avies. If script memory would
> be relocatable, then this problem doesn't
> exist of course. I can't simply estimate
> the average overhead caused by this, but
> because the algorithm described here is
> basically the one used by gmalloc (which
> in my test used 62% overhead) I'm pretty
> sure that it will be less than -say- 100%
> overhead; still 4 to 8 times more efficient
> than the current design on the table.
>
> The API for this design would be something
> like the following:
>
> namespace script_memory_management {
>
> void* ll_sbrk(ptrdiff_t);       // Increment the size of the heap
> int   ll_brk(void*);            // Set the size of the heap explicitely
>
> void* ll_malloc64(void);        // Get a new 64 kB block.
> void  ll_free64(void*);         // Free such a block.
>
> void* ll_malloc(size_t s);      // Allocate s bytes of memory for a script.
> void  ll_free(void*);           // Free it again.
>
> ...
>
> Assuming here that scripts cannot deal with
> relocation, otherwise one should also have:
>
> void* ll_realloc(size_t s);     // Allocate a different size of memory.
>
>
> ll_malloc then will round the number of requested bytes up
> to the nearest power of 2 (kBs) and retrieve a block from one
> of the free lists (maintained for 32, 16, 8, 4, 2 and 1 kB)
> (note that if scripts only seldom use 1 or 2 kB it might
> be more efficient to use a minimum of 2 or 4 kB instead of 1).
>
> Each 64 kB block would contain either one 64 kB allocation,
> or two 32 kB block allocations, or four 16 kB block allocations,
> etc, but never allocations of mixed sizes, thus making it
> easy to find a free block of such size.
>
> A free list is usually maintained by adding pointers inside
> the (unused) memory blocks, linking them together to a linked
> list of free memory blocks of a given size. That causes allocating
> to be instant, but freeing memory requires to traverse this
> list in order to update it's pointers. With the number of
> scripts that normally run in a sim this will not be a problem.
>
> --
> Carlo Wood <carlo at alinoe.com>
> _______________________________________________
> Policies and (un)subscribe information available here:
> http://wiki.secondlife.com/wiki/OpenSource-Dev
> Please read the policies before posting to keep unmoderated posting
> privileges
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.secondlife.com/pipermail/opensource-dev/attachments/20100308/a3e47b2c/attachment.htm 


More information about the opensource-dev mailing list