DEV Community

chrisarg
chrisarg

Posted on

4 1

Caching & Memoization with state variables

(This is a cross post from B.P.O ).

Chapter 3 of [Higher Order Perl]<(https://hop.perl.plover.com/) 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;

Enter fullscreen mode Exit fullscreen mode

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

Heroku

This site is built on Heroku

Join the ranks of developers at Salesforce, Airbase, DEV, and more who deploy their mission critical applications on Heroku. Sign up today and launch your first app!

Get Started

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more