From: nobu@... Date: 2015-01-10T06:45:50+00:00 Subject: [ruby-core:67488] [ruby-trunk - Bug #10714] Array#reject! nonlinear performance problem Issue #10714 has been updated by Nobuyoshi Nakada. Ok, then try if something dies? ~~~diff diff --git a/array.c b/array.c index 0de7231..f2f7352 100644 --- a/array.c +++ b/array.c @@ -2824,6 +2824,48 @@ rb_ary_select(VALUE ary) 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 @@ -2832,6 +2874,8 @@ rb_ary_select(VALUE ary) * 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 @@ -2843,22 +2887,14 @@ rb_ary_select(VALUE ary) 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); } /* @@ -3101,23 +3137,32 @@ ary_reject(VALUE orig, VALUE result) } 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); } /* @@ -3128,8 +3173,7 @@ ary_reject_bang(VALUE ary) * 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. * ~~~ ---------------------------------------- Bug #10714: Array#reject! nonlinear performance problem https://bugs.ruby-lang.org/issues/10714#change-50907 * Author: Akira Tanaka * Status: Rejected * Priority: Normal * Assignee: * Category: * Target version: * ruby -v: ruby 2.3.0dev (2015-01-08 trunk 49175) [x86_64-linux] * Backport: 2.0.0: UNKNOWN, 2.1: UNKNOWN, 2.2: UNKNOWN ---------------------------------------- I found Array#reject! is too slow. I measured it and it seems the performance is nonlinear. ``` % ./ruby -v -e ' 20.times {|i| a = [nil]*i*10000; t1 = Time.now a.reject! { true } t2 = Time.now t = t2 - t1 p ["*" * (t * 20).to_i , t] } ' ruby 2.3.0dev (2015-01-08 trunk 49175) [x86_64-linux] ["", 3.683e-06] ["", 0.019059723] ["*", 0.052964771] ["**", 0.1177318] ["****", 0.208824818] ["******", 0.334757354] ["*********", 0.482717139] ["*************", 0.669606441] ["*****************", 0.866588588] ["**********************", 1.116195389] ["***************************", 1.392828177] ["**********************************", 1.701906753] ["****************************************", 2.013290644] ["************************************************", 2.415258165] ["*******************************************************", 2.783918449] ["*****************************************************************", 3.27417584] ["**************************************************************************", 3.724958298] ["**************************************************************************************", 4.307263787] ["**************************************************************************************************", 4.922179118] ["************************************************************************************************************", 5.403641168] ``` Ruby 2.2, 2.1, 2.0, 1.9.3 also have the problem but Ruby 1.9.2 works well. ``` % ruby-1.9.2-p330 -v -e ' 20.times {|i| a = [nil]*i*10000; t1 = Time.now a.reject! { true } t2 = Time.now t = t2 - t1 p ["*" * (t * 20).to_i , t] } ' ruby 1.9.2p330 (2014-08-07 revision 47094) [x86_64-linux] ["", 2.111e-06] ["", 0.000798623] ["", 0.001441408] ["", 0.00155386] ["", 0.001656242] ["", 0.002166389] ["", 0.002355492] ["", 0.002703977] ["", 0.003123692] ["", 0.00348722] ["", 0.003884792] ["", 0.004300034] ["", 0.004701378] ["", 0.006854893] ["", 0.005485207] ["", 0.005972309] ["", 0.006298597] ["", 0.006901775] ["", 0.007216343] ["", 0.007373332] ``` -- https://bugs.ruby-lang.org/