Forum: Ruby Fastest way to iterate over a range in steps

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 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.

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 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.
> 
> 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 Klemme <shortcut...@googlemail.com> 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