From: Peter Vanbroekhoven <calamitates@...>
Date: 2011-10-03T16:15:25+09:00
Subject: [ruby-core:39854] [Ruby 1.9 - Bug #5378] Prime.each is slow


Issue #5378 has been updated by Peter Vanbroekhoven.


Note that the primes_up_to method Mike posted is not quite optional in that the intended optimization in the form of the reject doesn't do anything. The reject is executed before the loop and so the loop is still executed for all numbers instead of just for the primes.

If you use the version below instead, it is over 2.5 times faster for 2 mil primes on my machine. That would make the new built-in version still almost 5 times slower than the pure-Ruby version. Note also that in my benchmarks I changed the inject block to just return memo and not calculate the sum because that skews the results by quite a bit; there's the extra summing, but the sum gets in the Bignum range and so it adds object creation and garbage collection.

def primes_up_to(n)
 s = [nil, nil] + (2..n).to_a
 (2..(n ** 0.5).to_i).each do |i|
   if s[i]
     (i ** 2).step(n, i) { |j| s[j] = nil }
   end
 end
 s.compact
end

----------------------------------------
Bug #5378: Prime.each is slow
http://redmine.ruby-lang.org/issues/5378

Author: Mike Conigliaro
Status: Open
Priority: Normal
Assignee: 
Category: 
Target version: 
ruby -v: 1.9.2p290 (2011-07-09 revision 32553) [x86_64-darwin10.8.0]


See discussion here: https://gist.github.com/1246868


require 'benchmark'
require 'prime'

def primes_up_to(n)
  s = [nil, nil] + (2..n).to_a
  (2..(n ** 0.5).to_i).reject { |i| s[i].nil? }.each do |i|
    (i ** 2).step(n, i) { |j| s[j] = nil }
  end
  s.compact
end

Benchmark.bm(12) do |x|
  x.report('primes_up_to') { primes_up_to(2000000).inject(0) { |memo,obj| memo + obj } }
  x.report('Prime.each') { Prime.each(2000000).inject(0) { |memo,obj| memo + obj } }
end


$ ruby -v
ruby 1.9.2p290 (2011-07-09 revision 32553) [x86_64-darwin10.8.0]
$ ruby lol.rb 
                  user     system      total        real
primes_up_to  1.470000   0.020000   1.490000 (  1.491340)
Prime.each    7.820000   0.010000   7.830000 (  7.820969)


-- 
http://redmine.ruby-lang.org