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

Issue #10714 has been updated by Akira Tanaka.


Hm.
The failed test is introduced by you after [Bug #5752].

The bug report describes as "If this is indeed the intended behaviour, ...".
It means that the reporter is not sure that the current behavior is intended or not.

Why current behavior is desired over linear performance behavior?

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

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