ruby array internals

Question

How are ruby arrays internally implemented (mainly in CRuby, but any other info is welcomed)?

Are they growable arrays like a c++ vector or are they list based? What's the complexity of shift/unshift and accessing an element by index?

Answer 1

They're growable arrays which "grow at the end".

shift is O(1), unshift is O(n) and accessing by index is O(1). To the best of my knowledge this holds true for all ruby implementations, but it definitely does in MRI.

UPDATE: After this answer was originally written, Ruby was enhanced to make unshift amortized O(1). The enhanced array is in Ruby 2.0.0 and later, making shift, unshift, push, and pop all O(1) or amortized O(1).

Answer 2

unshift is O(N^2) in my ruby1.9 .

$ /usr/bin/time ruby -e 'n=100000;l=[];(1..n).each{|i| l.push(i);}'
        0.03 real         0.02 user         0.00 sys
$ /usr/bin/time ruby -e 'n=100000;l=[];(1..n).each{|i| l.unshift(i);}'
        3.15 real         3.11 user         0.01 sys
$ /usr/bin/time ruby -e 'n=200000;l=[];(1..n).each{|i| l.unshift(i);}'
       12.96 real        12.85 user         0.03 sys
$ ruby -v
ruby 1.9.3p194 (2012-04-20 revision 35410) [x86_64-darwin11.3.0]