another array patch - performance boosts all over the place

Is anybody interested in the patches I'm doing to make arrays
(and someday strings) faster?  I didn't see a response for my
last patch (shift/unshift).  Now I have another patch
(fastarray.diff - attached) that should help out a lot more
code sequences.  Here are the results using the attached
benchmark (end_test.rb):

n = 32768 (2**15)

code                        old   new
------------------------- ----- -----
;                          0.01  0.01
shift                      0.02  0.02
shift(1)                   0.03  0.04
pop                        0.02  0.01
pop(1)                     0.04  0.05
shift;pop                  0.02  0.02
shift(1);pop(1)            0.07  0.08
unshift(i)                 2.34  0.02
push(i)                    0.02  0.02
unshift(i);push(i)         2.35  0.03
unshift(shift)            17.61  0.03
unshift(*shift(1))        17.42  0.07
push(pop)                  0.04  0.02
push(*pop(1))             13.83  0.08
push(shift)               14.64  0.03
push(*shift(1))           15.39  0.08
unshift(pop)               2.33  0.03
unshift(*pop(1))          16.47  0.08
slice!(1)                  2.29  0.03
delete_at(1)               2.30  0.02
slice!(1,1)               12.75  0.05
self[1,1]=[]               2.36  0.05
slice!(-2)                 0.02  0.03
delete_at(-2)              0.02  0.02
slice!(-2,1)              10.37  0.05
self[-2,1]=[]              0.04  0.04
self[1,0]=[i]              3.49  0.04
insert(1,i)                3.44  0.04
self[-1,0]=[i]             1.07  0.05
insert(-2,i)               1.02  0.05
self[1,0]=slice!(1,1)     16.40  0.06
insert(1,delete_at(1))     5.60  0.06
self[-1,0]=slice!(-2,1)   11.92  0.06
insert(-2,delete_at(-2))   1.00  0.06
self[-1,0]=slice!(1,1)    14.10  0.07
insert(-2,delete_at(1))    3.29  0.06
self[1,0]=slice!(-2,1)    14.06  0.07
insert(1,delete_at(-2))    3.30  0.06
self[i]=self[i]            0.03  0.02
self[i]=at(i)              0.03  0.02
self[i,1]=self[i,1]       11.72  0.06
self[-i-1]=self[-i-1]      0.05  0.05
self[-i-1]=at(-i-1)        0.04  0.05
self[-i-1,1]=self[-i-1,1] 11.74  0.07
self[-i-1]=self[i]         0.03  0.03
self[-i-1]=at(i)           0.03  0.04
self[-i-1,1]=self[i,1]    11.67  0.07
self[i]=self[-i-1]         0.04  0.04
self[i]=at(-i-1)           0.03  0.03
self[i,1]=self[-i-1,1]    11.70  0.06

In each of the tests above, it runs the code n times on an
array that has an average length of n.  The massive performance
boosts you see above is because the old (current) code was O(n)
in those cases and my patched code is O(1).

Here were the changes I made:

- added a bit (ELTS_LFREE=FL_USER3) to say whether there is
free space to the left of ary->ptr and put the number of free
elements in ary->ptr[-1].

- instead of ary->aux.capa, did the same for free space to the
right of ary->ptr+ary->len-1 (new flag: ELTS_RFREE=FL_USER3 and
amount stored in ary->ptr[ary->len]).  This freed up
ary->shared for dedicated used (instead of being a union with
capa).

- instead of shared arrays all pointing to a common frozen
array object, put shared arrays in a circular linked list (used
ary->shared).  The original master array will have
ELTS_SHARED=0 and the others will have ELTS_SHARED=1.  Unshared
arrays will have ELTS_SHARED=0 and ary->shared=0.

- when a shared array is to be modified, there are 2 cases:
slave - make copy and remove from shared circular linked list;
master - make copies of all slaves and terminate sharing
between this master and its slaves.  When a shared array is to
be freed, it operates in a similar way.

- during GC, shared arrays are treated independently (master
can be freed).  This works because of the above mechanism. 
Before, unused object references would persist because of array
sharing (keeping an array slice around would keep references to
all objects in the original array).

- modified various functions (shift, unshift, delete_at,
splice), to insert/delete toward the closest side to minimize
the number of elements needed to be moved.

Does anybody see a downside to this?  The main problem I see is
that I don't see the big picture when making these changes
(i.e. GC).  And this needs to be better tested.  Anybody know
of something good to do array testing?  I just used the
self-testing benchmark attached and what's in test/ruby.

Eric



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