1 # -*- mode: perl; perl-indent-level: 2; -*-
4 # Transparent memoization of idempotent functions
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. If in doubt,
9 # write to mjd-perl-memoize+@plover.com for a license.
14 # Compile-time constants
20 # Usage memoize(functionname/ref,
21 # { NORMALIZER => coderef, INSTALL => name,
22 # LIST_CACHE => descriptor, SCALAR_CACHE => descriptor }
30 @EXPORT = qw(memoize);
31 @EXPORT_OK = qw(unmemoize flush_cache);
36 my @CONTEXT_TAGS = qw(MERGE TIE MEMORY FAULT HASH);
37 my %IS_CACHE_TAG = map {($_ => 1)} @CONTEXT_TAGS;
39 # Raise an error if the user tries to specify one of thesepackage as a
42 my %scalar_only = map {($_ => 1)} qw(DB_File GDBM_File SDBM_File ODBM_File NDBM_File);
47 my $options = \%options;
49 unless (defined($fn) &&
50 (ref $fn eq 'CODE' || ref $fn eq '')) {
51 croak "Usage: memoize 'functionname'|coderef {OPTIONS}";
54 my $uppack = caller; # TCL me Elmo!
55 my $cref; # Code reference to original function
56 my $name = (ref $fn ? undef : $fn);
58 # Convert function names to code references
59 $cref = &_make_cref($fn, $uppack);
61 # Locate function prototype, if any
62 my $proto = prototype $cref;
63 if (defined $proto) { $proto = "($proto)" }
66 # I would like to get rid of the eval, but there seems not to be any
67 # other way to set the prototype properly. The switch here for
68 # 'usethreads' works around a bug in threadperl having to do with
69 # magic goto. It would be better to fix the bug and use the magic
70 # goto version everywhere.
73 ? eval "sub $proto { &_memoizer(\$cref, \@_); }"
74 : eval "sub $proto { unshift \@_, \$cref; goto &_memoizer; }";
76 my $normalizer = $options{NORMALIZER};
77 if (defined $normalizer && ! ref $normalizer) {
78 $normalizer = _make_cref($normalizer, $uppack);
82 if (defined $options->{INSTALL}) {
84 $install_name = $options->{INSTALL};
85 } elsif (! exists $options->{INSTALL}) {
86 # No INSTALL option provided; use original name if possible
87 $install_name = $name;
89 # INSTALL => undef means don't install
92 if (defined $install_name) {
93 $install_name = $uppack . '::' . $install_name
94 unless $install_name =~ /::/;
96 local($^W) = 0; # ``Subroutine $install_name redefined at ...''
97 *{$install_name} = $wrapper; # Install memoized version
100 $revmemotable{$wrapper} = "" . $cref; # Turn code ref into hash key
102 # These will be the caches
104 for my $context (qw(SCALAR LIST)) {
105 # suppress subsequent 'uninitialized value' warnings
106 $options{"${context}_CACHE"} ||= '';
108 my $cache_opt = $options{"${context}_CACHE"};
110 if (ref $cache_opt) {
111 @cache_opt_args = @$cache_opt;
112 $cache_opt = shift @cache_opt_args;
114 if ($cache_opt eq 'FAULT') { # no cache
115 $caches{$context} = undef;
116 } elsif ($cache_opt eq 'HASH') { # user-supplied hash
117 my $cache = $cache_opt_args[0];
118 my $package = ref(tied %$cache);
119 if ($context eq 'LIST' && $scalar_only{$package}) {
120 croak("You can't use $package for LIST_CACHE because it can only store scalars");
122 $caches{$context} = $cache;
123 } elsif ($cache_opt eq '' || $IS_CACHE_TAG{$cache_opt}) {
124 # default is that we make up an in-memory hash
125 $caches{$context} = {};
126 # (this might get tied later, or MERGEd away)
128 croak "Unrecognized option to `${context}_CACHE': `$cache_opt' should be one of (@CONTEXT_TAGS); aborting";
132 # Perhaps I should check here that you didn't supply *both* merge
133 # options. But if you did, it does do something reasonable: They
134 # both get merged to the same in-memory hash.
135 if ($options{SCALAR_CACHE} eq 'MERGE' || $options{LIST_CACHE} eq 'MERGE') {
136 $options{MERGED} = 1;
137 $caches{SCALAR} = $caches{LIST};
140 # Now deal with the TIE options
143 foreach $context (qw(SCALAR LIST)) {
144 # If the relevant option wasn't `TIE', this call does nothing.
145 _my_tie($context, $caches{$context}, $options); # Croaks on failure
149 # We should put some more stuff in here eventually.
150 # We've been saying that for serveral versions now.
151 # And you know what? More stuff keeps going in!
154 O => $options, # Short keys here for things we need to access frequently
157 MEMOIZED => $wrapper,
159 NAME => $install_name,
160 S => $caches{SCALAR},
164 $wrapper # Return just memoized version
167 # This function tries to load a tied hash class and tie the hash to it.
169 my ($context, $hash, $options) = @_;
170 my $fullopt = $options->{"${context}_CACHE"};
172 # We already checked to make sure that this works.
173 my $shortopt = (ref $fullopt) ? $fullopt->[0] : $fullopt;
175 return unless defined $shortopt && $shortopt eq 'TIE';
176 carp("TIE option to memoize() is deprecated; use HASH instead")
179 my @args = ref $fullopt ? @$fullopt : ();
181 my $module = shift @args;
182 if ($context eq 'LIST' && $scalar_only{$module}) {
183 croak("You can't use $module for LIST_CACHE because it can only store scalars");
185 my $modulefile = $module . '.pm';
186 $modulefile =~ s{::}{/}g;
189 pop @INC if $INC[-1] eq '.';
193 croak "Memoize: Couldn't load hash tie module `$module': $@; aborting";
195 my $rc = (tie %$hash => $module, @args);
197 croak "Memoize: Couldn't tie hash to `$module': $!; aborting";
203 my $func = _make_cref($_[0], scalar caller);
204 my $info = $memotable{$revmemotable{$func}};
205 die "$func not memoized" unless defined $info;
206 for my $context (qw(S L)) {
207 my $cache = $info->{$context};
208 if (tied %$cache && ! (tied %$cache)->can('CLEAR')) {
209 my $funcname = defined($info->{NAME}) ?
210 "function $info->{NAME}" : "anonymous function $func";
211 my $context = {S => 'scalar', L => 'list'}->{$context};
212 croak "Tied cache hash for $context-context $funcname does not support flushing";
219 # This is the function that manages the memo tables.
221 my $orig = shift; # stringized version of ref to original func.
222 my $info = $memotable{$orig};
223 my $normalizer = $info->{N};
226 my $context = (wantarray() ? LIST : SCALAR);
228 if (defined $normalizer) {
230 if ($context == SCALAR) {
231 $argstr = &{$normalizer}(@_);
232 } elsif ($context == LIST) {
233 ($argstr) = &{$normalizer}(@_);
235 croak "Internal error \#41; context was neither LIST nor SCALAR\n";
237 } else { # Default normalizer
239 $argstr = join chr(28),@_;
242 if ($context == SCALAR) {
243 my $cache = $info->{S};
244 _crap_out($info->{NAME}, 'scalar') unless $cache;
245 if (exists $cache->{$argstr}) {
246 return $info->{O}{MERGED}
247 ? $cache->{$argstr}[0] : $cache->{$argstr};
249 my $val = &{$info->{U}}(@_);
250 # Scalars are considered to be lists; store appropriately
251 if ($info->{O}{MERGED}) {
252 $cache->{$argstr} = [$val];
254 $cache->{$argstr} = $val;
258 } elsif ($context == LIST) {
259 my $cache = $info->{L};
260 _crap_out($info->{NAME}, 'list') unless $cache;
261 if (exists $cache->{$argstr}) {
262 return @{$cache->{$argstr}};
264 my @q = &{$info->{U}}(@_);
265 $cache->{$argstr} = \@q;
269 croak "Internal error \#42; context was neither LIST nor SCALAR\n";
276 my $cref = _make_cref($f, $uppack);
278 unless (exists $revmemotable{$cref}) {
279 croak "Could not unmemoize function `$f', because it was not memoized to begin with";
282 my $tabent = $memotable{$revmemotable{$cref}};
283 unless (defined $tabent) {
284 croak "Could not figure out how to unmemoize function `$f'";
286 my $name = $tabent->{NAME};
289 local($^W) = 0; # ``Subroutine $install_name redefined at ...''
290 *{$name} = $tabent->{U}; # Replace with original function
292 undef $memotable{$revmemotable{$cref}};
293 undef $revmemotable{$cref};
295 # This removes the last reference to the (possibly tied) memo tables
296 # my ($old_function, $memotabs) = @{$tabent}{'U','S','L'};
299 # # Untie the memo tables if they were tied.
302 # if (tied %{$memotabs->[$i]}) {
303 # warn "Untying hash #$i\n";
304 # untie %{$memotabs->[$i]};
317 if (ref $fn eq 'CODE') {
319 } elsif (! ref $fn) {
323 $name = $uppack . '::' . $fn;
326 if (defined $name and !defined(&$name)) {
327 croak "Cannot operate on nonexistent function `$fn'";
330 $cref = *{$name}{CODE};
332 my $parent = (caller(1))[3]; # Function that called _make_cref
333 croak "Usage: argument 1 to `$parent' must be a function name or reference.\n";
335 $DEBUG and warn "${name}($fn) => $cref in _make_cref\n";
340 my ($funcname, $context) = @_;
341 if (defined $funcname) {
342 croak "Function `$funcname' called in forbidden $context context; faulting";
344 croak "Anonymous function called in forbidden $context context; faulting";
356 Memoize - Make functions faster by trading space for time
360 # This is the documentation for Memoize 1.03
362 memoize('slow_function');
363 slow_function(arguments); # Is faster than it was before
366 This is normally all you need to know. However, many options are available:
368 memoize(function, options...);
372 NORMALIZER => function
375 SCALAR_CACHE => 'MEMORY'
376 SCALAR_CACHE => ['HASH', \%cache_hash ]
377 SCALAR_CACHE => 'FAULT'
378 SCALAR_CACHE => 'MERGE'
380 LIST_CACHE => 'MEMORY'
381 LIST_CACHE => ['HASH', \%cache_hash ]
382 LIST_CACHE => 'FAULT'
383 LIST_CACHE => 'MERGE'
387 `Memoizing' a function makes it faster by trading space for time. It
388 does this by caching the return values of the function in a table.
389 If you call the function again with the same arguments, C<memoize>
390 jumps in and gives you the value out of the table, instead of letting
391 the function compute the value all over again.
393 Here is an extreme example. Consider the Fibonacci sequence, defined
394 by the following function:
396 # Compute Fibonacci numbers
400 fib($n-1) + fib($n-2);
403 This function is very slow. Why? To compute fib(14), it first wants
404 to compute fib(13) and fib(12), and add the results. But to compute
405 fib(13), it first has to compute fib(12) and fib(11), and then it
406 comes back and computes fib(12) all over again even though the answer
407 is the same. And both of the times that it wants to compute fib(12),
408 it has to compute fib(11) from scratch, and then it has to do it
409 again each time it wants to compute fib(13). This function does so
410 much recomputing of old results that it takes a really long time to
411 run---fib(14) makes 1,200 extra recursive calls to itself, to compute
412 and recompute things that it already computed.
414 This function is a good candidate for memoization. If you memoize the
415 `fib' function above, it will compute fib(14) exactly once, the first
416 time it needs to, and then save the result in a table. Then if you
417 ask for fib(14) again, it gives you the result out of the table.
418 While computing fib(14), instead of computing fib(12) twice, it does
419 it once; the second time it needs the value it gets it from the table.
420 It doesn't compute fib(11) four times; it computes it once, getting it
421 from the table the next three times. Instead of making 1,200
422 recursive calls to `fib', it makes 15. This makes the function about
425 You could do the memoization yourself, by rewriting the function, like
428 # Compute Fibonacci numbers, memoized version
432 return $fib[$n] if defined $fib[$n];
433 return $fib[$n] = $n if $n < 2;
434 $fib[$n] = fib($n-1) + fib($n-2);
438 Or you could use this module, like this:
443 # Rest of the fib function just like the original version.
445 This makes it easy to turn memoizing on and off.
447 Here's an even simpler example: I wrote a simple ray tracer; the
448 program would look in a certain direction, figure out what it was
449 looking at, and then convert the `color' value (typically a string
450 like `red') of that object to a red, green, and blue pixel value, like
453 for ($direction = 0; $direction < 300; $direction++) {
454 # Figure out which object is in direction $direction
455 $color = $object->{color};
456 ($r, $g, $b) = @{&ColorToRGB($color)};
460 Since there are relatively few objects in a picture, there are only a
461 few colors, which get looked up over and over again. Memoizing
462 C<ColorToRGB> sped up the program by several percent.
466 This module exports exactly one function, C<memoize>. The rest of the
467 functions in this package are None of Your Business.
473 where C<function> is the name of the function you want to memoize, or
474 a reference to it. C<memoize> returns a reference to the new,
475 memoized version of the function, or C<undef> on a non-fatal error.
476 At present, there are no non-fatal errors, but there might be some in
479 If C<function> was the name of a function, then C<memoize> hides the
480 old version and installs the new memoized version under the old name,
481 so that C<&function(...)> actually invokes the memoized version.
485 There are some optional options you can pass to C<memoize> to change
486 the way it behaves a little. To supply options, invoke C<memoize>
489 memoize(function, NORMALIZER => function,
491 SCALAR_CACHE => option,
495 Each of these options is optional; you can include some, all, or none
500 If you supply a function name with C<INSTALL>, memoize will install
501 the new, memoized version of the function under the name you give.
504 memoize('fib', INSTALL => 'fastfib')
506 installs the memoized version of C<fib> as C<fastfib>; without the
507 C<INSTALL> option it would have replaced the old C<fib> with the
510 To prevent C<memoize> from installing the memoized version anywhere, use
511 C<INSTALL =E<gt> undef>.
515 Suppose your function looks like this:
517 # Typical call: f('aha!', A => 11, B => 12);
521 $hash{B} ||= 2; # B defaults to 2
522 $hash{C} ||= 7; # C defaults to 7
524 # Do something with $a, %hash
527 Now, the following calls to your function are all completely equivalent:
532 f(OUCH, B => 2, C => 7);
533 f(OUCH, C => 7, B => 2);
536 However, unless you tell C<Memoize> that these calls are equivalent,
537 it will not know that, and it will compute the values for these
538 invocations of your function separately, and store them separately.
540 To prevent this, supply a C<NORMALIZER> function that turns the
541 program arguments into a string in a way that equivalent arguments
542 turn into the same string. A C<NORMALIZER> function for C<f> above
543 might look like this:
551 join(',', $a, map ($_ => $hash{$_}) sort keys %hash);
554 Each of the argument lists above comes out of the C<normalize_f>
555 function looking exactly the same, like this:
559 You would tell C<Memoize> to use this normalizer this way:
561 memoize('f', NORMALIZER => 'normalize_f');
563 C<memoize> knows that if the normalized version of the arguments is
564 the same for two argument lists, then it can safely look up the value
565 that it computed for one argument list and return it as the result of
566 calling the function with the other argument list, even if the
567 argument lists look different.
569 The default normalizer just concatenates the arguments with character
570 28 in between. (In ASCII, this is called FS or control-\.) This
571 always works correctly for functions with only one string argument,
572 and also when the arguments never contain character 28. However, it
573 can confuse certain argument lists:
575 normalizer("a\034", "b")
576 normalizer("a", "\034b")
577 normalizer("a\034\034b")
581 Since hash keys are strings, the default normalizer will not
582 distinguish between C<undef> and the empty string. It also won't work
583 when the function's arguments are references. For example, consider a
584 function C<g> which gets two arguments: A number, and a reference to
587 g(13, [1,2,3,4,5,6,7]);
589 The default normalizer will turn this into something like
590 C<"13\034ARRAY(0x436c1f)">. That would be all right, except that a
591 subsequent array of numbers might be stored at a different location
592 even though it contains the same data. If this happens, C<Memoize>
593 will think that the arguments are different, even though they are
594 equivalent. In this case, a normalizer like this is appropriate:
596 sub normalize { join ' ', $_[0], @{$_[1]} }
598 For the example above, this produces the key "13 1 2 3 4 5 6 7".
600 Another use for normalizers is when the function depends on data other
601 than those in its arguments. Suppose you have a function which
602 returns a value which depends on the current hour of the day:
605 my ($problem_type) = @_;
606 my $hour = (localtime)[2];
607 open my $fh, "$DIR/$problem_type" or die...;
615 At 10:23, this function generates the 10th line of a data file; at
616 3:45 PM it generates the 15th line instead. By default, C<Memoize>
617 will only see the $problem_type argument. To fix this, include the
618 current hour in the normalizer:
620 sub normalize { join ' ', (localtime)[2], @_ }
622 The calling context of the function (scalar or list context) is
623 propagated to the normalizer. This means that if the memoized
624 function will treat its arguments differently in list context than it
625 would in scalar context, you can have the normalizer function select
626 its behavior based on the results of C<wantarray>. Even if called in
627 a list context, a normalizer should still return a single string.
629 =head2 C<SCALAR_CACHE>, C<LIST_CACHE>
631 Normally, C<Memoize> caches your function's return values into an
632 ordinary Perl hash variable. However, you might like to have the
633 values cached on the disk, so that they persist from one run of your
634 program to the next, or you might like to associate some other
635 interesting semantics with the cached values.
637 There's a slight complication under the hood of C<Memoize>: There are
638 actually I<two> caches, one for scalar values and one for list values.
639 When your function is called in scalar context, its return value is
640 cached in one hash, and when your function is called in list context,
641 its value is cached in the other hash. You can control the caching
642 behavior of both contexts independently with these options.
644 The argument to C<LIST_CACHE> or C<SCALAR_CACHE> must either be one of
645 the following four strings:
652 or else it must be a reference to an array whose first element is one of
653 these four strings, such as C<[HASH, arguments...]>.
659 C<MEMORY> means that return values from the function will be cached in
660 an ordinary Perl hash variable. The hash variable will not persist
661 after the program exits. This is the default.
665 C<HASH> allows you to specify that a particular hash that you supply
666 will be used as the cache. You can tie this hash beforehand to give
667 it any behavior you want.
669 A tied hash can have any semantics at all. It is typically tied to an
670 on-disk database, so that cached values are stored in the database and
671 retrieved from it again when needed, and the disk file typically
672 persists after your program has exited. See C<perltie> for more
673 complete details about C<tie>.
675 A typical example is:
678 tie my %cache => 'DB_File', $filename, O_RDWR|O_CREAT, 0666;
679 memoize 'function', SCALAR_CACHE => [HASH => \%cache];
681 This has the effect of storing the cache in a C<DB_File> database
682 whose name is in C<$filename>. The cache will persist after the
683 program has exited. Next time the program runs, it will find the
684 cache already populated from the previous run of the program. Or you
685 can forcibly populate the cache by constructing a batch program that
686 runs in the background and populates the cache file. Then when you
687 come to run your real program the memoized function will be fast
688 because all its results have been precomputed.
690 Another reason to use C<HASH> is to provide your own hash variable.
691 You can then inspect or modify the contents of the hash to gain finer
692 control over the cache management.
696 This option is no longer supported. It is still documented only to
697 aid in the debugging of old programs that use it. Old programs should
698 be converted to use the C<HASH> option instead.
700 memoize ... ['TIE', PACKAGE, ARGS...]
702 is merely a shortcut for
705 { tie my %cache, PACKAGE, ARGS...;
706 memoize ... [HASH => \%cache];
711 C<FAULT> means that you never expect to call the function in scalar
712 (or list) context, and that if C<Memoize> detects such a call, it
713 should abort the program. The error message is one of
715 `foo' function called in forbidden list context at line ...
716 `foo' function called in forbidden scalar context at line ...
720 C<MERGE> normally means that the memoized function does not
721 distinguish between list and sclar context, and that return values in
722 both contexts should be stored together. Both C<LIST_CACHE =E<gt>
723 MERGE> and C<SCALAR_CACHE =E<gt> MERGE> mean the same thing.
725 Consider this function:
728 # ... time-consuming calculation of $result
732 The C<complicated> function will return the same numeric C<$result>
733 regardless of whether it is called in list or in scalar context.
735 Normally, the following code will result in two calls to C<complicated>, even
736 if C<complicated> is memoized:
738 $x = complicated(142);
739 ($y) = complicated(142);
740 $z = complicated(142);
742 The first call will cache the result, say 37, in the scalar cache; the
743 second will cach the list C<(37)> in the list cache. The third call
744 doesn't call the real C<complicated> function; it gets the value 37
745 from the scalar cache.
747 Obviously, the second call to C<complicated> is a waste of time, and
748 storing its return value is a waste of space. Specifying C<LIST_CACHE
749 =E<gt> MERGE> will make C<memoize> use the same cache for scalar and
750 list context return values, so that the second call uses the scalar
751 cache that was populated by the first call. C<complicated> ends up
752 being called only once, and both subsequent calls return C<3> from the
753 cache, regardless of the calling context.
755 =head3 List values in scalar context
757 Consider this function:
759 sub iota { return reverse (1..$_[0]) }
761 This function normally returns a list. Suppose you memoize it and
764 memoize 'iota', SCALAR_CACHE => 'MERGE';
769 Here the first call caches the list (1,2,3,4,5,6,7). The second call
770 does not really make sense. C<Memoize> cannot guess what behavior
771 C<iota> should have in scalar context without actually calling it in
772 scalar context. Normally C<Memoize> I<would> call C<iota> in scalar
773 context and cache the result, but the C<SCALAR_CACHE =E<gt> 'MERGE'>
774 option says not to do that, but to use the cache list-context value
775 instead. But it cannot return a list of seven elements in a scalar
776 context. In this case C<$i7> will receive the B<first element> of the
777 cached list value, namely 7.
779 =head3 Merged disk caches
781 Another use for C<MERGE> is when you want both kinds of return values
782 stored in the same disk file; this saves you from having to deal with
783 two disk files instead of one. You can use a normalizer function to
784 keep the two sets of return values separate. For example:
786 tie my %cache => 'MLDBM', 'DB_File', $filename, ...;
790 SCALAR_CACHE => [HASH => \%cache],
791 LIST_CACHE => 'MERGE',
795 my $context = wantarray() ? 'L' : 'S';
796 # ... now compute the hash key from the arguments ...
797 $hashkey = "$context:$hashkey";
800 This normalizer function will store scalar context return values in
801 the disk file under keys that begin with C<S:>, and list context
802 return values under keys that begin with C<L:>.
806 =head1 OTHER FACILITIES
810 There's an C<unmemoize> function that you can import if you want to.
811 Why would you want to? Here's an example: Suppose you have your cache
812 tied to a DBM file, and you want to make sure that the cache is
813 written out to disk if someone interrupts the program. If the program
814 exits normally, this will happen anyway, but if someone types
815 control-C or something then the program will terminate immediately
816 without synchronizing the database. So what you can do instead is
818 $SIG{INT} = sub { unmemoize 'function' };
820 C<unmemoize> accepts a reference to, or the name of a previously
821 memoized function, and undoes whatever it did to provide the memoized
822 version in the first place, including making the name refer to the
823 unmemoized version if appropriate. It returns a reference to the
824 unmemoized version of the function.
826 If you ask it to unmemoize a function that was never memoized, it
829 =head2 C<flush_cache>
831 C<flush_cache(function)> will flush out the caches, discarding I<all>
832 the cached data. The argument may be a function name or a reference
833 to a function. For finer control over when data is discarded or
834 expired, see the documentation for C<Memoize::Expire>, included in
837 Note that if the cache is a tied hash, C<flush_cache> will attempt to
838 invoke the C<CLEAR> method on the hash. If there is no C<CLEAR>
839 method, this will cause a run-time error.
841 An alternative approach to cache flushing is to use the C<HASH> option
842 (see above) to request that C<Memoize> use a particular hash variable
843 as its cache. Then you can examine or modify the hash at any time in
844 any way you desire. You may flush the cache by using C<%hash = ()>.
848 Memoization is not a cure-all:
854 Do not memoize a function whose behavior depends on program
855 state other than its own arguments, such as global variables, the time
856 of day, or file input. These functions will not produce correct
857 results when memoized. For a particularly easy example:
863 This function takes no arguments, and as far as C<Memoize> is
864 concerned, it always returns the same result. C<Memoize> is wrong, of
865 course, and the memoized version of this function will call C<time> once
866 to get the current time, and it will return that same time
867 every time you call it after that.
871 Do not memoize a function with side effects.
876 print "$a + $b = $s.\n";
879 This function accepts two arguments, adds them, and prints their sum.
880 Its return value is the numuber of characters it printed, but you
881 probably didn't care about that. But C<Memoize> doesn't understand
882 that. If you memoize this function, you will get the result you
883 expect the first time you ask it to print the sum of 2 and 3, but
884 subsequent calls will return 1 (the return value of
885 C<print>) without actually printing anything.
889 Do not memoize a function that returns a data structure that is
890 modified by its caller.
892 Consider these functions: C<getusers> returns a list of users somehow,
893 and then C<main> throws away the first user on the list and prints the
897 my $userlist = getusers();
899 foreach $u (@$userlist) {
906 # Do something to get a list of users;
907 \@users; # Return reference to list.
910 If you memoize C<getusers> here, it will work right exactly once. The
911 reference to the users list will be stored in the memo table. C<main>
912 will discard the first element from the referenced list. The next
913 time you invoke C<main>, C<Memoize> will not call C<getusers>; it will
914 just return the same reference to the same list it got last time. But
915 this time the list has already had its head removed; C<main> will
916 erroneously remove another element from it. The list will get shorter
917 and shorter every time you call C<main>.
925 will modify $u2 as well as $u1, because both variables are references
926 to the same array. Had C<getusers> not been memoized, $u1 and $u2
927 would have referred to different arrays.
931 Do not memoize a very simple function.
933 Recently someone mentioned to me that the Memoize module made his
934 program run slower instead of faster. It turned out that he was
935 memoizing the following function:
941 I pointed out that C<Memoize> uses a hash, and that looking up a
942 number in the hash is necessarily going to take a lot longer than a
943 single multiplication. There really is no way to speed up the
946 Memoization is not magical.
950 =head1 PERSISTENT CACHE SUPPORT
952 You can tie the cache tables to any sort of tied hash that you want
953 to, as long as it supports C<TIEHASH>, C<FETCH>, C<STORE>, and
954 C<EXISTS>. For example,
956 tie my %cache => 'GDBM_File', $filename, O_RDWR|O_CREAT, 0666;
957 memoize 'function', SCALAR_CACHE => [HASH => \%cache];
959 works just fine. For some storage methods, you need a little glue.
961 C<SDBM_File> doesn't supply an C<EXISTS> method, so included in this
962 package is a glue module called C<Memoize::SDBM_File> which does
963 provide one. Use this instead of plain C<SDBM_File> to store your
964 cache table on disk in an C<SDBM_File> database:
966 tie my %cache => 'Memoize::SDBM_File', $filename, O_RDWR|O_CREAT, 0666;
967 memoize 'function', SCALAR_CACHE => [HASH => \%cache];
969 C<NDBM_File> has the same problem and the same solution. (Use
970 C<Memoize::NDBM_File instead of plain NDBM_File.>)
972 C<Storable> isn't a tied hash class at all. You can use it to store a
973 hash to disk and retrieve it again, but you can't modify the hash while
974 it's on the disk. So if you want to store your cache table in a
975 C<Storable> database, use C<Memoize::Storable>, which puts a hashlike
976 front-end onto C<Storable>. The hash table is actually kept in
977 memory, and is loaded from your C<Storable> file at the time you
978 memoize the function, and stored back at the time you unmemoize the
979 function (or when your program exits):
981 tie my %cache => 'Memoize::Storable', $filename;
982 memoize 'function', SCALAR_CACHE => [HASH => \%cache];
984 tie my %cache => 'Memoize::Storable', $filename, 'nstore';
985 memoize 'function', SCALAR_CACHE => [HASH => \%cache];
987 Include the `nstore' option to have the C<Storable> database written
988 in `network order'. (See L<Storable> for more details about this.)
990 The C<flush_cache()> function will raise a run-time error unless the
991 tied package provides a C<CLEAR> method.
993 =head1 EXPIRATION SUPPORT
995 See Memoize::Expire, which is a plug-in module that adds expiration
996 functionality to Memoize. If you don't like the kinds of policies
997 that Memoize::Expire implements, it is easy to write your own plug-in
998 module to implement whatever policy you desire. Memoize comes with
999 several examples. An expiration manager that implements a LRU policy
1000 is available on CPAN as Memoize::ExpireLRU.
1004 The test suite is much better, but always needs improvement.
1006 There is some problem with the way C<goto &f> works under threaded
1007 Perl, perhaps because of the lexical scoping of C<@_>. This is a bug
1008 in Perl, and until it is resolved, memoized functions will see a
1009 slightly different C<caller()> and will perform a little more slowly
1010 on threaded perls than unthreaded perls.
1012 Some versions of C<DB_File> won't let you store data under a key of
1013 length 0. That means that if you have a function C<f> which you
1014 memoized and the cache is in a C<DB_File> database, then the value of
1015 C<f()> (C<f> called with no arguments) will not be memoized. If this
1016 is a big problem, you can supply a normalizer function that prepends
1017 C<"x"> to every key.
1021 To join a very low-traffic mailing list for announcements about
1022 C<Memoize>, send an empty note to C<mjd-perl-memoize-request@plover.com>.
1026 Mark-Jason Dominus (C<mjd-perl-memoize+@plover.com>), Plover Systems co.
1028 See the C<Memoize.pm> Page at http://perl.plover.com/Memoize/
1029 for news and upgrades. Near this page, at
1030 http://perl.plover.com/MiniMemoize/ there is an article about
1031 memoization and about the internals of Memoize that appeared in The
1032 Perl Journal, issue #13. (This article is also included in the
1033 Memoize distribution as `article.html'.)
1035 The author's book I<Higher-Order Perl> (2005, ISBN 1558607013, published
1036 by Morgan Kaufmann) discusses memoization (and many other
1037 topics) in tremendous detail. It is available on-line for free.
1038 For more information, visit http://hop.perl.plover.com/ .
1040 To join a mailing list for announcements about C<Memoize>, send an
1041 empty message to C<mjd-perl-memoize-request@plover.com>. This mailing
1042 list is for announcements only and has extremely low traffic---fewer than
1043 two messages per year.
1045 =head1 COPYRIGHT AND LICENSE
1047 Copyright 1998, 1999, 2000, 2001, 2012 by Mark Jason Dominus
1049 This library is free software; you may redistribute it and/or modify
1050 it under the same terms as Perl itself.
1054 Many thanks to Florian Ragwitz for administration and packaging
1055 assistance, to John Tromp for bug reports, to Jonathan Roy for bug reports
1056 and suggestions, to Michael Schwern for other bug reports and patches,
1057 to Mike Cariaso for helping me to figure out the Right Thing to Do
1058 About Expiration, to Joshua Gerth, Joshua Chamas, Jonathan Roy
1059 (again), Mark D. Anderson, and Andrew Johnson for more suggestions
1060 about expiration, to Brent Powers for the Memoize::ExpireLRU module,
1061 to Ariel Scolnicov for delightful messages about the Fibonacci
1062 function, to Dion Almaer for thought-provoking suggestions about the
1063 default normalizer, to Walt Mankowski and Kurt Starsinic for much help
1064 investigating problems under threaded Perl, to Alex Dudkevich for
1065 reporting the bug in prototyped functions and for checking my patch,
1066 to Tony Bass for many helpful suggestions, to Jonathan Roy (again) for
1067 finding a use for C<unmemoize()>, to Philippe Verdret for enlightening
1068 discussion of C<Hook::PrePostCall>, to Nat Torkington for advice I
1069 ignored, to Chris Nandor for portability advice, to Randal Schwartz
1070 for suggesting the 'C<flush_cache> function, and to Jenda Krynicky for
1071 being a light in the world.
1073 Special thanks to Jarkko Hietaniemi, the 5.8.0 pumpking, for including
1074 this module in the core and for his patient and helpful guidance
1075 during the integration process.