Array as queue
Many libraries use Array as queue (cause stdlib has no real dequeue class).
And typical pattern is to use #push and #shift methods with small count of #push
with following small count of #shift.
But currently big array makes a copy every time array is modified after #shift,
so that it degrades greatly when Array size growths.
Ironically, usage of #unshift with following #pop degrades much less, but most
libraries doesn't consider this fact, and other ruby's implementations suffers
from such pattern.
Test for 1.9.3 before patch: https://gist.github.com/2981959#file_test_before_patch
Main point of this patch is to change
rb_ary_modify so that it considers ARY_SHARED_NUM
and steel shared array pointer when ARY_SHARED_NUM == 1.
To make it possible, it saves array's capa instead of array's length in
and fixes rb_ary_sort_bang accordantly.
Test for 1.9.3 after patch: https://gist.github.com/2981959#file_test_after_patch
(note that gain is less for ruby-trunk but still exists)
(but I think, despite the patch, Ruby needs real Deque in stdlib)