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

Issue #6638 has been updated by jonforums (Jon Forums).


On Win7 32bit with a one-line tweak to Yura's `174.patch` to allow it to apply to trunk I get the following success when building with mingw-w64 gcc 4.7.2:

C:\Jenkins\workspace\ruby-trunk-svn>svn log -l 1
------------------------------------------------------------------------
r37463 | nobu | 2012-11-03 21:19:11 -0400 (Sat, 03 Nov 2012) | 5 lines


C:\Jenkins\workspace\ruby-trunk-svn>svn st
M       array.c
?       array_as_queue_trunk.patch


sh-3.1$ make test-all
...
Finished tests in 620.647090s, 18.4727 tests/s, 4309.2106 assertions/s.
11465 tests, 2674499 assertions, 0 failures, 0 errors, 83 skips

ruby -v: ruby 2.0.0dev (2012-11-04 trunk 37463) [i386-mingw32]


sh-3.1$ make test
...
sample/test.rb:gc OK 4

test succeeded
PASS all 957 tests
./miniruby.exe -I../../../../Jenkins/workspace/ruby-trunk-svn/lib -I. -I.ext/common  ../../../../Jenkins/workspace/ruby-trunk-svn/tool/runruby.rb --extout=.ext  -- --disable-gems "../../../../Jenkins/workspace/ruby-trunk-svn/bootstraptest/runner.rb" --ruby="ruby.exe"
../../../../Jenkins/workspace/ruby-trunk-svn/KNOWNBUGS.rb
2012-11-03 22:39:19 -0400
Driver is ruby 2.0.0dev (2012-11-04 trunk 37463) [i386-mingw32]
Target is ruby 2.0.0dev (2012-11-04 trunk 37463) [i386-mingw32]

KNOWNBUGS.rbPASS 0
No tests, no problem

----------------------------------------
Feature #6638: Array as queue
https://bugs.ruby-lang.org/issues/6638#change-32324

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/