Skip to content

Instantly share code, notes, and snippets.

@MattOates
Last active November 27, 2018 05:00
Show Gist options
  • Star 3 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save MattOates/c2e19950f46d1a1c241a to your computer and use it in GitHub Desktop.
Save MattOates/c2e19950f46d1a1c241a to your computer and use it in GitHub Desktop.
#!/usr/bin/env perl6
use v6;
use Stats;
#Tim's original times:
#primes-inline-loop(1000) ran in 2.425 seconds (σ = 0.213 seconds).
#primes-inline-loop-upto-sqrt(1000) ran in 2.311 seconds (σ = 0.131 seconds).
#primes-inline-loop-upto-int-sqrt(1000) ran in 2.274 seconds (σ = 0.161).
sub bench($name, &code) {
my ($start,$end);
my $max = 1000;
my @times;
for 1..100 {
$start = now;
code($max);
$end = now;
@times.push($end-$start);
}
my $sd = sd @times;
my $mu = mean @times;
say "$name: ran in $mu seconds (σ = $sd seconds)";
}
bench 'primes-inline-loop', {
my Int @primes;
loop (my $n = 2; $n <= $^max; $n++) {
# Use a loop-exit flag because labels are not implemented yet in Rakudo
my Bool $is-prime = True; # assume until proven otherwise
for @primes -> Int $prime {
($is-prime = False, last) if $n %% $prime;
}
@primes.push($n) if $is-prime;
}
}
bench 'primes-inline-loop-upto-sqrt', {
my Int @primes;
loop (my $n = 2; $n <= $^max; $n++) {
my Num $sqrt-n = sqrt $n;
# Use a loop-exit flag because labels are not implemented yet in Rakudo
my Bool $is-prime = True; # assume until proven otherwise
for @primes -> Int $prime {
($is-prime = False, last) if $n %% $prime;
last if $prime >= $sqrt-n; # OK to bail if ==; we checked %% above
}
@primes.push($n) if $is-prime;
}
}
bench 'primes-inline-loop-upto-int-sqrt', {
my Int @primes;
loop (my $n = 2; $n <= $^max; $n++) {
my Int $sqrt-n = truncate sqrt $n;
# Use a loop-exit flag because labels are not implemented yet in Rakudo
my Bool $is-prime = True; # assume until proven otherwise
for @primes -> Int $prime {
($is-prime = False, last) if $n %% $prime;
last if $prime >= $sqrt-n; # OK to bail if ==; we checked %% above
}
@primes.push($n) if $is-prime;
}
}
@MattOates
Copy link
Author

primes-inline-loop: ran in 0.308635043562439 seconds (σ = 0.0729929906546081 seconds)
primes-inline-loop-upto-sqrt: ran in 0.195664771466789 seconds (σ = 0.0386666711564992 seconds)
primes-inline-loop-upto-int-sqrt: ran in 0.208936484490399 seconds (σ = 0.0358119138232916 seconds)

@MattOates
Copy link
Author

Post GLR:

primes-inline-loop: ran in 0.336755138609061 seconds (σ = 0.00785057176785759 seconds)
primes-inline-loop-upto-sqrt: ran in 0.138902498197602 seconds (σ = 0.00645144910799771 seconds)
primes-inline-loop-upto-int-sqrt: ran in 0.14212326249274 seconds (σ = 0.00602594378470064 seconds)

@MattOates
Copy link
Author

The super good news post GLR 😼

bench 'primes-naive-parallel', {
    my @primes = (2 .. $^max).race(batch => ($^max/4).round, degree => 4).grep( *.is-prime );
}

primes-naive-parallel: ran in 0.0149324689357104 seconds (σ = 0.0157655363986777 seconds)

YAY!

@MattOates
Copy link
Author

primes-inline-loop: ran in 0.104453653971108 seconds (σ = 0.0110987629242834 seconds)
primes-inline-loop-upto-sqrt: ran in 0.0455166631366443 seconds (σ = 0.00430441749697748 seconds)
primes-inline-loop-upto-int-sqrt: ran in 0.0495610034603008 seconds (σ = 0.00597228719759492 seconds)

@JJ
Copy link

JJ commented Aug 30, 2016

After installing panda and
panda install Stats

results are

primes-inline-loop: ran in 0.0580656796274087 seconds (σ = 0.00159418753275446 seconds)
primes-inline-loop-upto-sqrt: ran in 0.0229888983774552 seconds (σ = 0.000843469230670578 seconds)
primes-inline-loop-upto-int-sqrt: ran in 0.0271452969241626 seconds (σ = 0.00242062958922672 seconds)

With

$ perl6 --version
This is Rakudo version 2016.08.1 built on MoarVM version 2016.08
implementing Perl 6.c.

And

 Intel(R) Core(TM) i7-4770 CPU @ 3.40GHz

@MattOates
Copy link
Author

Really nice! Shame Tim King hasn't responded to any emails from me :( I should really blog about benchmarks are showing a really good direction for P6. Most articles are like this, written 3 years ago and at least one if not two orders of magnitude out of date. Plenty of room to improve as you've noticed recently :)

@MattOates
Copy link
Author

primes-inline-loop: ran in 0.0103780771629563 seconds (σ = 0.0026101831797184 seconds)
primes-inline-loop-upto-sqrt: ran in 0.00845088332881545 seconds (σ = 0.0017436692620085 seconds)
primes-inline-loop-upto-int-sqrt: ran in 0.0101427212178877 seconds (σ = 0.00196348311703652 seconds)

@Matlib
Copy link

Matlib commented May 16, 2018

First loop with max=100000:

Rakudo version 2018.04.1 built on MoarVM version 2018.04.1
matlib@notek:~$ /tmp/primes.p6 100000
9592 primes
Execution time: 30.443s

Perl 5, version 26, subversion 2 (v5.26.2) built for x86_64-linux-gnu-thread-multi
matlib@notek:~$ /tmp/primes.pl 100000
9592 primes
Execution time: 4.057s

Same thing written in pure C:
matlib@notek:~$ /tmp/primes 100000
9592 primes
Execution time: 0.201s

#!/usr/bin/perl
use strict;
use warnings;
no warnings 'syntax';
use Time::HiRes;
my $start = Time::HiRes::time ();
my @primes;
N: for (my $n = 2; $n <= $ARGV [0]; $n ++)
{
	foreach (@primes)
	{
		next N unless $n % $_;
	}
	push (@primes, $n);
}
printf ("%d primes\nExecution time: %.3fs\n", scalar @primes, Time::HiRes::time () - $start);
#!/usr/bin/perl6
my $start = now;
my Int $max = @*ARGS[0].Int;
my Int @primes;
loop (my $n = 2; $n <= $max; $n++)
{
	my Bool $is-prime = True;
	for @primes -> Int $prime
	{
		($is-prime = False, last) if $n %% $prime;
	}
	@primes.push($n) if $is-prime;
}
printf "%d primes\nExecution time: %.3fs\n", @primes.elems, now - $start;

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment