Mercurial > octave

comparison doc/interpreter/vectorize.txi @ 31247:3dae836c598c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
doc: Expand and edit documentation for memoization (bug #60860)
author Arun Giridhar <arungiridhar@gmail.com>
date Fri, 30 Sep 2022 06:38:59 -0400
parents 43a6be589387
children f957849b2ba5
comparison
equal deleted inserted replaced
31246:43a6be589387 31247:3dae836c598c
553 @DOCSTRING(accumdim) 553 @DOCSTRING(accumdim)
554 554
555 @node Memoization 555 @node Memoization
556 @section Memoization Techniques 556 @section Memoization Techniques
557 557
558 Memoization is a technique to cache the results of slow function calls and return the cached value when the function is called with the same inputs again, instead of reevaluating it. It is very common to replace function calls with lookup tables if the same inputs are happening over and over again in a known, predictable way. Memoization is, at its core, an extension of this practice where the lookup table is extended even during runtime for new arguments not seen previously. A basic theoretical background can be found on Wikipedia or any undergraduate-level computer science textbook. 558 Memoization is a technique to cache the results of slow function calls and
559 559 return the cached value when the function is called with the same inputs again,
560 Octave's @code{memoize} function provides drop-in memoization functionality for any user function or Octave function, including compiled functions. To memoize a function @code{z = foo(x, y)}, use this pattern: 560 instead of reevaluating it. It is very common to replace function calls with
561 lookup tables if the same inputs are happening over and over again in a known,
562 predictable way. Memoization is, at its core, an extension of this practice
563 where the lookup table is extended even during runtime for new arguments not
564 seen previously. A basic theoretical background can be found on Wikipedia or
565 any undergraduate-level computer science textbook.
566
567 Octave's @code{memoize} function provides drop-in memoization functionality for
568 any user function or Octave function, including compiled functions.
569
570 @DOCSTRING(memoize)
571
572 To memoize a function @code{z = foo(x, y)}, use this general pattern:
561 573
562 @example 574 @example
563 @group 575 @group
564 foo2 = memoize (@@(@var{x, y}) @var{foo(x, y)}); 576 foo2 = memoize (@@(@var{x, y}) @var{foo(x, y)});
565 z = foo2 (x, y); 577 z = foo2 (x, y);
566 @end group 578 @end group
567 @end example 579 @end example
568 580
569 In the above example, the first line creates a memoized version @code{foo2} of the function @code{foo}. For simple functions with only trivial wrapping, this line can also be shortened to 581 In the above example, the first line creates a memoized version @code{foo2} of
582 the function @code{foo}. For simple functions with only trivial wrapping, this
583 line can also be shortened to
570 @example 584 @example
571 @group 585 @group
572 foo2 = memoize (@@foo); 586 foo2 = memoize (@@foo);
573 @end group 587 @end group
574 @end example 588 @end example
575 589
576 The second line @code{z = foo2 (x, y);} calls that memoized version @code{foo2} instead of the original function, allowing @code{memoize} to intercept the call and replace it with a looked-up value from a table if the inputs have occurred before, instead of evaluating the original function again. Note that this will not accelerate the @emph{first} call to the function but only subsequent calls. 590 The second line @code{z = foo2 (x, y);} calls that memoized version @code{foo2}
577 591 instead of the original function, allowing @code{memoize} to intercept the call
578 Note that due to the overhead incurred by @code{memoize} to create and manage the lookup tables for each function the user seeks to memoize, this technique is useful only for functions that take a significant time to execute, at least a few seconds. Such functions can be replaced by table lookups taking only a millisecond or less, but if the original function itself was taking only milliseconds or microseconds, memoizing it will not speed it up. 592 and replace it with a looked-up value from a table if the inputs have occurred
579 593 before, instead of evaluating the original function again. Note that this will
580 Octave's memoization also allows the user to clear the cache of lookup values when it is no longer needed, using the function @code{clearAllMemoizedCaches}. 594 not accelerate the @emph{first} call to the function but only subsequent calls.
595
596 Note that due to the overhead incurred by @code{memoize} to create and manage
597 the lookup tables for each function the user seeks to memoize, this technique
598 is useful only for functions that take a significant time to execute, at least
599 a few seconds. Such functions can be replaced by table lookups taking only a
600 millisecond or less, but if the original function itself was taking only
601 milliseconds or microseconds, memoizing it will not speed it up.
602
603 Octave's memoization also allows the user to clear the cache of lookup values
604 when it is no longer needed, using the function @code{clearAllMemoizedCaches}.
605
606 @DOCSTRING(clearAllMemoizedCaches)
581 607
582 @node Miscellaneous Techniques 608 @node Miscellaneous Techniques
583 @section Miscellaneous Techniques 609 @section Miscellaneous Techniques
584 @cindex execution speed 610 @cindex execution speed
585 @cindex speedups 611 @cindex speedups