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

Issue #10714 has been updated by Zachary Scott.


Here are the results for `reject!` using this benchmark:

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

namespace :perf do
  desc "Array#reject!"
  task :array_reject => [:setup] do
    Benchmark.ips do |x|
      20.times do |i|
        a = []
        i.times { |z| a = [nil]*z*10000 }

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

**2.2**

```shell
   Array#reject! * 0      8.236M (賊 6.4%) i/s -     40.928M
   Array#reject! * 1      8.255M (賊 5.9%) i/s -     41.049M
   Array#reject! * 2      8.298M (賊 5.5%) i/s -     41.297M
   Array#reject! * 3      8.291M (賊 5.7%) i/s -     41.243M
   Array#reject! * 4      8.244M (賊 7.0%) i/s -     40.901M
   Array#reject! * 5      8.148M (賊 8.0%) i/s -     40.375M
   Array#reject! * 6      8.247M (賊 6.6%) i/s -     40.939M
   Array#reject! * 7      8.309M (賊 5.3%) i/s -     41.319M
   Array#reject! * 8      8.313M (賊 5.1%) i/s -     41.369M
   Array#reject! * 9      8.332M (賊 4.0%) i/s -     41.522M
  Array#reject! * 10      8.331M (賊 4.0%) i/s -     41.491M
  Array#reject! * 11      8.281M (賊 5.6%) i/s -     41.106M
  Array#reject! * 12      8.162M (賊 8.2%) i/s -     39.586M
  Array#reject! * 13      1.006M (賊17.3%) i/s -    743.452k
  Array#reject! * 14      1.007M (賊17.0%) i/s -    743.165k
  Array#reject! * 15      1.007M (賊17.0%) i/s -    746.140k
  Array#reject! * 16      1.006M (賊17.2%) i/s -    747.039k
  Array#reject! * 17      1.007M (賊17.2%) i/s -    752.532k
  Array#reject! * 18      1.006M (賊17.2%) i/s -    741.489k
  Array#reject! * 19      1.006M (賊17.3%) i/s -    745.300k
```

**Patched**

```shell
   Array#reject! * 0      7.285M (賊 5.8%) i/s -     36.227M
   Array#reject! * 1      7.294M (賊 6.5%) i/s -     36.274M
   Array#reject! * 2      7.378M (賊 4.1%) i/s -     36.831M
   Array#reject! * 3      7.260M (賊 7.8%) i/s -     35.974M
   Array#reject! * 4      7.385M (賊 4.3%) i/s -     36.849M
   Array#reject! * 5      7.376M (賊 5.5%) i/s -     36.735M
   Array#reject! * 6      7.145M (賊10.2%) i/s -     35.136M
   Array#reject! * 7      6.974M (賊 9.6%) i/s -     34.385M
   Array#reject! * 8      7.279M (賊 5.7%) i/s -     36.259M
   Array#reject! * 9      7.333M (賊 5.3%) i/s -     36.532M
  Array#reject! * 10      7.345M (賊 5.5%) i/s -     36.554M
  Array#reject! * 11      7.328M (賊 5.3%) i/s -     36.481M
  Array#reject! * 12      7.325M (賊 3.2%) i/s -     36.579M
  Array#reject! * 13      7.319M (賊 4.1%) i/s -     36.522M
  Array#reject! * 14      7.335M (賊 5.5%) i/s -     36.527M
  Array#reject! * 15      7.338M (賊 6.0%) i/s -     36.480M
  Array#reject! * 16      7.405M (賊 5.2%) i/s -     36.901M
  Array#reject! * 17      7.151M (賊 4.8%) i/s -     35.624M
  Array#reject! * 18      7.378M (賊 5.7%) i/s -     36.714M
  Array#reject! * 19      7.414M (賊 4.4%) i/s -     36.952M
```

Seems to have fixed the non-linear regression by this benchmark.

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

* Author: Akira Tanaka
* Status: Open
* 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/