Re: another array patch - performance boosts all over the place

Has anybody evaluated this patch?  In addition to these cases
where the benchmark time went from O(n**2) to O(n), I can show
other cases where the memory went from O(n**2) to O(n).

I also looked at equivalent perl for many of these.  I never
found perl to have the element sharing problem (not sure if it
does element sharing).  I also found that perl 5.6.1+ has a
fast unshift like below (always had a fast shift), but doesn't
have fast random insert/delete.  perl's splice always operates
toward the right instead of the closest of the right or left
like my patch.

We can't even make a fast FIFO out of an Array now (see
push(shift) benchmark).  The reason for this is element sharing
cause large copies when a modification is made (shift does
sharing and push does the unsharing).  This is exactly what
Queue uses and its operations are O(n) instead of O(1) as they
should be.  I have several applications in mind but the one
that I have immediate use for is a FIFO buffer where that
buffer could be an Array or String (need the String patch
also).  Another idea (that I don't need right now) is for a
text editor buffer that is an inside-out gap buffer (don't know
what to call it) and has the same performance attributes as a
gap buffer.

I would also like to do a similar patch for String, but I need
to know whether this will be accepted before I invest the time.
 These are not trivial patches - they are involved because of
the data structure changes.

I will be at rubyconf if this needs to be discussed in person.

--- Eric Mahurin <[e-mail]> wrote:

> 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

look at previous message for patch and benchmark attachments



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