Quick Tip #18: Short circuit subroutines with multi

In yesterday’s Quick Tip I used the Fibonacci sequence as an example to show off Rakudo’s --profile option. In today’s tip I’ll use that same sequence to show off Perl 6’s multi-dispatch features.

Consider the situation where I have an out-of-control subroutine. The one I’m about to show is not really going crazy, but I’ve programmed it in such a way that for moderately low input values it becomes unusable:

sub fib_recursive ( Int $n where * >= 0 --> Int ) {
	state $called = 0;
	$called++;
	END { say "fib_recursive was called $called times" }
	note "Called with $n";
	return 1 if $n < 2;

	note "$n calling with {$n -1} and {$n-2}";
	return fib_recursive( $n - 1 ) + fib_recursive( $n - 2 )
	}

sub MAIN ( Int $n where * >= 0 --> Int ) {
	say fib_recursive( $n );
	}

I’ve added some calls to note so I can watch the progress:

$ perl6 fibonacci.p6 5
Called with 5
5 calling with 4 and 3
Called with 4
4 calling with 3 and 2
Called with 3
3 calling with 2 and 1
Called with 2
2 calling with 1 and 0
Called with 1
Called with 0
Called with 1
Called with 2
2 calling with 1 and 0
Called with 1
Called with 0
Called with 3
3 calling with 2 and 1
Called with 2
2 calling with 1 and 0
Called with 1
Called with 0
Called with 1
8
fib_recursive was called 15 times

If I map this out to call levels, I get something like this to explain the calls. Each level of indentation is a call level:

5
	4
		3
			2
				1
				0
			1
		2
			1
			0
	3
		2
			1
			0
		1

The note routine sends its output to standard error. If I don’t want those extra messages, I can redirect standard error to something else:

$ perl6 fibonacci.p6 5 2> /dev/null
8
fib_recursive was called 15 times

So far so good. I get the answer quickly enough that I don’t care how long it took. However, as the argument’s value increases, the slower and slower my program gets. The number of times I call the routine explodes as the number goes up. I’ll leave this as an exercise for the reader, but the number of calls follows the sequence F(n) = F(n-1) + F(n-2) + 1. That +1 is a sly way of saying that the number of recursive calls grows faster than the coresponding value in the Fibonacci sequence.

You may have heard (or read) me rant on this before, but this is what happens to languages that can’t do tail-call optimization. Perl 6 doesn’t know what subroutine it might call to get the next values, so it can’t turn this recursive algorithm into an iterative one. Some languages can optimize the literal source code into something much better, and that’s why you see examples like this. But I could spend all day talking about this (and do in my Mastering Perl class). The short answer is “Don’t do that.”

In this post, I’m not going to rewrite the subroutine as something better. I’m going to short-circuit it by define a new subroutine with the same name that handles particular cases.

Before I start, I want to see the Fibonacci sequence. In the Perl 6 REPL, I’ll slice an infinite lazy sequence:

$ perl6
> (1,1, *+* ... * )[0..30];
(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)

And here’s the number of calls to fib_recursive I have to make to get those numbers:

$ perl6
> (1,1, *+*+1 ... * )[0..30]
(1 1 3 5 9 15 25 41 67 109 177 287 465 753 1219 1973 3193 5167 8361 13529 21891 35421 57313 92735 150049 242785 392835 635621 1028457 1664079 2692537)

Oh, too hard to line up the values? Here’s a double zip (using the Z operator) of the sequence number, Fibonacci number, and subroutine call count:

$ perl6
> ( 0 .. 30 ) Z (1,1, *+* ... * )[0..30] Z (1,1, *+*+1 ... * )[0..30]
((0 1 1) (1 1 1) (2 2 3) (3 3 5) (4 5 9) (5 8 15) (6 13 25) (7 21 41) (8 34 67) (9 55 109) (10 89 177) (11 144 287) (12 233 465) (13 377 753) (14 610 1219) (15 987 1973) (16 1597 3193) (17 2584 5167) (18 4181 8361) (19 6765 13529) (20 10946 21891) (21 17711 35421) (22 28657 57313) (23 46368 92735) (24 75025 150049) (25 121393 242785) (26 196418 392835) (27 317811 635621) (28 514229 1028457) (29 832040 1664079) (30 1346269 2692537))

All those years you made fun of Lisp…

I now know these numbers and I can use this knowledge in my program so avoid computation. I’ll create a multi-sub that immediately returns the value for n = 25. I can see in that list that I would save 242,785 subroutine calls every time I’d call fib_recursive( 25 ):

In Perl 6, I can have multiple definitions of a subroutine if I give them different signatures. When I call the subroutine, Perl 6 will look through the list of definitions and use the first one that fits the argument list.

The special technique here is that I use a literal value in the signature. When the value of the argument is 25, that’s the subroutine Perl 6 will call:

# define first! Perl 6 looks in the order of definition!
multi fib_recursive ( 25 ) { 121393 }

# multi implies "sub", but you can write "multi sub" if you like
multi fib_recursive ( Int $n where * >= 0 --> Int ) {
	state $called = 0;
	$called++;
	END { say "fib_recursive was called $called times" }
	note "Called with $n";
	return 1 if $n < 2;

	note "$n calling with {$n -1} and {$n-2}";
	return fib_recursive( $n - 1 ) + fib_recursive( $n - 2 )
	}


sub MAIN ( Int $n where * >= 0 --> Int ) {
	say fib_recursive( $n );
	}

When I call it with 25 now, I immediately get the answer. The END block still runs and doesn’t have a value for $count because I never ran the other subroutine definition:

$ perl6 fibonacci.p6 25 2> /dev/null
121393
fib_recursive was called  times

When I run it with 26, I see that fib_recursive runs 150,050 times. From the sequence I generated earlier, I would have had to run it 392,835 times with the pure recursive solution. The difference of 392,835 and 150,050 is 242,785. That’s the number of calls from the 25 branch!

$ perl6 fibonacci.p6 26 2> /dev/null
196418
fib_recursive was called 150050 times

I saved some time there, but let’s go one better. I could have saved more by defining three multis. To really short-circuit the sequence, I need to short circuit the n-1 and n-2 branches. I define another multi with the literal value of 24:

multi fib_recursive ( 24 ) {  75025 }
multi fib_recursive ( 25 ) { 121393 }

multi fib_recursive ( Int $n where * >= 0 --> Int ) {
	state $called = 0;
	$called++;
	END { say "fib_recursive was called $called times" }
	note "Called with $n";
	return 1 if $n < 2;

	note "$n calling with {$n -1} and {$n-2}";
	return fib_recursive( $n - 1 ) + fib_recursive( $n - 2 )
	}


sub MAIN ( Int $n where * >= 0 --> Int ) {
	say fib_recursive( $n );
	}

When I try it with 26 now, I call the actually-recursing fib_recursive exactly once. That calls the two multis for fib_recursive(25) and fib_recursive(24), which immediately return values:

$ perl6 fibonacci.p6 26 2> /dev/null
196418
fib_recursive was called 1 times

In this example, I’ve saved time because I had some precomputed values. The problem is as complex as when I started. It’s not a better algorithm, really. It’s just cheating a bit.

Consider a different way to use this same technique that changes the complexity. I won’t write real code here, but I want to illustrate another use of this technique.

Suppose that I have a general subroutine that works in most cases, but there are a few special cases that could make the code really complicated. Handling the special cases requires a lot of structure. Let the multi subs handle that structure for you, perhaps calling common subroutines as needed:

multi open_for_business ( Date $d where *.is-a-federal-holiday ) { ... }
multi open_for_business ( Date $d where *.is-a-weekend ) { ... }
multi open_for_business ( Date $d ) { ... }

I could also use this for debugging where I know I have one case that I want to inspect while not seeing debugging output from the other cases.

Leave a Reply

Your email address will not be published. Required fields are marked *