[ruby-core:47394] [ruby-trunk - Feature #6638] Array as queue

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


I've update branch a bit, cause previous code leads to some performance degradation for average application (which do not use array as queue).

New code does not hurts performance of average application and still provides great performance for array used as a queue.
Pull request: https://github.com/ruby/ruby/pull/174
Patch: https://github.com/ruby/ruby/pull/174.patch
----------------------------------------
Feature #6638: Array as queue
https://bugs.ruby-lang.org/issues/6638#change-29139

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/