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