From: e@... Date: 2015-01-10T18:40:57+00:00 Subject: [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/