[opensource-dev] Script Memory Management Algorithm

[Marine Kelley]

I'm naive here, I don't know the server side of it. But how can a sim  
know when a script hits a threshold, and not be able to report the  
actual memory used ? Since it can check it against a threshold...



On 8 mars 2010, at 18:46, Kelly Linden <kelly at lindenlab.com> wrote:

> 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
>
> _______________________________________________
> 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/20100309/3f0929fc/attachment.htm