[ruby-core:67479] [ruby-trunk - Bug #10714] Array#reject! nonlinear performance problem

Issue #10714 has been updated by Akira Tanaka.


I don't think the modification must be observable from the given block.

[Bug #2545] doesn't discuss the observability in the block.
It discusses the receiver after "break".

If the modification is not required to be observable from the block,
it is possible to implement with linear performance.

```
% ruby -e '
class Array
  def my_reject!
    i = 0
    j = 0
    while i < self.length
      v = self[i]
      unless yield v
        self[j] = v
        j += 1
      end
      i += 1
    end
    i != j ? self : nil
  ensure
    if i != j
      self[j, i-j] = []
    end
  end
end
a = [1,2,3]; a.my_reject! {|v| v == 2 }; p a
a = [5,6,7,8,9,10]; a.my_reject! {|i| break i if i > 8; i < 7}; p a
'
[1, 3]
[7, 8, 9, 10]
```

So the problem is which is important between the linear performance and the observability.

I vote the linear performance because:
- the nonlinear performance makes reject! useless for long array and
- [Bug #2545] is not a issue for the observability.


----------------------------------------
Bug #10714: Array#reject! nonlinear performance problem
https://bugs.ruby-lang.org/issues/10714#change-50898

* 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/