From: Hiroshi Shirosaki <h.shirosaki@...>
Date: 2011-10-01T15:26:36+09:00
Subject: [ruby-core:39806] [Ruby 1.9 - Bug #5378] Prime.each is slow


Issue #5378 has been updated by Hiroshi Shirosaki.

File prime.patch added

It seems that converting from integer to bitmap tables in EratosthenesSieve class is slow.

This patch improves Prime performance.



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') { p primes_up_to(1500000).inject(0) { |memo,obj| memo + obj } }
  2.times do
    x.report('Prime.each') { p Prime.each(1500000).inject(0) { |memo,obj| memo + obj } }
  end
end


# before

$ ruby -v ~/prime_bench.rb
ruby 1.9.4dev (2011-10-01 trunk 33368) [x86_64-darwin11.1.0]
                   user     system      total        real
primes_up_to   2.530000   0.020000   2.550000 (  2.550595)
Prime.each     6.450000   0.010000   6.460000 (  6.461948)
Prime.each     0.880000   0.000000   0.880000 (  0.877138)


# after

$ ruby -v -Ilib ~/prime_bench.rb
ruby 1.9.4dev (2011-10-01 trunk 33368) [x86_64-darwin11.1.0]
                   user     system      total        real
primes_up_to   2.560000   0.020000   2.580000 (  2.583900)
Prime.each     4.630000   0.010000   4.640000 (  4.633154)
Prime.each     0.330000   0.000000   0.330000 (  0.325838)
----------------------------------------
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