From: Eric Mahurin <eric_mahurin@...>
Date: 2005-09-15T23:01:23+09:00
Subject: array sharing

This is my first time poking around in the ruby source code, so
I wouldn't mind some guidance...

In array.c, there looks to be an optimization to share slices
of arrays as long as they are not modified.  But, there also
appears to be another use for this sharing: to maintain the
original allocation pointer used for malloc.  This is what I
see in rb_ary_shift (compare to pop that just decrements the
length).  In this case, shouldn't modification be allowed?  If
so, how about designating the two cases with some flag on the
shared object: FL_FREEZE maybe (frozen - don't modify,
non-frozen - shared just gives malloc info).

What I was wanting to do was to give Array#unshift O(1)
performance.  This looks doable using the shared array which
tells me the capacity of the array to the left - but I don't
want to mess up any real shared arrays.  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.  Each following
element would just store the element and decrement the pointer
until the capacity is used up again.  The average would be
O(1).

After that is done, I would like to move on to general
insertions/deletions to cut their run-time in half - inserting
or deleting toward the closest end of the array.  Random
insert/delete performance would still be O(n), but now n is the
minimum of the number of elements from the beginning or end as
opposed to now it is the number of elements from the end.

I assume the same can be done for string.c, but I haven't
looked at it yet.

Eric



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