Are Ruby arrays true arrays?

Question

I understand that Ruby arrays are both dynamically allocated and dynamically resized; however, I can't seem to find any clear information on whether they are true arrays; i.e. they are contiguous in memory (more specifically, the references they hold are contiguous in memory).

My assumption would be that increasing the size of a Ruby array entails reallocation of the entire array to a larger contiguous memory block where required.

Is this correct, or is "array" a misnomer in this instance?

Answer 1

Having reviewed the source and the article referenced by Darek in the comments, I can confirm that Ruby's arrays are, indeed, genuine arrays and consist of contiguous memory blocks, where the element at a given index can be accessed in O(1) time.

It seems that Ruby over-allocates arrays to improve the efficiency of push and similar operations; however, when the capacity of the array is exceeded, the array is automatically reallocated at a larger size.

This is a fairly important distinction that seems to be largely neglected, so hopefully this information will be useful to others searching for similar enlightenment.

Answer 2

The Ruby Language Specification does not prescribe any particular memory representation for Array objects (or any object, actually). That would be too restricting for the implementors. In fact, it doesn't even prescribe that objects have to live in memory at all, which makes possible implementations like MagLev where the Object Memory is a distributed on-disk OO database instead of RAM.

The Ruby Language Specification also does not prescribe any particular performance characteristics for any methods of the Array class.

However, Ruby programmers have come to expect certain performance guarantees from certain Array methods (and any implementation that doesn't meet those guarantees will simply be ignored by the community), e.g.

• Array#[] shall have a worst-case step complexity of O(#of items sliced)
• Array#<< shall have a worst-case step complexity of O(n) and an amortized worst-case step complexity of O(1)
• … and so on.

Basically, the typical performance guarantees you would expect from a dynamic array.

This more or less means that the only way to meet those performance guarantees is that the implementation must use contiguous storage and exponential resizing.