1 # -*- mode: perl; perl-indent-level: 2; -*-
2 # vim: ts=8 sw=2 sts=2 noexpandtab
6 # Copyright 1998, 1999, 2000, 2001, 2012 M. J. Dominus.
7 # You may copy and distribute this program under the
8 # same terms as Perl itself.
10 use strict; use warnings;
13 our $VERSION = '1.16';
16 use Scalar::Util 1.11 (); # for set_prototype
18 BEGIN { require Exporter; *import = \&Exporter::import }
19 our @EXPORT = qw(memoize);
20 our @EXPORT_OK = qw(unmemoize flush_cache);
25 my @info = values %memotable;
26 %memotable = map +($_->{WRAPPER} => $_), @info;
33 unless (defined($fn) &&
34 (ref $fn eq 'CODE' || ref $fn eq '')) {
35 croak "Usage: memoize 'functionname'|coderef {OPTIONS}";
38 my $uppack = caller; # TCL me Elmo!
39 my $name = (ref $fn ? undef : $fn);
40 my $cref = _make_cref($fn, $uppack);
42 my $normalizer = $options{NORMALIZER};
43 if (defined $normalizer && ! ref $normalizer) {
44 $normalizer = _make_cref($normalizer, $uppack);
47 my $install_name = exists $options{INSTALL}
48 ? $options{INSTALL} # use given name (or, if undef: do not install)
49 : $name; # no INSTALL option provided: default to original name if possible
51 if (defined $install_name) {
52 $install_name = $uppack . '::' . $install_name
53 unless $install_name =~ /::/;
56 # convert LIST_CACHE => MERGE to SCALAR_CACHE => MERGE
57 # to ensure TIE/HASH will always be checked by _check_suitable
58 if (($options{LIST_CACHE} || '') eq 'MERGE') {
59 $options{LIST_CACHE} = $options{SCALAR_CACHE};
60 $options{SCALAR_CACHE} = 'MERGE';
63 # These will be the caches
65 for my $context (qw(LIST SCALAR)) { # SCALAR_CACHE must be last, to process MERGE
66 my $fullopt = $options{"${context}_CACHE"} ||= 'MEMORY';
67 my ($cache_opt, @cache_opt_args) = ref $fullopt ? @$fullopt : $fullopt;
68 if ($cache_opt eq 'FAULT') { # no cache
69 $caches{$context} = undef;
70 } elsif ($cache_opt eq 'HASH') { # user-supplied hash
71 my $cache = $cache_opt_args[0];
72 _check_suitable($context, ref tied %$cache);
73 $caches{$context} = $cache;
74 } elsif ($cache_opt eq 'TIE') {
75 carp("TIE option to memoize() is deprecated; use HASH instead")
76 if warnings::enabled('all');
77 my $module = shift(@cache_opt_args) || '';
78 _check_suitable($context, $module);
79 my $hash = $caches{$context} = {};
80 (my $modulefile = $module . '.pm') =~ s{::}{/}g;
82 tie(%$hash, $module, @cache_opt_args)
83 or croak "Couldn't tie memoize hash to `$module': $!";
84 } elsif ($cache_opt eq 'MEMORY') {
85 $caches{$context} = {};
86 } elsif ($cache_opt eq 'MERGE' and not ref $fullopt) { # ['MERGE'] was never supported
87 die "cannot MERGE $context\_CACHE" if $context ne 'SCALAR'; # should never happen
88 die 'bad cache setup order' if not exists $caches{LIST}; # should never happen
90 $caches{SCALAR} = $caches{LIST};
92 croak "Unrecognized option to `${context}_CACHE': `$cache_opt' should be one of (MERGE TIE MEMORY FAULT HASH)";
96 my $wrapper = _wrap($install_name, $cref, $normalizer, $options{MERGED}, \%caches);
98 if (defined $install_name) {
100 no warnings 'redefine';
101 *{$install_name} = $wrapper;
104 $memotable{$wrapper} = {
106 S => $caches{SCALAR},
108 NAME => $install_name,
112 $wrapper # Return just memoized version
116 my $func = _make_cref($_[0], scalar caller);
117 my $info = $memotable{$func};
118 die "$func not memoized" unless defined $info;
119 for my $context (qw(S L)) {
120 my $cache = $info->{$context};
121 if (tied %$cache && ! (tied %$cache)->can('CLEAR')) {
122 my $funcname = defined($info->{NAME}) ?
123 "function $info->{NAME}" : "anonymous function $func";
124 my $context = {S => 'scalar', L => 'list'}->{$context};
125 croak "Tied cache hash for $context-context $funcname does not support flushing";
133 my ($name, $orig, $normalizer, $merged, $caches) = @_;
134 my ($cache_L, $cache_S) = @$caches{qw(LIST SCALAR)};
135 undef $caches; # keep the pad from keeping the hash alive forever
136 Scalar::Util::set_prototype(sub {
138 no warnings 'uninitialized';
140 ? ( wantarray ? ( $normalizer->( @_ ) )[0] : $normalizer->( @_ ) )
141 . '' # coerce undef to string while the warning is off
146 _crap_out($name, 'list') unless $cache_L;
147 exists $cache_L->{$argstr} ? (
148 @{$cache_L->{$argstr}}
150 my @q = do { no warnings 'recursion'; &$orig };
151 $cache_L->{$argstr} = \@q;
155 _crap_out($name, 'scalar') unless $cache_S;
156 exists $cache_S->{$argstr} ? (
157 $merged ? $cache_S->{$argstr}[0] : $cache_S->{$argstr}
159 my $val = do { no warnings 'recursion'; &$orig };
160 $cache_S->{$argstr} = $merged ? [$val] : $val;
170 my $cref = _make_cref($f, $uppack);
172 unless (exists $memotable{$cref}) {
173 croak "Could not unmemoize function `$f', because it was not memoized to begin with";
176 my $tabent = $memotable{$cref};
177 unless (defined $tabent) {
178 croak "Could not figure out how to unmemoize function `$f'";
180 my $name = $tabent->{NAME};
183 no warnings 'redefine';
184 *{$name} = $tabent->{U}; # Replace with original function
186 delete $memotable{$cref};
197 if (ref $fn eq 'CODE') {
199 } elsif (! ref $fn) {
203 $name = $uppack . '::' . $fn;
206 if (defined $name and !defined(&$name)) {
207 croak "Cannot operate on nonexistent function `$fn'";
210 $cref = *{$name}{CODE};
212 my $parent = (caller(1))[3]; # Function that called _make_cref
213 croak "Usage: argument 1 to `$parent' must be a function name or reference.\n";
215 our $DEBUG and warn "${name}($fn) => $cref in _make_cref\n";
220 my ($funcname, $context) = @_;
221 if (defined $funcname) {
222 croak "Function `$funcname' called in forbidden $context context; faulting";
224 croak "Anonymous function called in forbidden $context context; faulting";
228 # Raise an error if the user tries to specify one of these packages as a
230 my %scalar_only = map {($_ => 1)} qw(DB_File GDBM_File SDBM_File ODBM_File), map +($_, "Memoize::$_"), qw(AnyDBM_File NDBM_File);
231 sub _check_suitable {
232 my ($context, $package) = @_;
233 croak "You can't use $package for LIST_CACHE because it can only store scalars"
234 if $context eq 'LIST' and $scalar_only{$package};
245 Memoize - Make functions faster by trading space for time
250 memoize('slow_function');
251 slow_function(arguments); # Is faster than it was before
254 This is normally all you need to know. However, many options are available:
256 memoize(function, options...);
260 NORMALIZER => function
263 SCALAR_CACHE => 'MEMORY'
264 SCALAR_CACHE => ['HASH', \%cache_hash ]
265 SCALAR_CACHE => 'FAULT'
266 SCALAR_CACHE => 'MERGE'
268 LIST_CACHE => 'MEMORY'
269 LIST_CACHE => ['HASH', \%cache_hash ]
270 LIST_CACHE => 'FAULT'
271 LIST_CACHE => 'MERGE'
275 I<Memoizing> a function makes it faster by trading space for time. It
276 does this by caching the return values of the function in a table.
277 If you call the function again with the same arguments, C<memoize>
278 jumps in and gives you the value out of the table, instead of letting
279 the function compute the value all over again.
283 Here is an extreme example. Consider the Fibonacci sequence, defined
284 by the following function:
286 # Compute Fibonacci numbers
290 fib($n-1) + fib($n-2);
293 This function is very slow. Why? To compute fib(14), it first wants
294 to compute fib(13) and fib(12), and add the results. But to compute
295 fib(13), it first has to compute fib(12) and fib(11), and then it
296 comes back and computes fib(12) all over again even though the answer
297 is the same. And both of the times that it wants to compute fib(12),
298 it has to compute fib(11) from scratch, and then it has to do it
299 again each time it wants to compute fib(13). This function does so
300 much recomputing of old results that it takes a really long time to
301 run---fib(14) makes 1,200 extra recursive calls to itself, to compute
302 and recompute things that it already computed.
304 This function is a good candidate for memoization. If you memoize the
305 C<fib> function above, it will compute fib(14) exactly once, the first
306 time it needs to, and then save the result in a table. Then if you
307 ask for fib(14) again, it gives you the result out of the table.
308 While computing fib(14), instead of computing fib(12) twice, it does
309 it once; the second time it needs the value it gets it from the table.
310 It doesn't compute fib(11) four times; it computes it once, getting it
311 from the table the next three times. Instead of making 1,200
312 recursive calls to C<fib>, it makes 15. This makes the function about
315 You could do the memoization yourself, by rewriting the function, like
318 # Compute Fibonacci numbers, memoized version
322 return $fib[$n] if defined $fib[$n];
323 return $fib[$n] = $n if $n < 2;
324 $fib[$n] = fib($n-1) + fib($n-2);
328 Or you could use this module, like this:
333 # Rest of the fib function just like the original version.
335 This makes it easy to turn memoizing on and off.
337 Here's an even simpler example: I wrote a simple ray tracer; the
338 program would look in a certain direction, figure out what it was
339 looking at, and then convert the C<color> value (typically a string
340 like C<red>) of that object to a red, green, and blue pixel value, like
343 for ($direction = 0; $direction < 300; $direction++) {
344 # Figure out which object is in direction $direction
345 $color = $object->{color};
346 ($r, $g, $b) = @{&ColorToRGB($color)};
350 Since there are relatively few objects in a picture, there are only a
351 few colors, which get looked up over and over again. Memoizing
352 C<ColorToRGB> sped up the program by several percent.
356 This module exports exactly one function, C<memoize>. The rest of the
357 functions in this package are None of Your Business.
363 where C<function> is the name of the function you want to memoize, or
364 a reference to it. C<memoize> returns a reference to the new,
365 memoized version of the function, or C<undef> on a non-fatal error.
366 At present, there are no non-fatal errors, but there might be some in
369 If C<function> was the name of a function, then C<memoize> hides the
370 old version and installs the new memoized version under the old name,
371 so that C<&function(...)> actually invokes the memoized version.
375 There are some optional options you can pass to C<memoize> to change
376 the way it behaves a little. To supply options, invoke C<memoize>
379 memoize(function, NORMALIZER => function,
381 SCALAR_CACHE => option,
385 Each of these options is optional; you can include some, all, or none
390 If you supply a function name with C<INSTALL>, memoize will install
391 the new, memoized version of the function under the name you give.
394 memoize('fib', INSTALL => 'fastfib')
396 installs the memoized version of C<fib> as C<fastfib>; without the
397 C<INSTALL> option it would have replaced the old C<fib> with the
400 To prevent C<memoize> from installing the memoized version anywhere, use
401 C<INSTALL =E<gt> undef>.
405 Suppose your function looks like this:
407 # Typical call: f('aha!', A => 11, B => 12);
411 $hash{B} ||= 2; # B defaults to 2
412 $hash{C} ||= 7; # C defaults to 7
414 # Do something with $a, %hash
417 Now, the following calls to your function are all completely equivalent:
422 f(OUCH, B => 2, C => 7);
423 f(OUCH, C => 7, B => 2);
426 However, unless you tell C<Memoize> that these calls are equivalent,
427 it will not know that, and it will compute the values for these
428 invocations of your function separately, and store them separately.
430 To prevent this, supply a C<NORMALIZER> function that turns the
431 program arguments into a string in a way that equivalent arguments
432 turn into the same string. A C<NORMALIZER> function for C<f> above
433 might look like this:
441 join(',', $a, map ($_ => $hash{$_}) sort keys %hash);
444 Each of the argument lists above comes out of the C<normalize_f>
445 function looking exactly the same, like this:
449 You would tell C<Memoize> to use this normalizer this way:
451 memoize('f', NORMALIZER => 'normalize_f');
453 C<memoize> knows that if the normalized version of the arguments is
454 the same for two argument lists, then it can safely look up the value
455 that it computed for one argument list and return it as the result of
456 calling the function with the other argument list, even if the
457 argument lists look different.
459 The default normalizer just concatenates the arguments with character
460 28 in between. (In ASCII, this is called FS or control-\.) This
461 always works correctly for functions with only one string argument,
462 and also when the arguments never contain character 28. However, it
463 can confuse certain argument lists:
465 normalizer("a\034", "b")
466 normalizer("a", "\034b")
467 normalizer("a\034\034b")
471 Since hash keys are strings, the default normalizer will not
472 distinguish between C<undef> and the empty string. It also won't work
473 when the function's arguments are references. For example, consider a
474 function C<g> which gets two arguments: A number, and a reference to
477 g(13, [1,2,3,4,5,6,7]);
479 The default normalizer will turn this into something like
480 C<"13\034ARRAY(0x436c1f)">. That would be all right, except that a
481 subsequent array of numbers might be stored at a different location
482 even though it contains the same data. If this happens, C<Memoize>
483 will think that the arguments are different, even though they are
484 equivalent. In this case, a normalizer like this is appropriate:
486 sub normalize { join ' ', $_[0], @{$_[1]} }
488 For the example above, this produces the key "13 1 2 3 4 5 6 7".
490 Another use for normalizers is when the function depends on data other
491 than those in its arguments. Suppose you have a function which
492 returns a value which depends on the current hour of the day:
495 my ($problem_type) = @_;
496 my $hour = (localtime)[2];
497 open my $fh, "$DIR/$problem_type" or die...;
505 At 10:23, this function generates the 10th line of a data file; at
506 3:45 PM it generates the 15th line instead. By default, C<Memoize>
507 will only see the $problem_type argument. To fix this, include the
508 current hour in the normalizer:
510 sub normalize { join ' ', (localtime)[2], @_ }
512 The calling context of the function (scalar or list context) is
513 propagated to the normalizer. This means that if the memoized
514 function will treat its arguments differently in list context than it
515 would in scalar context, you can have the normalizer function select
516 its behavior based on the results of C<wantarray>. Even if called in
517 a list context, a normalizer should still return a single string.
519 =head2 C<SCALAR_CACHE>, C<LIST_CACHE>
521 Normally, C<Memoize> caches your function's return values into an
522 ordinary Perl hash variable. However, you might like to have the
523 values cached on the disk, so that they persist from one run of your
524 program to the next, or you might like to associate some other
525 interesting semantics with the cached values.
527 There's a slight complication under the hood of C<Memoize>: There are
528 actually I<two> caches, one for scalar values and one for list values.
529 When your function is called in scalar context, its return value is
530 cached in one hash, and when your function is called in list context,
531 its value is cached in the other hash. You can control the caching
532 behavior of both contexts independently with these options.
534 The argument to C<LIST_CACHE> or C<SCALAR_CACHE> must either be one of
535 the following four strings:
542 or else it must be a reference to an array whose first element is one of
543 these four strings, such as C<[HASH, arguments...]>.
549 C<MEMORY> means that return values from the function will be cached in
550 an ordinary Perl hash variable. The hash variable will not persist
551 after the program exits. This is the default.
555 C<HASH> allows you to specify that a particular hash that you supply
556 will be used as the cache. You can tie this hash beforehand to give
557 it any behavior you want.
559 A tied hash can have any semantics at all. It is typically tied to an
560 on-disk database, so that cached values are stored in the database and
561 retrieved from it again when needed, and the disk file typically
562 persists after your program has exited. See C<perltie> for more
563 complete details about C<tie>.
565 A typical example is:
568 tie my %cache => 'DB_File', $filename, O_RDWR|O_CREAT, 0666;
569 memoize 'function', SCALAR_CACHE => [HASH => \%cache];
571 This has the effect of storing the cache in a C<DB_File> database
572 whose name is in C<$filename>. The cache will persist after the
573 program has exited. Next time the program runs, it will find the
574 cache already populated from the previous run of the program. Or you
575 can forcibly populate the cache by constructing a batch program that
576 runs in the background and populates the cache file. Then when you
577 come to run your real program the memoized function will be fast
578 because all its results have been precomputed.
580 Another reason to use C<HASH> is to provide your own hash variable.
581 You can then inspect or modify the contents of the hash to gain finer
582 control over the cache management.
586 This option is no longer supported. It is still documented only to
587 aid in the debugging of old programs that use it. Old programs should
588 be converted to use the C<HASH> option instead.
590 memoize ... ['TIE', PACKAGE, ARGS...]
592 is merely a shortcut for
595 { tie my %cache, PACKAGE, ARGS...;
596 memoize ... [HASH => \%cache];
601 C<FAULT> means that you never expect to call the function in scalar
602 (or list) context, and that if C<Memoize> detects such a call, it
603 should abort the program. The error message is one of
605 `foo' function called in forbidden list context at line ...
606 `foo' function called in forbidden scalar context at line ...
610 C<MERGE> normally means that the memoized function does not
611 distinguish between list and scalar context, and that return values in
612 both contexts should be stored together. Both C<LIST_CACHE =E<gt>
613 MERGE> and C<SCALAR_CACHE =E<gt> MERGE> mean the same thing.
615 Consider this function:
618 # ... time-consuming calculation of $result
622 The C<complicated> function will return the same numeric C<$result>
623 regardless of whether it is called in list or in scalar context.
625 Normally, the following code will result in two calls to C<complicated>, even
626 if C<complicated> is memoized:
628 $x = complicated(142);
629 ($y) = complicated(142);
630 $z = complicated(142);
632 The first call will cache the result, say 37, in the scalar cache; the
633 second will cache the list C<(37)> in the list cache. The third call
634 doesn't call the real C<complicated> function; it gets the value 37
635 from the scalar cache.
637 Obviously, the second call to C<complicated> is a waste of time, and
638 storing its return value is a waste of space. Specifying C<LIST_CACHE
639 =E<gt> MERGE> will make C<memoize> use the same cache for scalar and
640 list context return values, so that the second call uses the scalar
641 cache that was populated by the first call. C<complicated> ends up
642 being called only once, and both subsequent calls return C<37> from the
643 cache, regardless of the calling context.
647 =head3 List values in scalar context
649 Consider this function:
651 sub iota { return reverse (1..$_[0]) }
653 This function normally returns a list. Suppose you memoize it and
656 memoize 'iota', SCALAR_CACHE => 'MERGE';
661 Here the first call caches the list (1,2,3,4,5,6,7). The second call
662 does not really make sense. C<Memoize> cannot guess what behavior
663 C<iota> should have in scalar context without actually calling it in
664 scalar context. Normally C<Memoize> I<would> call C<iota> in scalar
665 context and cache the result, but the C<SCALAR_CACHE =E<gt> 'MERGE'>
666 option says not to do that, but to use the cache list-context value
667 instead. But it cannot return a list of seven elements in a scalar
668 context. In this case C<$i7> will receive the B<first element> of the
669 cached list value, namely 7.
671 =head3 Merged disk caches
673 Another use for C<MERGE> is when you want both kinds of return values
674 stored in the same disk file; this saves you from having to deal with
675 two disk files instead of one. You can use a normalizer function to
676 keep the two sets of return values separate. For example:
678 local $MLDBM::UseDB = 'DB_File';
679 tie my %cache => 'MLDBM', $filename, ...;
683 SCALAR_CACHE => [HASH => \%cache],
684 LIST_CACHE => 'MERGE',
688 my $context = wantarray() ? 'L' : 'S';
689 # ... now compute the hash key from the arguments ...
690 $hashkey = "$context:$hashkey";
693 This normalizer function will store scalar context return values in
694 the disk file under keys that begin with C<S:>, and list context
695 return values under keys that begin with C<L:>.
697 =head1 OTHER FACILITIES
701 There's an C<unmemoize> function that you can import if you want to.
702 Why would you want to? Here's an example: Suppose you have your cache
703 tied to a DBM file, and you want to make sure that the cache is
704 written out to disk if someone interrupts the program. If the program
705 exits normally, this will happen anyway, but if someone types
706 control-C or something then the program will terminate immediately
707 without synchronizing the database. So what you can do instead is
709 $SIG{INT} = sub { unmemoize 'function' };
711 C<unmemoize> accepts a reference to, or the name of a previously
712 memoized function, and undoes whatever it did to provide the memoized
713 version in the first place, including making the name refer to the
714 unmemoized version if appropriate. It returns a reference to the
715 unmemoized version of the function.
717 If you ask it to unmemoize a function that was never memoized, it
720 =head2 C<flush_cache>
722 C<flush_cache(function)> will flush out the caches, discarding I<all>
723 the cached data. The argument may be a function name or a reference
724 to a function. For finer control over when data is discarded or
725 expired, see the documentation for C<Memoize::Expire>, included in
728 Note that if the cache is a tied hash, C<flush_cache> will attempt to
729 invoke the C<CLEAR> method on the hash. If there is no C<CLEAR>
730 method, this will cause a run-time error.
732 An alternative approach to cache flushing is to use the C<HASH> option
733 (see above) to request that C<Memoize> use a particular hash variable
734 as its cache. Then you can examine or modify the hash at any time in
735 any way you desire. You may flush the cache by using C<%hash = ()>.
739 Memoization is not a cure-all:
745 Do not memoize a function whose behavior depends on program
746 state other than its own arguments, such as global variables, the time
747 of day, or file input. These functions will not produce correct
748 results when memoized. For a particularly easy example:
754 This function takes no arguments, and as far as C<Memoize> is
755 concerned, it always returns the same result. C<Memoize> is wrong, of
756 course, and the memoized version of this function will call C<time> once
757 to get the current time, and it will return that same time
758 every time you call it after that.
762 Do not memoize a function with side effects.
767 print "$a + $b = $s.\n";
770 This function accepts two arguments, adds them, and prints their sum.
771 Its return value is the number of characters it printed, but you
772 probably didn't care about that. But C<Memoize> doesn't understand
773 that. If you memoize this function, you will get the result you
774 expect the first time you ask it to print the sum of 2 and 3, but
775 subsequent calls will return 1 (the return value of
776 C<print>) without actually printing anything.
780 Do not memoize a function that returns a data structure that is
781 modified by its caller.
783 Consider these functions: C<getusers> returns a list of users somehow,
784 and then C<main> throws away the first user on the list and prints the
788 my $userlist = getusers();
790 foreach $u (@$userlist) {
797 # Do something to get a list of users;
798 \@users; # Return reference to list.
801 If you memoize C<getusers> here, it will work right exactly once. The
802 reference to the users list will be stored in the memo table. C<main>
803 will discard the first element from the referenced list. The next
804 time you invoke C<main>, C<Memoize> will not call C<getusers>; it will
805 just return the same reference to the same list it got last time. But
806 this time the list has already had its head removed; C<main> will
807 erroneously remove another element from it. The list will get shorter
808 and shorter every time you call C<main>.
816 will modify $u2 as well as $u1, because both variables are references
817 to the same array. Had C<getusers> not been memoized, $u1 and $u2
818 would have referred to different arrays.
822 Do not memoize a very simple function.
824 Recently someone mentioned to me that the Memoize module made his
825 program run slower instead of faster. It turned out that he was
826 memoizing the following function:
832 I pointed out that C<Memoize> uses a hash, and that looking up a
833 number in the hash is necessarily going to take a lot longer than a
834 single multiplication. There really is no way to speed up the
837 Memoization is not magical.
841 =head1 PERSISTENT CACHE SUPPORT
843 You can tie the cache tables to any sort of tied hash that you want
844 to, as long as it supports C<TIEHASH>, C<FETCH>, C<STORE>, and
845 C<EXISTS>. For example,
847 tie my %cache => 'GDBM_File', $filename, O_RDWR|O_CREAT, 0666;
848 memoize 'function', SCALAR_CACHE => [HASH => \%cache];
850 works just fine. For some storage methods, you need a little glue.
852 C<SDBM_File> doesn't supply an C<EXISTS> method, so included in this
853 package is a glue module called C<Memoize::SDBM_File> which does
854 provide one. Use this instead of plain C<SDBM_File> to store your
855 cache table on disk in an C<SDBM_File> database:
857 tie my %cache => 'Memoize::SDBM_File', $filename, O_RDWR|O_CREAT, 0666;
858 memoize 'function', SCALAR_CACHE => [HASH => \%cache];
860 C<NDBM_File> has the same problem and the same solution. (Use
861 C<Memoize::NDBM_File instead of plain NDBM_File.>)
863 C<Storable> isn't a tied hash class at all. You can use it to store a
864 hash to disk and retrieve it again, but you can't modify the hash while
865 it's on the disk. So if you want to store your cache table in a
866 C<Storable> database, use C<Memoize::Storable>, which puts a hashlike
867 front-end onto C<Storable>. The hash table is actually kept in
868 memory, and is loaded from your C<Storable> file at the time you
869 memoize the function, and stored back at the time you unmemoize the
870 function (or when your program exits):
872 tie my %cache => 'Memoize::Storable', $filename;
873 memoize 'function', SCALAR_CACHE => [HASH => \%cache];
875 tie my %cache => 'Memoize::Storable', $filename, 'nstore';
876 memoize 'function', SCALAR_CACHE => [HASH => \%cache];
878 Include the C<nstore> option to have the C<Storable> database written
879 in I<network order>. (See L<Storable> for more details about this.)
881 The C<flush_cache()> function will raise a run-time error unless the
882 tied package provides a C<CLEAR> method.
884 =head1 EXPIRATION SUPPORT
886 See Memoize::Expire, which is a plug-in module that adds expiration
887 functionality to Memoize. If you don't like the kinds of policies
888 that Memoize::Expire implements, it is easy to write your own plug-in
889 module to implement whatever policy you desire. Memoize comes with
890 several examples. An expiration manager that implements a LRU policy
891 is available on CPAN as Memoize::ExpireLRU.
895 The test suite is much better, but always needs improvement.
897 There is some problem with the way C<goto &f> works under threaded
898 Perl, perhaps because of the lexical scoping of C<@_>. This is a bug
899 in Perl, and until it is resolved, memoized functions will see a
900 slightly different C<caller()> and will perform a little more slowly
901 on threaded perls than unthreaded perls.
903 Some versions of C<DB_File> won't let you store data under a key of
904 length 0. That means that if you have a function C<f> which you
905 memoized and the cache is in a C<DB_File> database, then the value of
906 C<f()> (C<f> called with no arguments) will not be memoized. If this
907 is a big problem, you can supply a normalizer function that prepends
912 At L<https://perl.plover.com/MiniMemoize/> there is an article about
913 memoization and about the internals of Memoize that appeared in The
914 Perl Journal, issue #13.
916 Mark-Jason Dominus's book I<Higher-Order Perl> (2005, ISBN 1558607013,
918 by Morgan Kaufmann) discusses memoization (and many other
919 topics) in tremendous detail. It is available on-line for free.
920 For more information, visit L<https://hop.perl.plover.com/>.
924 Many thanks to Florian Ragwitz for administration and packaging
925 assistance, to John Tromp for bug reports, to Jonathan Roy for bug reports
926 and suggestions, to Michael Schwern for other bug reports and patches,
927 to Mike Cariaso for helping me to figure out the Right Thing to Do
928 About Expiration, to Joshua Gerth, Joshua Chamas, Jonathan Roy
929 (again), Mark D. Anderson, and Andrew Johnson for more suggestions
930 about expiration, to Brent Powers for the Memoize::ExpireLRU module,
931 to Ariel Scolnicov for delightful messages about the Fibonacci
932 function, to Dion Almaer for thought-provoking suggestions about the
933 default normalizer, to Walt Mankowski and Kurt Starsinic for much help
934 investigating problems under threaded Perl, to Alex Dudkevich for
935 reporting the bug in prototyped functions and for checking my patch,
936 to Tony Bass for many helpful suggestions, to Jonathan Roy (again) for
937 finding a use for C<unmemoize()>, to Philippe Verdret for enlightening
938 discussion of C<Hook::PrePostCall>, to Nat Torkington for advice I
939 ignored, to Chris Nandor for portability advice, to Randal Schwartz
940 for suggesting the 'C<flush_cache> function, and to Jenda Krynicky for
941 being a light in the world.
943 Special thanks to Jarkko Hietaniemi, the 5.8.0 pumpking, for including
944 this module in the core and for his patient and helpful guidance
945 during the integration process.
951 =head1 COPYRIGHT AND LICENSE
953 This software is copyright (c) 2012 by Mark Jason Dominus.
955 This is free software; you can redistribute it and/or modify it under
956 the same terms as the Perl 5 programming language system itself.