realprogrammers: Talks: Paulm: Memoize -- by hackers, for hackers

Memoize Awareness Moment

Who's heard of it?
Who's used it?
Who liked it?

It's in perl 5.8.0 core now. So it must be good.

The idea

Memoize caches function arguments so if a function is called with the same args it simply returns the value straight away. As the manpage says, it trades space for time.

Removing a PitA

Have you written code like:

my %frobbed;

sub frob($) {
	my $frobbee = shift;
	return $frobbed{$frobbee} if exists $frobbed{$frobbee};
	
	# ...

	$frobbed{$frobbee} = $the_result;
}

Then perhaps added a parameter,

	my ($frobbee, $fooed) = @_;

Er, now what? Have to deal with caching two variables. Perhaps you could join them with something odd, and then store that key and use it later to cache the answer. Quickly, your code gets yucky.

The Memoize Pill

use Memoize; # exports 'memoize'

sub frob($) {
	my ($frobbee, $fooed) = @_;
	
	# ...
}

memoize('frob');
# memoize('frob', INSTALL => 'memoized_frob');

That's it! That's enough to find Memoize useful.

Gotchas

Can't cache functions that have side-effects

If your function does IO, is dependent on external input e.g. the time Memoize will probably be confusing and unhelpful.

Hash ordering

Suppose you have a hash of %options. They could be passed in in any order, so ( pigs => 2, ducks => 3 ) could end up in the other way around (since the keys in a hash don't come back in a defined order). Memoize would be default consider those different questions.

NORMALIZER

This function canonicalises the parameters, e.g. sorts the keys so the semantically same parameters always appear to Memoize in the same order. Its interface is the params and its return value must be the params too.

memoize('invite_people', NORMALIZER => sub { sort @_ });

The normalizer can also be used to inform Memoize in some way about the sub's external dependencies. E.g. a function dependent on time could have part of the time returned to Memoize. (Discussed in manual.)

Other features

Changing where it stores the cache

If the results are that interesting, you can make them persist. In essence this involves telling Memoize to use your own scalar, list or hash cache. You could then for example tie this to make it persistent.

tie my %cache => 'GDBM_File', $filename, O_RDWR|O_CREAT, 0666 or die "$filename: $!\n";
memoize 'function', SCALAR_CACHE => [HASH => \%cache];

Flushing

It's possible to empty the cache. I've occasionally found this useful in the mod_perl environment.

Gossip

Where did Memoize come from? MJD's head? No, Lisp. You won't find that in the docs though. :-)

realprogrammers.com

Memoize