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.
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 02/05/2010 07:36 PM, Aaron Gifford wrote:
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.
On Feb 5, 2:52 pm, Robert Klemme <shortcut...@googlemail.com> 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.
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 02/05/2010 09:19 PM, Intransition wrote:
On Feb 5, 2:52 pm, Robert Klemme <shortcut...@googlemail.com> 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.
>> 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.
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 |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 Feb 6, 8:40 am, Robert Klemme <shortcut...@googlemail.com> wrote:
On 02/05/2010 09:19 PM, Intransition wrote:
> On Feb 5, 2:52 pm, Robert Klemme <shortcut...@googlemail.com> 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.
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 |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.
Why? All method bodies did not do anything (apart from while's which needs to increment).
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?
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
···
On 02/06/2010 04:03 PM, Intransition wrote:
On Feb 6, 8:40 am, Robert Klemme <shortcut...@googlemail.com> wrote:
On 02/05/2010 09:19 PM, Intransition wrote:
On Feb 5, 2:52 pm, Robert Klemme <shortcut...@googlemail.com> wrote:
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.
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:~$
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.
