Project

General

Profile

Actions

Feature #6638

closed

Array as queue

Added by funny_falcon (Yura Sokolov) almost 12 years ago. Updated over 11 years ago.

Status:
Closed
Target version:
[ruby-core:45818]

Description

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)

Updated by matz (Yukihiro Matsumoto) almost 12 years ago

If it doesn't change the behavior, I am positive to merge this.

Matz.

Updated by funny_falcon (Yura Sokolov) almost 12 years ago

I've fixed error introduced in second commit on the case x.concat(x).

Updated by funny_falcon (Yura Sokolov) almost 12 years ago

This patch actually fixes non-linear Queue behaviour considered in http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/391324

Updated by funny_falcon (Yura Sokolov) almost 12 years ago

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 most of time provides
    a room for future unshifts.
  • In case when array is not shared and it is large enough (currently, more than 116 elements), #unshift makes it
    shared and ensures that there is a room for future unshifts.

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

Updated by funny_falcon (Yura Sokolov) almost 12 years ago

Another couple of commits to https://github.com/ruby/ruby/pull/133 :

  • fixed error in rb_ary_cat_to_shared which leads to memory corruption
  • avoid pathological performance cases (when array length is close to capacity)
    by increasing capacity earlier and leaving more room for future values

Updated by naruse (Yui NARUSE) over 11 years ago

  • Status changed from Open to Assigned
  • Assignee set to nobu (Nobuyoshi Nakada)

Updated by funny_falcon (Yura Sokolov) over 11 years ago

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

Updated by jonforums (Jon Forums) over 11 years ago

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

Updated by funny_falcon (Yura Sokolov) over 11 years ago

I've rebased branch against trunk.

Actions #10

Updated by nobu (Nobuyoshi Nakada) over 11 years ago

  • Status changed from Assigned to Closed
  • % Done changed from 0 to 100

This issue was solved with changeset r37581.
Yura, thank you for reporting this issue.
Your contribution to Ruby is greatly appreciated.
May Ruby be with you.


array.c: steal shared array's container when ARY_SHARED_NUM == 1

  • array.c (rb_ary_modify): steal shared array's container when
    ARY_SHARED_NUM == 1. [Feature #6638]
    • Do not allocate new memory in rb_ary_modify when ARY_SHARED_NUM == 1
      and length almost same.
    • Store ARY_CAPA instead of RARRAY_LEN in ary_make_shared, to make
      it useful.
    • Fix rb_ary_sort_bang accordantly.
Actions

Also available in: Atom PDF

Like0
Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0