From: George <george.ogata@...>
Date: 2007-11-07T01:09:57+09:00
Subject: Re: sieve.rb sample

Hi Siep,

On Nov 6, 2007 10:14 PM, Siep Korteling <s.korteling@gmail.com> wrote:
>
> max = Integer(ARGV.shift || 100)
> sieve = []
> for i in 2 .. max
>   sieve[i] = i
> end
>
> for i in 2 .. Math.sqrt(max)
>   next unless sieve[i]
>   (i*i).step(max, i) do |j|
>     sieve[j] = nil
>   end
> end
> puts sieve.compact.join(", ")
>
>
> Is Math.sqrt(max) calculated every loop?

Shouldn't be, no.

> ....
> m=Math.sqrt(max)
> for i in 2 .. m
> ....
>
> runs about 20% faster on my machine.

I'm not sure how you're benchmarking it, but I'm not seeing such
behavior with the current svn HEAD.  What I did notice, however, was
that the first run of my Benchmark seemed to be noticably quicker than
the others, which I found rather odd:

      user     system      total        real
sieve1  1.080000   0.000000   1.080000 (  1.082122)
sieve2  1.340000   0.010000   1.350000 (  1.350781)
sieve1  1.360000   0.000000   1.360000 (  1.362670)
sieve2  1.350000   0.010000   1.360000 (  1.350056)

It was even more pronounced when I upped the iterations tenfold:

      user     system      total        real
sieve1 22.510000   0.050000  22.560000 ( 22.546830)
sieve2 50.500000   0.060000  50.560000 ( 50.510556)
sieve1 50.470000   0.070000  50.540000 ( 50.500493)
sieve2 50.480000   0.080000  50.560000 ( 50.503374)

If I added a call to #sieve2 (see comment in code below) before
running the timings, the benchmarks were brought back even again:

g@bang:~/tmp$ ruby19 sieve.rb
      user     system      total        real
sieve1  1.390000   0.000000   1.390000 (  1.392173)
sieve2  1.370000   0.000000   1.370000 (  1.376944)
sieve1  1.400000   0.000000   1.400000 (  1.425670)
sieve2  1.370000   0.010000   1.380000 (  1.393410)

Somehow calling #sieve2 is slowing down subsequent calls to #sieve1.
I don't know YARV well enough yet, but I'm curious as to what's
causing this.  :-/

g@bang:~/src/ruby$ ruby19 -v
ruby 1.9.0 (2007-11-06 patchlevel 0) [i686-linux]

Regards,
George.

Code:

def sieve1
  max = Integer(ARGV.shift || 1000000)
  sieve = []
  for i in 2 .. max
    sieve[i] = i
  end

  for i in 2 .. Math.sqrt(max)
    next unless sieve[i]
    (i*i).step(max, i) do |j|
      sieve[j] = nil
    end
  end
end

def sieve2
  max = Integer(ARGV.shift || 1000000)
  sieve = []
  for i in 2 .. max
    sieve[i] = i
  end

  m = Math.sqrt(max)
  for i in 2 .. m
    next unless sieve[i]
    (i*i).step(max, i) do |j|
      sieve[j] = nil
    end
  end
end

require 'benchmark'

Benchmark.bm do |x|
  # sieve2  # uncomment to remove the anomaly
  x.report('sieve1'){sieve1}
  x.report('sieve2'){sieve2}
  x.report('sieve1'){sieve1}
  x.report('sieve2'){sieve2}
end