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

--- nobuyoshi nakada <[e-mail]> wrote:
> Eric Mahurin wrote in [ruby-core:05861]:
> > - 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.
> 
> What kind of merit and necessity, compared with the current
> code?  It seems to be complicated.

The changes regarding element sharing were the largest, but I
believe they will be be most beneficial.  This was the best
solution I came up with.  Here are the issues with the
old/current way of element sharing that are solved by my new
way:

1. After a slice is taken from a large array and then that
array needs to be modified, the large array is copied to a new
area so that the shared slice is not disturbed.  This causes a
extra copy (O(n)) of this large array compared to not doing
element sharing (coping the small slice to begin with).  With
my solution, I copy all of the shared slices instead of the
master array when the master array needs to be modified.  Here
is a benchmark that demonstrates the problem (FIFO taking 2
elements in/out at a time):

ruby -e 'n=2**16; a=(0...n).to_a; n.times{a.push(*a.shift(2))};
puts(Process.times)'

old - O(n**2) time:

#<struct Struct::Tms utime=17.19, stime=20.14, cutime=0.0,
cstime=0.0>

new - O(n) time:

#<struct Struct::Tms utime=0.1, stime=0.0, cutime=0.0,
cstime=0.0>


2. If you take a small slice of a large array, modify the large
array, and keep the original, the small slice will maintain a
link to the original large array and keep all that space. 
You'll be maintaining about double the memory that you would
without element sharing.  Because my patch copies the slices
instead of the large array, this problem doesn't exist.  Here
is an example (works in linux using the /proc filesystem to get
memory usage):

ruby -e 'n=2**13; a=(0...n).to_a; n.times{a.push(a.pop(2))};
IO.readlines("/proc/#{Process.pid}/status").grep(/VmSize/).display;
puts(Process.times)'

old - O(n**2) memory and time:

VmSize:   199864 kB
#<struct Struct::Tms utime=4.02, stime=0.18, cutime=0.0,
cstime=0.0>

new - O(n) memory and time:

VmSize:     3360 kB
#<struct Struct::Tms utime=0.01, stime=0.0, cutime=0.0,
cstime=0.0>


3. If a slice is taken and held, references to all of the
elements of the original array are kept even after the original
array is not needed.  With the method I used, when the original
is GC'd, the slice is copied and all of the other elements of
the original array can be GC'd.  Here is an example that shows
the issue:

ruby -e 'n=2**13; a=[];
n.times{|i|a.push([i,(0..i).to_a][0,1])};
IO.readlines("/proc/#{Process.pid}/status").grep(/VmSize/).display;
puts(Process.times)'

old - O(n**2) memory, O(n**2) time:

VmSize:   166644 kB
#<struct Struct::Tms utime=14.9, stime=0.25, cutime=0.0,
cstime=0.0>

new - O(n) memory, O(n**2) time:

VmSize:     7252 kB
#<struct Struct::Tms utime=9.47, stime=0.03, cutime=0.0,
cstime=0.0>

I tried all of the above tests in perl and it has the
performance/memory characteristics of my patch.

If we are to have element sharing in ruby, I think the
delay/memory penalty should be no worse than the same order of
magnitude than if we didn't have it.  This is definitely not
the case currently.

This is only one part of my patch - element sharing.  The other
major part is doing all insertions/deletions toward the closest
end of the array (instead of always toward the right end). 
Looking at the performance of perl's unshift, they don't have
this capability.  Maybe this is the first time someone has done
something like this.

Eric



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