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