[opensource-dev] Script Memory Management Algorithm

[Lear Cale]

If it were a simple change, I'm sure it would be considered.  What
you're suggesting sounds like would require a massive rewrite.  I
agree that a dynamic system would be much better, easier to code and
less wasted memory.  But without detailed knowledge of how the system
is currently implemented, it's not possible to assess how difficult it
would be to change from a fixed allocation scheme to a dynamic one.

It's easy to ask for changes without regard to the cost.  LL needs to
consider the cost, in terms of effort and risk.  Can you do a
cost/benefit analysis on your suggestion?  Or are you just being
immovably stubborn?

Lear

On Tue, Mar 9, 2010 at 8:26 AM, Carlo Wood <carlo at alinoe.com> wrote:
> This is exactly the kind of reaction that drives me away from here.
>
> I propose a simple way get FOUR times the memory for all the scripts, at
> no other cost than adding some malloc code to your mono engine.
>
> And you simply say, "This is what we ARE doing, we're not going to change that".
>
> Why this immovable stubbornness about internal development decisions?
>
> In case with the below you mean to say "allowing people to set ammount
> of memory at which their scripts crash, up front, is as good," then
> read the past posts on this list again.
>
> People say that it is NOT, by FAR not, as good. Scripters shouldn't
> have to manually figure out the maximum ammount of memory their scripts
> can possibly use and use that as the fixed ammount of memory that
> their script reserves. That was last done 10 years ago. Just have the
> server take care of this: give a script a minimum, and when it needs
> more, give it more. No hassle for the users.
>
> On Mon, Mar 08, 2010 at 09:46:44AM -0800, Kelly Linden 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
>>
>>
>
> --
> 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
>