Combined primes benchmark with a parallel implementation that does well to keep up despite doing a lot more calculations!

find-primes.p6

#!/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;
        });
    }
}

Finding just the first 1000 primes we get the following times:

primes-junction: ran in 1.66073073755107 seconds (σ = 0.0206100850915907 seconds)
primes-inline-loop: ran in 0.202653997378768 seconds (σ = 0.011790271133024 seconds)
primes-inline-loop-upto-sqrt: ran in 0.0975718533201189 seconds (σ = 0.00744531628583971 seconds)
primes-inline-loop-upto-int-sqrt: ran in 0.0973667200049783 seconds (σ = 0.0046157395648829 seconds)
primes-builtin-grep: ran in 0.00444661391006278 seconds (σ = 0.00259859473118987 seconds)
primes-builtin-parallel-grep: ran in 0.0112422533253806 seconds (σ = 0.0124179011405679 seconds)
primes-naive-grep: ran in 0.3853507565337 seconds (σ = 0.0281967246393655 seconds)
primes-naive-parallel-grep: ran in 0.0053202479338843 seconds (σ = 0.0085918281877937 seconds)

When we up the primes to find the first 4000 suddenly we see parallel come into play:

primes-inline-loop: ran in 1.55372596153846 seconds (σ = 0.0487761566628439 seconds)
primes-inline-loop-upto-sqrt: ran in 0.400759205606658 seconds (σ = 0.0248756843689261 seconds)
primes-inline-loop-upto-int-sqrt: ran in 0.41657058316766 seconds (σ = 0.00589925091158933 seconds)
primes-builtin-grep: ran in 0.768982644190727 seconds (σ = 0.0588293906287831 seconds)
primes-builtin-parallel-grep: ran in 0.515499118930656 seconds (σ = 0.0496987069370339 seconds)
primes-naive-grep: ran in 3.6274155587906 seconds (σ = 0.0515005976483521 seconds)
primes-naive-parallel-grep: ran in 2.64503737130319 seconds (σ = 1.06473626142782 seconds)

Find the first 4000 now even faster in parallel:

primes-inline-loop: ran in 2.42469081885017 seconds (σ = 0.0662052989904901 seconds)
primes-inline-loop-upto-sqrt: ran in 0.616707250507986 seconds (σ = 0.0215266789277347 seconds)
primes-inline-loop-upto-int-sqrt: ran in 0.630929839759211 seconds (σ = 0.0487531266482091 seconds)
primes-builtin-grep: ran in 1.07095588962815 seconds (σ = 0.0372840374986076 seconds)
primes-builtin-parallel-grep: ran in 0.0141229818270572 seconds (σ = 0.0246400596826532 seconds)
primes-naive-grep: ran in 3.94567029198385 seconds (σ = 0.310005296302405 seconds)
primes-naive-parallel-grep: ran in 0.00909935004642526 seconds (σ = 0.0118682432472145 seconds)

doh parallel code returns [] for some reason...

Find the first 1000:

primes-inline-loop: ran in 0.0847184927215749 seconds (σ = 0.00653991800649466 seconds)
primes-inline-loop-upto-sqrt: ran in 0.0341267607679786 seconds (σ = 0.002918595530725 seconds)
primes-inline-loop-upto-int-sqrt: ran in 0.0353628270736239 seconds (σ = 0.00286854652895954 seconds)
primes-builtin-grep: ran in 0.00278578290105668 seconds (σ = 0.0010083101883041 seconds)
primes-naive-grep: ran in 0.164191588638154 seconds (σ = 0.0119106317100529 seconds)

Find the first 4000:

primes-inline-loop: ran in 0.820945420146528 seconds (σ = 0.102421808132555 seconds)
primes-inline-loop-upto-sqrt: ran in 0.144921570539126 seconds (σ = 0.0049769280087846 seconds)
primes-inline-loop-upto-int-sqrt: ran in 0.152069456263921 seconds (σ = 0.0085906386451137 seconds)
primes-builtin-grep: ran in 0.715209365782299 seconds (σ = 0.0219503471885187 seconds)
primes-naive-grep: ran in 1.11546153846154 seconds (σ = 0.0608834430967651 seconds)

Find the first 10000:

primes-inline-loop: ran in 3.60023780884434 seconds (σ = 0.0485307508079927 seconds)
primes-inline-loop-upto-sqrt: ran in 0.401088174617687 seconds (σ = 0.010708371579181 seconds)
primes-inline-loop-upto-int-sqrt: ran in 0.41050630117862 seconds (σ = 0.0105410701615026 seconds)
primes-builtin-grep: ran in 2.90140372623522 seconds (σ = 0.186935300602485 seconds)
primes-naive-grep: ran in 3.99494429822877 seconds (σ = 0.08880099031206 seconds)

Find the first 1000:

primes-inline-loop: ran in 0.0863153095900084 seconds (σ = 0.00545417566092206 seconds)
primes-inline-loop-upto-sqrt: ran in 0.0324782168507454 seconds (σ = 0.00327724961985983 seconds)
primes-inline-loop-upto-int-sqrt: ran in 0.0346928255085518 seconds (σ = 0.00425161012027679 seconds)
primes-builtin-grep: ran in 0.00262430939226519 seconds (σ = 0.00115841525545125 seconds)
primes-naive-grep: ran in 0.166755793226381 seconds (σ = 0.0166214632287269 seconds)

Find the first 4000:

primes-inline-loop: ran in 0.7751544273631 seconds (σ = 0.0170898419092668 seconds)
primes-inline-loop-upto-sqrt: ran in 0.15702334828634 seconds (σ = 0.00612336584448666 seconds)
primes-inline-loop-upto-int-sqrt: ran in 0.160405405405405 seconds (σ = 0.00707816337907538 seconds)
primes-builtin-grep: ran in 0.697985277024409 seconds (σ = 0.0234028001051805 seconds)
primes-naive-grep: ran in 1.13563672664308 seconds (σ = 0.0571618379595419 seconds)

Find the first 10000:

primes-inline-loop: ran in 3.8401067081209 seconds (σ = 0.120365661925961 seconds)
primes-inline-loop-upto-sqrt: ran in 0.458401045109456 seconds (σ = 0.0516038688661802 seconds)
primes-inline-loop-upto-int-sqrt: ran in 0.466405544069523 seconds (σ = 0.0610229545439329 seconds)
primes-builtin-grep: ran in 2.87758751071545 seconds (σ = 0.154074734199533 seconds)
primes-naive-grep: ran in 4.23427025885341 seconds (σ = 0.231216507642805 seconds)

raku find-primes.p6 --upto=1000
primes-inline-loop: ran in 0.0059819452500000005 seconds (σ = 0.004668907526270199 seconds)
primes-inline-loop-upto-sqrt: ran in 0.00612508885 seconds (σ = 0.0016543207954406414 seconds)
primes-inline-loop-upto-int-sqrt: ran in 0.00312807945 seconds (σ = 0.0010985241689974402 seconds)
primes-builtin-grep: ran in 0.0008701288999999999 seconds (σ = 0.0005383776592040177 seconds)
primes-builtin-parallel-grep: ran in 0.00249316835 seconds (σ = 0.001838846646906883 seconds)
primes-naive-grep: ran in 0.0390340034 seconds (σ = 0.0037588704118367558 seconds)
primes-naive-parallel-grep: ran in 0.0241461431 seconds (σ = 0.0022330027133252955 seconds)

raku find-primes.p6 --upto=4000
primes-inline-loop: ran in 0.033629628950000004 seconds (σ = 0.006648503613195089 seconds)
primes-inline-loop-upto-sqrt: ran in 0.0228248987 seconds (σ = 0.002130113336848532 seconds)
primes-inline-loop-upto-int-sqrt: ran in 0.01510629605 seconds (σ = 0.0015419873459969979 seconds)
primes-builtin-grep: ran in 0.0025033154500000003 seconds (σ = 0.0007599109150009766 seconds)
primes-builtin-parallel-grep: ran in 0.002675187 seconds (σ = 0.0019132264604405792 seconds)
primes-naive-grep: ran in 0.27961235819999997 seconds (σ = 0.01427041870039437 seconds)
primes-naive-parallel-grep: ran in 0.10735563045 seconds (σ = 0.01090097056305715 seconds)

raku find-primes.p6 --upto=10000
primes-inline-loop: ran in 0.14017285955 seconds (σ = 0.01225077013417422 seconds)
primes-inline-loop-upto-sqrt: ran in 0.06237731965 seconds (σ = 0.005235357854880181 seconds)
primes-inline-loop-upto-int-sqrt: ran in 0.0329874452 seconds (σ = 0.0019993036980522163 seconds)
primes-builtin-grep: ran in 0.00586502905 seconds (σ = 0.0009077538900541895 seconds)
primes-builtin-parallel-grep: ran in 0.0033269004499999998 seconds (σ = 0.0025038392498444055 seconds)
primes-naive-grep: ran in 1.3193265539 seconds (σ = 0.027068861214782018 seconds)
primes-naive-parallel-grep: ran in 0.5437498864 seconds (σ = 0.00983717863745748 seconds)

raku find-primes.p6 --upto=1000
primes-inline-loop: ran in 0.008660391350000001 seconds (σ = 0.003211351893340412 seconds)
primes-inline-loop-upto-sqrt: ran in 0.0046972503 seconds (σ = 0.0030790326776700384 seconds)
primes-inline-loop-upto-int-sqrt: ran in 0.0055529983 seconds (σ = 0.0023747971629474486 seconds)
primes-builtin-grep: ran in 0.0015005363000000001 seconds (σ = 0.002016950206788938 seconds)
primes-builtin-parallel-grep: ran in 0.005358949 seconds (σ = 0.006405673705248168 seconds)
primes-naive-grep: ran in 0.04600502765 seconds (σ = 0.00889591301107634 seconds)
primes-naive-parallel-grep: ran in 0.031814976499999995 seconds (σ = 0.006417407771306549 seconds)

raku find-primes.p6 --upto=4000
primes-inline-loop: ran in 0.09259022795 seconds (σ = 0.013403383708464542 seconds)
primes-inline-loop-upto-sqrt: ran in 0.0189525164 seconds (σ = 0.007869147458685184 seconds)
primes-inline-loop-upto-int-sqrt: ran in 0.02391939905 seconds (σ = 0.0021665191941684743 seconds)
primes-builtin-grep: ran in 0.0048600346 seconds (σ = 0.0039553147103356615 seconds)
primes-builtin-parallel-grep: ran in 0.009992852350000001 seconds (σ = 0.012552403579574203 seconds)
primes-naive-grep: ran in 0.34906389125000004 seconds (σ = 0.0541279268961619 seconds)
primes-naive-parallel-grep: ran in 0.19844532305 seconds (σ = 0.012962662209210276 seconds)

raku find-primes.p6 --upto=10000
primes-inline-loop: ran in 0.43534172990000003 seconds (σ = 0.06955750104457165 seconds)
primes-inline-loop-upto-sqrt: ran in 0.0496837132 seconds (σ = 0.00809527795087767 seconds)
primes-inline-loop-upto-int-sqrt: ran in 0.0609998166 seconds (σ = 0.005529290036786555 seconds)
primes-builtin-grep: ran in 0.0077852791000000005 seconds (σ = 0.0029963404407812254 seconds)
primes-builtin-parallel-grep: ran in 0.0093485796 seconds (σ = 0.009076229526148876 seconds)
primes-naive-grep: ran in 1.22618909395 seconds (σ = 0.20676152412400306 seconds)
primes-naive-parallel-grep: ran in 0.7368552409 seconds (σ = 0.0583776018112988 seconds)

Running with Rakudo v2021.12 on MacBook Pro with M1 Pro 10 core

raku find-primes.raku --upto=1000
primes-inline-loop: ran in 0.01004322775 seconds (σ = 0.015566435698432525 seconds)
primes-inline-loop-upto-sqrt: ran in 0.0021444244 seconds (σ = 0.0006014301541457775 seconds)
primes-inline-loop-upto-int-sqrt: ran in 0.0017250761 seconds (σ = 0.0005452344272131783 seconds)
primes-builtin-grep: ran in 0.0006137899 seconds (σ = 0.0005555497241630495 seconds)
primes-builtin-parallel-grep: ran in 0.0015878532 seconds (σ = 0.001983326629655843 seconds)
primes-naive-grep: ran in 0.022108198449999998 seconds (σ = 0.0009993921414470288 seconds)
primes-naive-parallel-grep: ran in 0.01397306805 seconds (σ = 0.0008803797823021999 seconds)

raku find-primes.raku --upto=4000
primes-inline-loop: ran in 0.044283732799999996 seconds (σ = 0.011909012650670021 seconds)
primes-inline-loop-upto-sqrt: ran in 0.0091936939 seconds (σ = 0.0005906285005060453 seconds)
primes-inline-loop-upto-int-sqrt: ran in 0.0072716675 seconds (σ = 0.0005839996615820925 seconds)
primes-builtin-grep: ran in 0.0018863263500000001 seconds (σ = 0.0007506107664876773 seconds)
primes-builtin-parallel-grep: ran in 0.00185553465 seconds (σ = 0.0020809822610920736 seconds)
primes-naive-grep: ran in 0.14554954675 seconds (σ = 0.0019736673265611866 seconds)
primes-naive-parallel-grep: ran in 0.07221033545 seconds (σ = 0.006950228909433103 seconds)

raku find-primes.raku --upto=10000
primes-inline-loop: ran in 0.2011304914 seconds (σ = 0.013926456832506444 seconds)
primes-inline-loop-upto-sqrt: ran in 0.02549488425 seconds (σ = 0.0005571448593402978 seconds)
primes-inline-loop-upto-int-sqrt: ran in 0.01931281135 seconds (σ = 0.0006822094200030417 seconds)
primes-builtin-grep: ran in 0.00436385715 seconds (σ = 0.0005480360717324083 seconds)
primes-builtin-parallel-grep: ran in 0.0023704015500000002 seconds (σ = 0.0023306963335366837 seconds)
primes-naive-grep: ran in 0.5454789365 seconds (σ = 0.0024097584454185364 seconds)
primes-naive-parallel-grep: ran in 0.2864098717 seconds (σ = 0.03974775012003365 seconds)

Running with Rakudo v2023.02 and MoarVM version 2023.02 on a Windows 11 PC using an AMD Ryzen 5 5600X MPK Prism and 2x16GB CorVenLPX DDR4 3600C 18 of memory.

PS C:\Users\matto> raku find-primes.raku --upto=1000
primes-inline-loop: ran in 0.0050568950000000005 seconds (σ = 0.0019135264524948324 seconds)
primes-inline-loop-upto-sqrt: ran in 0.0023065 seconds (σ = 0.0012005748645939171 seconds)
primes-inline-loop-upto-int-sqrt: ran in 0.001802615 seconds (σ = 0.001146828056373326 seconds)
primes-builtin-grep: ran in 0.0005507299999999999 seconds (σ = 0.000850845533912743 seconds)
primes-builtin-parallel-grep: ran in 0.0019552099999999998 seconds (σ = 0.0029532143600834223 seconds)
primes-naive-grep: ran in 0.023995045 seconds (σ = 0.003148231928632888 seconds)
primes-naive-parallel-grep: ran in 0.013312584999999998 seconds (σ = 0.0019379224621425633 seconds)

PS C:\Users\matto> raku find-primes.raku --upto=4000
primes-inline-loop: ran in 0.043977050000000004 seconds (σ = 0.0038821551485842074 seconds)
primes-inline-loop-upto-sqrt: ran in 0.009914275 seconds (σ = 0.0012950653723423746 seconds)
primes-inline-loop-upto-int-sqrt: ran in 0.007219765 seconds (σ = 0.0013275851371994162 seconds)
primes-builtin-grep: ran in 0.0016525700000000001 seconds (σ = 0.0010420731572608353 seconds)
primes-builtin-parallel-grep: ran in 0.00252828 seconds (σ = 0.003520011884978961 seconds)
primes-naive-grep: ran in 0.16787363 seconds (σ = 0.007972814090928723 seconds)
primes-naive-parallel-grep: ran in 0.078848115 seconds (σ = 0.007144407603725878 seconds)

PS C:\Users\matto> raku find-primes.raku --upto=10000
primes-inline-loop: ran in 0.196803405 seconds (σ = 0.007683908761939135 seconds)
primes-inline-loop-upto-sqrt: ran in 0.024585614999999998 seconds (σ = 0.0028958402375199974 seconds)
primes-inline-loop-upto-int-sqrt: ran in 0.019132635000000002 seconds (σ = 0.0025026631529515508 seconds)
primes-builtin-grep: ran in 0.00370609 seconds (σ = 0.0011789071852645319 seconds)
primes-builtin-parallel-grep: ran in 0.0034111500000000004 seconds (σ = 0.0037983079611655394 seconds)
primes-naive-grep: ran in 0.634306935 seconds (σ = 0.04044783802771811 seconds)
primes-naive-parallel-grep: ran in 0.27289585 seconds (σ = 0.013028538827568555 seconds)