Caching & Memoization with state variables

Chapter 3 of Higher Order Perl describes various approaches to memoization of an expensive function: private cache and the Memoize module. The book was written in 2005 (Perl was at version 5.8 back then) , so it does not include another way for function caching that is now available : caching through state variables (introduced in Perl 5.10). The Fibonacci example considered in HOP also requires the ability to initialize state hash variables (available since Perl 5.28). The code below contrasts the implementation with a state variable v.s. the memoize module:

use v5.38;
use Time::HiRes qw(time);
use Memoize;
sub fib_cache_with_state ($number) {
  state %fib = ( 0 => 0, 1 => 1 );
  unless ( exists $fib{$number} ) {
    $fib{$number} = fib_cache_with_state( $number - 1 ) +
    fib_cache_with_state( $number - 2 );
  }
  return $fib{$number};
}
memoize 'fib';
sub fib ($number) {
  return $number if $number < 2;
  return fib( $number - 1 ) + fib( $number - 2 );
}
my $number = 80;
## using the memoize module
my $start_time = time;
my $fi1 = fib($number);
my $end_time = time;
my $dt1 = $end_time - $start_time;
## using a state variable to memoize
$start_time = time;
my $fib2 = fib_cache_with_state($number);
$end_time = time;
my $dt2 = $end_time - $start_time;
printf "Fibonacci of %d with the memoize module took : %.2g\n", $number, $dt1;
printf "Fibonacci of %d with a state variable took : %.2g\n", $number, $dt2;
printf "Speedup state var /memoize module: %.2g\n", $dt1 / $dt2;
say "Difference in calculations : ", $fi1 - $fib2;

State variable is faster for CPUs , but the Memoize module is faster for humans. Both of them are great tricks to know :)

4 Comments

I don't like state variables in named subroutines. They make it hard to reuse the subroutines, imagine in this example we'd like to generate the Lucas sequence (L1 = 1, L2 = 3), too, but we can't, as we only have one state variable. If we use an anonymous subroutine, the static variable is different each time we create the subroutine, so we can have two different sequence generators.

I love state variables, but oddly only use them when creating sub based state machine xD - which is typically just for show. But the idea of co-routines in Perl is nifty.

I think E. Choroba means something like:

sub foo {
  state $foo = 1;
  ...
  say $foo;
  ++$foo;
}

foreach my $i (1 .. 10) {
foo();
}

versus,

my $foo = 1;
foreach my $i (1 .. 10) {
  my $sub = sub {
    my $myfoo = $foo;
    ...
    say $myfoo;
  };
  ++$foo;
  $sub->();
}

No, I mean we only have one subroutine, but we want to use it to generate two different sequences.

Leave a comment

About chrisarg

user-pic I like to use Perl for material other than text.