What’s the fastest way to iterate over a range in variable increments?
For example, using irb (1.9.1):
irb(main):001:0>
a=0;s=Time.now;i=0;while(i<1000000000);a+=i;i+=5;end;e=Time.now;p
e-s;p a
8.715433734
99999999500000000
=> 99999999500000000
irb(main):002:0>
a=0;s=Time.now;Range.new(0,1000000000,true).step(5){|i|a+=i};e=Time.now;p
e-s;p a
18.932204045
99999999500000000
=> 99999999500000000
As you can see I’m stepping by 5 over the range 0 to 1000000000
exclusive (excluding the last item) doing a simple operation each
iteration (the operation above is totally contrived).
In this case, it appears that while outperforms Range’s step method.
Wondering,
Aaron out.
On 02/05/2010 07:36 PM, Aaron Gifford wrote:
irb(main):002:0>
In this case, it appears that while outperforms Range’s step method.
robert@fussel:~$ ruby19 xx.rb
Rehearsal --------------------------------------------------
while 15.650000 0.030000 15.680000 ( 17.892211)
range step 33.650000 0.070000 33.720000 ( 38.560748)
step 30.680000 0.110000 30.790000 ( 34.767791)
---------------------------------------- total: 80.190000sec
user system total real
while 15.700000 0.050000 15.750000 ( 18.651631)
range step 33.690000 0.060000 33.750000 ( 38.554879)
step 30.660000 0.100000 30.760000 ( 35.095686)
robert@fussel:~$ cat xx.rb
require ‘benchmark’
LI = 1000000000
ST = 5
Benchmark.bmbm 15 do |b|
b.report “while” do
i = 0
while i < LI
i += ST
end
end
b.report “range step” do |b|
(0…LI).step ST do
end
end
b.report “step” do |b|
0.step LI, ST do
end
end
end
robert@fussel:~$
I think we are seeing an effect of the missing call to the block that
happens on each iteration for #step approaches. The while loop does not
have this overhead.
Kind regards
robert
On Feb 5, 2:52 pm, Robert K. [email protected] wrote:
I think we are seeing an effect of the missing call to the block that
happens on each iteration for #step approaches. The while loop does not
have this overhead.
Might consider how #succ plays into this as well.
On 02/05/2010 09:19 PM, Intransition wrote:
On Feb 5, 2:52 pm, Robert K. [email protected] wrote:
I think we are seeing an effect of the missing call to the block that
happens on each iteration for #step approaches. The while loop does not
have this overhead.
Might consider how #succ plays into this as well.
Good idea!
robert@fussel:~$ ruby19 xx.rb
Rehearsal --------------------------------------------------
while 15.550000 0.060000 15.610000 ( 22.225998)
succ 66.930000 0.340000 67.270000 ( 93.726408)
range step 31.930000 0.080000 32.010000 ( 44.892588)
step 30.650000 0.140000 30.790000 ( 43.183693)
--------------------------------------- total: 145.680000sec
user system total real
while 15.430000 0.080000 15.510000 ( 21.889805)
succ 67.170000 0.440000 67.610000 ( 95.958702)
range step 32.090000 0.160000 32.250000 ( 44.213130)
step 30.670000 0.110000 30.780000 ( 43.151260)
robert@fussel:~$ cat xx.rb
require ‘benchmark’
LI = 1000000000
ST = 5
Benchmark.bmbm 15 do |b|
b.report “while” do
i = 0
while i < LI
i += ST
end
end
b.report “succ” do
i = 0
while i < LI
i = i.succ
end
end
b.report “range step” do |b|
(0…LI).step ST do
end
end
b.report “step” do |b|
0.step LI, ST do
end
end
end
robert@fussel:~$
… or rather not. 
Kind regards
robert
On Feb 6, 8:40 am, Robert K. [email protected] wrote:
Might consider how #succ plays into this as well.
ST = 5
i = 0
while i < LI
i = i.succ
end
end
b.report “range step” do |b|
(0…LI).step ST do |i|
i
end
end
b.report “step” do |b|
0.step LI, ST do |i|
i
end
end
end
To be fair maybe add a reference to i.
robert@fussel:~$
… or rather not.
Good to know too. Though actually I was wondering if range#step uses
#succ? I think in the case of integers it’s optimized to not use
#succ, but there can be different types of ranges (eg. String ranges)
and in those cases it does. Sometime back I suggested that #succ take
an optional parameter to specify how many times to #succ. This would
allow classes like Fixnum to optimize multiple steps.
In any case I find it striking how much faster while is. It’s
understandable that there is some overhead accompany the use of a
block. But that much?
On 02/06/2010 04:03 PM, Intransition wrote:
Might consider how #succ plays into this as well.
user system total real
while i < LI
b.report “step” do |b|
0.step LI, ST do |i|
i
end
end
end
To be fair maybe add a reference to i.
Why? All method bodies did not do anything (apart from while’s which
needs to increment).
In any case I find it striking how much faster while is. It’s
understandable that there is some overhead accompany the use of a
block. But that much?
Well, the loop bodies did not do anything. The overhead might be
negligible for “real” applications depending on what the loop body does.
Kind regards
robert
Interesting, I am getting different results:
Rehearsal --------------------------------------------------
while 12.880000 0.010000 12.890000 ( 13.000285)
succ 51.880000 0.000000 51.880000 ( 52.045592)
range step 10.760000 3.700000 14.460000 ( 14.518478)
step 10.520000 3.740000 14.260000 ( 14.255010)
---------------------------------------- total: 93.490000sec
user system total real
while 13.110000 0.000000 13.110000 ( 13.111040)
succ 52.650000 0.000000 52.650000 ( 52.654402)
range step 10.820000 3.650000 14.470000 ( 14.465861)
step 10.380000 3.850000 14.230000 ( 14.233755)
I had to drop a 0 off LI for my platform. I’m guessing you are running
1.9.2? My results are for 1.8.7.
On 02/06/2010 07:54 PM, Intransition wrote:
while 13.110000 0.000000 13.110000 ( 13.111040)
succ 52.650000 0.000000 52.650000 ( 52.654402)
range step 10.820000 3.650000 14.470000 ( 14.465861)
step 10.380000 3.850000 14.230000 ( 14.233755)
I had to drop a 0 off LI for my platform. I’m guessing you are running
1.9.2? My results are for 1.8.7.
No, 1.9.1:
robert@fussel:~$ allruby xx.rb
ruby 1.8.7 (2009-06-12 patchlevel 174) [i486-linux]
Rehearsal --------------------------------------------------
while 12.920000 0.030000 12.950000 ( 13.175308)
succ 57.090000 0.060000 57.150000 ( 58.147065)
range step 3.690000 0.010000 3.700000 ( 3.764357)
step 3.330000 0.000000 3.330000 ( 3.414265)
---------------------------------------- total: 77.130000sec
user system total real
while 12.900000 0.010000 12.910000 ( 13.136198)
succ 57.170000 0.110000 57.280000 ( 59.248970)
range step 3.680000 0.010000 3.690000 ( 4.048842)
step 3.390000 0.000000 3.390000 ( 3.837864)
ruby 1.9.1p376 (2009-12-07 revision 26041) [i686-linux]
Rehearsal --------------------------------------------------
while 1.440000 0.000000 1.440000 ( 1.586378)
succ 6.140000 0.010000 6.150000 ( 6.615136)
range step 2.930000 0.010000 2.940000 ( 3.040969)
step 2.810000 0.000000 2.810000 ( 2.952599)
---------------------------------------- total: 13.340000sec
user system total real
while 1.460000 0.000000 1.460000 ( 1.609680)
succ 6.200000 0.000000 6.200000 ( 6.464387)
range step 2.960000 0.000000 2.960000 ( 3.104242)
step 2.830000 0.000000 2.830000 ( 2.962337)
jruby 1.2.0 (ruby 1.8.6 patchlevel 287) (2009-09-04 rev 6586)
[i386-java]
Rehearsal --------------------------------------------------
while 5.252000 0.000000 5.252000 ( 4.421000)
succ 18.914000 0.000000 18.914000 ( 18.914000)
range step 5.321000 0.000000 5.321000 ( 5.321000)
step 5.518000 0.000000 5.518000 ( 5.518000)
---------------------------------------- total: 35.005000sec
user system total real
while 4.393000 0.000000 4.393000 ( 4.393000)
succ 18.992000 0.000000 18.992000 ( 18.992000)
range step 5.695000 0.000000 5.695000 ( 5.695000)
step 5.485000 0.000000 5.485000 ( 5.485000)
robert@fussel:~$ uname -a
Linux fussel 2.6.31-19-generic #56-Ubuntu SMP Thu Jan 28 01:26:53 UTC
2010 i686 GNU/Linux
robert@fussel:~$ cat xx.rb
require ‘benchmark’
LI = 100_000_000
ST = 5
Benchmark.bmbm 15 do |b|
b.report “while” do
i = 0
while i < LI
i += ST
end
end
b.report “succ” do
i = 0
while i < LI
i = i.succ
end
end
b.report “range step” do
(0…LI).step ST do
end
end
b.report “step” do
0.step LI, ST do
end
end
end
robert@fussel:~$
Cheers
robert