Peter Zotov wrote in post #1037082:
> Eric Wong ڧѧ 17.12.2011 03:05:
>>> I wonder if we can make a more efficient Array by making it a circular buffer,
>>> so that #shift and #pop would always be O(1), and #unshift and #push
>>> be
>>> O(n) only if the array grows bigger. Are there any implications I
>>> don't see?
>>
>> It would require a lot of changes to existing C code in both Ruby
>> itself
>> and C extensions that depend on RARRAY_PTR().
>
> Yes, RARRAY_PTR will break. This is unacceptable.
>

Well, I actually did it, see https://github.com/ruby/ruby/pull/133
(corresponding issue http://bugs.ruby-lang.org/issues/6638 )
and see tests here https://gist.github.com/2981959

And it doesn't break RARRAY_PTR() cause Array#shift already moves array
to shared copy, I just used that fact in a full way.

Strictly speaking, it still some times do whole memmove, but very very
rare, so that it could be considered as real circular buffer in
practice.

I've only implemented it for #push/#shift pattern, cause most libraries
actually use it. But it could be extended for #unshift/#pop as well.

Sokolov Yura aka funny-falcon