Are Ruby arrays true arrays?
arrays, ruby
Solution
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.
Problem
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?