Last active
May 19, 2024 19:41
-
-
Save MattOates/c5879a07b1ef2c013097 to your computer and use it in GitHub Desktop.
Combined primes benchmark with a parallel implementation that does well to keep up despite doing a lot more calculations!
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env perl6 | |
use v6; | |
use Stats; | |
sub bench(Str $name, Int $upto, &code) { | |
my ($start,$end); | |
my @times; | |
for 1..20 { | |
$start = now; | |
code($upto); | |
$end = now; | |
@times.push($end-$start); | |
} | |
my $sd = sd @times; | |
my $mu = mean @times; | |
say "$name: ran in $mu seconds (σ = $sd seconds)"; | |
} | |
sub MAIN(Int :$upto) { | |
bench 'primes-inline-loop', $upto, { | |
my Int @primes; | |
TOCHECK: loop (my $n = 2; $n <= $^max; $n++) { | |
for @primes -> Int $prime { | |
next TOCHECK if $n %% $prime; | |
} | |
@primes.push($n); | |
} | |
} | |
bench 'primes-inline-loop-upto-sqrt', $upto, { | |
my Int @primes; | |
TOCHECK: loop (my $n = 2; $n <= $^max; $n++) { | |
my Num $sqrt-n = sqrt $n; | |
for @primes -> Int $prime { | |
next TOCHECK if $n %% $prime; | |
last if $prime >= $sqrt-n; # OK to bail if ==; we checked %% above | |
} | |
@primes.push($n); | |
} | |
} | |
bench 'primes-inline-loop-upto-int-sqrt', $upto, { | |
my int @primes; | |
TOCHECK: loop (my int $n = 2; $n <= $^max; $n++) { | |
my int $sqrt-n = truncate sqrt $n; | |
for @primes -> int $prime { | |
next TOCHECK if $n %% $prime; | |
last if $prime >= $sqrt-n; # OK to bail if ==; we checked %% above | |
} | |
@primes.push($n); | |
} | |
} | |
bench 'primes-builtin-grep', $upto, { | |
my @primes = (2..$^max).grep: *.is-prime; | |
} | |
bench 'primes-builtin-parallel-grep', $upto, { | |
my @primes = (2..$^max).race(batch => $^max / 4, degree => 4).grep: *.is-prime; | |
} | |
bench 'primes-naive-grep', $upto, { | |
my @primes = (2 .. $^max).grep({ | |
(2 .. truncate sqrt $^n).grep($^n %% *).elems == 0; | |
}); | |
} | |
bench 'primes-naive-parallel-grep', $upto, { | |
my @primes = (2 .. $^max).race(batch => $^max / 4, degree => 4).grep({ | |
(2 .. truncate sqrt $^n).grep($^n %% *).elems == 0; | |
}); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
First run on an M1 Pro Macbook Pro
➜ zef git:(main) raku ~/bin/find-primes.raku --upto=1000
primes-inline-loop: ran in 0.0072473708 seconds (σ = 0.006680025362886249 seconds)
primes-inline-loop-upto-sqrt: ran in 0.002169841 seconds (σ = 0.0005846115771510021 seconds)
primes-inline-loop-upto-int-sqrt: ran in 0.001736742 seconds (σ = 0.0006214027234185742 seconds)
primes-builtin-grep: ran in 0.000584616 seconds (σ = 0.0005148058293779747 seconds)
primes-builtin-parallel-grep: ran in 0.00153531225 seconds (σ = 0.0019351125540771849 seconds)
primes-naive-grep: ran in 0.0210788355 seconds (σ = 0.0013931801572090125 seconds)
primes-naive-parallel-grep: ran in 0.01147687535 seconds (σ = 0.001198478877677276 seconds)
➜ zef git:(main) raku ~/bin/find-primes.raku --upto=4000
primes-inline-loop: ran in 0.0468484226 seconds (σ = 0.019635280771149354 seconds)
primes-inline-loop-upto-sqrt: ran in 0.010372989150000001 seconds (σ = 0.0005093287011327316 seconds)
primes-inline-loop-upto-int-sqrt: ran in 0.007157870500000001 seconds (σ = 0.0005815257291472761 seconds)
primes-builtin-grep: ran in 0.0018524338500000002 seconds (σ = 0.0004970552946949883 seconds)
primes-builtin-parallel-grep: ran in 0.0019807862999999997 seconds (σ = 0.0022700226223986925 seconds)
primes-naive-grep: ran in 0.13691626065 seconds (σ = 0.0015472421177950425 seconds)
primes-naive-parallel-grep: ran in 0.05019228535 seconds (σ = 0.003706547497701837 seconds)
➜ zef git:(main) raku ~/bin/find-primes.raku --upto=10000
primes-inline-loop: ran in 0.19926601495000001 seconds (σ = 0.011636135647852488 seconds)
primes-inline-loop-upto-sqrt: ran in 0.0290350873 seconds (σ = 0.0005717311702342393 seconds)
primes-inline-loop-upto-int-sqrt: ran in 0.01949524185 seconds (σ = 0.0007170818191406237 seconds)
primes-builtin-grep: ran in 0.0044379843 seconds (σ = 0.00045680951848042816 seconds)
primes-builtin-parallel-grep: ran in 0.00279419885 seconds (σ = 0.002497165698350676 seconds)
primes-naive-grep: ran in 0.5074069433 seconds (σ = 0.0039019076032818212 seconds)
primes-naive-parallel-grep: ran in 0.1813150039 seconds (σ = 0.0035306037434770176 seconds)