1 # -*- mode: perl; perl-indent-level: 2; -*-
4 # Transparent memoization of idempotent functions
6 # Copyright 1998, 1999, 2000, 2001 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.
11 # Version 1.00 $Revision: 1.18 $ $Date: 2001/06/24 17:16:47 $
16 # Compile-time constants
22 # Usage memoize(functionname/ref,
23 # { NORMALIZER => coderef, INSTALL => name,
24 # LIST_CACHE => descriptor, SCALAR_CACHE => descriptor }
32 @EXPORT = qw(memoize);
33 @EXPORT_OK = qw(unmemoize flush_cache);
38 my @CONTEXT_TAGS = qw(MERGE TIE MEMORY FAULT HASH);
39 my %IS_CACHE_TAG = map {($_ => 1)} @CONTEXT_TAGS;
41 # Raise an error if the user tries to specify one of thesepackage as a
44 my %scalar_only = map {($_ => 1)} qw(DB_File GDBM_File SDBM_File ODBM_File NDBM_File);
49 my $options = \%options;
51 unless (defined($fn) &&
52 (ref $fn eq 'CODE' || ref $fn eq '')) {
53 croak "Usage: memoize 'functionname'|coderef {OPTIONS}";
56 my $uppack = caller; # TCL me Elmo!
57 my $cref; # Code reference to original function
58 my $name = (ref $fn ? undef : $fn);
60 # Convert function names to code references
61 $cref = &_make_cref($fn, $uppack);
63 # Locate function prototype, if any
64 my $proto = prototype $cref;
65 if (defined $proto) { $proto = "($proto)" }
68 # I would like to get rid of the eval, but there seems not to be any
69 # other way to set the prototype properly. The switch here for
70 # 'usethreads' works around a bug in threadperl having to do with
71 # magic goto. It would be better to fix the bug and use the magic
72 # goto version everywhere.
75 ? eval "sub $proto { &_memoizer(\$cref, \@_); }"
76 : eval "sub $proto { unshift \@_, \$cref; goto &_memoizer; }";
78 my $normalizer = $options{NORMALIZER};
79 if (defined $normalizer && ! ref $normalizer) {
80 $normalizer = _make_cref($normalizer, $uppack);
84 if (defined $options->{INSTALL}) {
86 $install_name = $options->{INSTALL};
87 } elsif (! exists $options->{INSTALL}) {
88 # No INSTALL option provided; use original name if possible
89 $install_name = $name;
91 # INSTALL => undef means don't install
94 if (defined $install_name) {
95 $install_name = $uppack . '::' . $install_name
96 unless $install_name =~ /::/;
98 local($^W) = 0; # ``Subroutine $install_name redefined at ...''
99 *{$install_name} = $wrapper; # Install memoized version
102 $revmemotable{$wrapper} = "" . $cref; # Turn code ref into hash key
104 # These will be the caches
106 for my $context (qw(SCALAR LIST)) {
107 # suppress subsequent 'uninitialized value' warnings
108 $options{"${context}_CACHE"} ||= '';
110 my $cache_opt = $options{"${context}_CACHE"};
112 if (ref $cache_opt) {
113 @cache_opt_args = @$cache_opt;
114 $cache_opt = shift @cache_opt_args;
116 if ($cache_opt eq 'FAULT') { # no cache
117 $caches{$context} = undef;
118 } elsif ($cache_opt eq 'HASH') { # user-supplied hash
119 my $cache = $cache_opt_args[0];
120 my $package = ref(tied %$cache);
121 if ($context eq 'LIST' && $scalar_only{$package}) {
122 croak("You can't use $package for LIST_CACHE because it can only store scalars");
124 $caches{$context} = $cache;
125 } elsif ($cache_opt eq '' || $IS_CACHE_TAG{$cache_opt}) {
126 # default is that we make up an in-memory hash
127 $caches{$context} = {};
128 # (this might get tied later, or MERGEd away)
130 croak "Unrecognized option to `${context}_CACHE': `$cache_opt' should be one of (@CONTEXT_TAGS); aborting";
134 # Perhaps I should check here that you didn't supply *both* merge
135 # options. But if you did, it does do something reasonable: They
136 # both get merged to the same in-memory hash.
137 if ($options{SCALAR_CACHE} eq 'MERGE') {
138 $caches{SCALAR} = $caches{LIST};
139 } elsif ($options{LIST_CACHE} eq 'MERGE') {
140 $caches{LIST} = $caches{SCALAR};
143 # Now deal with the TIE options
146 foreach $context (qw(SCALAR LIST)) {
147 # If the relevant option wasn't `TIE', this call does nothing.
148 _my_tie($context, $caches{$context}, $options); # Croaks on failure
152 # We should put some more stuff in here eventually.
153 # We've been saying that for serveral versions now.
154 # And you know what? More stuff keeps going in!
157 O => $options, # Short keys here for things we need to access frequently
160 MEMOIZED => $wrapper,
162 NAME => $install_name,
163 S => $caches{SCALAR},
167 $wrapper # Return just memoized version
170 use warnings::register;
172 # This function tries to load a tied hash class and tie the hash to it.
174 my ($context, $hash, $options) = @_;
175 my $fullopt = $options->{"${context}_CACHE"};
177 # We already checked to make sure that this works.
178 my $shortopt = (ref $fullopt) ? $fullopt->[0] : $fullopt;
180 return unless defined $shortopt && $shortopt eq 'TIE';
181 carp("TIE option to memoize() is deprecated; use HASH instead")
182 if warnings::enabled('deprecated');
184 my @args = ref $fullopt ? @$fullopt : ();
186 my $module = shift @args;
187 if ($context eq 'LIST' && $scalar_only{$module}) {
188 croak("You can't use $module for LIST_CACHE because it can only store scalars");
190 my $modulefile = $module . '.pm';
191 $modulefile =~ s{::}{/}g;
192 eval { require $modulefile };
194 croak "Memoize: Couldn't load hash tie module `$module': $@; aborting";
196 my $rc = (tie %$hash => $module, @args);
198 croak "Memoize: Couldn't tie hash to `$module': $!; aborting";
204 my $func = _make_cref($_[0], scalar caller);
205 my $info = $memotable{$revmemotable{$func}};
206 die "$func not memoized" unless defined $info;
207 for my $context (qw(S L)) {
208 my $cache = $info->{$context};
209 if (tied %$cache && ! (tied %$cache)->can('CLEAR')) {
210 my $funcname = defined($info->{NAME}) ?
211 "function $info->{NAME}" : "anonymous function $func";
212 my $context = {S => 'scalar', L => 'list'}->{$context};
213 croak "Tied cache hash for $context-context $funcname does not support flushing";
220 # This is the function that manages the memo tables.
222 my $orig = shift; # stringized version of ref to original func.
223 my $info = $memotable{$orig};
224 my $normalizer = $info->{N};
227 my $context = (wantarray() ? LIST : SCALAR);
229 if (defined $normalizer) {
231 if ($context == SCALAR) {
232 $argstr = &{$normalizer}(@_);
233 } elsif ($context == LIST) {
234 ($argstr) = &{$normalizer}(@_);
236 croak "Internal error \#41; context was neither LIST nor SCALAR\n";
238 } else { # Default normalizer
240 $argstr = join chr(28),@_;
243 if ($context == SCALAR) {
244 my $cache = $info->{S};
245 _crap_out($info->{NAME}, 'scalar') unless $cache;
246 if (exists $cache->{$argstr}) {
247 return $cache->{$argstr};
249 my $val = &{$info->{U}}(@_);
250 # Scalars are considered to be lists; store appropriately
251 if ($info->{O}{SCALAR_CACHE} eq 'MERGE') {
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 my $val = $cache->{$argstr};
263 # If LISTCONTEXT=>MERGE, then the function never returns lists,
264 # so we have a scalar value cached, so just return it straightaway:
265 return ($val) if $info->{O}{LIST_CACHE} eq 'MERGE';
266 # Maybe in a later version we can use a faster test.
268 # Otherwise, we cached an array containing the returned list:
271 my $q = $cache->{$argstr} = [&{$info->{U}}(@_)];
275 croak "Internal error \#42; context was neither LIST nor SCALAR\n";
282 my $cref = _make_cref($f, $uppack);
284 unless (exists $revmemotable{$cref}) {
285 croak "Could not unmemoize function `$f', because it was not memoized to begin with";
288 my $tabent = $memotable{$revmemotable{$cref}};
289 unless (defined $tabent) {
290 croak "Could not figure out how to unmemoize function `$f'";
292 my $name = $tabent->{NAME};
295 local($^W) = 0; # ``Subroutine $install_name redefined at ...''
296 *{$name} = $tabent->{U}; # Replace with original function
298 undef $memotable{$revmemotable{$cref}};
299 undef $revmemotable{$cref};
301 # This removes the last reference to the (possibly tied) memo tables
302 # my ($old_function, $memotabs) = @{$tabent}{'U','S','L'};
305 # # Untie the memo tables if they were tied.
308 # if (tied %{$memotabs->[$i]}) {
309 # warn "Untying hash #$i\n";
310 # untie %{$memotabs->[$i]};
323 if (ref $fn eq 'CODE') {
325 } elsif (! ref $fn) {
329 $name = $uppack . '::' . $fn;
332 if (defined $name and !defined(&$name)) {
333 croak "Cannot operate on nonexistent function `$fn'";
336 $cref = *{$name}{CODE};
338 my $parent = (caller(1))[3]; # Function that called _make_cref
339 croak "Usage: argument 1 to `$parent' must be a function name or reference.\n";
341 $DEBUG and warn "${name}($fn) => $cref in _make_cref\n";
346 my ($funcname, $context) = @_;
347 if (defined $funcname) {
348 croak "Function `$funcname' called in forbidden $context context; faulting";
350 croak "Anonymous function called in forbidden $context context; faulting";
362 Memoize - Make functions faster by trading space for time
366 # This is the documentation for Memoize 1.00
368 memoize('slow_function');
369 slow_function(arguments); # Is faster than it was before
372 This is normally all you need to know. However, many options are available:
374 memoize(function, options...);
378 NORMALIZER => function
381 SCALAR_CACHE => 'MEMORY'
382 SCALAR_CACHE => ['HASH', \%cache_hash ]
383 SCALAR_CACHE => 'FAULT'
384 SCALAR_CACHE => 'MERGE'
386 LIST_CACHE => 'MEMORY'
387 LIST_CACHE => ['HASH', \%cache_hash ]
388 LIST_CACHE => 'FAULT'
389 LIST_CACHE => 'MERGE'
393 `Memoizing' a function makes it faster by trading space for time. It
394 does this by caching the return values of the function in a table.
395 If you call the function again with the same arguments, C<memoize>
396 jumps in and gives you the value out of the table, instead of letting
397 the function compute the value all over again.
399 Here is an extreme example. Consider the Fibonacci sequence, defined
400 by the following function:
402 # Compute Fibonacci numbers
406 fib($n-1) + fib($n-2);
409 This function is very slow. Why? To compute fib(14), it first wants
410 to compute fib(13) and fib(12), and add the results. But to compute
411 fib(13), it first has to compute fib(12) and fib(11), and then it
412 comes back and computes fib(12) all over again even though the answer
413 is the same. And both of the times that it wants to compute fib(12),
414 it has to compute fib(11) from scratch, and then it has to do it
415 again each time it wants to compute fib(13). This function does so
416 much recomputing of old results that it takes a really long time to
417 run---fib(14) makes 1,200 extra recursive calls to itself, to compute
418 and recompute things that it already computed.
420 This function is a good candidate for memoization. If you memoize the
421 `fib' function above, it will compute fib(14) exactly once, the first
422 time it needs to, and then save the result in a table. Then if you
423 ask for fib(14) again, it gives you the result out of the table.
424 While computing fib(14), instead of computing fib(12) twice, it does
425 it once; the second time it needs the value it gets it from the table.
426 It doesn't compute fib(11) four times; it computes it once, getting it
427 from the table the next three times. Instead of making 1,200
428 recursive calls to `fib', it makes 15. This makes the function about
431 You could do the memoization yourself, by rewriting the function, like
434 # Compute Fibonacci numbers, memoized version
438 return $fib[$n] if defined $fib[$n];
439 return $fib[$n] = $n if $n < 2;
440 $fib[$n] = fib($n-1) + fib($n-2);
444 Or you could use this module, like this:
449 # Rest of the fib function just like the original version.
451 This makes it easy to turn memoizing on and off.
453 Here's an even simpler example: I wrote a simple ray tracer; the
454 program would look in a certain direction, figure out what it was
455 looking at, and then convert the `color' value (typically a string
456 like `red') of that object to a red, green, and blue pixel value, like
459 for ($direction = 0; $direction < 300; $direction++) {
460 # Figure out which object is in direction $direction
461 $color = $object->{color};
462 ($r, $g, $b) = @{&ColorToRGB($color)};
466 Since there are relatively few objects in a picture, there are only a
467 few colors, which get looked up over and over again. Memoizing
468 C<ColorToRGB> sped up the program by several percent.
472 This module exports exactly one function, C<memoize>. The rest of the
473 functions in this package are None of Your Business.
479 where C<function> is the name of the function you want to memoize, or
480 a reference to it. C<memoize> returns a reference to the new,
481 memoized version of the function, or C<undef> on a non-fatal error.
482 At present, there are no non-fatal errors, but there might be some in
485 If C<function> was the name of a function, then C<memoize> hides the
486 old version and installs the new memoized version under the old name,
487 so that C<&function(...)> actually invokes the memoized version.
491 There are some optional options you can pass to C<memoize> to change
492 the way it behaves a little. To supply options, invoke C<memoize>
495 memoize(function, NORMALIZER => function,
497 SCALAR_CACHE => option,
501 Each of these options is optional; you can include some, all, or none
506 If you supply a function name with C<INSTALL>, memoize will install
507 the new, memoized version of the function under the name you give.
510 memoize('fib', INSTALL => 'fastfib')
512 installs the memoized version of C<fib> as C<fastfib>; without the
513 C<INSTALL> option it would have replaced the old C<fib> with the
516 To prevent C<memoize> from installing the memoized version anywhere, use
517 C<INSTALL =E<gt> undef>.
521 Suppose your function looks like this:
523 # Typical call: f('aha!', A => 11, B => 12);
527 $hash{B} ||= 2; # B defaults to 2
528 $hash{C} ||= 7; # C defaults to 7
530 # Do something with $a, %hash
533 Now, the following calls to your function are all completely equivalent:
538 f(OUCH, B => 2, C => 7);
539 f(OUCH, C => 7, B => 2);
542 However, unless you tell C<Memoize> that these calls are equivalent,
543 it will not know that, and it will compute the values for these
544 invocations of your function separately, and store them separately.
546 To prevent this, supply a C<NORMALIZER> function that turns the
547 program arguments into a string in a way that equivalent arguments
548 turn into the same string. A C<NORMALIZER> function for C<f> above
549 might look like this:
557 join(',', $a, map ($_ => $hash{$_}) sort keys %hash);
560 Each of the argument lists above comes out of the C<normalize_f>
561 function looking exactly the same, like this:
565 You would tell C<Memoize> to use this normalizer this way:
567 memoize('f', NORMALIZER => 'normalize_f');
569 C<memoize> knows that if the normalized version of the arguments is
570 the same for two argument lists, then it can safely look up the value
571 that it computed for one argument list and return it as the result of
572 calling the function with the other argument list, even if the
573 argument lists look different.
575 The default normalizer just concatenates the arguments with character
576 28 in between. (In ASCII, this is called FS or control-\.) This
577 always works correctly for functions with only one string argument,
578 and also when the arguments never contain character 28. However, it
579 can confuse certain argument lists:
581 normalizer("a\034", "b")
582 normalizer("a", "\034b")
583 normalizer("a\034\034b")
587 Since hash keys are strings, the default normalizer will not
588 distinguish between C<undef> and the empty string. It also won't work
589 when the function's arguments are references. For example, consider a
590 function C<g> which gets two arguments: A number, and a reference to
593 g(13, [1,2,3,4,5,6,7]);
595 The default normalizer will turn this into something like
596 C<"13\034ARRAY(0x436c1f)">. That would be all right, except that a
597 subsequent array of numbers might be stored at a different location
598 even though it contains the same data. If this happens, C<Memoize>
599 will think that the arguments are different, even though they are
600 equivalent. In this case, a normalizer like this is appropriate:
602 sub normalize { join ' ', $_[0], @{$_[1]} }
604 For the example above, this produces the key "13 1 2 3 4 5 6 7".
606 Another use for normalizers is when the function depends on data other
607 than those in its arguments. Suppose you have a function which
608 returns a value which depends on the current hour of the day:
611 my ($problem_type) = @_;
612 my $hour = (localtime)[2];
613 open my $fh, "$DIR/$problem_type" or die...;
621 At 10:23, this function generates the 10th line of a data file; at
622 3:45 PM it generates the 15th line instead. By default, C<Memoize>
623 will only see the $problem_type argument. To fix this, include the
624 current hour in the normalizer:
626 sub normalize { join ' ', (localtime)[2], @_ }
628 The calling context of the function (scalar or list context) is
629 propagated to the normalizer. This means that if the memoized
630 function will treat its arguments differently in list context than it
631 would in scalar context, you can have the normalizer function select
632 its behavior based on the results of C<wantarray>. Even if called in
633 a list context, a normalizer should still return a single string.
635 =head2 C<SCALAR_CACHE>, C<LIST_CACHE>
637 Normally, C<Memoize> caches your function's return values into an
638 ordinary Perl hash variable. However, you might like to have the
639 values cached on the disk, so that they persist from one run of your
640 program to the next, or you might like to associate some other
641 interesting semantics with the cached values.
643 There's a slight complication under the hood of C<Memoize>: There are
644 actually I<two> caches, one for scalar values and one for list values.
645 When your function is called in scalar context, its return value is
646 cached in one hash, and when your function is called in list context,
647 its value is cached in the other hash. You can control the caching
648 behavior of both contexts independently with these options.
650 The argument to C<LIST_CACHE> or C<SCALAR_CACHE> must either be one of
651 the following four strings:
658 or else it must be a reference to a list whose first element is one of
659 these four strings, such as C<[HASH, arguments...]>.
665 C<MEMORY> means that return values from the function will be cached in
666 an ordinary Perl hash variable. The hash variable will not persist
667 after the program exits. This is the default.
671 C<HASH> allows you to specify that a particular hash that you supply
672 will be used as the cache. You can tie this hash beforehand to give
673 it any behavior you want.
675 A tied hash can have any semantics at all. It is typically tied to an
676 on-disk database, so that cached values are stored in the database and
677 retrieved from it again when needed, and the disk file typically
678 persists after your program has exited. See C<perltie> for more
679 complete details about C<tie>.
681 A typical example is:
684 tie my %cache => 'DB_File', $filename, O_RDWR|O_CREAT, 0666;
685 memoize 'function', SCALAR_CACHE => [HASH => \%cache];
687 This has the effect of storing the cache in a C<DB_File> database
688 whose name is in C<$filename>. The cache will persist after the
689 program has exited. Next time the program runs, it will find the
690 cache already populated from the previous run of the program. Or you
691 can forcibly populate the cache by constructing a batch program that
692 runs in the background and populates the cache file. Then when you
693 come to run your real program the memoized function will be fast
694 because all its results have been precomputed.
698 This option is no longer supported. It is still documented only to
699 aid in the debugging of old programs that use it. Old programs should
700 be converted to use the C<HASH> option instead.
702 memoize ... [TIE, PACKAGE, ARGS...]
704 is merely a shortcut for
708 tie %cache, PACKAGE, ARGS...;
710 memoize ... [HASH => \%cache];
714 C<FAULT> means that you never expect to call the function in scalar
715 (or list) context, and that if C<Memoize> detects such a call, it
716 should abort the program. The error message is one of
718 `foo' function called in forbidden list context at line ...
719 `foo' function called in forbidden scalar context at line ...
723 C<MERGE> normally means the function does not distinguish between list
724 and sclar context, and that return values in both contexts should be
725 stored together. C<LIST_CACHE =E<gt> MERGE> means that list context
726 return values should be stored in the same hash that is used for
727 scalar context returns, and C<SCALAR_CACHE =E<gt> MERGE> means the
728 same, mutatis mutandis. It is an error to specify C<MERGE> for both,
729 but it probably does something useful.
731 Consider this function:
735 Normally, the following code will result in two calls to C<pi>:
741 The first call caches the value C<3> in the scalar cache; the second
742 caches the list C<(3)> in the list cache. The third call doesn't call
743 the real C<pi> function; it gets the value from the scalar cache.
745 Obviously, the second call to C<pi> is a waste of time, and storing
746 its return value is a waste of space. Specifying C<LIST_CACHE =E<gt>
747 MERGE> will make C<memoize> use the same cache for scalar and list
748 context return values, so that the second call uses the scalar cache
749 that was populated by the first call. C<pi> ends up being called only
750 once, and both subsequent calls return C<3> from the cache, regardless
751 of the calling context.
753 Another use for C<MERGE> is when you want both kinds of return values
754 stored in the same disk file; this saves you from having to deal with
755 two disk files instead of one. You can use a normalizer function to
756 keep the two sets of return values separate. For example:
758 tie my %cache => 'MLDBM', 'DB_File', $filename, ...;
762 SCALAR_CACHE => [HASH => \%cache],
767 my $context = wantarray() ? 'L' : 'S';
768 # ... now compute the hash key from the arguments ...
769 $hashkey = "$context:$hashkey";
772 This normalizer function will store scalar context return values in
773 the disk file under keys that begin with C<S:>, and list context
774 return values under keys that begin with C<L:>.
778 =head1 OTHER FACILITIES
782 There's an C<unmemoize> function that you can import if you want to.
783 Why would you want to? Here's an example: Suppose you have your cache
784 tied to a DBM file, and you want to make sure that the cache is
785 written out to disk if someone interrupts the program. If the program
786 exits normally, this will happen anyway, but if someone types
787 control-C or something then the program will terminate immediately
788 without synchronizing the database. So what you can do instead is
790 $SIG{INT} = sub { unmemoize 'function' };
792 C<unmemoize> accepts a reference to, or the name of a previously
793 memoized function, and undoes whatever it did to provide the memoized
794 version in the first place, including making the name refer to the
795 unmemoized version if appropriate. It returns a reference to the
796 unmemoized version of the function.
798 If you ask it to unmemoize a function that was never memoized, it
801 =head2 C<flush_cache>
803 C<flush_cache(function)> will flush out the caches, discarding I<all>
804 the cached data. The argument may be a function name or a reference
805 to a function. For finer control over when data is discarded or
806 expired, see the documentation for C<Memoize::Expire>, included in
809 Note that if the cache is a tied hash, C<flush_cache> will attempt to
810 invoke the C<CLEAR> method on the hash. If there is no C<CLEAR>
811 method, this will cause a run-time error.
813 An alternative approach to cache flushing is to use the C<HASH> option
814 (see above) to request that C<Memoize> use a particular hash variable
815 as its cache. Then you can examine or modify the hash at any time in
816 any way you desire. You may flush the cache by using C<%hash = ()>.
820 Memoization is not a cure-all:
826 Do not memoize a function whose behavior depends on program
827 state other than its own arguments, such as global variables, the time
828 of day, or file input. These functions will not produce correct
829 results when memoized. For a particularly easy example:
835 This function takes no arguments, and as far as C<Memoize> is
836 concerned, it always returns the same result. C<Memoize> is wrong, of
837 course, and the memoized version of this function will call C<time> once
838 to get the current time, and it will return that same time
839 every time you call it after that.
843 Do not memoize a function with side effects.
848 print "$a + $b = $s.\n";
851 This function accepts two arguments, adds them, and prints their sum.
852 Its return value is the numuber of characters it printed, but you
853 probably didn't care about that. But C<Memoize> doesn't understand
854 that. If you memoize this function, you will get the result you
855 expect the first time you ask it to print the sum of 2 and 3, but
856 subsequent calls will return 1 (the return value of
857 C<print>) without actually printing anything.
861 Do not memoize a function that returns a data structure that is
862 modified by its caller.
864 Consider these functions: C<getusers> returns a list of users somehow,
865 and then C<main> throws away the first user on the list and prints the
869 my $userlist = getusers();
871 foreach $u (@$userlist) {
878 # Do something to get a list of users;
879 \@users; # Return reference to list.
882 If you memoize C<getusers> here, it will work right exactly once. The
883 reference to the users list will be stored in the memo table. C<main>
884 will discard the first element from the referenced list. The next
885 time you invoke C<main>, C<Memoize> will not call C<getusers>; it will
886 just return the same reference to the same list it got last time. But
887 this time the list has already had its head removed; C<main> will
888 erroneously remove another element from it. The list will get shorter
889 and shorter every time you call C<main>.
897 will modify $u2 as well as $u1, because both variables are references
898 to the same array. Had C<getusers> not been memoized, $u1 and $u2
899 would have referred to different arrays.
903 Do not memoize a very simple function.
905 Recently someone mentioned to me that the Memoize module made his
906 program run slower instead of faster. It turned out that he was
907 memoizing the following function:
913 I pointed out that C<Memoize> uses a hash, and that looking up a
914 number in the hash is necessarily going to take a lot longer than a
915 single multiplication. There really is no way to speed up the
918 Memoization is not magical.
922 =head1 PERSISTENT CACHE SUPPORT
924 You can tie the cache tables to any sort of tied hash that you want
925 to, as long as it supports C<TIEHASH>, C<FETCH>, C<STORE>, and
926 C<EXISTS>. For example,
928 tie my %cache => 'GDBM_File', $filename, O_RDWR|O_CREAT, 0666;
929 memoize 'function', SCALAR_CACHE => [HASH => \%cache];
931 works just fine. For some storage methods, you need a little glue.
933 C<SDBM_File> doesn't supply an C<EXISTS> method, so included in this
934 package is a glue module called C<Memoize::SDBM_File> which does
935 provide one. Use this instead of plain C<SDBM_File> to store your
936 cache table on disk in an C<SDBM_File> database:
938 tie my %cache => 'Memoize::SDBM_File', $filename, O_RDWR|O_CREAT, 0666;
939 memoize 'function', SCALAR_CACHE => [HASH => \%cache];
941 C<NDBM_File> has the same problem and the same solution. (Use
942 C<Memoize::NDBM_File instead of plain NDBM_File.>)
944 C<Storable> isn't a tied hash class at all. You can use it to store a
945 hash to disk and retrieve it again, but you can't modify the hash while
946 it's on the disk. So if you want to store your cache table in a
947 C<Storable> database, use C<Memoize::Storable>, which puts a hashlike
948 front-end onto C<Storable>. The hash table is actually kept in
949 memory, and is loaded from your C<Storable> file at the time you
950 memoize the function, and stored back at the time you unmemoize the
951 function (or when your program exits):
953 tie my %cache => 'Memoize::Storable', $filename;
954 memoize 'function', SCALAR_CACHE => [HASH => \%cache];
956 tie my %cache => 'Memoize::Storable', $filename, 'nstore';
957 memoize 'function', SCALAR_CACHE => [HASH => \%cache];
959 Include the `nstore' option to have the C<Storable> database written
960 in `network order'. (See L<Storable> for more details about this.)
962 The C<flush_cache()> function will raise a run-time error unless the
963 tied package provides a C<CLEAR> method.
965 =head1 EXPIRATION SUPPORT
967 See Memoize::Expire, which is a plug-in module that adds expiration
968 functionality to Memoize. If you don't like the kinds of policies
969 that Memoize::Expire implements, it is easy to write your own plug-in
970 module to implement whatever policy you desire. Memoize comes with
971 several examples. An expiration manager that implements a LRU policy
972 is available on CPAN as Memoize::ExpireLRU.
976 The test suite is much better, but always needs improvement.
978 There is some problem with the way C<goto &f> works under threaded
979 Perl, perhaps because of the lexical scoping of C<@_>. This is a bug
980 in Perl, and until it is resolved, memoized functions will see a
981 slightly different C<caller()> and will perform a little more slowly
982 on threaded perls than unthreaded perls.
984 Some versions of C<DB_File> won't let you store data under a key of
985 length 0. That means that if you have a function C<f> which you
986 memoized and the cache is in a C<DB_File> database, then the value of
987 C<f()> (C<f> called with no arguments) will not be memoized. If this
988 is a big problem, you can supply a normalizer function that prepends
993 To join a very low-traffic mailing list for announcements about
994 C<Memoize>, send an empty note to C<mjd-perl-memoize-request@plover.com>.
998 Mark-Jason Dominus (C<mjd-perl-memoize+@plover.com>), Plover Systems co.
1000 See the C<Memoize.pm> Page at http://www.plover.com/~mjd/perl/Memoize/
1001 for news and upgrades. Near this page, at
1002 http://www.plover.com/~mjd/perl/MiniMemoize/ there is an article about
1003 memoization and about the internals of Memoize that appeared in The
1004 Perl Journal, issue #13. (This article is also included in the
1005 Memoize distribution as `article.html'.)
1007 My upcoming book will discuss memoization (and many other fascinating
1008 topics) in tremendous detail. It will be published by Morgan Kaufmann
1009 in 2002, possibly under the title I<Perl Advanced Techniques
1010 Handbook>. It will also be available on-line for free. For more
1011 information, visit http://perl.plover.com/book/ .
1013 To join a mailing list for announcements about C<Memoize>, send an
1014 empty message to C<mjd-perl-memoize-request@plover.com>. This mailing
1015 list is for announcements only and has extremely low traffic---about
1016 two messages per year.
1018 =head1 COPYRIGHT AND LICENSE
1020 Copyright 1998, 1999, 2000, 2001 by Mark Jason Dominus
1022 This library is free software; you may redistribute it and/or modify
1023 it under the same terms as Perl itself.
1027 Many thanks to Jonathan Roy for bug reports and suggestions, to
1028 Michael Schwern for other bug reports and patches, to Mike Cariaso for
1029 helping me to figure out the Right Thing to Do About Expiration, to
1030 Joshua Gerth, Joshua Chamas, Jonathan Roy (again), Mark D. Anderson,
1031 and Andrew Johnson for more suggestions about expiration, to Brent
1032 Powers for the Memoize::ExpireLRU module, to Ariel Scolnicov for
1033 delightful messages about the Fibonacci function, to Dion Almaer for
1034 thought-provoking suggestions about the default normalizer, to Walt
1035 Mankowski and Kurt Starsinic for much help investigating problems
1036 under threaded Perl, to Alex Dudkevich for reporting the bug in
1037 prototyped functions and for checking my patch, to Tony Bass for many
1038 helpful suggestions, to Jonathan Roy (again) for finding a use for
1039 C<unmemoize()>, to Philippe Verdret for enlightening discussion of
1040 C<Hook::PrePostCall>, to Nat Torkington for advice I ignored, to Chris
1041 Nandor for portability advice, to Randal Schwartz for suggesting the
1042 'C<flush_cache> function, and to Jenda Krynicky for being a light in
1045 Special thanks to Jarkko Hietaniemi, the 5.8.0 pumpking, for including
1046 this module in the core and for his patient and helpful guidance
1047 during the integration process.