Re: array sharing

I've been looking at the code a bit more regarding element
sharing.  With the way it is implemented, it seems too
dangerous with regard to memory usage.  The goal is to reduce
memory usage (and data copying) by sharing elements among
multiple arrays.  But, as soon as you want to modify one of the
arrays being shared, it copies it before modifying it.  This
can result in much higher memory usage if the other array being
shared only uses a few elements from a large shared array. 
Here is an example that uses O(n^2) memory because of this
sharing instead of O(n):

ruby -e
'n=1000000;a=[0]*n;b=[];n.times{|i|b.push(a.pop(2));a.push(i,i)}'

I'm using the new Array#pop(n) form of v1.9.

It looks like anytime you take a small slice of an array, store
it somewhere, and then modify the original (big) array, you
have this same problem.  I would call this a form of a memory
leak.  Something taking O(n^2) memory when it should take O(n)
memory seems like an implementation problem.

Here are a few solutions:

- only do element sharing when the array/string is frozen

- when one of the slaves needs modifying, look at the other
slaves (sharing the same master data) to see what data should
be copied.  For example, if you have a 1000000 element array
and a 2 element array sharing data, you should copy the 2
element array when you needed to modify the 1000000 element
array.  This would require a data structure change - right now
all slaves just point to the master.  Maybe use a circular
linked list instead?

- only share if the slice is a large percentage of the entire
array.  Although you can still get memory inefficiency, I don't
think you can have something like the above where you go from
O(n) to O(n^2) memory usage.

- don't do sharing automatically.  Maybe provide some explicit
methods to do it.


Personally, I think element sharing should be done on just a
frozen array/string.



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