Fibonacci in Perl 6 talk
Wellington Perl Mongers

By Steve Piner
steve.piner@gmail.com




This talk came about because I stupidly said within earshot of Grant that I was thinking about doing a presentation^H^H^H^H
--
--
This talk came about because I was reading about Perl 6 and they were often using the Fibonacci sequence to illustrate some point

I wondered how good were the various ways of doing things. And how well do they compare to Perl 5?

And since Fibonacci kept coming up, I figured I might as well use that as a test case.
--
This is not a talk about the Fibonacci sequence
--

That said, you might have seen this

This is the result of drawing Pascal's triangle, where odd numbers are white and even numbers are black.
--
To make Pascal's triangle, you start with a hexagonal grid
--
Then put a 1 in it
1

Then each cell on the row below is the sum of the two numbers above it.
--
 1
1 1
--
Then
  1
 1 1
1 2 1
--
And
   1
  1 1
 1 2 1
1 3 3 1
--
So
    1
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1
--
On
     1
    1 1
   1 2 1
  1 3 3 1
 1 4 6 4 1
1 5 10 10 5 1
--
      1
     1 1
    1 2 1
   1 3 3 1
  1 4 6 4 1
 1 5 10 10 5 1
1 6 15 20 15 6 1
--
       1
      1 1
     1 2 1
    1 3 3 1
   1 4 6 4 1
  1 5 10 10 5 1
 1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
--
If you squint a little and concentrate on the odd numbers, you can start to see the pattern emerging even here.
--
[Colour odd/even different colours]
--
What's this got to do with Fibonacci? Nothing, it's just a cool pattern that falls out of maths simple enough for me to understand. Kind of like a Fractals for dummies.
--
--
And then I offered to do this talk.

And on the Wikipedia page for the Fibonacci number is this image.

How cool is that?

--

So what is the Fibonacci sequence

Named after Leonardo of Pisa
It appears unexpectedly often in mathematics
It is also quite common in nature
It is known for its relationship to the Golden Ratio
The sequence starts with 0 and 1
Add the previous two numbers to get the next number
The first few numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049 ...

--

And for this talk I'm mainly concerned with the recursive properties of this:

fib(0) = 0
fib(1) = 1
fib(n) = fib(n - 1) + fib(n - 2)

I have a few different ways of writing the Fibonacci sequence in both Perl 5 and Perl 6. I have a script in each Perl that I'll use to compare the running time.

Here's the Perl 5 boilerplate I use:
--
use v5.22;
use strict;
use warnings;
use autodie;

And the Perl 6 equivalent

use v6;

Note that this boilerplate is very important: it will save you hours of puzzling over cryptic error messages
--
C:\Users\Steve>perl \\prole\steve\Fibonacci-Perl6-presentation\fib.pl6
Illegal declaration of subroutine main::fib at \\prole\steve\Fibonacci-Perl6-presentation\fib.pl6 line 11.
--
before you realise your fingers were on autopilot and typed 'perl' not 'perl6'.
--
So here is our first Fibonacci sequence of the evening. Perl 5.

sub fib_basic {
    my ($n) = @_;
    if ($n > 1) {
        return fib_basic($n - 1) + fib_basic($n - 2);
    }
    return $n;
}

And here it is in Perl 6
--
sub fib_perl5 {
    my ($n) = @_;
    if ($n > 1) {
        return fib_perl5($n - 1) + fib_perl5($n - 2);
    }
    return $n;
}

Got that? The only change I made was to rename the function.

That surprised me too.

The more 'Perl 6'-y version of that function is this.
--
sub fib-basic($n) {
    if $n > 1 {
       return fib-basic($n - 1) + fib-basic($n - 2);
    }
    return $n;
}

So how am I going to test them. In Perl 5 world, the standard is Benchmark, which uses a many-repetitions approach. You run something lots of times to get an indication of how quickly something will happens. Ideally you're comparing things that you can run at the same time, so the comparison happens with the same background load on the computer which should make a comparison more meaningful.

I'm not going to do this. I don't know whether there is a Benchmark for Perl 6, and I want to test some methods that might have very different first-run times.

So here is my timing harness for Perl 6
--
sub time($function) {
    my $stop;
    my $start = now;
    $function.();
    $stop = now;
    say $stop - $start;
}

And for Perl 5.
--
sub time1 {
    my ($function) = @_;
    my $stop;
    my $start = time;
    $function->();
    $stop = time();
    say $stop - $start;
}

No, not really.

Perl 6 time is measured in instants, which for our purposes can be considered real numbers.

Time in Perl 5 is an integer value, so approximately a million times less granular. Here's the actual equivalent in Perl 5.
--
use Time::HiRes 'gettimeofday';

sub time2 {
    my ($function) = @_;
    my ($stop_s, $stop_ms);
    my ($start_s, $start_ms) = gettimeofday;
    $function->();
    ($stop_s, $stop_ms) = gettimeofday;

    my ($duration_s, $duration_ms) = ($stop_s - $start_s, $stop_ms - $start_ms);
    if ($duration_ms < 0) {
        $duration_s--;
        $duration_ms += 1_000_000;
    }
    printf "%d.%06d\n", $duration_s, $duration_ms;
}

These functions display times in microseconds, which is fine enough for what I'm doing.

Next, how I call those functions.
--
Perl 5

my @tests = (
    [ 'Basic',                  \&fib_basic     ],
    # I might just be adding another couple here, maybe.
);

my $n = 22;

foreach (@tests) {
    my ($title, $sub) = @$_;
    say $title;
    time2 sub { $result = $sub->($n) };
}

And Perl 6
--
my @tests =
    'Perl 5',              &fib_perl5,
    'Basic',               &fib-basic,
    #`( Gosh, that's a suspicious amount 
        of space between the two columns. )
;

my $n = 22;

for @tests -> $title, $sub {
    say $title;
    time { $sub.($n) }
}

Things to note: parenthesis on the array declaration is optional. That's also the multiline comment syntax - the parenthesis can be replaced by other characters or brackets, like in regex matching in Perl 5.

In the Perl 5 version I used a reference so I didn't have to faff with array indexing in the loop. In the Perl 6 version of the loop, I could simply grab as many as I wanted at a time.

So, lets see how well they run
--
(Perl 5)
Basic
0.015186

Incidentally earlier versions of the script were displaying the final result, so I could check that they were working. I took it out when I realised that it is likely to skew the results.

Here's the Perl 6 results.
--
(Perl 6)
Perl 5
0.922909

Uh-oh. 60 times slower.

(Perl 6)
Basic
0.0991101

Oh, that's better. Only 6.5 times slower

But lets try to make that better. In Perl 5 we could optimise it by doing something like this:
--
sub fib_optimised {
    $_[0] > 1 ? fib_optimised($_[0] - 1) + fib_optimised($_[0] - 2) : $_[0];
}
--
which runs in 0.012013 seconds, or over 20% faster.

Lets try it in Perl 6.
--
sub fib-optimised {
    @_[0] > 1 ?? fib-optimised(@_[0] - 1) + fib-optimised(@_[0] - 2) !! @_[0];
}

Optimised
0.4099719

Oops. Four times slower than the basic version.

Let's try that again.

Lets try swapping out bits from the basic version and see if we can see what is making it slow.
--
sub fib-optimised-v2($n) {
    $n > 1 ?? fib-optimised-v2($n - 1) + fib-optimised-v2($n - 2) !! $n;
}

sub fib-optimised-v3 {
    if @_[0] > 1 {
        fib-optimised-v3(@_[0] - 1) + fib-optimised-v3(@_[0] - 2);
    }
    else {
        @_[0];
    }
}

The initial name of this function was fib-optimised-2, but that gets parsed as fib-optimised - 2...
--
Optimised v2 runs 16-17% faster than the basic version.
--
Optimised v3
Use of uninitialized value of type Any in numeric context  in block  at fib.pl6 line 28
Use of uninitialized value of type Any in numeric context  in block  at fib.pl6 line 28
Use of uninitialized value of type Any in numeric context  in block  at fib.pl6 line 28
Use of uninitialized value of type Any in numeric context  in block  at fib.pl6 line 28

What?

What's on line 28?
--
sub fib-optimised-v3 {
    if @_[0] > 1 {
28>        fib-optimised-v3(@_[0] - 1) + fib-optimised-v3(@_[0] - 2);
    }
    else {
        @_[0];
    }
}

The reason is that the block is a closure and has a @_ of its own. All blocks are closures unless they stand alone - according to the docs, most flow control is just ways to tell Perl 6 when, how, and how many times to enter the block.
--
Here's a variation.

sub fib-optimised-v4 {
    $^a > 1 ?? fib-optimised-v4($^a - 1) + fib-optimised-v4($^a - 2) !! $^a;
}

$^a is a placeholder variable. They can be used in a bare block or subroutine without an explicit parameter list. They are assigned in Unicode order. This is what has become of the special-casing of $a and $b as used in sort in Perl 5.
--
This is 14-15% faster than the basic version, a little slower than v2.
--
sub fib-optimised-v5($n) {
    if $n > 1 {
        fib-optimised-v5($n - 1) + fib-optimised-v5($n - 2);
    }
    else {
        $n;
    }
}

All I did here was just drop out the return.
--
This is about 35-36% faster than the basic version.
--
It's still about 4.25 times slower than the basic Perl 5 version, but not too bad.

So what other ways can we do this.

You may have seen this.
--
use v6;

sub MAIN(Str $action, *@files, Bool :$verbose, Int :$count, Str :$message) {
}

Which, if run without the correct parameters gives this
--
perl6 utility.pl6
Usage:
  utility.pl6 [--verbose] [--count=<Int>] [--message=<Str>] <action> [<files> ...]

We can use a multi, which is a sub with a number of implementations, where the correct implementation is chosen based on the parameters passed. This works particularly well with the type system.
--

multi pass(Test $item) { ... }

multi pass(Parcel $item) { ... }

multi pass(Wind $item) { ... }

So you can pass a test, you can pass a parcel.

But it's not just types. You can also distinguish between implementations using literal constants.
--
I've also changed which parameters are required as you might expect in differing contexts within a real application.

multi MAIN('fold', *@files, Bool :$verbose, Int :$count, Str :$message) {
}

multi MAIN('spindle', *@files, Bool :$verbose, Int :$count, Str :$message!) {
}

multi MAIN('mutilate', *@files, Bool :$verbose, Int :$count!, Str :$message) {
}

Which gives...
--
perl6 multility.pl6
Usage:
  multility.pl6 [--verbose] [--count=<Int>] [--message=<Str>] fold [<files> ...]
  multility.pl6 --message=<Str> [--verbose] [--count=<Int>] spindle [<files> ...]
  multility.pl6 --count=<Int> [--verbose] [--message=<Str>] mutilate [<files> ...]

So back to our Fibonacci implementations.
--
multi fib-multi(0) { 0 }
multi fib-multi(1) { 1 }
multi fib-multi($n) { fib-multi($n - 1) + fib-multi($n - 2) }

Looks kinda familiar, doesn't it...
fib(0) = 0
fib(1) = 1
fib(n) = fib(n - 1) + fib(n - 2)

Multis are resolved in order. It's worth noting that although it is declared like three subs, it is considered one function, and will work with our existing test infrastructure.

So how does it run?
--
Multi
1.609581

Ow. 16 times slower than the basic version. And precious little room for improvement.

Ok, lets try out some other features. Constraints.
--
sub fib-constraint($n where * >= 0) {
    if $n > 1 {
        return fib-constraint($n - 1) + fib-constraint($n - 2);
    }
    return $n;
}

That star is known as the whatever star. That's saying where whatever is greater-than or equal to zero.
--
Constraint
0.1881728

This takes about 1.9 times as long as the basic version.

Lets try out that new-fangled type system.
--
sub fib-typed(Int $n --> Int) {
    if $n > 1 {
       return fib-typed($n - 1) + fib-typed($n - 2);
    }
    return $n;
}

Small enough a change. We now require $n to be an int, and we return an int.
--
Typed
0.0600536

That's our best so far. Probably would have been faster if I had dropped the returns off it. That 60-61% of the basic Perl 6 version, and just under 4 times as long as the Perl 5 version.

Ok, lets try with a better matching type.
--
sub fib-typed-uint(UInt $n --> UInt) {
    if $n > 1 {
       return fib-typed-uint($n - 1) + fib-typed-uint($n - 2);
    }
    return $n;
}
--
Better type
0.5104746

Hmm. 5.15 times as slow. Not quite as good a fit as Int.

Ok, how about requiring that the number is defined?
--
sub fib-defined-int(Int:D $n --> Int:D) {
    if $n > 1 {
       return fib-defined-int($n - 1) + fib-defined-int($n - 2);
    }
    return $n;
}

In theory, this should be faster, as Perl no longer has to check the definedness of a value.
--
In practice, it's pretty much exactly the same.

So it's not going so well for Perl 6. Let's try something that we can't do in Perl 5.
--
constant DEPTH = 5;
sub fib-promise($n, $depth = DEPTH) {
    if $n < 2 {
        return $n;
    }
    given ($depth) {
        when DEPTH {
            my @promises = (
                fib-promise($n - 2, $depth - 1), 
                fib-promise($n - 1, $depth - 1),
            ).flat;
            await Promise.allof(@promises);
            return [+] @promises>>.result;
        }
        when 1 {
            return start { fib-promise($n - 1, 0) },
                start { fib-promise($n - 2, 0) };
        }
        when * > 0 {
            return fib-promise($n - 1, $depth - 1), 
                fib-promise($n - 2, $depth - 1);
        }
    }
    return fib-promise($n - 1, 0) + fib-promise($n - 2, 0);
}

Concurrency. Ok, it can be done in Perl 5, but I've never seen it used in anger.

Firstly, we've got our terminating condition.

Then, based on how deeply we are in to the recursion, we do different things. I've got the depth backwards: it counts down the deeper we are.

So when this function is called, it will call itself at a different depth, gathering the responses. Notice the .flat method call - Perl 6 structures nest.

We then wait for all the promises to finish, add the results together and return them.

---

When depth is 1, we create the promises for this call, and return them in a list.

Then when whatever is greater than 0, call the next level down. Note that this block won't be called when $depth is 1 or DEPTH, because the 'when 1' and 'when DEPTH' blocks above will have already been checked and executed if they should. 'Given', which is Perl 6's version of switch doesn't automatically fall through to the next condition.

Finally, outside of the given block, we do the actual work.

How it works when running is like this.
---
So we call this. There is a default parameter there in the function declaration, so this is actually...
--
At this depth, this function is concerned with gathering up the promises made and waiting for them to finish before summing them for our result.

---
fib($n, 5)
---
Our next call simply returns promises it gets from the calls it makes.

What is the '$' there?
That's an anonymous variable.
---
You use it when you need a variable, but don't care about the result.
For example..
If you had a CSV, and you wanted the first and third columns from it.
---

Split will give you all the columns. So using '$' you can pick out the columns you want without having to declare a junk variable.

I should say that you can use 'undef' in Perl 5 in the same way.

I'm using an anonymous variable there because I don't know what the value is. It's not for Perl, it's for you guys. In the first call the value is $n. In the second, it's either $n-1 or $n-2. In the third it's from $n-2 to $n-4, and so on.
--
You could say that I should have used whatever star.

I decided against using the whatever star because I figured that the anonymous variable was semantically closer to the meaning I wanted. However, an argument could be made each way.
--
This does have the bonus of showing off some more new stuff though.
--
Whatever.

Anyway,
--

Here we are, and at this level we're just returning promises.
--
Same again, for the next two levels.
--
Then at level 1, all the promises are created. We create 32 promises here. In theory, this should scale up nicely on 32 core processors.
--
Finally, once we've created the promises, we do the usual Fibonacci.

So how does it perform?
--
This is my CPU load while running the test.
[CPU load]

It's certainly concurrenting.

You can see the load for the entire test running, then the concurrency test runs. You can also see why I ran this on my 6 core/12 threaded Windows box rather than my 2 core Linux server.

So how does it run?
--
Well, our target is the Perl 5 basic version, so how did we do?
--
0.6 of a second. That's 6 times worse than the basic Perl 6 version!
--
--
Hang on. What about thread start up time?
--
Err, no.

I don't know whats going on here. I suspect there is something being shared and that Perl 6 is busywaiting for it, because if it was just being blocked, then the load wouldn't be so high. 
--
I remembered that Perl 6 passes parameters as aliases - so the value is a read only reference. So lets try making those copies, in case that has some effect.
--
Not so great.

Hang on.
--
--
--
--
--
We can split this function into the four things it does, and see how it performs when there's a lot less 'what are we doing now' going on.

Here's the first one. Gathering up the promises and waiting for the results as before.
--
Here's the second one. Still just passing stuff around until depth is zero, at which point it calls the third one.
--
Here's the third and fourth ones. The third creates all the promises. The fourth is the fastest Perl 6 Fibonacci we've found so far.

So how do we do?
--
A lot better, but still not as good as the basic Perl 6 version.

I can make it faster...
--
by reducing the concurrency. :-(
--
Interestingly enough, running it on my Linux server - which has a lot less grunt - gives the same sort of ratios. So it looks like something is a bit rotten with Perl 6's threading at this time.

I've reported it as a bug.

So how else can we make things go faster?
--
We can cache stuff.

Here's an implementation of a caching Fibonacci sequence.

sub fib_cache {
    state @fib_cache;
    my ($n) = @_;
    if ($n < @fib_cache) {
        return $fib_cache[$n];
    }
    if ($n > 1) {
        $fib_cache[$n] = fib_cache($n - 1) + fib_cache($n - 2);
    }
    else {
        if ($n) {
            fib_cache(0);
        }
        $fib_cache[$n] = $n;
    }
    return $fib_cache[$n];
}

And how does it run?
--
Pretty good
--
This was building up a cache, so the second run should be faster.
--
Umm
--
--
The caching can be separated out from the actual functionality, and the Perl 5 module for that is Memoize.
--
use Memoize;

sub fib_memoized {
    my ($n) = @_;
    if ($n > 1) {
        return fib_memoized($n - 1) + fib_memoized($n - 2);
    }
    return $n;
}
memoize('fib_memoized');

And here's another case where the Fibonacci sequence appears
--
The Memoize documentation!
--
Anyway, how did it go?
--
Memoized - first run
0.000333
--
Pretty good. But Memoize is a cache, so some of this time will have been spent caching results. So how does it go when we run it a second time?

Memoized - second run
0.000011

So how do we do that in Perl 6?
--
use experimental :cached;
sub fib-cached($n) is cached {
    if $n > 1 {
       return fib-basic($n - 1) + fib-basic($n - 2);
    }
    return $n;
}

Just say that the function is cached.

And the results: the first run.
--
Cached - 1st run
0.0845879

And the second run.
--
Cached - 2nd run
0.0005003

So how do the two compare?
--
Run     Perl 5    Perl 6     Ratio
First   0.000333  0.0120049  36
Second  0.000011  0.0005003  45
Ratio   30        24

This comparison is interesting because it's almost a fair comparison. Perl 5 is written in C, which is a much lower level language, much closer to the machine, and hence performs a lot better. Perl 6 is largely written in NQP, or Not-Quite-Perl, and runs on virtual machines - MoarVM or JVM - therefore its performance is limited by the virtual machine as well as the underlying hardware.

But both Memoize and cached are written in their respective languages, so in theory they should be more comparable.

But even here, it looks like Memoize takes the performance cake. Even relatively speaking.
--
And here we're comparing it against the basic Fibonacci implementations.

Run     Perl 5    Perl 6     Ratio
Basic   0.015186  0.0991101  7
Second  0.000011  0.0005003  45
Ratio   1,381     198

A big overall speed-up for Perl 5. There's really not much else to say. There is a decent speed increase in Perl 6, too, but there's an order of magnitude difference in the improvement.

So what else can we do?
--
Well, there is this.

This function differs from the previous examples in that it's not recursive - it iteratively builds up an array to the size needed to be able to return the value we need. It's very similar to the cache version, but the cache version implicitly relied on the cache array being populated in the correct order, whereas this explicitly requires it.

So how does it run?
--
That's fast.
--
That's faster.

And Perl 6?
--
Fast and fasterer.

I'll address this in a minute. Let's have a look at the code.
--
sub fib-generator($n) {
    state @fib = 0, 1, * + * ... *;
    return @fib[$n];
}

That's all there is to it. That array is kind of the standard Perl 6 way to do Fibonacci, in the same way that this...
--
...is the standard way to define a factorial operator.
--
... but that's a whole nother talk!

But let's break the down what's happening in the list generator.
--
'state' is the same as the keyword in Perl 5, so I'll skip that. Its only purpose here was to keep the scope within the function. I'll also ditch the semi-colon at the end.
--
The whatever star at the end becomes infinity, or Inf, which can be written as this
--
Or this.
--
I'll write it like this, as it's easier for me to type.
--
Now, this * + * is essentially a magical closure, it can be replaced with these guys. $^a will be the second-to-last value and $^b will be the last value before this one.

It doesn't matter how many values you have at the start, as long as there is enough to be able to determine the next value.

Incidentally, you can do power sequences as well.
--
Which is the same as this...
--
... which might convey more meaning, depending on what you're trying to say.

But anyway, back to this.
--

As it turns out, on Windows, Perl 6 timing seems to have about a 500 microsecond resolution, so any times close to, or less than, that are suspect.

I couldn't see the same pattern on Linux, and Time::HiRes in Perl 5 doesn't seem to have the same issue.

So the one benchmark where Perl 6 beats Perl 5, it turns out Perl 6 was cheating.
--
So, what conclusions have I drawn.
--
It's not a speed demon yet
--
TMTOWTDI is alive and well
--
It's stable. I don't recall a single crash despite all the random garbage I was throwing at it.
--
Don't use it for computation-intensive work. Which is a polite way of saying it's slow. It might be fine for tasks which are I/O heavy.
--
Do use it for the things it can do. For example the slide deck you've just been watching was generated from a source file by a Perl 5 script. But that script was run from a Perl 6 script that was watching the source file for changes.
--
Lessons have been learned. It looks like they've tried create a certain consistency throughout the system, which given the size of it is very impressive.

They've also tried to take away limits where possible. You saw that in the timing functionality: the time returned is still seconds since 1st January 1970, but they now include the fractions of a second there. No need for a Time::HiRes type module here. They also seamlessly use arbitrary precision arithmetic. In Perl 5 on my machine, an integer is 64 bits. In Perl 6, well, I stopped it running when it was generating numbers over 2000 digits long.

Hell, just the fact that 0.1 + 0.2 - 0.3 actually equals zero is great.

The type system is also very well designed. Scalars generally work how you expect them to be able to work from Perl 5, even though everything has types now: you can still concatenate two numbers, e.g. 1 and 6, and then divide the result by 4. You shouldn't do that. But you can if you need to.

--
It's cool.

There are two things that I really like about Perl 5. The first is the expressiveness. Being able to say open file or die, or close file if end-of-file in more or less those words was a revelation.

The second is that it made me a better programmer. I didn't really understand closures before I learned Perl - I had tried something similar in C or C++ and it didn't go so well, but with Perl 5 they just gelled. Even the object system - it showed me how little you actually needed for solid foundations to be able to build something like Moose upon.

And you know what? I get the feeling I'm going to be learning a whole lot more from Perl 6.
----