Issue #6638 has been updated by funny_falcon (Yura Sokolov).


I've rebased branch against trunk.
----------------------------------------
Feature #6638: Array as queue
https://bugs.ruby-lang.org/issues/6638#change-32337

Author: funny_falcon (Yura Sokolov)
Status: Assigned
Priority: Normal
Assignee: nobu (Nobuyoshi Nakada)
Category: core
Target version: 2.0.0


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 `ary_make_shared`
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)

Pull request https://github.com/ruby/ruby/pull/133
Patch https://github.com/ruby/ruby/pull/133.patch

(but I think, despite the patch, Ruby needs real Deque in stdlib)


-- 
http://bugs.ruby-lang.org/