[ruby-core:67501] [ruby-trunk - Feature #10714] Array#reject! nonlinear performance problem

Issue #10714 has been updated by Zachary Scott.


Using the following benchmark I compared nobu's patch vs. 2.2:

```ruby
require 'derailed_benchmarks'
require 'derailed_benchmarks/tasks'

namespace :perf do
  desc "Array#select! and friends"
  task :array_select => [:setup] do
    Benchmark.ips do |x|
      [10, 100, 1000].map do |i|
        a = []
        i.times { |z| a = [nil]*z*i }

        x.report("Array#select! * #{i}") { a.select! { true } }
      end

      x.compare!
    end
  end
end
```

Here are the results:

**2.2**
```
Calculating -------------------------------------
  Array#select! * 10    14.903k i/100ms
 Array#select! * 100   205.000  i/100ms
Array#select! * 1000     1.000  i/100ms
-------------------------------------------------
  Array#select! * 10    211.199k (賊10.1%) i/s -      1.058M
 Array#select! * 100      2.086k (賊 7.6%) i/s -     10.455k
Array#select! * 1000     21.069  (賊 9.5%) i/s -    105.000

Comparison:
  Array#select! * 10:   211198.7 i/s
 Array#select! * 100:     2086.2 i/s - 101.24x slower
Array#select! * 1000:       21.1 i/s - 10023.98x slower
```

**Patched**
```
Calculating -------------------------------------
  Array#select! * 10    14.124k i/100ms
 Array#select! * 100   207.000  i/100ms
Array#select! * 1000     2.000  i/100ms
-------------------------------------------------
  Array#select! * 10    223.828k (賊 6.0%) i/s -      1.116M
 Array#select! * 100      2.101k (賊 5.4%) i/s -     10.557k
Array#select! * 1000     20.865  (賊 4.8%) i/s -    106.000

Comparison:
  Array#select! * 10:   223827.6 i/s
 Array#select! * 100:     2101.3 i/s - 106.52x slower
Array#select! * 1000:       20.9 i/s - 10727.54x slower
```

This test shows that this patch might actually be slower. Can anyone else c/d??

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

* Author: Akira Tanaka
* Status: Rejected
* Priority: Normal
* Assignee: 
* Category: 
* Target version: 
----------------------------------------
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/