------art_11886_23296308.1159155438268
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

On 9/24/06, Yukihiro Matsumoto <matz / ruby-lang.org> wrote:
>
> Hi,
>
> In message "Re: Array shift bug"
>     on Mon, 25 Sep 2006 01:09:10 +0900, "Eric Mahurin" <
> eric.mahurin / gmail.com> writes:
>
> |This was one of the issues I was addressing in a patch I made a year ago:
> |
> |http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-core/5861
>
> I have somehow missed to check your patch.  Let me consider the pro
> and cons of your modification.
>
>                                                         matz.
>
>
Here is a quick summary of what I did:

* used 2 unused flag bits for designating whether there is free space before
and after the array data.  Then, the first positions outside of the used
data will be a count of the excess capacity in that direction.  I'm sure
there are other ways to do this, but this was the only way I could think of
that wouldn't use any more memory than is used now.  And, it also freed up
ary->shared for dedicated use (union with ary->capa not needed anymore).

* used ary->shared to put master and slave (slice of master) arrays in a
circular linked list so that the master could access all slaves and any
slave could access the master (and other slaves).  The master will have
ELTS_SHAREDand the slave will have ELTS_SHARED  Again, there may be
better ways to do this, but this way gives the same memory footprint.

* Before a slave is modified, its data is copied and sharing with its master
data ceases.  Before a master is modified (or freed), the data for all of
its slaves are copied and the sharing ceases.  In the current ruby (last I
checked), the master data is copied before being modified instead.  The
slave(s) continue sharing with the original data.  I would consider that
implementation "leaky", because the majority of that original data is not
used anymore (just a slice of it).

* made various functions that insert or delete (shift, unshift, insert,
delete_at, slice, etc) do so toward the closest side of the array.
Inserting or deleting on the first half of the array would use or add
capacity in the space before the array data.  On the second half capacity
after the array data would be modified.  Also, when extra capacity is needed
on either side, the array is reallocated with the new capacity on that side
being relative to the current array size.  This makes all insert delete
operations near either end of the array amoritized O(1) operations.

The primary cons I know for these changes are:

* C extensions will need to be recompiled in the array structure changed.

* risk.  These are significant changes.  There may be hidden bugs.

I haven't looked at this stuff in a while.  I haven't checked out ruby
1.9since about a year ago.  If you are interested, I can try making a
patch for
the current ruby 1.9 or 1.8.5.

These same techniques (or something like them) could be applied to String
also.

------art_11886_23296308.1159155438268--