Commit | Line | Data |
a0cb3900 |
1 | # -*- mode: perl; perl-indent-level: 2; -*- |
2 | # Memoize.pm |
3 | # |
4 | # Transparent memoization of idempotent functions |
5 | # |
6 | # Copyright 1998, 1999 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. |
10 | # |
11 | # Version 0.64 beta $Revision: 1.17 $ $Date: 2000/10/24 04:33:49 $ |
12 | |
13 | package Memoize; |
14 | $VERSION = '0.64'; |
15 | |
16 | # Compile-time constants |
17 | sub SCALAR () { 0 } |
18 | sub LIST () { 1 } |
19 | |
20 | |
21 | # |
22 | # Usage memoize(functionname/ref, |
23 | # { NORMALIZER => coderef, INSTALL => name, |
24 | # LIST_CACHE => descriptor, SCALAR_CACHE => descriptor } |
25 | # |
26 | |
27 | use Carp; |
28 | use Exporter; |
29 | use vars qw($DEBUG); |
30 | @ISA = qw(Exporter); |
31 | @EXPORT = qw(memoize); |
32 | @EXPORT_OK = qw(unmemoize flush_cache); |
33 | use strict; |
34 | |
35 | my %memotable; |
36 | my %revmemotable; |
37 | my @CONTEXT_TAGS = qw(MERGE TIE MEMORY FAULT HASH); |
38 | my %IS_CACHE_TAG = map {($_ => 1)} @CONTEXT_TAGS; |
39 | |
40 | # Raise an error if the user tries to specify one of thesepackage as a |
41 | # tie for LIST_CACHE |
42 | |
43 | my %scalar_only = map {($_ => 1)} qw(DB_File GDBM_File SDBM_File ODBM_File NDBM_File); |
44 | |
45 | sub memoize { |
46 | my $fn = shift; |
47 | my %options = @_; |
48 | my $options = \%options; |
49 | |
50 | unless (defined($fn) && |
51 | (ref $fn eq 'CODE' || ref $fn eq '')) { |
52 | croak "Usage: memoize 'functionname'|coderef {OPTIONS}"; |
53 | } |
54 | |
55 | my $uppack = caller; # TCL me Elmo! |
56 | my $cref; # Code reference to original function |
57 | my $name = (ref $fn ? undef : $fn); |
58 | |
59 | # Convert function names to code references |
60 | $cref = &_make_cref($fn, $uppack); |
61 | |
62 | # Locate function prototype, if any |
63 | my $proto = prototype $cref; |
64 | if (defined $proto) { $proto = "($proto)" } |
65 | else { $proto = "" } |
66 | |
67 | # Goto considered harmful! Hee hee hee. |
68 | my $wrapper = eval "sub $proto { unshift \@_, qq{$cref}; goto &_memoizer; }"; |
69 | # Actually I would like to get rid of the eval, but there seems not |
70 | # to be any other way to set the prototype properly. |
71 | |
72 | # --- THREADED PERL COMMENT --- |
73 | # The above line might not work under threaded perl because goto & |
74 | # semantics are broken. If that's the case, try the following instead: |
75 | # my $wrapper = eval "sub { &_memoizer(qq{$cref}, \@_); }"; |
76 | # Confirmed 1998-12-27 this does work. |
77 | # 1998-12-29: Sarathy says this bug is fixed in 5.005_54. |
78 | # However, the module still fails, although the sample test program doesn't. |
79 | |
80 | my $normalizer = $options{NORMALIZER}; |
81 | if (defined $normalizer && ! ref $normalizer) { |
82 | $normalizer = _make_cref($normalizer, $uppack); |
83 | } |
84 | |
85 | my $install_name; |
86 | if (defined $options->{INSTALL}) { |
87 | # INSTALL => name |
88 | $install_name = $options->{INSTALL}; |
89 | } elsif (! exists $options->{INSTALL}) { |
90 | # No INSTALL option provided; use original name if possible |
91 | $install_name = $name; |
92 | } else { |
93 | # INSTALL => undef means don't install |
94 | } |
95 | |
96 | if (defined $install_name) { |
97 | $install_name = $uppack . '::' . $install_name |
98 | unless $install_name =~ /::/; |
99 | no strict; |
100 | local($^W) = 0; # ``Subroutine $install_name redefined at ...'' |
101 | *{$install_name} = $wrapper; # Install memoized version |
102 | } |
103 | |
104 | $revmemotable{$wrapper} = "" . $cref; # Turn code ref into hash key |
105 | |
106 | # These will be the caches |
107 | my %caches; |
108 | for my $context (qw(SCALAR LIST)) { |
109 | # suppress subsequent 'uninitialized value' warnings |
110 | $options{"${context}_CACHE"} ||= ''; |
111 | |
112 | my $cache_opt = $options{"${context}_CACHE"}; |
113 | my @cache_opt_args; |
114 | if (ref $cache_opt) { |
115 | @cache_opt_args = @$cache_opt; |
116 | $cache_opt = shift @cache_opt_args; |
117 | } |
118 | if ($cache_opt eq 'FAULT') { # no cache |
119 | $caches{$context} = undef; |
120 | } elsif ($cache_opt eq 'HASH') { # user-supplied hash |
121 | $caches{$context} = $cache_opt_args[0]; |
122 | } elsif ($cache_opt eq '' || $IS_CACHE_TAG{$cache_opt}) { |
123 | # default is that we make up an in-memory hash |
124 | $caches{$context} = {}; |
125 | # (this might get tied later, or MERGEd away) |
126 | } else { |
127 | croak "Unrecognized option to `${context}_CACHE': `$cache_opt' should be one of (@CONTEXT_TAGS); aborting"; |
128 | } |
129 | } |
130 | |
131 | # Perhaps I should check here that you didn't supply *both* merge |
132 | # options. But if you did, it does do something reasonable: They |
133 | # both get merged to the same in-memory hash. |
134 | if ($options{SCALAR_CACHE} eq 'MERGE') { |
135 | $caches{SCALAR} = $caches{LIST}; |
136 | } elsif ($options{LIST_CACHE} eq 'MERGE') { |
137 | $caches{LIST} = $caches{SCALAR}; |
138 | } |
139 | |
140 | # Now deal with the TIE options |
141 | { |
142 | my $context; |
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 |
146 | } |
147 | } |
148 | |
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! |
152 | $memotable{$cref} = |
153 | { |
154 | O => $options, # Short keys here for things we need to access frequently |
155 | N => $normalizer, |
156 | U => $cref, |
157 | MEMOIZED => $wrapper, |
158 | PACKAGE => $uppack, |
159 | NAME => $install_name, |
160 | S => $caches{SCALAR}, |
161 | L => $caches{LIST}, |
162 | }; |
163 | |
164 | $wrapper # Return just memoized version |
165 | } |
166 | |
167 | # This function tries to load a tied hash class and tie the hash to it. |
168 | sub _my_tie { |
169 | my ($context, $hash, $options) = @_; |
170 | my $fullopt = $options->{"${context}_CACHE"}; |
171 | |
172 | # We already checked to make sure that this works. |
173 | my $shortopt = (ref $fullopt) ? $fullopt->[0] : $fullopt; |
174 | |
175 | return unless defined $shortopt && $shortopt eq 'TIE'; |
176 | |
177 | my @args = ref $fullopt ? @$fullopt : (); |
178 | shift @args; |
179 | my $module = shift @args; |
180 | if ($context eq 'LIST' && $scalar_only{$module}) { |
181 | croak("You can't use $module for LIST_CACHE because it can only store scalars"); |
182 | } |
183 | my $modulefile = $module . '.pm'; |
184 | $modulefile =~ s{::}{/}g; |
185 | eval { require $modulefile }; |
186 | if ($@) { |
187 | croak "Memoize: Couldn't load hash tie module `$module': $@; aborting"; |
188 | } |
189 | # eval { import $module }; |
190 | # if ($@) { |
191 | # croak "Memoize: Couldn't import hash tie module `$module': $@; aborting"; |
192 | # } |
193 | # eval "use $module ()"; |
194 | # if ($@) { |
195 | # croak "Memoize: Couldn't use hash tie module `$module': $@; aborting"; |
196 | # } |
197 | my $rc = (tie %$hash => $module, @args); |
198 | unless ($rc) { |
199 | croak "Memoize: Couldn't tie hash to `$module': $@; aborting"; |
200 | } |
201 | 1; |
202 | } |
203 | |
204 | sub flush_cache { |
205 | my $func = _make_cref($_[0], scalar caller); |
206 | my $info = $memotable{$revmemotable{$func}}; |
207 | die "$func not memoized" unless defined $info; |
208 | for my $context (qw(S L)) { |
209 | my $cache = $info->{$context}; |
210 | if (tied %$cache && ! (tied %$cache)->can('CLEAR')) { |
211 | my $funcname = defined($info->{NAME}) ? |
212 | "function $info->{NAME}" : "anonymous function $func"; |
213 | my $context = {S => 'scalar', L => 'list'}->{$context}; |
214 | croak "Tied cache hash for $context-context $funcname does not support flushing"; |
215 | } else { |
216 | %$cache = (); |
217 | } |
218 | } |
219 | } |
220 | |
221 | # This is the function that manages the memo tables. |
222 | sub _memoizer { |
223 | my $orig = shift; # stringized version of ref to original func. |
224 | my $info = $memotable{$orig}; |
225 | my $normalizer = $info->{N}; |
226 | |
227 | my $argstr; |
228 | my $context = (wantarray() ? LIST : SCALAR); |
229 | |
230 | if (defined $normalizer) { |
231 | no strict; |
232 | if ($context == SCALAR) { |
233 | $argstr = &{$normalizer}(@_); |
234 | } elsif ($context == LIST) { |
235 | ($argstr) = &{$normalizer}(@_); |
236 | } else { |
237 | croak "Internal error \#41; context was neither LIST nor SCALAR\n"; |
238 | } |
239 | } else { # Default normalizer |
240 | $argstr = join $;,@_; # $;,@_;? Perl is great. |
241 | } |
242 | |
243 | if ($context == SCALAR) { |
244 | my $cache = $info->{S}; |
245 | _crap_out($info->{NAME}, 'scalar') unless defined $cache; |
246 | if (exists $cache->{$argstr}) { |
247 | return $cache->{$argstr}; |
248 | } else { |
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]; |
253 | } else { |
254 | $cache->{$argstr} = $val; |
255 | } |
256 | $val; |
257 | } |
258 | } elsif ($context == LIST) { |
259 | my $cache = $info->{L}; |
260 | _crap_out($info->{NAME}, 'list') unless defined $cache; |
261 | if (exists $cache->{$argstr}) { |
262 | my $val = $cache->{$argstr}; |
263 | return ($val) unless ref $val eq 'ARRAY'; |
264 | # An array ref is ambiguous. Did the function really return |
265 | # an array ref? Or did we cache a list-context list return in |
266 | # an anonymous array? |
267 | # If LISTCONTEXT=>MERGE, then the function never returns lists, |
268 | # so we know for sure: |
269 | return ($val) if $info->{O}{LIST_CACHE} eq 'MERGE'; |
270 | # Otherwise, we're doomed. ###BUG |
271 | return @$val; |
272 | } else { |
273 | my $q = $cache->{$argstr} = [&{$info->{U}}(@_)]; |
274 | @$q; |
275 | } |
276 | } else { |
277 | croak "Internal error \#42; context was neither LIST nor SCALAR\n"; |
278 | } |
279 | } |
280 | |
281 | sub unmemoize { |
282 | my $f = shift; |
283 | my $uppack = caller; |
284 | my $cref = _make_cref($f, $uppack); |
285 | |
286 | unless (exists $revmemotable{$cref}) { |
287 | croak "Could not unmemoize function `$f', because it was not memoized to begin with"; |
288 | } |
289 | |
290 | my $tabent = $memotable{$revmemotable{$cref}}; |
291 | unless (defined $tabent) { |
292 | croak "Could not figure out how to unmemoize function `$f'"; |
293 | } |
294 | my $name = $tabent->{NAME}; |
295 | if (defined $name) { |
296 | no strict; |
297 | local($^W) = 0; # ``Subroutine $install_name redefined at ...'' |
298 | *{$name} = $tabent->{U}; # Replace with original function |
299 | } |
300 | undef $memotable{$revmemotable{$cref}}; |
301 | undef $revmemotable{$cref}; |
302 | |
303 | # This removes the last reference to the (possibly tied) memo tables |
304 | # my ($old_function, $memotabs) = @{$tabent}{'U','S','L'}; |
305 | # undef $tabent; |
306 | |
307 | # # Untie the memo tables if they were tied. |
308 | # my $i; |
309 | # for $i (0,1) { |
310 | # if (tied %{$memotabs->[$i]}) { |
311 | # warn "Untying hash #$i\n"; |
312 | # untie %{$memotabs->[$i]}; |
313 | # } |
314 | # } |
315 | |
316 | $tabent->{U}; |
317 | } |
318 | |
319 | sub _make_cref { |
320 | my $fn = shift; |
321 | my $uppack = shift; |
322 | my $cref; |
323 | my $name; |
324 | |
325 | if (ref $fn eq 'CODE') { |
326 | $cref = $fn; |
327 | } elsif (! ref $fn) { |
328 | if ($fn =~ /::/) { |
329 | $name = $fn; |
330 | } else { |
331 | $name = $uppack . '::' . $fn; |
332 | } |
333 | no strict; |
334 | if (defined $name and !defined(&$name)) { |
335 | croak "Cannot operate on nonexistent function `$fn'"; |
336 | } |
337 | # $cref = \&$name; |
338 | $cref = *{$name}{CODE}; |
339 | } else { |
340 | my $parent = (caller(1))[3]; # Function that called _make_cref |
341 | croak "Usage: argument 1 to `$parent' must be a function name or reference.\n"; |
342 | } |
343 | $DEBUG and warn "${name}($fn) => $cref in _make_cref\n"; |
344 | $cref; |
345 | } |
346 | |
347 | sub _crap_out { |
348 | my ($funcname, $context) = @_; |
349 | if (defined $funcname) { |
350 | croak "Function `$funcname' called in forbidden $context context; faulting"; |
351 | } else { |
352 | croak "Anonymous function called in forbidden $context context; faulting"; |
353 | } |
354 | } |
355 | |
356 | 1; |
357 | |
358 | |
359 | |
360 | |
361 | |
362 | =head1 NAME |
363 | |
364 | Memoize - Make your functions faster by trading space for time |
365 | |
366 | =head1 SYNOPSIS |
367 | |
368 | use Memoize; |
369 | memoize('slow_function'); |
370 | slow_function(arguments); # Is faster than it was before |
371 | |
372 | |
373 | This is normally all you need to know. However, many options are available: |
374 | |
375 | memoize(function, options...); |
376 | |
377 | Options include: |
378 | |
379 | NORMALIZER => function |
380 | INSTALL => new_name |
381 | |
382 | SCALAR_CACHE => 'MEMORY' |
383 | SCALAR_CACHE => ['HASH', \%cache_hash ] |
384 | SCALAR_CACHE => 'FAULT' |
385 | SCALAR_CACHE => 'MERGE' |
386 | |
387 | LIST_CACHE => 'MEMORY' |
388 | LIST_CACHE => ['HASH', \%cache_hash ] |
389 | LIST_CACHE => 'FAULT' |
390 | LIST_CACHE => 'MERGE' |
391 | |
392 | =head1 DESCRIPTION |
393 | |
394 | `Memoizing' a function makes it faster by trading space for time. It |
395 | does this by caching the return values of the function in a table. |
396 | If you call the function again with the same arguments, C<memoize> |
397 | jmups in and gives you the value out of the table, instead of letting |
398 | the function compute the value all over again. |
399 | |
400 | Here is an extreme example. Consider the Fibonacci sequence, defined |
401 | by the following function: |
402 | |
403 | # Compute Fibonacci numbers |
404 | sub fib { |
405 | my $n = shift; |
406 | return $n if $n < 2; |
407 | fib($n-1) + fib($n-2); |
408 | } |
409 | |
410 | This function is very slow. Why? To compute fib(14), it first wants |
411 | to compute fib(13) and fib(12), and add the results. But to compute |
412 | fib(13), it first has to compute fib(12) and fib(11), and then it |
413 | comes back and computes fib(12) all over again even though the answer |
414 | is the same. And both of the times that it wants to compute fib(12), |
415 | it has to compute fib(11) from scratch, and then it has to do it |
416 | again each time it wants to compute fib(13). This function does so |
417 | much recomputing of old results that it takes a really long time to |
418 | run---fib(14) makes 1,200 extra recursive calls to itself, to compute |
419 | and recompute things that it already computed. |
420 | |
421 | This function is a good candidate for memoization. If you memoize the |
422 | `fib' function above, it will compute fib(14) exactly once, the first |
423 | time it needs to, and then save the result in a table. Then if you |
424 | ask for fib(14) again, it gives you the result out of the table. |
425 | While computing fib(14), instead of computing fib(12) twice, it does |
426 | it once; the second time it needs the value it gets it from the table. |
427 | It doesn't compute fib(11) four times; it computes it once, getting it |
428 | from the table the next three times. Instead of making 1,200 |
429 | recursive calls to `fib', it makes 15. This makes the function about |
430 | 150 times faster. |
431 | |
432 | You could do the memoization yourself, by rewriting the function, like |
433 | this: |
434 | |
435 | # Compute Fibonacci numbers, memoized version |
436 | { my @fib; |
437 | sub fib { |
438 | my $n = shift; |
439 | return $fib[$n] if defined $fib[$n]; |
440 | return $fib[$n] = $n if $n < 2; |
441 | $fib[$n] = fib($n-1) + fib($n-2); |
442 | } |
443 | } |
444 | |
445 | Or you could use this module, like this: |
446 | |
447 | use Memoize; |
448 | memoize('fib'); |
449 | |
450 | # Rest of the fib function just like the original version. |
451 | |
452 | This makes it easy to turn memoizing on and off. |
453 | |
454 | Here's an even simpler example: I wrote a simple ray tracer; the |
455 | program would look in a certain direction, figure out what it was |
456 | looking at, and then convert the `color' value (typically a string |
457 | like `red') of that object to a red, green, and blue pixel value, like |
458 | this: |
459 | |
460 | for ($direction = 0; $direction < 300; $direction++) { |
461 | # Figure out which object is in direction $direction |
462 | $color = $object->{color}; |
463 | ($r, $g, $b) = @{&ColorToRGB($color)}; |
464 | ... |
465 | } |
466 | |
467 | Since there are relatively few objects in a picture, there are only a |
468 | few colors, which get looked up over and over again. Memoizing |
469 | C<ColorToRGB> speeded up the program by several percent. |
470 | |
471 | =head1 DETAILS |
472 | |
473 | This module exports exactly one function, C<memoize>. The rest of the |
474 | functions in this package are None of Your Business. |
475 | |
476 | You should say |
477 | |
478 | memoize(function) |
479 | |
480 | where C<function> is the name of the function you want to memoize, or |
481 | a reference to it. C<memoize> returns a reference to the new, |
482 | memoized version of the function, or C<undef> on a non-fatal error. |
483 | At present, there are no non-fatal errors, but there might be some in |
484 | the future. |
485 | |
486 | If C<function> was the name of a function, then C<memoize> hides the |
487 | old version and installs the new memoized version under the old name, |
488 | so that C<&function(...)> actually invokes the memoized version. |
489 | |
490 | =head1 OPTIONS |
491 | |
492 | There are some optional options you can pass to C<memoize> to change |
493 | the way it behaves a little. To supply options, invoke C<memoize> |
494 | like this: |
495 | |
496 | memoize(function, NORMALIZER => function, |
497 | INSTALL => newname, |
498 | SCALAR_CACHE => option, |
499 | LIST_CACHE => option |
500 | ); |
501 | |
502 | Each of these options is optional; you can include some, all, or none |
503 | of them. |
504 | |
505 | =head2 INSTALL |
506 | |
507 | If you supply a function name with C<INSTALL>, memoize will install |
508 | the new, memoized version of the function under the name you give. |
509 | For example, |
510 | |
511 | memoize('fib', INSTALL => 'fastfib') |
512 | |
513 | installs the memoized version of C<fib> as C<fastfib>; without the |
514 | C<INSTALL> option it would have replaced the old C<fib> with the |
515 | memoized version. |
516 | |
517 | To prevent C<memoize> from installing the memoized version anywhere, use |
518 | C<INSTALL =E<gt> undef>. |
519 | |
520 | =head2 NORMALIZER |
521 | |
522 | Suppose your function looks like this: |
523 | |
524 | # Typical call: f('aha!', A => 11, B => 12); |
525 | sub f { |
526 | my $a = shift; |
527 | my %hash = @_; |
528 | $hash{B} ||= 2; # B defaults to 2 |
529 | $hash{C} ||= 7; # C defaults to 7 |
530 | |
531 | # Do something with $a, %hash |
532 | } |
533 | |
534 | Now, the following calls to your function are all completely equivalent: |
535 | |
536 | f(OUCH); |
537 | f(OUCH, B => 2); |
538 | f(OUCH, C => 7); |
539 | f(OUCH, B => 2, C => 7); |
540 | f(OUCH, C => 7, B => 2); |
541 | (etc.) |
542 | |
543 | However, unless you tell C<Memoize> that these calls are equivalent, |
544 | it will not know that, and it will compute the values for these |
545 | invocations of your function separately, and store them separately. |
546 | |
547 | To prevent this, supply a C<NORMALIZER> function that turns the |
548 | program arguments into a string in a way that equivalent arguments |
549 | turn into the same string. A C<NORMALIZER> function for C<f> above |
550 | might look like this: |
551 | |
552 | sub normalize_f { |
553 | my $a = shift; |
554 | my %hash = @_; |
555 | $hash{B} ||= 2; |
556 | $hash{C} ||= 7; |
557 | |
558 | join($;, $a, map ($_ => $hash{$_}) sort keys %hash); |
559 | } |
560 | |
561 | Each of the argument lists above comes out of the C<normalize_f> |
562 | function looking exactly the same, like this: |
563 | |
564 | OUCH^\B^\2^\C^\7 |
565 | |
566 | You would tell C<Memoize> to use this normalizer this way: |
567 | |
568 | memoize('f', NORMALIZER => 'normalize_f'); |
569 | |
570 | C<memoize> knows that if the normalized version of the arguments is |
571 | the same for two argument lists, then it can safely look up the value |
572 | that it computed for one argument list and return it as the result of |
573 | calling the function with the other argument list, even if the |
574 | argument lists look different. |
575 | |
576 | The default normalizer just concatenates the arguments with C<$;> in |
577 | between. This always works correctly for functions with only one |
578 | argument, and also when the arguments never contain C<$;> (which is |
579 | normally character #28, control-\. ) However, it can confuse certain |
580 | argument lists: |
581 | |
582 | normalizer("a\034", "b") |
583 | normalizer("a", "\034b") |
584 | normalizer("a\034\034b") |
585 | |
586 | for example. |
587 | |
588 | The default normalizer also won't work when the function's arguments |
589 | are references. For exampple, consider a function C<g> which gets two |
590 | arguments: A number, and a reference to an array of numbers: |
591 | |
592 | g(13, [1,2,3,4,5,6,7]); |
593 | |
594 | The default normalizer will turn this into something like |
595 | C<"13\024ARRAY(0x436c1f)">. That would be all right, except that a |
596 | subsequent array of numbers might be stored at a different location |
597 | even though it contains the same data. If this happens, C<Memoize> |
598 | will think that the arguments are different, even though they are |
599 | equivalent. In this case, a normalizer like this is appropriate: |
600 | |
601 | sub normalize { join ' ', $_[0], @{$_[1]} } |
602 | |
603 | For the example above, this produces the key "13 1 2 3 4 5 6 7". |
604 | |
605 | Another use for normalizers is when the function depends on data other |
606 | than those in its arguments. Suppose you have a function which |
607 | returns a value which depends on the current hour of the day: |
608 | |
609 | sub on_duty { |
610 | my ($problem_type) = @_; |
611 | my $hour = (localtime)[2]; |
612 | open my $fh, "$DIR/$problem_type" or die...; |
613 | my $line; |
614 | while ($hour-- > 0) |
615 | $line = <$fh>; |
616 | } |
617 | return $line; |
618 | } |
619 | |
620 | At 10:23, this function generates the tenth line of a data file; at |
621 | 3:45 PM it generates the 15th line instead. By default, C<Memoize> |
622 | will only see the $problem_type argument. To fix this, include the |
623 | current hour in the normalizer: |
624 | |
625 | sub normalize { join ' ', (localtime)[2], @_ } |
626 | |
627 | The calling context of the function (scalar or list context) is |
628 | propagated to the normalizer. This means that if the memoized |
629 | function will treat its arguments differently in list context than it |
630 | would in scalar context, you can have the normalizer function select |
631 | its behavior based on the results of C<wantarray>. Even if called in |
632 | a list context, a normalizer should still return a single string. |
633 | |
634 | =head2 C<SCALAR_CACHE>, C<LIST_CACHE> |
635 | |
636 | Normally, C<Memoize> caches your function's return values into an |
637 | ordinary Perl hash variable. However, you might like to have the |
638 | values cached on the disk, so that they persist from one run of your |
639 | program to the next, or you might like to associate some other |
640 | interesting semantics with the cached values. |
641 | |
642 | There's a slight complication under the hood of C<Memoize>: There are |
643 | actually I<two> caches, one for scalar values and one for list values. |
644 | When your function is called in scalar context, its return value is |
645 | cached in one hash, and when your function is called in list context, |
646 | its value is cached in the other hash. You can control the caching |
647 | behavior of both contexts independently with these options. |
648 | |
649 | The argument to C<LIST_CACHE> or C<SCALAR_CACHE> must either be one of |
650 | the following four strings: |
651 | |
652 | MEMORY |
653 | FAULT |
654 | MERGE |
655 | HASH |
656 | |
657 | or else it must be a reference to a list whose first element is one of |
658 | these four strings, such as C<[HASH, arguments...]>. |
659 | |
660 | =over 4 |
661 | |
662 | =item C<MEMORY> |
663 | |
664 | C<MEMORY> means that return values from the function will be cached in |
665 | an ordinary Perl hash variable. The hash variable will not persist |
666 | after the program exits. This is the default. |
667 | |
668 | =item C<HASH> |
669 | |
670 | C<HASH> allows you to specify that a particular hash that you supply |
671 | will be used as the cache. You can tie this hash beforehand to give |
672 | it any behavior you want. |
673 | |
674 | A tied hash can have any semantics at all. It is typically tied to an |
675 | on-disk database, so that cached values are stored in the database and |
676 | retrieved from it again when needed, and the disk file typically |
677 | persists after your program has exited. See C<perltie> for more |
678 | complete details about C<tie>. |
679 | |
680 | A typical example is: |
681 | |
682 | use DB_File; |
683 | tie my %cache => 'DB_File', $filename, O_RDWR|O_CREAT, 0666; |
684 | memoize 'function', SCALAR_CACHE => [HASH => \%cache]; |
685 | |
686 | This has the effect of storing the cache in a C<DB_File> database |
687 | whose name is in C<$filename>. The cache will persist after the |
688 | program has exited. Next time the program runs, it will find the |
689 | cache already populated from the previous run of the program. Or you |
690 | can forcibly populate the cache by constructing a batch program that |
691 | runs in the background and populates the cache file. Then when you |
692 | come to run your real program the memoized function will be fast |
693 | because all its results have been precomputed. |
694 | |
695 | =item C<TIE> |
696 | |
697 | This option is B<strongly deprecated> and will be removed |
698 | in the B<next> version of C<Memoize>. Use the C<HASH> option instead. |
699 | |
700 | memoize ... [TIE, ARGS...] |
701 | |
702 | is merely a shortcut for |
703 | |
704 | tie my %cache, ARGS...; |
705 | memoize ... [HASH => \%cache]; |
706 | |
707 | |
708 | =item C<FAULT> |
709 | |
710 | C<FAULT> means that you never expect to call the function in scalar |
711 | (or list) context, and that if C<Memoize> detects such a call, it |
712 | should abort the program. The error message is one of |
713 | |
714 | `foo' function called in forbidden list context at line ... |
715 | `foo' function called in forbidden scalar context at line ... |
716 | |
717 | =item C<MERGE> |
718 | |
719 | C<MERGE> normally means the function does not distinguish between list |
720 | and sclar context, and that return values in both contexts should be |
721 | stored together. C<LIST_CACHE =E<gt> MERGE> means that list context |
722 | return values should be stored in the same hash that is used for |
723 | scalar context returns, and C<SCALAR_CACHE =E<gt> MERGE> means the |
724 | same, mutatis mutandis. It is an error to specify C<MERGE> for both, |
725 | but it probably does something useful. |
726 | |
727 | Consider this function: |
728 | |
729 | sub pi { 3; } |
730 | |
731 | Normally, the following code will result in two calls to C<pi>: |
732 | |
733 | $x = pi(); |
734 | ($y) = pi(); |
735 | $z = pi(); |
736 | |
737 | The first call caches the value C<3> in the scalar cache; the second |
738 | caches the list C<(3)> in the list cache. The third call doesn't call |
739 | the real C<pi> function; it gets the value from the scalar cache. |
740 | |
741 | Obviously, the second call to C<pi> is a waste of time, and storing |
742 | its return value is a waste of space. Specifying C<LIST_CACHE |
743 | =E<gt> MERGE> will make C<memoize> use the same cache for scalar and |
744 | list context return values, so that the second call uses the scalar |
745 | cache that was populated by the first call. C<pi> ends up being |
746 | cvalled only once, and both subsequent calls return C<3> from the |
747 | cache, regardless of the calling context. |
748 | |
749 | Another use for C<MERGE> is when you want both kinds of return values |
750 | stored in the same disk file; this saves you from having to deal with |
751 | two disk files instead of one. You can use a normalizer function to |
752 | keep the two sets of return values separate. For example: |
753 | |
754 | tie my %cache => 'MLDBM', 'DB_File', $filename, ...; |
755 | |
756 | memoize 'myfunc', |
757 | NORMALIZER => 'n', |
758 | SCALAR_CACHE => [HASH => \%cache], |
759 | LIST_CACHE => MERGE, |
760 | ; |
761 | |
762 | sub n { |
763 | my $context = wantarray() ? 'L' : 'S'; |
764 | # ... now compute the hash key from the arguments ... |
765 | $hashkey = "$context:$hashkey"; |
766 | } |
767 | |
768 | This normalizer function will store scalar context return values in |
769 | the disk file under keys that begin with C<S:>, and list context |
770 | return values under keys that begin with C<L:>. |
771 | |
772 | =back |
773 | |
774 | =head1 OTHER FACILITIES |
775 | |
776 | =head2 C<unmemoize> |
777 | |
778 | There's an C<unmemoize> function that you can import if you want to. |
779 | Why would you want to? Here's an example: Suppose you have your cache |
780 | tied to a DBM file, and you want to make sure that the cache is |
781 | written out to disk if someone interrupts the program. If the program |
782 | exits normally, this will happen anyway, but if someone types |
783 | control-C or something then the program will terminate immediately |
784 | without synchronizing the database. So what you can do instead is |
785 | |
786 | $SIG{INT} = sub { unmemoize 'function' }; |
787 | |
788 | Thanks to Jonathan Roy for discovering a use for C<unmemoize>. |
789 | |
790 | C<unmemoize> accepts a reference to, or the name of a previously |
791 | memoized function, and undoes whatever it did to provide the memoized |
792 | version in the first place, including making the name refer to the |
793 | unmemoized version if appropriate. It returns a reference to the |
794 | unmemoized version of the function. |
795 | |
796 | If you ask it to unmemoize a function that was never memoized, it |
797 | croaks. |
798 | |
799 | =head2 C<flush_cache> |
800 | |
801 | C<flush_cache(function)> will flush out the caches, discarding I<all> |
802 | the cached data. The argument may be a funciton name or a reference |
803 | to a function. For finer control over when data is discarded or |
804 | expired, see the documentation for C<Memoize::Expire>, included in |
805 | this package. |
806 | |
807 | Note that if the cache is a tied hash, C<flush_cache> will attempt to |
808 | invoke the C<CLEAR> method on the hash. If there is no C<CLEAR> |
809 | method, this will cause a run-time error. |
810 | |
811 | An alternative approach to cache flushing is to use the C<HASH> option |
812 | (see above) to request that C<Memoize> use a particular hash variable |
813 | as its cache. Then you can examine or modify the hash at any time in |
814 | any way you desire. |
815 | |
816 | =head1 CAVEATS |
817 | |
818 | Memoization is not a cure-all: |
819 | |
820 | =over 4 |
821 | |
822 | =item * |
823 | |
824 | Do not memoize a function whose behavior depends on program |
825 | state other than its own arguments, such as global variables, the time |
826 | of day, or file input. These functions will not produce correct |
827 | results when memoized. For a particularly easy example: |
828 | |
829 | sub f { |
830 | time; |
831 | } |
832 | |
833 | This function takes no arguments, and as far as C<Memoize> is |
834 | concerned, it always returns the same result. C<Memoize> is wrong, of |
835 | course, and the memoized version of this function will call C<time> once |
836 | to get the current time, and it will return that same time |
837 | every time you call it after that. |
838 | |
839 | =item * |
840 | |
841 | Do not memoize a function with side effects. |
842 | |
843 | sub f { |
844 | my ($a, $b) = @_; |
845 | my $s = $a + $b; |
846 | print "$a + $b = $s.\n"; |
847 | } |
848 | |
849 | This function accepts two arguments, adds them, and prints their sum. |
850 | Its return value is the numuber of characters it printed, but you |
851 | probably didn't care about that. But C<Memoize> doesn't understand |
852 | that. If you memoize this function, you will get the result you |
853 | expect the first time you ask it to print the sum of 2 and 3, but |
854 | subsequent calls will return 1 (the return value of |
855 | C<print>) without actually printing anything. |
856 | |
857 | =item * |
858 | |
859 | Do not memoize a function that returns a data structure that is |
860 | modified by its caller. |
861 | |
862 | Consider these functions: C<getusers> returns a list of users somehow, |
863 | and then C<main> throws away the first user on the list and prints the |
864 | rest: |
865 | |
866 | sub main { |
867 | my $userlist = getusers(); |
868 | shift @$userlist; |
869 | foreach $u (@$userlist) { |
870 | print "User $u\n"; |
871 | } |
872 | } |
873 | |
874 | sub getusers { |
875 | my @users; |
876 | # Do something to get a list of users; |
877 | \@users; # Return reference to list. |
878 | } |
879 | |
880 | If you memoize C<getusers> here, it will work right exactly once. The |
881 | reference to the users list will be stored in the memo table. C<main> |
882 | will discard the first element from the referenced list. The next |
883 | time you invoke C<main>, C<Memoize> will not call C<getusers>; it will |
884 | just return the same reference to the same list it got last time. But |
885 | this time the list has already had its head removed; C<main> will |
886 | erroneously remove another element from it. The list will get shorter |
887 | and shorter every time you call C<main>. |
888 | |
889 | Similarly, this: |
890 | |
891 | $u1 = getusers(); |
892 | $u2 = getusers(); |
893 | pop @$u1; |
894 | |
895 | will modify $u2 as well as $u1, because both variables are references |
896 | to the same array. Had C<getusers> not been memoized, $u1 and $u2 |
897 | would have referred to different arrays. |
898 | |
899 | =item * |
900 | |
901 | Do not memoize a very simple function. |
902 | |
903 | Recently someone mentioned to me that the Memoize module made his |
904 | program run slower instead of faster. It turned out that he was |
905 | memoizing the following function: |
906 | |
907 | sub square { |
908 | $_[0] * $_[0]; |
909 | } |
910 | |
911 | I pointed out that C<Memoize> uses a hash, and that looking up a |
912 | number in the hash is necessarily going to take a lot longer than a |
913 | single multiplication. There really is no way to speed up the |
914 | C<square> function. |
915 | |
916 | Memoization is not magical. |
917 | |
918 | =back |
919 | |
920 | =head1 PERSISTENT CACHE SUPPORT |
921 | |
922 | You can tie the cache tables to any sort of tied hash that you want |
923 | to, as long as it supports C<TIEHASH>, C<FETCH>, C<STORE>, and |
924 | C<EXISTS>. For example, |
925 | |
926 | tie my %cache => 'GDBM_File', $filename, O_RDWR|O_CREAT, 0666; |
927 | memoize 'function', SCALAR_CACHE => [HASH => \%cache]; |
928 | |
929 | works just fine. For some storage methods, you need a little glue. |
930 | |
931 | C<SDBM_File> doesn't supply an C<EXISTS> method, so included in this |
932 | package is a glue module called C<Memoize::SDBM_File> which does |
933 | provide one. Use this instead of plain C<SDBM_File> to store your |
934 | cache table on disk in an C<SDBM_File> database: |
935 | |
936 | tie my %cache => 'Memoize::SDBM_File', $filename, O_RDWR|O_CREAT, 0666; |
937 | memoize 'function', SCALAR_CACHE => [HASH => \%cache]; |
938 | |
939 | C<NDBM_File> has the same problem and the same solution. (Use |
940 | C<Memoize::NDBM_File instead of Plain NDBM_File.>) |
941 | |
942 | C<Storable> isn't a tied hash class at all. You can use it to store a |
943 | hash to disk and retrieve it again, but you can't modify the hash while |
944 | it's on the disk. So if you want to store your cache table in a |
945 | C<Storable> database, use C<Memoize::Storable>, which puts a hashlike |
946 | front-end onto C<Storable>. The hash table is actually kept in |
947 | memory, and is loaded from your C<Storable> file at the time you |
948 | memoize the function, and stored back at the time you unmemoize the |
949 | function (or when your program exits): |
950 | |
951 | tie my %cache => 'Memoize::Storable', $filename; |
952 | memoize 'function', SCALAR_CACHE => [HASH => \%cache]; |
953 | |
954 | tie my %cache => 'Memoize::Storable', $filename, 'nstore'; |
955 | memoize 'function', SCALAR_CACHE => [HASH => \%cache]; |
956 | |
957 | Include the `nstore' option to have the C<Storable> database written |
958 | in `network order'. (See L<Storable> for more details about this.) |
959 | |
960 | =head1 EXPIRATION SUPPORT |
961 | |
962 | See Memoize::Expire, which is a plug-in module that adds expiration |
963 | functionality to Memoize. If you don't like the kinds of policies |
964 | that Memoize::Expire implements, it is easy to write your own plug-in |
965 | module to implement whatever policy you desire. Memoize comes with |
966 | several examples. An expiration manager that implements a LRU policy |
967 | is available on CPAN as Memoize::ExpireLRU. |
968 | |
969 | =head1 BUGS |
970 | |
971 | The test suite is much better, but always needs improvement. |
972 | |
973 | There used to be some problem with the way C<goto &f> works under |
974 | threaded Perl, because of the lexical scoping of C<@_>. This is a bug |
975 | in Perl, and until it is resolved, Memoize won't work with these |
976 | Perls. This is probably still the case, although I have not been able |
977 | to try it out. If you encounter this problem, you can fix it by |
978 | chopping the source code a little. Find the comment in the source |
979 | code that says C<--- THREADED PERL COMMENT---> and comment out the |
980 | active line and uncomment the commented one. Then try it again. |
981 | |
982 | Here's a bug that isn't my fault: Some versions of C<DB_File> won't |
983 | let you store data under a key of length 0. That means that if you |
984 | have a function C<f> which you memoized and the cache is in a |
985 | C<DB_File> database, then the value of C<f()> (C<f> called with no |
986 | arguments) will not be memoized. Let us all breathe deeply and repeat |
987 | this mantra: ``Gosh, Keith, that sure was a stupid thing to do.'' |
988 | |
989 | =head1 MAILING LIST |
990 | |
991 | To join a very low-traffic mailing list for announcements about |
992 | C<Memoize>, send an empty note to C<mjd-perl-memoize-request@plover.com>. |
993 | |
994 | =head1 AUTHOR |
995 | |
996 | Mark-Jason Dominus (C<mjd-perl-memoize+@plover.com>), Plover Systems co. |
997 | |
998 | See the C<Memoize.pm> Page at http://www.plover.com/~mjd/perl/Memoize/ |
999 | for news and upgrades. Near this page, at |
1000 | http://www.plover.com/~mjd/perl/MiniMemoize/ there is an article about |
1001 | memoization and about the internals of Memoize that appeared in The |
1002 | Perl Journal, issue #13. (This article is also included in the |
1003 | Memoize distribution as `article.html'.) |
1004 | |
1005 | To join a mailing list for announcements about C<Memoize>, send an |
1006 | empty message to C<mjd-perl-memoize-request@plover.com>. This mailing |
1007 | list is for announcements only and has extremely low traffic---about |
1008 | four messages per year. |
1009 | |
1010 | =head1 THANK YOU |
1011 | |
1012 | Many thanks to Jonathan Roy for bug reports and suggestions, to |
1013 | Michael Schwern for other bug reports and patches, to Mike Cariaso for |
1014 | helping me to figure out the Right Thing to Do About Expiration, to |
1015 | Joshua Gerth, Joshua Chamas, Jonathan Roy, Mark D. Anderson, and |
1016 | Andrew Johnson for more suggestions about expiration, to Brent Powers |
1017 | for the Memoize::ExpireLRU module, to Ariel Scolnicov for delightful |
1018 | messages about the Fibonacci function, to Dion Almaer for |
1019 | thought-provoking suggestions about the default normalizer, to Walt |
1020 | Mankowski and Kurt Starsinic for much help investigating problems |
1021 | under threaded Perl, to Alex Dudkevich for reporting the bug in |
1022 | prototyped functions and for checking my patch, to Tony Bass for many |
1023 | helpful suggestions, to Philippe Verdret for enlightening discussion |
1024 | of Hook::PrePostCall, to Nat Torkington for advice I ignored, to Chris |
1025 | Nandor for portability advice, to Randal Schwartz for suggesting the |
1026 | 'C<flush_cache> function, and to Jenda Krynicky for being a light in |
1027 | the world. |
1028 | |
1029 | =cut |