Debian Codegraph @

upstream/mageia-cauldron/man3pm/Memoize.3pm

raw
1 .\" -*- mode: troff; coding: utf-8 -*-
2 .\" Automatically generated by Pod::Man v6.0.2 (Pod::Simple 3.45)
3 .\"
4 .\" Standard preamble:
5 .\" ========================================================================
6 .de Sp \" Vertical space (when we can't use .PP)
7 .if t .sp .5v
8 .if n .sp
9 ..
10 .de Vb \" Begin verbatim text
11 .ft CW
12 .nf
13 .ne \\$1
14 ..
15 .de Ve \" End verbatim text
16 .ft R
17 .fi
18 ..
19 .\" \*(C` and \*(C' are quotes in nroff, nothing in troff, for use with C<>.
20 .ie n \{\
21 . ds C` ""
22 . ds C' ""
23 'br\}
24 .el\{\
25 . ds C`
26 . ds C'
27 'br\}
28 .\"
29 .\" Escape single quotes in literal strings from groff's Unicode transform.
30 .ie \n(.g .ds Aq \(aq
31 .el .ds Aq '
32 .\"
33 .\" If the F register is >0, we'll generate index entries on stderr for
34 .\" titles (.TH), headers (.SH), subsections (.SS), items (.Ip), and index
35 .\" entries marked with X<> in POD. Of course, you'll have to process the
36 .\" output yourself in some meaningful fashion.
37 .\"
38 .\" Avoid warning from groff about undefined register 'F'.
39 .de IX
40 ..
41 .nr rF 0
42 .if \n(.g .if rF .nr rF 1
43 .if (\n(rF:(\n(.g==0)) \{\
44 . if \nF \{\
45 . de IX
46 . tm Index:\\$1\t\\n%\t"\\$2"
47 ..
48 . if !\nF==2 \{\
49 . nr % 0
50 . nr F 2
51 . \}
52 . \}
53 .\}
54 .rr rF
55 .\"
56 .\" Required to disable full justification in groff 1.23.0.
57 .if n .ds AD l
58 .\" ========================================================================
59 .\"
60 .IX Title "Memoize 3pm"
61 .TH Memoize 3pm 2025-06-24 "perl v5.42.0" "Perl Programmers Reference Guide"
62 .\" For nroff, turn off justification. Always turn off hyphenation; it makes
63 .\" way too many mistakes in technical documents.
64 .if n .ad l
65 .nh
66 .SH NAME
67 Memoize \- Make functions faster by trading space for time
68 .SH SYNOPSIS
69 .IX Header "SYNOPSIS"
70 .Vb 3
71 \& use Memoize;
72 \& memoize(\*(Aqslow_function\*(Aq);
73 \& slow_function(arguments); # Is faster than it was before
74 .Ve
75 .PP
76 This is normally all you need to know. However, many options are available:
77 .PP
78 .Vb 1
79 \& memoize(function, options...);
80 .Ve
81 .PP
82 Options include:
83 .PP
84 .Vb 2
85 \& NORMALIZER => function
86 \& INSTALL => new_name
87 \&
88 \& SCALAR_CACHE => \*(AqMEMORY\*(Aq
89 \& SCALAR_CACHE => [\*(AqHASH\*(Aq, \e%cache_hash ]
90 \& SCALAR_CACHE => \*(AqFAULT\*(Aq
91 \& SCALAR_CACHE => \*(AqMERGE\*(Aq
92 \&
93 \& LIST_CACHE => \*(AqMEMORY\*(Aq
94 \& LIST_CACHE => [\*(AqHASH\*(Aq, \e%cache_hash ]
95 \& LIST_CACHE => \*(AqFAULT\*(Aq
96 \& LIST_CACHE => \*(AqMERGE\*(Aq
97 .Ve
98 .SH DESCRIPTION
99 .IX Header "DESCRIPTION"
100 \&\fIMemoizing\fR a function makes it faster by trading space for time. It
101 does this by caching the return values of the function in a table.
102 If you call the function again with the same arguments, \f(CW\*(C`memoize\*(C'\fR
103 jumps in and gives you the value out of the table, instead of letting
104 the function compute the value all over again.
105 .SH EXAMPLE
106 .IX Header "EXAMPLE"
107 Here is an extreme example. Consider the Fibonacci sequence, defined
108 by the following function:
109 .PP
110 .Vb 6
111 \& # Compute Fibonacci numbers
112 \& sub fib {
113 \& my $n = shift;
114 \& return $n if $n < 2;
115 \& fib($n\-1) + fib($n\-2);
116 \& }
117 .Ve
118 .PP
119 This function is very slow. Why? To compute fib(14), it first wants
120 to compute fib(13) and fib(12), and add the results. But to compute
121 fib(13), it first has to compute fib(12) and fib(11), and then it
122 comes back and computes fib(12) all over again even though the answer
123 is the same. And both of the times that it wants to compute fib(12),
124 it has to compute fib(11) from scratch, and then it has to do it
125 again each time it wants to compute fib(13). This function does so
126 much recomputing of old results that it takes a really long time to
127 run\-\-\-fib(14) makes 1,200 extra recursive calls to itself, to compute
128 and recompute things that it already computed.
129 .PP
130 This function is a good candidate for memoization. If you memoize the
131 \&\f(CW\*(C`fib\*(C'\fR function above, it will compute fib(14) exactly once, the first
132 time it needs to, and then save the result in a table. Then if you
133 ask for fib(14) again, it gives you the result out of the table.
134 While computing fib(14), instead of computing fib(12) twice, it does
135 it once; the second time it needs the value it gets it from the table.
136 It doesn\*(Aqt compute fib(11) four times; it computes it once, getting it
137 from the table the next three times. Instead of making 1,200
138 recursive calls to \f(CW\*(C`fib\*(C'\fR, it makes 15. This makes the function about
139 150 times faster.
140 .PP
141 You could do the memoization yourself, by rewriting the function, like
142 this:
143 .PP
144 .Vb 9
145 \& # Compute Fibonacci numbers, memoized version
146 \& { my @fib;
147 \& sub fib {
148 \& my $n = shift;
149 \& return $fib[$n] if defined $fib[$n];
150 \& return $fib[$n] = $n if $n < 2;
151 \& $fib[$n] = fib($n\-1) + fib($n\-2);
152 \& }
153 \& }
154 .Ve
155 .PP
156 Or you could use this module, like this:
157 .PP
158 .Vb 2
159 \& use Memoize;
160 \& memoize(\*(Aqfib\*(Aq);
161 \&
162 \& # Rest of the fib function just like the original version.
163 .Ve
164 .PP
165 This makes it easy to turn memoizing on and off.
166 .PP
167 Here\*(Aqs an even simpler example: I wrote a simple ray tracer; the
168 program would look in a certain direction, figure out what it was
169 looking at, and then convert the \f(CW\*(C`color\*(C'\fR value (typically a string
170 like \f(CW\*(C`red\*(C'\fR) of that object to a red, green, and blue pixel value, like
171 this:
172 .PP
173 .Vb 6
174 \& for ($direction = 0; $direction < 300; $direction++) {
175 \& # Figure out which object is in direction $direction
176 \& $color = $object\->{color};
177 \& ($r, $g, $b) = @{&ColorToRGB($color)};
178 \& ...
179 \& }
180 .Ve
181 .PP
182 Since there are relatively few objects in a picture, there are only a
183 few colors, which get looked up over and over again. Memoizing
184 \&\f(CW\*(C`ColorToRGB\*(C'\fR sped up the program by several percent.
185 .SH DETAILS
186 .IX Header "DETAILS"
187 This module exports exactly one function, \f(CW\*(C`memoize\*(C'\fR. The rest of the
188 functions in this package are None of Your Business.
189 .PP
190 You should say
191 .PP
192 .Vb 1
193 \& memoize(function)
194 .Ve
195 .PP
196 where \f(CW\*(C`function\*(C'\fR is the name of the function you want to memoize, or
197 a reference to it. \f(CW\*(C`memoize\*(C'\fR returns a reference to the new,
198 memoized version of the function, or \f(CW\*(C`undef\*(C'\fR on a non\-fatal error.
199 At present, there are no non\-fatal errors, but there might be some in
200 the future.
201 .PP
202 If \f(CW\*(C`function\*(C'\fR was the name of a function, then \f(CW\*(C`memoize\*(C'\fR hides the
203 old version and installs the new memoized version under the old name,
204 so that \f(CW&function(...)\fR actually invokes the memoized version.
205 .SH OPTIONS
206 .IX Header "OPTIONS"
207 There are some optional options you can pass to \f(CW\*(C`memoize\*(C'\fR to change
208 the way it behaves a little. To supply options, invoke \f(CW\*(C`memoize\*(C'\fR
209 like this:
210 .PP
211 .Vb 5
212 \& memoize(function, NORMALIZER => function,
213 \& INSTALL => newname,
214 \& SCALAR_CACHE => option,
215 \& LIST_CACHE => option
216 \& );
217 .Ve
218 .PP
219 Each of these options is optional; you can include some, all, or none
220 of them.
221 .SS INSTALL
222 .IX Subsection "INSTALL"
223 If you supply a function name with \f(CW\*(C`INSTALL\*(C'\fR, memoize will install
224 the new, memoized version of the function under the name you give.
225 For example,
226 .PP
227 .Vb 1
228 \& memoize(\*(Aqfib\*(Aq, INSTALL => \*(Aqfastfib\*(Aq)
229 .Ve
230 .PP
231 installs the memoized version of \f(CW\*(C`fib\*(C'\fR as \f(CW\*(C`fastfib\*(C'\fR; without the
232 \&\f(CW\*(C`INSTALL\*(C'\fR option it would have replaced the old \f(CW\*(C`fib\*(C'\fR with the
233 memoized version.
234 .PP
235 To prevent \f(CW\*(C`memoize\*(C'\fR from installing the memoized version anywhere, use
236 \&\f(CW\*(C`INSTALL => undef\*(C'\fR.
237 .SS NORMALIZER
238 .IX Subsection "NORMALIZER"
239 Suppose your function looks like this:
240 .PP
241 .Vb 6
242 \& # Typical call: f(\*(Aqaha!\*(Aq, A => 11, B => 12);
243 \& sub f {
244 \& my $a = shift;
245 \& my %hash = @_;
246 \& $hash{B} ||= 2; # B defaults to 2
247 \& $hash{C} ||= 7; # C defaults to 7
248 \&
249 \& # Do something with $a, %hash
250 \& }
251 .Ve
252 .PP
253 Now, the following calls to your function are all completely equivalent:
254 .PP
255 .Vb 6
256 \& f(OUCH);
257 \& f(OUCH, B => 2);
258 \& f(OUCH, C => 7);
259 \& f(OUCH, B => 2, C => 7);
260 \& f(OUCH, C => 7, B => 2);
261 \& (etc.)
262 .Ve
263 .PP
264 However, unless you tell \f(CW\*(C`Memoize\*(C'\fR that these calls are equivalent,
265 it will not know that, and it will compute the values for these
266 invocations of your function separately, and store them separately.
267 .PP
268 To prevent this, supply a \f(CW\*(C`NORMALIZER\*(C'\fR function that turns the
269 program arguments into a string in a way that equivalent arguments
270 turn into the same string. A \f(CW\*(C`NORMALIZER\*(C'\fR function for \f(CW\*(C`f\*(C'\fR above
271 might look like this:
272 .PP
273 .Vb 5
274 \& sub normalize_f {
275 \& my $a = shift;
276 \& my %hash = @_;
277 \& $hash{B} ||= 2;
278 \& $hash{C} ||= 7;
279 \&
280 \& join(\*(Aq,\*(Aq, $a, map ($_ => $hash{$_}) sort keys %hash);
281 \& }
282 .Ve
283 .PP
284 Each of the argument lists above comes out of the \f(CW\*(C`normalize_f\*(C'\fR
285 function looking exactly the same, like this:
286 .PP
287 .Vb 1
288 \& OUCH,B,2,C,7
289 .Ve
290 .PP
291 You would tell \f(CW\*(C`Memoize\*(C'\fR to use this normalizer this way:
292 .PP
293 .Vb 1
294 \& memoize(\*(Aqf\*(Aq, NORMALIZER => \*(Aqnormalize_f\*(Aq);
295 .Ve
296 .PP
297 \&\f(CW\*(C`memoize\*(C'\fR knows that if the normalized version of the arguments is
298 the same for two argument lists, then it can safely look up the value
299 that it computed for one argument list and return it as the result of
300 calling the function with the other argument list, even if the
301 argument lists look different.
302 .PP
303 The default normalizer just concatenates the arguments with character
304 28 in between. (In ASCII, this is called FS or control\-\e.) This
305 always works correctly for functions with only one string argument,
306 and also when the arguments never contain character 28. However, it
307 can confuse certain argument lists:
308 .PP
309 .Vb 3
310 \& normalizer("a\e034", "b")
311 \& normalizer("a", "\e034b")
312 \& normalizer("a\e034\e034b")
313 .Ve
314 .PP
315 for example.
316 .PP
317 Since hash keys are strings, the default normalizer will not
318 distinguish between \f(CW\*(C`undef\*(C'\fR and the empty string. It also won\*(Aqt work
319 when the function\*(Aqs arguments are references. For example, consider a
320 function \f(CW\*(C`g\*(C'\fR which gets two arguments: A number, and a reference to
321 an array of numbers:
322 .PP
323 .Vb 1
324 \& g(13, [1,2,3,4,5,6,7]);
325 .Ve
326 .PP
327 The default normalizer will turn this into something like
328 \&\f(CW"13\e034ARRAY(0x436c1f)"\fR. That would be all right, except that a
329 subsequent array of numbers might be stored at a different location
330 even though it contains the same data. If this happens, \f(CW\*(C`Memoize\*(C'\fR
331 will think that the arguments are different, even though they are
332 equivalent. In this case, a normalizer like this is appropriate:
333 .PP
334 .Vb 1
335 \& sub normalize { join \*(Aq \*(Aq, $_[0], @{$_[1]} }
336 .Ve
337 .PP
338 For the example above, this produces the key "13 1 2 3 4 5 6 7".
339 .PP
340 Another use for normalizers is when the function depends on data other
341 than those in its arguments. Suppose you have a function which
342 returns a value which depends on the current hour of the day:
343 .PP
344 .Vb 10
345 \& sub on_duty {
346 \& my ($problem_type) = @_;
347 \& my $hour = (localtime)[2];
348 \& open my $fh, "$DIR/$problem_type" or die...;
349 \& my $line;
350 \& while ($hour\-\- > 0)
351 \& $line = <$fh>;
352 \& }
353 \& return $line;
354 \& }
355 .Ve
356 .PP
357 At 10:23, this function generates the 10th line of a data file; at
358 3:45 PM it generates the 15th line instead. By default, \f(CW\*(C`Memoize\*(C'\fR
359 will only see the \f(CW$problem_type\fR argument. To fix this, include the
360 current hour in the normalizer:
361 .PP
362 .Vb 1
363 \& sub normalize { join \*(Aq \*(Aq, (localtime)[2], @_ }
364 .Ve
365 .PP
366 The calling context of the function (scalar or list context) is
367 propagated to the normalizer. This means that if the memoized
368 function will treat its arguments differently in list context than it
369 would in scalar context, you can have the normalizer function select
370 its behavior based on the results of \f(CW\*(C`wantarray\*(C'\fR. Even if called in
371 a list context, a normalizer should still return a single string.
372 .ie n .SS """SCALAR_CACHE"", ""LIST_CACHE"""
373 .el .SS "\f(CWSCALAR_CACHE\fP, \f(CWLIST_CACHE\fP"
374 .IX Subsection "SCALAR_CACHE, LIST_CACHE"
375 Normally, \f(CW\*(C`Memoize\*(C'\fR caches your function\*(Aqs return values into an
376 ordinary Perl hash variable. However, you might like to have the
377 values cached on the disk, so that they persist from one run of your
378 program to the next, or you might like to associate some other
379 interesting semantics with the cached values.
380 .PP
381 There\*(Aqs a slight complication under the hood of \f(CW\*(C`Memoize\*(C'\fR: There are
382 actually \fItwo\fR caches, one for scalar values and one for list values.
383 When your function is called in scalar context, its return value is
384 cached in one hash, and when your function is called in list context,
385 its value is cached in the other hash. You can control the caching
386 behavior of both contexts independently with these options.
387 .PP
388 The argument to \f(CW\*(C`LIST_CACHE\*(C'\fR or \f(CW\*(C`SCALAR_CACHE\*(C'\fR must either be one of
389 the following four strings:
390 .PP
391 .Vb 4
392 \& MEMORY
393 \& FAULT
394 \& MERGE
395 \& HASH
396 .Ve
397 .PP
398 or else it must be a reference to an array whose first element is one of
399 these four strings, such as \f(CW\*(C`[HASH, arguments...]\*(C'\fR.
400 .ie n .IP """MEMORY""" 4
401 .el .IP \f(CWMEMORY\fR 4
402 .IX Item "MEMORY"
403 \&\f(CW\*(C`MEMORY\*(C'\fR means that return values from the function will be cached in
404 an ordinary Perl hash variable. The hash variable will not persist
405 after the program exits. This is the default.
406 .ie n .IP """HASH""" 4
407 .el .IP \f(CWHASH\fR 4
408 .IX Item "HASH"
409 \&\f(CW\*(C`HASH\*(C'\fR allows you to specify that a particular hash that you supply
410 will be used as the cache. You can tie this hash beforehand to give
411 it any behavior you want.
412 .Sp
413 A tied hash can have any semantics at all. It is typically tied to an
414 on\-disk database, so that cached values are stored in the database and
415 retrieved from it again when needed, and the disk file typically
416 persists after your program has exited. See \f(CW\*(C`perltie\*(C'\fR for more
417 complete details about \f(CW\*(C`tie\*(C'\fR.
418 .Sp
419 A typical example is:
420 .Sp
421 .Vb 3
422 \& use DB_File;
423 \& tie my %cache => \*(AqDB_File\*(Aq, $filename, O_RDWR|O_CREAT, 0666;
424 \& memoize \*(Aqfunction\*(Aq, SCALAR_CACHE => [HASH => \e%cache];
425 .Ve
426 .Sp
427 This has the effect of storing the cache in a \f(CW\*(C`DB_File\*(C'\fR database
428 whose name is in \f(CW$filename\fR. The cache will persist after the
429 program has exited. Next time the program runs, it will find the
430 cache already populated from the previous run of the program. Or you
431 can forcibly populate the cache by constructing a batch program that
432 runs in the background and populates the cache file. Then when you
433 come to run your real program the memoized function will be fast
434 because all its results have been precomputed.
435 .Sp
436 Another reason to use \f(CW\*(C`HASH\*(C'\fR is to provide your own hash variable.
437 You can then inspect or modify the contents of the hash to gain finer
438 control over the cache management.
439 .ie n .IP """TIE""" 4
440 .el .IP \f(CWTIE\fR 4
441 .IX Item "TIE"
442 This option is no longer supported. It is still documented only to
443 aid in the debugging of old programs that use it. Old programs should
444 be converted to use the \f(CW\*(C`HASH\*(C'\fR option instead.
445 .Sp
446 .Vb 1
447 \& memoize ... [\*(AqTIE\*(Aq, PACKAGE, ARGS...]
448 .Ve
449 .Sp
450 is merely a shortcut for
451 .Sp
452 .Vb 4
453 \& require PACKAGE;
454 \& { tie my %cache, PACKAGE, ARGS...;
455 \& memoize ... [HASH => \e%cache];
456 \& }
457 .Ve
458 .ie n .IP """FAULT""" 4
459 .el .IP \f(CWFAULT\fR 4
460 .IX Item "FAULT"
461 \&\f(CW\*(C`FAULT\*(C'\fR means that you never expect to call the function in scalar
462 (or list) context, and that if \f(CW\*(C`Memoize\*(C'\fR detects such a call, it
463 should abort the program. The error message is one of
464 .Sp
465 .Vb 2
466 \& \`foo\*(Aq function called in forbidden list context at line ...
467 \& \`foo\*(Aq function called in forbidden scalar context at line ...
468 .Ve
469 .ie n .IP """MERGE""" 4
470 .el .IP \f(CWMERGE\fR 4
471 .IX Item "MERGE"
472 \&\f(CW\*(C`MERGE\*(C'\fR normally means that the memoized function does not
473 distinguish between list and scalar context, and that return values in
474 both contexts should be stored together. Both \f(CW\*(C`LIST_CACHE =>
475 MERGE\*(C'\fR and \f(CW\*(C`SCALAR_CACHE => MERGE\*(C'\fR mean the same thing.
476 .Sp
477 Consider this function:
478 .Sp
479 .Vb 4
480 \& sub complicated {
481 \& # ... time\-consuming calculation of $result
482 \& return $result;
483 \& }
484 .Ve
485 .Sp
486 The \f(CW\*(C`complicated\*(C'\fR function will return the same numeric \f(CW$result\fR
487 regardless of whether it is called in list or in scalar context.
488 .Sp
489 Normally, the following code will result in two calls to \f(CW\*(C`complicated\*(C'\fR, even
490 if \f(CW\*(C`complicated\*(C'\fR is memoized:
491 .Sp
492 .Vb 3
493 \& $x = complicated(142);
494 \& ($y) = complicated(142);
495 \& $z = complicated(142);
496 .Ve
497 .Sp
498 The first call will cache the result, say 37, in the scalar cache; the
499 second will cache the list \f(CW\*(C`(37)\*(C'\fR in the list cache. The third call
500 doesn\*(Aqt call the real \f(CW\*(C`complicated\*(C'\fR function; it gets the value 37
501 from the scalar cache.
502 .Sp
503 Obviously, the second call to \f(CW\*(C`complicated\*(C'\fR is a waste of time, and
504 storing its return value is a waste of space. Specifying \f(CW\*(C`LIST_CACHE
505 => MERGE\*(C'\fR will make \f(CW\*(C`memoize\*(C'\fR use the same cache for scalar and
506 list context return values, so that the second call uses the scalar
507 cache that was populated by the first call. \f(CW\*(C`complicated\*(C'\fR ends up
508 being called only once, and both subsequent calls return \f(CW37\fR from the
509 cache, regardless of the calling context.
510 .PP
511 \fIList values in scalar context\fR
512 .IX Subsection "List values in scalar context"
513 .PP
514 Consider this function:
515 .PP
516 .Vb 1
517 \& sub iota { return reverse (1..$_[0]) }
518 .Ve
519 .PP
520 This function normally returns a list. Suppose you memoize it and
521 merge the caches:
522 .PP
523 .Vb 1
524 \& memoize \*(Aqiota\*(Aq, SCALAR_CACHE => \*(AqMERGE\*(Aq;
525 \&
526 \& @i7 = iota(7);
527 \& $i7 = iota(7);
528 .Ve
529 .PP
530 Here the first call caches the list (1,2,3,4,5,6,7). The second call
531 does not really make sense. \f(CW\*(C`Memoize\*(C'\fR cannot guess what behavior
532 \&\f(CW\*(C`iota\*(C'\fR should have in scalar context without actually calling it in
533 scalar context. Normally \f(CW\*(C`Memoize\*(C'\fR \fIwould\fR call \f(CW\*(C`iota\*(C'\fR in scalar
534 context and cache the result, but the \f(CW\*(C`SCALAR_CACHE => \*(AqMERGE\*(Aq\*(C'\fR
535 option says not to do that, but to use the cache list\-context value
536 instead. But it cannot return a list of seven elements in a scalar
537 context. In this case \f(CW$i7\fR will receive the \fBfirst element\fR of the
538 cached list value, namely 7.
539 .PP
540 \fIMerged disk caches\fR
541 .IX Subsection "Merged disk caches"
542 .PP
543 Another use for \f(CW\*(C`MERGE\*(C'\fR is when you want both kinds of return values
544 stored in the same disk file; this saves you from having to deal with
545 two disk files instead of one. You can use a normalizer function to
546 keep the two sets of return values separate. For example:
547 .PP
548 .Vb 2
549 \& local $MLDBM::UseDB = \*(AqDB_File\*(Aq;
550 \& tie my %cache => \*(AqMLDBM\*(Aq, $filename, ...;
551 \&
552 \& memoize \*(Aqmyfunc\*(Aq,
553 \& NORMALIZER => \*(Aqn\*(Aq,
554 \& SCALAR_CACHE => [HASH => \e%cache],
555 \& LIST_CACHE => \*(AqMERGE\*(Aq,
556 \& ;
557 \&
558 \& sub n {
559 \& my $context = wantarray() ? \*(AqL\*(Aq : \*(AqS\*(Aq;
560 \& # ... now compute the hash key from the arguments ...
561 \& $hashkey = "$context:$hashkey";
562 \& }
563 .Ve
564 .PP
565 This normalizer function will store scalar context return values in
566 the disk file under keys that begin with \f(CW\*(C`S:\*(C'\fR, and list context
567 return values under keys that begin with \f(CW\*(C`L:\*(C'\fR.
568 .SH "OTHER FACILITIES"
569 .IX Header "OTHER FACILITIES"
570 .ie n .SS """unmemoize"""
571 .el .SS \f(CWunmemoize\fP
572 .IX Subsection "unmemoize"
573 There\*(Aqs an \f(CW\*(C`unmemoize\*(C'\fR function that you can import if you want to.
574 Why would you want to? Here\*(Aqs an example: Suppose you have your cache
575 tied to a DBM file, and you want to make sure that the cache is
576 written out to disk if someone interrupts the program. If the program
577 exits normally, this will happen anyway, but if someone types
578 control\-C or something then the program will terminate immediately
579 without synchronizing the database. So what you can do instead is
580 .PP
581 .Vb 1
582 \& $SIG{INT} = sub { unmemoize \*(Aqfunction\*(Aq };
583 .Ve
584 .PP
585 \&\f(CW\*(C`unmemoize\*(C'\fR accepts a reference to, or the name of a previously
586 memoized function, and undoes whatever it did to provide the memoized
587 version in the first place, including making the name refer to the
588 unmemoized version if appropriate. It returns a reference to the
589 unmemoized version of the function.
590 .PP
591 If you ask it to unmemoize a function that was never memoized, it
592 croaks.
593 .ie n .SS """flush_cache"""
594 .el .SS \f(CWflush_cache\fP
595 .IX Subsection "flush_cache"
596 \&\f(CWflush_cache(function)\fR will flush out the caches, discarding \fIall\fR
597 the cached data. The argument may be a function name or a reference
598 to a function. For finer control over when data is discarded or
599 expired, see the documentation for \f(CW\*(C`Memoize::Expire\*(C'\fR, included in
600 this package.
601 .PP
602 Note that if the cache is a tied hash, \f(CW\*(C`flush_cache\*(C'\fR will attempt to
603 invoke the \f(CW\*(C`CLEAR\*(C'\fR method on the hash. If there is no \f(CW\*(C`CLEAR\*(C'\fR
604 method, this will cause a run\-time error.
605 .PP
606 An alternative approach to cache flushing is to use the \f(CW\*(C`HASH\*(C'\fR option
607 (see above) to request that \f(CW\*(C`Memoize\*(C'\fR use a particular hash variable
608 as its cache. Then you can examine or modify the hash at any time in
609 any way you desire. You may flush the cache by using \f(CW\*(C`%hash = ()\*(C'\fR.
610 .SH CAVEATS
611 .IX Header "CAVEATS"
612 Memoization is not a cure\-all:
613 .IP \(bu 4
614 Do not memoize a function whose behavior depends on program
615 state other than its own arguments, such as global variables, the time
616 of day, or file input. These functions will not produce correct
617 results when memoized. For a particularly easy example:
618 .Sp
619 .Vb 3
620 \& sub f {
621 \& time;
622 \& }
623 .Ve
624 .Sp
625 This function takes no arguments, and as far as \f(CW\*(C`Memoize\*(C'\fR is
626 concerned, it always returns the same result. \f(CW\*(C`Memoize\*(C'\fR is wrong, of
627 course, and the memoized version of this function will call \f(CW\*(C`time\*(C'\fR once
628 to get the current time, and it will return that same time
629 every time you call it after that.
630 .IP \(bu 4
631 Do not memoize a function with side effects.
632 .Sp
633 .Vb 5
634 \& sub f {
635 \& my ($a, $b) = @_;
636 \& my $s = $a + $b;
637 \& print "$a + $b = $s.\en";
638 \& }
639 .Ve
640 .Sp
641 This function accepts two arguments, adds them, and prints their sum.
642 Its return value is the number of characters it printed, but you
643 probably didn\*(Aqt care about that. But \f(CW\*(C`Memoize\*(C'\fR doesn\*(Aqt understand
644 that. If you memoize this function, you will get the result you
645 expect the first time you ask it to print the sum of 2 and 3, but
646 subsequent calls will return 1 (the return value of
647 \&\f(CW\*(C`print\*(C'\fR) without actually printing anything.
648 .IP \(bu 4
649 Do not memoize a function that returns a data structure that is
650 modified by its caller.
651 .Sp
652 Consider these functions: \f(CW\*(C`getusers\*(C'\fR returns a list of users somehow,
653 and then \f(CW\*(C`main\*(C'\fR throws away the first user on the list and prints the
654 rest:
655 .Sp
656 .Vb 7
657 \& sub main {
658 \& my $userlist = getusers();
659 \& shift @$userlist;
660 \& foreach $u (@$userlist) {
661 \& print "User $u\en";
662 \& }
663 \& }
664 \&
665 \& sub getusers {
666 \& my @users;
667 \& # Do something to get a list of users;
668 \& \e@users; # Return reference to list.
669 \& }
670 .Ve
671 .Sp
672 If you memoize \f(CW\*(C`getusers\*(C'\fR here, it will work right exactly once. The
673 reference to the users list will be stored in the memo table. \f(CW\*(C`main\*(C'\fR
674 will discard the first element from the referenced list. The next
675 time you invoke \f(CW\*(C`main\*(C'\fR, \f(CW\*(C`Memoize\*(C'\fR will not call \f(CW\*(C`getusers\*(C'\fR; it will
676 just return the same reference to the same list it got last time. But
677 this time the list has already had its head removed; \f(CW\*(C`main\*(C'\fR will
678 erroneously remove another element from it. The list will get shorter
679 and shorter every time you call \f(CW\*(C`main\*(C'\fR.
680 .Sp
681 Similarly, this:
682 .Sp
683 .Vb 3
684 \& $u1 = getusers();
685 \& $u2 = getusers();
686 \& pop @$u1;
687 .Ve
688 .Sp
689 will modify \f(CW$u2\fR as well as \f(CW$u1\fR, because both variables are references
690 to the same array. Had \f(CW\*(C`getusers\*(C'\fR not been memoized, \f(CW$u1\fR and \f(CW$u2\fR
691 would have referred to different arrays.
692 .IP \(bu 4
693 Do not memoize a very simple function.
694 .Sp
695 Recently someone mentioned to me that the Memoize module made his
696 program run slower instead of faster. It turned out that he was
697 memoizing the following function:
698 .Sp
699 .Vb 3
700 \& sub square {
701 \& $_[0] * $_[0];
702 \& }
703 .Ve
704 .Sp
705 I pointed out that \f(CW\*(C`Memoize\*(C'\fR uses a hash, and that looking up a
706 number in the hash is necessarily going to take a lot longer than a
707 single multiplication. There really is no way to speed up the
708 \&\f(CW\*(C`square\*(C'\fR function.
709 .Sp
710 Memoization is not magical.
711 .SH "PERSISTENT CACHE SUPPORT"
712 .IX Header "PERSISTENT CACHE SUPPORT"
713 You can tie the cache tables to any sort of tied hash that you want
714 to, as long as it supports \f(CW\*(C`TIEHASH\*(C'\fR, \f(CW\*(C`FETCH\*(C'\fR, \f(CW\*(C`STORE\*(C'\fR, and
715 \&\f(CW\*(C`EXISTS\*(C'\fR. For example,
716 .PP
717 .Vb 2
718 \& tie my %cache => \*(AqGDBM_File\*(Aq, $filename, O_RDWR|O_CREAT, 0666;
719 \& memoize \*(Aqfunction\*(Aq, SCALAR_CACHE => [HASH => \e%cache];
720 .Ve
721 .PP
722 works just fine. For some storage methods, you need a little glue.
723 .PP
724 \&\f(CW\*(C`SDBM_File\*(C'\fR doesn\*(Aqt supply an \f(CW\*(C`EXISTS\*(C'\fR method, so included in this
725 package is a glue module called \f(CW\*(C`Memoize::SDBM_File\*(C'\fR which does
726 provide one. Use this instead of plain \f(CW\*(C`SDBM_File\*(C'\fR to store your
727 cache table on disk in an \f(CW\*(C`SDBM_File\*(C'\fR database:
728 .PP
729 .Vb 2
730 \& tie my %cache => \*(AqMemoize::SDBM_File\*(Aq, $filename, O_RDWR|O_CREAT, 0666;
731 \& memoize \*(Aqfunction\*(Aq, SCALAR_CACHE => [HASH => \e%cache];
732 .Ve
733 .PP
734 \&\f(CW\*(C`NDBM_File\*(C'\fR has the same problem and the same solution. (Use
735 \&\f(CW\*(C`Memoize::NDBM_File instead of plain NDBM_File.\*(C'\fR)
736 .PP
737 \&\f(CW\*(C`Storable\*(C'\fR isn\*(Aqt a tied hash class at all. You can use it to store a
738 hash to disk and retrieve it again, but you can\*(Aqt modify the hash while
739 it\*(Aqs on the disk. So if you want to store your cache table in a
740 \&\f(CW\*(C`Storable\*(C'\fR database, use \f(CW\*(C`Memoize::Storable\*(C'\fR, which puts a hashlike
741 front\-end onto \f(CW\*(C`Storable\*(C'\fR. The hash table is actually kept in
742 memory, and is loaded from your \f(CW\*(C`Storable\*(C'\fR file at the time you
743 memoize the function, and stored back at the time you unmemoize the
744 function (or when your program exits):
745 .PP
746 .Vb 2
747 \& tie my %cache => \*(AqMemoize::Storable\*(Aq, $filename;
748 \& memoize \*(Aqfunction\*(Aq, SCALAR_CACHE => [HASH => \e%cache];
749 \&
750 \& tie my %cache => \*(AqMemoize::Storable\*(Aq, $filename, \*(Aqnstore\*(Aq;
751 \& memoize \*(Aqfunction\*(Aq, SCALAR_CACHE => [HASH => \e%cache];
752 .Ve
753 .PP
754 Include the \f(CW\*(C`nstore\*(C'\fR option to have the \f(CW\*(C`Storable\*(C'\fR database written
755 in \fInetwork order\fR. (See Storable for more details about this.)
756 .PP
757 The \f(CWflush_cache()\fR function will raise a run\-time error unless the
758 tied package provides a \f(CW\*(C`CLEAR\*(C'\fR method.
759 .SH "EXPIRATION SUPPORT"
760 .IX Header "EXPIRATION SUPPORT"
761 See Memoize::Expire, which is a plug\-in module that adds expiration
762 functionality to Memoize. If you don\*(Aqt like the kinds of policies
763 that Memoize::Expire implements, it is easy to write your own plug\-in
764 module to implement whatever policy you desire. Memoize comes with
765 several examples. An expiration manager that implements a LRU policy
766 is available on CPAN as Memoize::ExpireLRU.
767 .SH BUGS
768 .IX Header "BUGS"
769 The test suite is much better, but always needs improvement.
770 .PP
771 There is some problem with the way \f(CW\*(C`goto &f\*(C'\fR works under threaded
772 Perl, perhaps because of the lexical scoping of \f(CW@_\fR. This is a bug
773 in Perl, and until it is resolved, memoized functions will see a
774 slightly different \f(CWcaller()\fR and will perform a little more slowly
775 on threaded perls than unthreaded perls.
776 .PP
777 Some versions of \f(CW\*(C`DB_File\*(C'\fR won\*(Aqt let you store data under a key of
778 length 0. That means that if you have a function \f(CW\*(C`f\*(C'\fR which you
779 memoized and the cache is in a \f(CW\*(C`DB_File\*(C'\fR database, then the value of
780 \&\f(CWf()\fR (\f(CW\*(C`f\*(C'\fR called with no arguments) will not be memoized. If this
781 is a big problem, you can supply a normalizer function that prepends
782 \&\f(CW"x"\fR to every key.
783 .SH "SEE ALSO"
784 .IX Header "SEE ALSO"
785 At <https://perl.plover.com/MiniMemoize/> there is an article about
786 memoization and about the internals of Memoize that appeared in The
787 Perl Journal, issue #13.
788 .PP
789 Mark\-Jason Dominus\*(Aqs book \fIHigher\-Order Perl\fR (2005, ISBN 1558607013,
790 published
791 by Morgan Kaufmann) discusses memoization (and many other
792 topics) in tremendous detail. It is available on\-line for free.
793 For more information, visit <https://hop.perl.plover.com/>.
794 .SH "THANK YOU"
795 .IX Header "THANK YOU"
796 Many thanks to Florian Ragwitz for administration and packaging
797 assistance, to John Tromp for bug reports, to Jonathan Roy for bug reports
798 and suggestions, to Michael Schwern for other bug reports and patches,
799 to Mike Cariaso for helping me to figure out the Right Thing to Do
800 About Expiration, to Joshua Gerth, Joshua Chamas, Jonathan Roy
801 (again), Mark D. Anderson, and Andrew Johnson for more suggestions
802 about expiration, to Brent Powers for the Memoize::ExpireLRU module,
803 to Ariel Scolnicov for delightful messages about the Fibonacci
804 function, to Dion Almaer for thought\-provoking suggestions about the
805 default normalizer, to Walt Mankowski and Kurt Starsinic for much help
806 investigating problems under threaded Perl, to Alex Dudkevich for
807 reporting the bug in prototyped functions and for checking my patch,
808 to Tony Bass for many helpful suggestions, to Jonathan Roy (again) for
809 finding a use for \f(CWunmemoize()\fR, to Philippe Verdret for enlightening
810 discussion of \f(CW\*(C`Hook::PrePostCall\*(C'\fR, to Nat Torkington for advice I
811 ignored, to Chris Nandor for portability advice, to Randal Schwartz
812 for suggesting the \*(Aq\f(CW\*(C`flush_cache\*(C'\fR function, and to Jenda Krynicky for
813 being a light in the world.
814 .PP
815 Special thanks to Jarkko Hietaniemi, the 5.8.0 pumpking, for including
816 this module in the core and for his patient and helpful guidance
817 during the integration process.
818 .SH AUTHOR
819 .IX Header "AUTHOR"
820 Mark Jason Dominus
821 .SH "COPYRIGHT AND LICENSE"
822 .IX Header "COPYRIGHT AND LICENSE"
823 This software is copyright (c) 2012 by Mark Jason Dominus.
824 .PP
825 This is free software; you can redistribute it and/or modify it under
826 the same terms as the Perl 5 programming language system itself.