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 <ca...@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
