ruby-changes:37174
From: nobu <ko1@a...>
Date: Thu, 15 Jan 2015 10:45:13 +0900 (JST)
Subject: [ruby-changes:37174] nobu:r49255 (trunk): array.c: linear performance
nobu 2015-01-15 10:44:57 +0900 (Thu, 15 Jan 2015) New Revision: 49255 http://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=revision&revision=49255 Log: array.c: linear performance * array.c (rb_ary_select_bang, ary_reject_bang): linear performance. [ruby-core:67418] [Feature #10714] Modified files: trunk/ChangeLog trunk/NEWS trunk/array.c trunk/test/ruby/test_array.rb Index: array.c =================================================================== --- array.c (revision 49254) +++ array.c (revision 49255) @@ -2822,6 +2822,48 @@ rb_ary_select(VALUE ary) https://github.com/ruby/ruby/blob/trunk/array.c#L2822 return result; } +struct select_bang_arg { + VALUE ary; + long len[2]; +}; + +static VALUE +select_bang_i(VALUE a) +{ + volatile struct select_bang_arg *arg = (void *)a; + VALUE ary = arg->ary; + long i1, i2; + + for (i1 = i2 = 0; i1 < RARRAY_LEN(ary); arg->len[0] = ++i1) { + VALUE v = RARRAY_AREF(ary, i1); + if (!RTEST(rb_yield(v))) continue; + if (i1 != i2) { + rb_ary_store(ary, i2, v); + } + arg->len[1] = ++i2; + } + return (i1 == i2) ? Qnil : ary; +} + +static VALUE +select_bang_ensure(VALUE a) +{ + volatile struct select_bang_arg *arg = (void *)a; + VALUE ary = arg->ary; + long len = RARRAY_LEN(ary); + long i1 = arg->len[0], i2 = arg->len[1]; + + if (i2 < i1) { + if (i1 < len) { + RARRAY_PTR_USE(ary, ptr, { + MEMMOVE(ptr + i2, ptr + i1, VALUE, len - i1); + }); + } + ARY_SET_LEN(ary, len - i1 + i2); + } + return ary; +} + /* * call-seq: * ary.select! {|item| block } -> ary or nil @@ -2830,6 +2872,8 @@ rb_ary_select(VALUE ary) https://github.com/ruby/ruby/blob/trunk/array.c#L2872 * Invokes the given block passing in successive elements from +self+, * deleting elements for which the block returns a +false+ value. * + * The array may not be changed instantly every time the block is called. + * * If changes were made, it will return +self+, otherwise it returns +nil+. * * See also Array#keep_if @@ -2841,22 +2885,14 @@ rb_ary_select(VALUE ary) https://github.com/ruby/ruby/blob/trunk/array.c#L2885 static VALUE rb_ary_select_bang(VALUE ary) { - long i; - VALUE result = Qnil; + struct select_bang_arg args; RETURN_SIZED_ENUMERATOR(ary, 0, 0, ary_enum_length); rb_ary_modify(ary); - for (i = 0; i < RARRAY_LEN(ary); ) { - VALUE v = RARRAY_AREF(ary, i); - if (!RTEST(rb_yield(v))) { - rb_ary_delete_at(ary, i); - result = ary; - } - else { - i++; - } - } - return result; + + args.ary = ary; + args.len[0] = args.len[1] = 0; + return rb_ensure(select_bang_i, (VALUE)&args, select_bang_ensure, (VALUE)&args); } /* @@ -3099,23 +3135,32 @@ ary_reject(VALUE orig, VALUE result) https://github.com/ruby/ruby/blob/trunk/array.c#L3135 } static VALUE -ary_reject_bang(VALUE ary) +reject_bang_i(VALUE a) { - long i; - VALUE result = Qnil; + volatile struct select_bang_arg *arg = (void *)a; + VALUE ary = arg->ary; + long i1, i2; - rb_ary_modify_check(ary); - for (i = 0; i < RARRAY_LEN(ary); ) { - VALUE v = RARRAY_AREF(ary, i); - if (RTEST(rb_yield(v))) { - rb_ary_delete_at(ary, i); - result = ary; - } - else { - i++; + for (i1 = i2 = 0; i1 < RARRAY_LEN(ary); arg->len[0] = ++i1) { + VALUE v = RARRAY_AREF(ary, i1); + if (RTEST(rb_yield(v))) continue; + if (i1 != i2) { + rb_ary_store(ary, i2, v); } + arg->len[1] = ++i2; } - return result; + return (i1 == i2) ? Qnil : ary; +} + +static VALUE +ary_reject_bang(VALUE ary) +{ + struct select_bang_arg args; + + rb_ary_modify_check(ary); + args.ary = ary; + args.len[0] = args.len[1] = 0; + return rb_ensure(reject_bang_i, (VALUE)&args, select_bang_ensure, (VALUE)&args); } /* @@ -3126,8 +3171,7 @@ ary_reject_bang(VALUE ary) https://github.com/ruby/ruby/blob/trunk/array.c#L3171 * Equivalent to Array#delete_if, deleting elements from +self+ for which the * block evaluates to +true+, but returns +nil+ if no changes were made. * - * The array is changed instantly every time the block is called, not after - * the iteration is over. + * The array may not be changed instantly every time the block is called. * * See also Enumerable#reject and Array#delete_if. * Index: ChangeLog =================================================================== --- ChangeLog (revision 49254) +++ ChangeLog (revision 49255) @@ -1,3 +1,8 @@ https://github.com/ruby/ruby/blob/trunk/ChangeLog#L1 +Thu Jan 15 10:45:04 2015 Nobuyoshi Nakada <nobu@r...> + + * array.c (rb_ary_select_bang, ary_reject_bang): linear + performance. [ruby-core:67418] [Feature #10714] + Wed Jan 14 18:06:06 2015 Martin Duerst <duerst@i...> * lib/uri/mailto.rb: raising URI::InvalidComponentError instead Index: NEWS =================================================================== --- NEWS (revision 49254) +++ NEWS (revision 49255) @@ -17,6 +17,11 @@ with all sufficient information, see the https://github.com/ruby/ruby/blob/trunk/NEWS#L17 === Core classes compatibility issues (excluding feature bug fixes) +* Array + * Array#select!, Array#keep_if, Array#reject!, and Array#delete_if + no longer changes the receiver array instantly every time the + block is called. + === Stdlib updates (outstanding ones only) === Stdlib compatibility issues (excluding feature bug fixes) Index: test/ruby/test_array.rb =================================================================== --- test/ruby/test_array.rb (revision 49254) +++ test/ruby/test_array.rb (revision 49255) @@ -661,7 +661,7 @@ class TestArray < Test::Unit::TestCase https://github.com/ruby/ruby/blob/trunk/test/ruby/test_array.rb#L661 bug2545 = '[ruby-core:27366]' a = @cls[ 5, 6, 7, 8, 9, 10 ] - assert_equal(9, a.delete_if {|i| break i if i > 8; assert_equal(a[0], i) || true if i < 7}) + assert_equal(9, a.delete_if {|i| break i if i > 8; i < 7}) assert_equal(@cls[7, 8, 9, 10], a, bug2545) end @@ -1160,7 +1160,7 @@ class TestArray < Test::Unit::TestCase https://github.com/ruby/ruby/blob/trunk/test/ruby/test_array.rb#L1160 bug2545 = '[ruby-core:27366]' a = @cls[ 5, 6, 7, 8, 9, 10 ] - assert_equal(9, a.reject! {|i| break i if i > 8; assert_equal(a[0], i) || true if i < 7}) + assert_equal(9, a.reject! {|i| break i if i > 8; i < 7}) assert_equal(@cls[7, 8, 9, 10], a, bug2545) end -- ML: ruby-changes@q... Info: http://www.atdot.net/~ko1/quickml/