From: "funny_falcon (Yura Sokolov)" <funny.falcon@...>
Date: 2012-06-26T19:38:45+09:00
Subject: [ruby-core:45884] [ruby-trunk - Feature #6638] Array as queue


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


I've add a couple commits to https://github.com/ruby/ruby/pull/133 and now Array becomes fully useful as a deque:

- `#shift` behaves old way: used shared array for circular buffer
- `#push` now knows if array is shared, and when `ARY_SHARED_NUM(shared) == 1` then tries to push entries directly
  into shared array. So that, there is no additional allocations or `memmove` for most of pushes
- `#pop` behaves almost in old way, but it clears shared array element as `#shift` do.
- `#unshift` tries to unshift elements to shared array when `ARY_SHARED_NUM(shared) == 1`, and ensures that there
  is a room for future inserts.
- In case when array is not shared and it is large enough, `#unshift` makes it shared and ensures that there is a
  room for future inserts.

Full diff https://github.com/ruby/ruby/pull/133.diff
Patch (separate commits) https://github.com/ruby/ruby/pull/133.patch
Tests and patch against 1.9.3 https://gist.github.com/2981959
----------------------------------------
Feature #6638: Array as queue
https://bugs.ruby-lang.org/issues/6638#change-27476

Author: funny_falcon (Yura Sokolov)
Status: Open
Priority: Normal
Assignee: 
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/