note
danaj
<p>tilly's is a very nice closure implementation. It isn't the fastest pure Perl SoE though. For example, for the first 5761455 primes (primes up to 10^8) tilly's code takes 35.7s on my Macbook. The vector sieve on RosettaCode <a href="http://rosettacode.org/wiki/Sieve_of_Eratosthenes#Odds_only.2C_using_vectors_for_lower_memory_use">here</a> takes 37.9s, and the string sieve <a href="http://rosettacode.org/wiki/Sieve_of_Eratosthenes#Odds_only.2C_using_strings_for_best_performance">here</a> takes only 10.2 seconds, albeit with more memory and not an iterator. Using the pure-Perl segmented sieve in Math::Prime::Util::PP takes 7.1 seconds. All of these are terrifically slow compared to C.</p>
<p>If you're looking for even faster SoEs, I recommend <a href="http://ntheory.org/sieves/benchmarks.html">Prime Sieve Benchmarks</a> for a list of benchmarks. The C code from AnonymousMonk back in 2003 works fine, but is about 2x slower than the "Trivial 4-line SoE" shown on that page, because it doesn't get the inner loop start correct. Of course they're all in C, though one is built into a Perl module. In general <a href="https://primesieve.org">primesieve</a> is the fastest and easiest solution for most projects.</p>
<p>To compare using XS modules, printing primes to 10^8. At this point a majority of our time is actually spent printing, which is why the specialized "print_primes()" routine stomps on everything else, since it has optimized C code (even C's printf is a major bottleneck once the sieving is fast enough).
<ul>
<li>3.4s Math::Prime::XS</li>
<li>2.8s Math::Prime::FastSieve</li>
<li>2.0s Math::Prime::Util "say for @{primes(1e8)}"</li>
<li>1.9s Math::Prime::Util "forprimes { say } 1e8"</li>
<li>0.15s Math::Prime::Util "print_primes(1e8);"</li>
</ul></p>
<p>Slightly better, here we're naively counting, except for the last one which uses a fast exact prime count method.
<ul>
<li>1.7s Math::Prime::XS</li>
<li>0.89s Math::Prime::FastSieve</li>
<li>0.39s Math::Prime::Util "$n++ for @{primes(1e8)}"</li>
<li>0.18s Math::Prime::Util "forprimes { $n++ } 1e8;"</li>
<li>0.00026s Math::Prime::Util "say prime_count(1e8)"</li>
</ul></p>
276103
1214579