From: Eric Mahurin <eric_mahurin@...>
Date: 2005-09-16T01:28:46+09:00
Subject: Re: array sharing

--- mathew <meta@pobox.com> wrote:

> Eric Mahurin wrote:
> 
> >The first #unshift would malloc some extra capacity to the
> left of the array just
> >like is done now to the right of the array.
> >
> 
> You can use realloc to make an existing allocated chunk of
> memory 
> larger, but it always extends rightwards. How do you allocate
> extra 
> capacity to the left of an allocated chunk?

What I was thinking was that the first #unshift would yield
something like this:

     X X X X X A B C D ... X X X X X X X X X X
    ^         ^           ^                   ^
shared->ptr  ptr     &ptr[length]   &shared->ptr[shared->capa] 
  

Following unshifts would simply decrement ptr and put in a new
value - until ptr reached shared->ptr.  You'd realloc
shared->ptr when you used up your left capacity.  As long as
the excess capacity allocated is a percentage of the current
length, you'll only need to realloc once every O(n) operations
(just like push), so the average is O(1) performance.

This is similar to what #shift does now.  The difference is
that shift doesn't need to make any data modifications to the
"shared" array.  What I'm asking for is to have two modes for 
this shared array - non-modifiable (multiple objects use it)
and modifiable (one object uses it).  Anybody see any issues
with that?

> i.e. is your solution portable?

I see no reason why not.  I was thinking of other solutions
that may not be though - filling the empty (excess capacity)
elements with 0 and searching for the first non-zero element
which should be the malloc header (I think - don't know the
malloc details).

Another portable solution would be to have a couple flags for
whether you have any extra left capacity and right capacity. 
If you do have any extra capcity, store the remaining capacity
in the element immediately to the left or right of the array:

So instead of:

     X X X X X A B C D ... X  X X X X X X X X X
              ^           ^                   

you'd have:

     X X X X 5 A B C D ... 10 X X X X X X X X X
              ^           ^                   

left_free = FL_TEST(ary, FL_LFREE) && ary->ptr[-1];
right_free = FL_TEST(ary, FL_RFREE) && ary->ptr[ary->length];

I'm not sure, but you may even be able to get rid of the "aux"
field (shared/capa) and remove a long/pointer of overhead from
Array.  It looked like you mainly needed to know whether the
data was shared not pointer to the shared data.

I like this solution better (symmetrical push vs. unshift,
simpler, probably more efficient), but I realize it is a big
change and would require a complete rewrite of array.c.

I still don't understand how ruby does garbage collecting (from
the mallocs/reallocs of the array data mainly), so maybe I'm
not getting something.



		
__________________________________ 
Yahoo! Mail - PC Magazine Editors' Choice 2005 
http://mail.yahoo.com