Memoize#

📦 std

Make functions faster by trading space for time - cache a function’s results by its arguments and return the cached result on a repeated call.

memoize('f') replaces f with a wrapper that remembers every result it has computed. The next call with the same arguments returns the remembered result without running f again. This is only sound for a function whose result depends on nothing but its arguments and which has no side effects; the call to memoize is your assertion that it is such a function.

The wrapper is installed under the function’s own name, so existing callers hit the cache transparently, and it is returned as a code reference. INSTALL => 'other' installs it under another name, INSTALL => undef installs nothing and only returns it. Scalar- and list-context results are cached separately, because a function may return different things in each; SCALAR_CACHE and LIST_CACHE choose the storage per context: MEMORY (in-process, the default), [HASH => \%h] (a hash you supply, possibly tied to a DBM file so the cache persists across runs), FAULT (croak if called in that context) and MERGE (one cache for both contexts). NORMALIZER names a function that turns the argument list into the cache key when the default key, the arguments joined with chr(28), is not the right notion of “same arguments”.

flush_cache('f') empties a function’s cache; unmemoize('f') restores the original function. Both are exported on request only.

The cache is native: nothing here is a Perl closure, the key is built and probed in the runtime, and a hit costs one hash probe and a copy of the stored result.

A pure numeric function is memoized further down still. It is compiled, its results are kept in a native table, and memoize puts the compiled function itself under the name rather than anything wrapped around it - so a loop calling it can be compiled too, and a repeated call is then a table probe in registers with no call at all. This covers one to four numeric arguments and recursion (the compiled body’s recursive calls probe the same table), so memoize('fib'), and equally a two- or three-argument recurrence, run compiled, memoized and - for a repeated call - allocation- and call-free. Deep recursion behaves as in perl: it is limited by memory, not by a fixed depth, and the Deep recursion warning appears as usual under use warnings. Anything outside that shape - five or more arguments, a non-numeric argument, a NORMALIZER, list context - uses the general cache above, which is correct for every function memoize accepts.

Synopsis#

use Memoize;
memoize('slow_function');
slow_function(@args);          # computed
slow_function(@args);          # returned from the cache

use Memoize qw(memoize flush_cache unmemoize);
memoize('fib', NORMALIZER => sub { $_[0] });
flush_cache('fib');
unmemoize('fib');

Differences from upstream#

Upstream Memoize is pure Perl and wraps each function in a Perl closure; here the wrapper is native, and that shows in four places. From inside the memoized function caller sees its own caller directly, with no Memoize::__ANON__ frame in between - there is no Perl closure to make one. For the same reason the Deep recursion warning names the memoized function (subroutine "main::fib") where the pure-Perl module’s recursion is first counted on its wrapper (anonymous subroutine). A die from flush_cache or unmemoize reports the caller’s location, as XS errors do, rather than a line inside Memoize.pm. The module does not define CLONE, because this runtime has no interpreter threads.

Modules#

Functions#

Memoization#

memoize#

Memoize a function: memoize('name', %options) or memoize(\&code, %options).

flush_cache#

Empty a memoized function’s caches: flush_cache('name') or flush_cache(\&wrapper).

unmemoize#

Undo memoize: unmemoize('name') or unmemoize(\&wrapper).