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 0.65 beta $Revision: 1.17 $ $Date: 2000/10/24 04:33:49 $
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 # This function tries to load a tied hash class and tie the hash to it.
172 my ($context, $hash, $options) = @_;
173 my $fullopt = $options->{"${context}_CACHE"};
175 # We already checked to make sure that this works.
176 my $shortopt = (ref $fullopt) ? $fullopt->[0] : $fullopt;
178 return unless defined $shortopt && $shortopt eq 'TIE';
179 carp("TIE option to memoize() is deprecated; use HASH instead") if $^W;
182 my @args = ref $fullopt ? @$fullopt : ();
184 my $module = shift @args;
185 if ($context eq 'LIST' && $scalar_only{$module}) {
186 croak("You can't use $module for LIST_CACHE because it can only store scalars");
188 my $modulefile = $module . '.pm';
189 $modulefile =~ s{::}{/}g;
190 eval { require $modulefile };
192 croak "Memoize: Couldn't load hash tie module `$module': $@; aborting";
194 my $rc = (tie %$hash => $module, @args);
196 croak "Memoize: Couldn't tie hash to `$module': $!; aborting";
202 my $func = _make_cref($_[0], scalar caller);
203 my $info = $memotable{$revmemotable{$func}};
204 die "$func not memoized" unless defined $info;
205 for my $context (qw(S L)) {
206 my $cache = $info->{$context};
207 if (tied %$cache && ! (tied %$cache)->can('CLEAR')) {
208 my $funcname = defined($info->{NAME}) ?
209 "function $info->{NAME}" : "anonymous function $func";
210 my $context = {S => 'scalar', L => 'list'}->{$context};
211 croak "Tied cache hash for $context-context $funcname does not support flushing";
218 # This is the function that manages the memo tables.
220 my $orig = shift; # stringized version of ref to original func.
221 my $info = $memotable{$orig};
222 my $normalizer = $info->{N};
225 my $context = (wantarray() ? LIST : SCALAR);
227 if (defined $normalizer) {
229 if ($context == SCALAR) {
230 $argstr = &{$normalizer}(@_);
231 } elsif ($context == LIST) {
232 ($argstr) = &{$normalizer}(@_);
234 croak "Internal error \#41; context was neither LIST nor SCALAR\n";
236 } else { # Default normalizer
238 $argstr = join chr(28),@_;
241 if ($context == SCALAR) {
242 my $cache = $info->{S};
243 _crap_out($info->{NAME}, 'scalar') unless $cache;
244 if (exists $cache->{$argstr}) {
245 return $cache->{$argstr};
247 my $val = &{$info->{U}}(@_);
248 # Scalars are considered to be lists; store appropriately
249 if ($info->{O}{SCALAR_CACHE} eq 'MERGE') {
250 $cache->{$argstr} = [$val];
252 $cache->{$argstr} = $val;
256 } elsif ($context == LIST) {
257 my $cache = $info->{L};
258 _crap_out($info->{NAME}, 'list') unless $cache;
259 if (exists $cache->{$argstr}) {
260 my $val = $cache->{$argstr};
261 # If LISTCONTEXT=>MERGE, then the function never returns lists,
262 # so we have a scalar value cached, so just return it straightaway:
263 return ($val) if $info->{O}{LIST_CACHE} eq 'MERGE';
264 # Maybe in a later version we can use a faster test.
266 # Otherwise, we cached an array containing the returned list:
269 my $q = $cache->{$argstr} = [&{$info->{U}}(@_)];
273 croak "Internal error \#42; context was neither LIST nor SCALAR\n";
280 my $cref = _make_cref($f, $uppack);
282 unless (exists $revmemotable{$cref}) {
283 croak "Could not unmemoize function `$f', because it was not memoized to begin with";
286 my $tabent = $memotable{$revmemotable{$cref}};
287 unless (defined $tabent) {
288 croak "Could not figure out how to unmemoize function `$f'";
290 my $name = $tabent->{NAME};
293 local($^W) = 0; # ``Subroutine $install_name redefined at ...''
294 *{$name} = $tabent->{U}; # Replace with original function
296 undef $memotable{$revmemotable{$cref}};
297 undef $revmemotable{$cref};
299 # This removes the last reference to the (possibly tied) memo tables
300 # my ($old_function, $memotabs) = @{$tabent}{'U','S','L'};
303 # # Untie the memo tables if they were tied.
306 # if (tied %{$memotabs->[$i]}) {
307 # warn "Untying hash #$i\n";
308 # untie %{$memotabs->[$i]};
321 if (ref $fn eq 'CODE') {
323 } elsif (! ref $fn) {
327 $name = $uppack . '::' . $fn;
330 if (defined $name and !defined(&$name)) {
331 croak "Cannot operate on nonexistent function `$fn'";
334 $cref = *{$name}{CODE};
336 my $parent = (caller(1))[3]; # Function that called _make_cref
337 croak "Usage: argument 1 to `$parent' must be a function name or reference.\n";
339 $DEBUG and warn "${name}($fn) => $cref in _make_cref\n";
344 my ($funcname, $context) = @_;
345 if (defined $funcname) {
346 croak "Function `$funcname' called in forbidden $context context; faulting";
348 croak "Anonymous function called in forbidden $context context; faulting";
360 Memoize - Make your functions faster by trading space for time
365 memoize('slow_function');
366 slow_function(arguments); # Is faster than it was before
369 This is normally all you need to know. However, many options are available:
371 memoize(function, options...);
375 NORMALIZER => function
378 SCALAR_CACHE => 'MEMORY'
379 SCALAR_CACHE => ['HASH', \%cache_hash ]
380 SCALAR_CACHE => 'FAULT'
381 SCALAR_CACHE => 'MERGE'
383 LIST_CACHE => 'MEMORY'
384 LIST_CACHE => ['HASH', \%cache_hash ]
385 LIST_CACHE => 'FAULT'
386 LIST_CACHE => 'MERGE'
390 `Memoizing' a function makes it faster by trading space for time. It
391 does this by caching the return values of the function in a table.
392 If you call the function again with the same arguments, C<memoize>
393 jmups in and gives you the value out of the table, instead of letting
394 the function compute the value all over again.
396 Here is an extreme example. Consider the Fibonacci sequence, defined
397 by the following function:
399 # Compute Fibonacci numbers
403 fib($n-1) + fib($n-2);
406 This function is very slow. Why? To compute fib(14), it first wants
407 to compute fib(13) and fib(12), and add the results. But to compute
408 fib(13), it first has to compute fib(12) and fib(11), and then it
409 comes back and computes fib(12) all over again even though the answer
410 is the same. And both of the times that it wants to compute fib(12),
411 it has to compute fib(11) from scratch, and then it has to do it
412 again each time it wants to compute fib(13). This function does so
413 much recomputing of old results that it takes a really long time to
414 run---fib(14) makes 1,200 extra recursive calls to itself, to compute
415 and recompute things that it already computed.
417 This function is a good candidate for memoization. If you memoize the
418 `fib' function above, it will compute fib(14) exactly once, the first
419 time it needs to, and then save the result in a table. Then if you
420 ask for fib(14) again, it gives you the result out of the table.
421 While computing fib(14), instead of computing fib(12) twice, it does
422 it once; the second time it needs the value it gets it from the table.
423 It doesn't compute fib(11) four times; it computes it once, getting it
424 from the table the next three times. Instead of making 1,200
425 recursive calls to `fib', it makes 15. This makes the function about
428 You could do the memoization yourself, by rewriting the function, like
431 # Compute Fibonacci numbers, memoized version
435 return $fib[$n] if defined $fib[$n];
436 return $fib[$n] = $n if $n < 2;
437 $fib[$n] = fib($n-1) + fib($n-2);
441 Or you could use this module, like this:
446 # Rest of the fib function just like the original version.
448 This makes it easy to turn memoizing on and off.
450 Here's an even simpler example: I wrote a simple ray tracer; the
451 program would look in a certain direction, figure out what it was
452 looking at, and then convert the `color' value (typically a string
453 like `red') of that object to a red, green, and blue pixel value, like
456 for ($direction = 0; $direction < 300; $direction++) {
457 # Figure out which object is in direction $direction
458 $color = $object->{color};
459 ($r, $g, $b) = @{&ColorToRGB($color)};
463 Since there are relatively few objects in a picture, there are only a
464 few colors, which get looked up over and over again. Memoizing
465 C<ColorToRGB> speeded up the program by several percent.
469 This module exports exactly one function, C<memoize>. The rest of the
470 functions in this package are None of Your Business.
476 where C<function> is the name of the function you want to memoize, or
477 a reference to it. C<memoize> returns a reference to the new,
478 memoized version of the function, or C<undef> on a non-fatal error.
479 At present, there are no non-fatal errors, but there might be some in
482 If C<function> was the name of a function, then C<memoize> hides the
483 old version and installs the new memoized version under the old name,
484 so that C<&function(...)> actually invokes the memoized version.
488 There are some optional options you can pass to C<memoize> to change
489 the way it behaves a little. To supply options, invoke C<memoize>
492 memoize(function, NORMALIZER => function,
494 SCALAR_CACHE => option,
498 Each of these options is optional; you can include some, all, or none
503 If you supply a function name with C<INSTALL>, memoize will install
504 the new, memoized version of the function under the name you give.
507 memoize('fib', INSTALL => 'fastfib')
509 installs the memoized version of C<fib> as C<fastfib>; without the
510 C<INSTALL> option it would have replaced the old C<fib> with the
513 To prevent C<memoize> from installing the memoized version anywhere, use
514 C<INSTALL =E<gt> undef>.
518 Suppose your function looks like this:
520 # Typical call: f('aha!', A => 11, B => 12);
524 $hash{B} ||= 2; # B defaults to 2
525 $hash{C} ||= 7; # C defaults to 7
527 # Do something with $a, %hash
530 Now, the following calls to your function are all completely equivalent:
535 f(OUCH, B => 2, C => 7);
536 f(OUCH, C => 7, B => 2);
539 However, unless you tell C<Memoize> that these calls are equivalent,
540 it will not know that, and it will compute the values for these
541 invocations of your function separately, and store them separately.
543 To prevent this, supply a C<NORMALIZER> function that turns the
544 program arguments into a string in a way that equivalent arguments
545 turn into the same string. A C<NORMALIZER> function for C<f> above
546 might look like this:
554 join($;, $a, map ($_ => $hash{$_}) sort keys %hash);
557 Each of the argument lists above comes out of the C<normalize_f>
558 function looking exactly the same, like this:
562 You would tell C<Memoize> to use this normalizer this way:
564 memoize('f', NORMALIZER => 'normalize_f');
566 C<memoize> knows that if the normalized version of the arguments is
567 the same for two argument lists, then it can safely look up the value
568 that it computed for one argument list and return it as the result of
569 calling the function with the other argument list, even if the
570 argument lists look different.
572 The default normalizer just concatenates the arguments with C<$;> in
573 between. This always works correctly for functions with only one
574 string argument, and also when the arguments never contain C<$;>
575 (which is normally character #28, control-\. ) However, it can
576 confuse certain argument lists:
578 normalizer("a\034", "b")
579 normalizer("a", "\034b")
580 normalizer("a\034\034b")
584 Since hash keys are strings, the default normalizer will not
585 distinguish between C<undef> and the empty string. It also won't work
586 when the function's arguments are references. For example, consider
587 a function C<g> which gets two arguments: A number, and a reference to
590 g(13, [1,2,3,4,5,6,7]);
592 The default normalizer will turn this into something like
593 C<"13\024ARRAY(0x436c1f)">. That would be all right, except that a
594 subsequent array of numbers might be stored at a different location
595 even though it contains the same data. If this happens, C<Memoize>
596 will think that the arguments are different, even though they are
597 equivalent. In this case, a normalizer like this is appropriate:
599 sub normalize { join ' ', $_[0], @{$_[1]} }
601 For the example above, this produces the key "13 1 2 3 4 5 6 7".
603 Another use for normalizers is when the function depends on data other
604 than those in its arguments. Suppose you have a function which
605 returns a value which depends on the current hour of the day:
608 my ($problem_type) = @_;
609 my $hour = (localtime)[2];
610 open my $fh, "$DIR/$problem_type" or die...;
618 At 10:23, this function generates the tenth line of a data file; at
619 3:45 PM it generates the 15th line instead. By default, C<Memoize>
620 will only see the $problem_type argument. To fix this, include the
621 current hour in the normalizer:
623 sub normalize { join ' ', (localtime)[2], @_ }
625 The calling context of the function (scalar or list context) is
626 propagated to the normalizer. This means that if the memoized
627 function will treat its arguments differently in list context than it
628 would in scalar context, you can have the normalizer function select
629 its behavior based on the results of C<wantarray>. Even if called in
630 a list context, a normalizer should still return a single string.
632 =head2 C<SCALAR_CACHE>, C<LIST_CACHE>
634 Normally, C<Memoize> caches your function's return values into an
635 ordinary Perl hash variable. However, you might like to have the
636 values cached on the disk, so that they persist from one run of your
637 program to the next, or you might like to associate some other
638 interesting semantics with the cached values.
640 There's a slight complication under the hood of C<Memoize>: There are
641 actually I<two> caches, one for scalar values and one for list values.
642 When your function is called in scalar context, its return value is
643 cached in one hash, and when your function is called in list context,
644 its value is cached in the other hash. You can control the caching
645 behavior of both contexts independently with these options.
647 The argument to C<LIST_CACHE> or C<SCALAR_CACHE> must either be one of
648 the following four strings:
655 or else it must be a reference to a list whose first element is one of
656 these four strings, such as C<[HASH, arguments...]>.
662 C<MEMORY> means that return values from the function will be cached in
663 an ordinary Perl hash variable. The hash variable will not persist
664 after the program exits. This is the default.
668 C<HASH> allows you to specify that a particular hash that you supply
669 will be used as the cache. You can tie this hash beforehand to give
670 it any behavior you want.
672 A tied hash can have any semantics at all. It is typically tied to an
673 on-disk database, so that cached values are stored in the database and
674 retrieved from it again when needed, and the disk file typically
675 persists after your program has exited. See C<perltie> for more
676 complete details about C<tie>.
678 A typical example is:
681 tie my %cache => 'DB_File', $filename, O_RDWR|O_CREAT, 0666;
682 memoize 'function', SCALAR_CACHE => [HASH => \%cache];
684 This has the effect of storing the cache in a C<DB_File> database
685 whose name is in C<$filename>. The cache will persist after the
686 program has exited. Next time the program runs, it will find the
687 cache already populated from the previous run of the program. Or you
688 can forcibly populate the cache by constructing a batch program that
689 runs in the background and populates the cache file. Then when you
690 come to run your real program the memoized function will be fast
691 because all its results have been precomputed.
695 This option is B<strongly deprecated> and will be removed
696 in the B<next> release of C<Memoize>. Use the C<HASH> option instead.
698 memoize ... [TIE, ARGS...]
700 is merely a shortcut for
702 tie my %cache, ARGS...;
703 memoize ... [HASH => \%cache];
708 C<FAULT> means that you never expect to call the function in scalar
709 (or list) context, and that if C<Memoize> detects such a call, it
710 should abort the program. The error message is one of
712 `foo' function called in forbidden list context at line ...
713 `foo' function called in forbidden scalar context at line ...
717 C<MERGE> normally means the function does not distinguish between list
718 and sclar context, and that return values in both contexts should be
719 stored together. C<LIST_CACHE =E<gt> MERGE> means that list context
720 return values should be stored in the same hash that is used for
721 scalar context returns, and C<SCALAR_CACHE =E<gt> MERGE> means the
722 same, mutatis mutandis. It is an error to specify C<MERGE> for both,
723 but it probably does something useful.
725 Consider this function:
729 Normally, the following code will result in two calls to C<pi>:
735 The first call caches the value C<3> in the scalar cache; the second
736 caches the list C<(3)> in the list cache. The third call doesn't call
737 the real C<pi> function; it gets the value from the scalar cache.
739 Obviously, the second call to C<pi> is a waste of time, and storing
740 its return value is a waste of space. Specifying C<LIST_CACHE
741 =E<gt> MERGE> will make C<memoize> use the same cache for scalar and
742 list context return values, so that the second call uses the scalar
743 cache that was populated by the first call. C<pi> ends up being
744 cvalled only once, and both subsequent calls return C<3> from the
745 cache, regardless of the calling context.
747 Another use for C<MERGE> is when you want both kinds of return values
748 stored in the same disk file; this saves you from having to deal with
749 two disk files instead of one. You can use a normalizer function to
750 keep the two sets of return values separate. For example:
752 tie my %cache => 'MLDBM', 'DB_File', $filename, ...;
756 SCALAR_CACHE => [HASH => \%cache],
761 my $context = wantarray() ? 'L' : 'S';
762 # ... now compute the hash key from the arguments ...
763 $hashkey = "$context:$hashkey";
766 This normalizer function will store scalar context return values in
767 the disk file under keys that begin with C<S:>, and list context
768 return values under keys that begin with C<L:>.
772 =head1 OTHER FACILITIES
776 There's an C<unmemoize> function that you can import if you want to.
777 Why would you want to? Here's an example: Suppose you have your cache
778 tied to a DBM file, and you want to make sure that the cache is
779 written out to disk if someone interrupts the program. If the program
780 exits normally, this will happen anyway, but if someone types
781 control-C or something then the program will terminate immediately
782 without synchronizing the database. So what you can do instead is
784 $SIG{INT} = sub { unmemoize 'function' };
786 Thanks to Jonathan Roy for discovering a use for C<unmemoize>.
788 C<unmemoize> accepts a reference to, or the name of a previously
789 memoized function, and undoes whatever it did to provide the memoized
790 version in the first place, including making the name refer to the
791 unmemoized version if appropriate. It returns a reference to the
792 unmemoized version of the function.
794 If you ask it to unmemoize a function that was never memoized, it
797 =head2 C<flush_cache>
799 C<flush_cache(function)> will flush out the caches, discarding I<all>
800 the cached data. The argument may be a funciton name or a reference
801 to a function. For finer control over when data is discarded or
802 expired, see the documentation for C<Memoize::Expire>, included in
805 Note that if the cache is a tied hash, C<flush_cache> will attempt to
806 invoke the C<CLEAR> method on the hash. If there is no C<CLEAR>
807 method, this will cause a run-time error.
809 An alternative approach to cache flushing is to use the C<HASH> option
810 (see above) to request that C<Memoize> use a particular hash variable
811 as its cache. Then you can examine or modify the hash at any time in
816 Memoization is not a cure-all:
822 Do not memoize a function whose behavior depends on program
823 state other than its own arguments, such as global variables, the time
824 of day, or file input. These functions will not produce correct
825 results when memoized. For a particularly easy example:
831 This function takes no arguments, and as far as C<Memoize> is
832 concerned, it always returns the same result. C<Memoize> is wrong, of
833 course, and the memoized version of this function will call C<time> once
834 to get the current time, and it will return that same time
835 every time you call it after that.
839 Do not memoize a function with side effects.
844 print "$a + $b = $s.\n";
847 This function accepts two arguments, adds them, and prints their sum.
848 Its return value is the numuber of characters it printed, but you
849 probably didn't care about that. But C<Memoize> doesn't understand
850 that. If you memoize this function, you will get the result you
851 expect the first time you ask it to print the sum of 2 and 3, but
852 subsequent calls will return 1 (the return value of
853 C<print>) without actually printing anything.
857 Do not memoize a function that returns a data structure that is
858 modified by its caller.
860 Consider these functions: C<getusers> returns a list of users somehow,
861 and then C<main> throws away the first user on the list and prints the
865 my $userlist = getusers();
867 foreach $u (@$userlist) {
874 # Do something to get a list of users;
875 \@users; # Return reference to list.
878 If you memoize C<getusers> here, it will work right exactly once. The
879 reference to the users list will be stored in the memo table. C<main>
880 will discard the first element from the referenced list. The next
881 time you invoke C<main>, C<Memoize> will not call C<getusers>; it will
882 just return the same reference to the same list it got last time. But
883 this time the list has already had its head removed; C<main> will
884 erroneously remove another element from it. The list will get shorter
885 and shorter every time you call C<main>.
893 will modify $u2 as well as $u1, because both variables are references
894 to the same array. Had C<getusers> not been memoized, $u1 and $u2
895 would have referred to different arrays.
899 Do not memoize a very simple function.
901 Recently someone mentioned to me that the Memoize module made his
902 program run slower instead of faster. It turned out that he was
903 memoizing the following function:
909 I pointed out that C<Memoize> uses a hash, and that looking up a
910 number in the hash is necessarily going to take a lot longer than a
911 single multiplication. There really is no way to speed up the
914 Memoization is not magical.
918 =head1 PERSISTENT CACHE SUPPORT
920 You can tie the cache tables to any sort of tied hash that you want
921 to, as long as it supports C<TIEHASH>, C<FETCH>, C<STORE>, and
922 C<EXISTS>. For example,
924 tie my %cache => 'GDBM_File', $filename, O_RDWR|O_CREAT, 0666;
925 memoize 'function', SCALAR_CACHE => [HASH => \%cache];
927 works just fine. For some storage methods, you need a little glue.
929 C<SDBM_File> doesn't supply an C<EXISTS> method, so included in this
930 package is a glue module called C<Memoize::SDBM_File> which does
931 provide one. Use this instead of plain C<SDBM_File> to store your
932 cache table on disk in an C<SDBM_File> database:
934 tie my %cache => 'Memoize::SDBM_File', $filename, O_RDWR|O_CREAT, 0666;
935 memoize 'function', SCALAR_CACHE => [HASH => \%cache];
937 C<NDBM_File> has the same problem and the same solution. (Use
938 C<Memoize::NDBM_File instead of plain NDBM_File.>)
940 C<Storable> isn't a tied hash class at all. You can use it to store a
941 hash to disk and retrieve it again, but you can't modify the hash while
942 it's on the disk. So if you want to store your cache table in a
943 C<Storable> database, use C<Memoize::Storable>, which puts a hashlike
944 front-end onto C<Storable>. The hash table is actually kept in
945 memory, and is loaded from your C<Storable> file at the time you
946 memoize the function, and stored back at the time you unmemoize the
947 function (or when your program exits):
949 tie my %cache => 'Memoize::Storable', $filename;
950 memoize 'function', SCALAR_CACHE => [HASH => \%cache];
952 tie my %cache => 'Memoize::Storable', $filename, 'nstore';
953 memoize 'function', SCALAR_CACHE => [HASH => \%cache];
955 Include the `nstore' option to have the C<Storable> database written
956 in `network order'. (See L<Storable> for more details about this.)
958 =head1 EXPIRATION SUPPORT
960 See Memoize::Expire, which is a plug-in module that adds expiration
961 functionality to Memoize. If you don't like the kinds of policies
962 that Memoize::Expire implements, it is easy to write your own plug-in
963 module to implement whatever policy you desire. Memoize comes with
964 several examples. An expiration manager that implements a LRU policy
965 is available on CPAN as Memoize::ExpireLRU.
969 The test suite is much better, but always needs improvement.
971 There used to be some problem with the way C<goto &f> works under
972 threaded Perl, because of the lexical scoping of C<@_>. This is a bug
973 in Perl, and until it is resolved, Memoize won't work with these
974 Perls. This is probably still the case, although I have not been able
975 to try it out. If you encounter this problem, you can fix it by
976 chopping the source code a little. Find the comment in the source
977 code that says C<--- THREADED PERL COMMENT---> and comment out the
978 active line and uncomment the commented one. Then try it again.
980 Here's a bug that isn't my fault: Some versions of C<DB_File> won't
981 let you store data under a key of length 0. That means that if you
982 have a function C<f> which you memoized and the cache is in a
983 C<DB_File> database, then the value of C<f()> (C<f> called with no
984 arguments) will not be memoized. Let us all breathe deeply and repeat
985 this mantra: ``Gosh, Keith, that sure was a stupid thing to do.''
989 To join a very low-traffic mailing list for announcements about
990 C<Memoize>, send an empty note to C<mjd-perl-memoize-request@plover.com>.
994 Mark-Jason Dominus (C<mjd-perl-memoize+@plover.com>), Plover Systems co.
996 See the C<Memoize.pm> Page at http://www.plover.com/~mjd/perl/Memoize/
997 for news and upgrades. Near this page, at
998 http://www.plover.com/~mjd/perl/MiniMemoize/ there is an article about
999 memoization and about the internals of Memoize that appeared in The
1000 Perl Journal, issue #13. (This article is also included in the
1001 Memoize distribution as `article.html'.)
1003 To join a mailing list for announcements about C<Memoize>, send an
1004 empty message to C<mjd-perl-memoize-request@plover.com>. This mailing
1005 list is for announcements only and has extremely low traffic---about
1006 four messages per year.
1008 =head1 COPYRIGHT AND LICENSE
1010 Copyright 1998, 1999, 2000, 2001 by Mark Jason Dominus
1012 This library is free software; you may redistribute it and/or modify
1013 it under the same terms as Perl itself.
1017 Many thanks to Jonathan Roy for bug reports and suggestions, to
1018 Michael Schwern for other bug reports and patches, to Mike Cariaso for
1019 helping me to figure out the Right Thing to Do About Expiration, to
1020 Joshua Gerth, Joshua Chamas, Jonathan Roy, Mark D. Anderson, and
1021 Andrew Johnson for more suggestions about expiration, to Brent Powers
1022 for the Memoize::ExpireLRU module, to Ariel Scolnicov for delightful
1023 messages about the Fibonacci function, to Dion Almaer for
1024 thought-provoking suggestions about the default normalizer, to Walt
1025 Mankowski and Kurt Starsinic for much help investigating problems
1026 under threaded Perl, to Alex Dudkevich for reporting the bug in
1027 prototyped functions and for checking my patch, to Tony Bass for many
1028 helpful suggestions, to Philippe Verdret for enlightening discussion
1029 of Hook::PrePostCall, to Nat Torkington for advice I ignored, to Chris
1030 Nandor for portability advice, to Randal Schwartz for suggesting the
1031 'C<flush_cache> function, and to Jenda Krynicky for being a light in
1034 Special thanks to Jarkko Hietaniemi, the 5.8.0 pumpking, for including
1035 this module in the core and for his patient and helpful guidance
1036 during the integration process.