From: "jonforums (Jon Forums)" Date: 2012-11-04T11:44:02+09:00 Subject: [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/