From: "headius (Charles Nutter)" <headius@...>
Date: 2012-11-01T05:21:48+09:00
Subject: [ruby-core:48681] [ruby-trunk - Feature #5378] Prime.each is slow


Issue #5378 has been updated by headius (Charles Nutter).


JRuby numbers for the various implementations proposed (best times out of ten in-process iterations):

mconigliario's version:

                   user     system      total        real
primes_up_to   2.100000   0.000000   2.100000 (  1.062000)
Prime.each     0.980000   0.010000   0.990000 (  0.883000)

h.shirosaki's version:

                   user     system      total        real
primes_up_to   2.100000   0.010000   2.110000 (  1.014000)
Prime.each     1.030000   0.000000   1.030000 (  0.930000)

calamitas's version:

                   user     system      total        real
primes_up_to   1.130000   0.020000   1.150000 (  0.467000)
Prime.each     1.020000   0.000000   1.020000 (  0.908000)

mame's version:

                   user     system      total        real
primes_up_to   0.180000   0.000000   0.180000 (  0.143000)
Prime.each     0.970000   0.000000   0.970000 (  0.948000)

Ruby 1.9.3p286 running mame's version:

                   user     system      total        real
primes_up_to   0.380000   0.000000   0.380000 (  0.382392)
Prime.each     0.790000   0.000000   0.790000 (  0.793005)

Definitely some room for improvement over the base implementation.
----------------------------------------
Feature #5378: Prime.each is slow
https://bugs.ruby-lang.org/issues/5378#change-32123

Author: mconigliaro (Mike Conigliaro)
Status: Assigned
Priority: Normal
Assignee: yugui (Yuki Sonoda)
Category: 
Target version: next minor


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://bugs.ruby-lang.org/