# HG changeset patch # User Guillaume Flandin # Date 1664309565 14400 # Node ID a887ffb997a7cb074d9fa9121f72fa265e027457 # Parent 80a0905905be8260213b154f53704d06f56334c5 New function memoize to optimize repetitive function calls (bug #60860). * scripts/miscellaneous/clearAllMemoizedCaches.m: new function. * scripts/miscellaneous/memoize.m: new function. * scripts/miscellaneous/private/__memoize__.m: new function. * scripts/miscellaneous/module.mk: add new functions to build system. * scripts/+matlab/+lang/MemoizedFunction.m: new function. * scripts/+matlab/+lang/module.mk: add new functions to build system. diff -r 80a0905905be -r a887ffb997a7 etc/NEWS.8.md --- a/etc/NEWS.8.md Wed Sep 28 17:05:06 2022 -0400 +++ b/etc/NEWS.8.md Tue Sep 27 16:12:45 2022 -0400 @@ -76,6 +76,9 @@ ### Alphabetical list of new functions added in Octave 8 +* `clearAllMemoizedCaches` +* `matlab.lang.MemoizedFunction` +* `memoize` * `pagectranspose` * `pagetranspose` * `uifigure` diff -r 80a0905905be -r a887ffb997a7 scripts/+matlab/+lang/MemoizedFunction.m --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/scripts/+matlab/+lang/MemoizedFunction.m Tue Sep 27 16:12:45 2022 -0400 @@ -0,0 +1,203 @@ +######################################################################## +## +## Copyright (C) 2021 The Octave Project Developers +## +## See the file COPYRIGHT.md in the top-level directory of this +## distribution or . +## +## This file is part of Octave. +## +## Octave is free software: you can redistribute it and/or modify it +## under the terms of the GNU General Public License as published by +## the Free Software Foundation, either version 3 of the License, or +## (at your option) any later version. +## +## Octave is distributed in the hope that it will be useful, but +## WITHOUT ANY WARRANTY; without even the implied warranty of +## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +## GNU General Public License for more details. +## +## You should have received a copy of the GNU General Public License +## along with Octave; see the file COPYING. If not, see +## . +## +######################################################################## + + +classdef MemoizedFunction < handle + + properties (GetAccess = public, SetAccess = private) + Function = []; + endproperties + + properties (Access = public) + Enabled = true; + CacheSize = 10; + endproperties + + properties (Access = private, Hidden = true) + Cache; + endproperties + + methods (Access = public) + + function this = MemoizedFunction (fcn_handle) + if (! isa (fcn_handle, "function_handle")) + error (["matlab.lang.MemoizedFunction: FCN_HANDLE must be a ", ... + "function handle"]); + endif + this.Function = fcn_handle; + this.Cache = init_cache (); + endfunction + + function varargout = subsref (this, s) + switch (s(1).type) + case "." + switch (s(1).subs) + case "Function" + varargout{1} = this.Function; + case "Enabled" + varargout{1} = this.Enabled; + case "CacheSize" + varargout{1} = this.CacheSize; + case "clearCache" + clearCache (this); + varargout = {}; + case "stats" + varargout{1} = stats (this); + otherwise + error ("matlab.lang.MemoizedFunction: unknown property '%s'", ... + s(1).subs); + endswitch + case "()" + n_out = ifelse (nargout == 0, 1, nargout); + if (! this.Enabled) + [varargout{1:n_out}] = feval (this.Function, s(1).subs{:}); + else + cache_idx = []; + for i=1:numel (this.Cache.Inputs) + if (isequaln (this.Cache.Inputs{i}, s(1).subs) ... + && isequal (this.Cache.Nargout(i), nargout)) + cache_idx = i; + break; + endif + endfor + if (! isempty (cache_idx)) + [varargout{1:n_out}] = deal (this.Cache.Outputs{cache_idx}{:}); + this.Cache.TotalHits += 1; + this.Cache.HitCount(cache_idx) += 1; + else + [varargout{1:n_out}] = feval (this.Function, s(1).subs{:}); + n = numel(this.Cache.Inputs) + 1; + if (n > this.CacheSize) + this.Cache.Inputs(1) = []; + this.Cache.Nargout(1) = []; + this.Cache.Outputs(1) = []; + this.Cache.HitCount(1) = []; + n -= 1; # FIFO + endif + this.Cache.Inputs{n} = s(1).subs; + this.Cache.Nargout(n) = nargout; + this.Cache.Outputs{n} = varargout; + this.Cache.HitCount(n) = 0; + this.Cache.TotalMisses += 1; + endif + endif + otherwise + error (["matlab.lang.MemoizedFunction: only '()' indexing is ", ... + "supported"]); + endswitch + if (numel (s) > 1) + varargout{1} = subsref (varargout{1}, s(2:end)); + endif + endfunction + + function this = subsasgn (this, s, val) + if (numel (s) > 1) + error (["matlab.lang.MemoizedFunction: only one level of indexing ", ... + "is supported"]); + endif + switch (s(1).type) + case "." + switch (s(1).subs) + case "Function" + error (["matlab.lang.MemoizedFunction: property Function is ", ... + "read-only"]); + case "Enabled" + if (! isscalar (val) || ! (isnumeric (val) || islogical (val)) ... + || ! isfinite (val)) + error (["matlab.lang.MemoizedFunction: Enabled must be a ", ... + "logical scalar"]); + endif + this.Enabled = logical (val); + case "CacheSize" + if (! isscalar (val) || ! isnumeric (val) || ! isfinite (val) ... + || ceil (val) != val || val < 1) + error (["matlab.lang.MemoizedFunction: CacheSize must ", ... + "be a positive integer scalar"]) + endif + this.CacheSize = double (val); + n = numel(this.Cache.Inputs) - this.CacheSize; + if (n > 0) + this.Cache.Inputs(1:n) = []; + this.Cache.Nargout(1:n) = []; + this.Cache.Outputs(1:n) = []; + this.Cache.HitCount(1:n) = []; + endif + otherwise + error ("matlab.lang.MemoizedFunction: unknown property '%s'", ... + s(1).subs); + endswitch + otherwise + error (["matlab.lang.MemoizedFunction: only '.' indexing is ", ... + "supported for assigning values"]); + endswitch + endfunction + + function clearCache (this) + if (nargin > 1 || nargout) + error ("matlab.lang.MemoizedFunction: Invalid call"); + endif + this.Cache = init_cache (); + endfunction + + function s = stats (this) + if (isempty (this.Cache.Inputs)) + CacheHitRatePercent = 0; + CacheOccupancyPercent = 0; + MostHitCachedInput = []; + else + CacheHitRatePercent = (this.Cache.TotalHits / ... + (this.Cache.TotalHits + this.Cache.TotalMisses)) * 100; + CacheOccupancyPercent = numel (this.Cache.Inputs) / this.CacheSize * 100; + [~, i] = max (this.Cache.HitCount); + MostHitCachedInput = struct ("Hits", this.Cache.HitCount(i), ... + "Input", {this.Cache.Inputs{i}}); + endif + s = struct (... + "Cache", this.Cache, ... + "MostHitCachedInput", MostHitCachedInput, ... + "CacheHitRatePercent", CacheHitRatePercent, ... + "CacheOccupancyPercent", CacheOccupancyPercent); + endfunction + + function newobj = horzcat (varargin) + error ("matlab.lang.MemoizedFunction: concatenation is not allowed"); + endfunction + + function newobj = horzcat (varargin) + error ("matlab.lang.MemoizedFunction: concatenation is not allowed"); + endfunction + + endmethods + +endclassdef + +function cache = init_cache () +cache = struct ("Inputs", {{}}, ... + "Nargout", [], ... + "Outputs", {{}}, ... + "HitCount", [], ... + "TotalHits", 0, ... + "TotalMisses", 0); +endfunction diff -r 80a0905905be -r a887ffb997a7 scripts/+matlab/+lang/module.mk --- a/scripts/+matlab/+lang/module.mk Wed Sep 28 17:05:06 2022 -0400 +++ b/scripts/+matlab/+lang/module.mk Tue Sep 27 16:12:45 2022 -0400 @@ -2,7 +2,8 @@ %canon_reldir%_FCN_FILES = \ %reldir%/makeUniqueStrings.m \ - %reldir%/makeValidName.m + %reldir%/makeValidName.m \ + %reldir%/MemoizedFunction.m %canon_reldir%dir = $(fcnfiledir)/+matlab/+lang diff -r 80a0905905be -r a887ffb997a7 scripts/miscellaneous/clearAllMemoizedCaches.m --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/scripts/miscellaneous/clearAllMemoizedCaches.m Tue Sep 27 16:12:45 2022 -0400 @@ -0,0 +1,44 @@ +######################################################################## +## +## Copyright (C) 2021 The Octave Project Developers +## +## See the file COPYRIGHT.md in the top-level directory of this +## distribution or . +## +## This file is part of Octave. +## +## Octave is free software: you can redistribute it and/or modify it +## under the terms of the GNU General Public License as published by +## the Free Software Foundation, either version 3 of the License, or +## (at your option) any later version. +## +## Octave is distributed in the hope that it will be useful, but +## WITHOUT ANY WARRANTY; without even the implied warranty of +## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +## GNU General Public License for more details. +## +## You should have received a copy of the GNU General Public License +## along with Octave; see the file COPYING. If not, see +## . +## +######################################################################## + +## -*- texinfo -*- +## @deftypefn {} {} clearAllMemoizedCaches () +## Clear all memoized caches. +## +## @seealso{memoize} +## @end deftypefn + +function clearAllMemoizedCaches + + if (nargin || nargout) + print_usage (); + endif + + __memoize__ (); + +endfunction + +## Mark file as being tested. No real test needed for this function. +%!assert (1) diff -r 80a0905905be -r a887ffb997a7 scripts/miscellaneous/memoize.m --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/scripts/miscellaneous/memoize.m Tue Sep 27 16:12:45 2022 -0400 @@ -0,0 +1,73 @@ +######################################################################## +## +## Copyright (C) 2021 The Octave Project Developers +## +## See the file COPYRIGHT.md in the top-level directory of this +## distribution or . +## +## This file is part of Octave. +## +## Octave is free software: you can redistribute it and/or modify it +## under the terms of the GNU General Public License as published by +## the Free Software Foundation, either version 3 of the License, or +## (at your option) any later version. +## +## Octave is distributed in the hope that it will be useful, but +## WITHOUT ANY WARRANTY; without even the implied warranty of +## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +## GNU General Public License for more details. +## +## You should have received a copy of the GNU General Public License +## along with Octave; see the file COPYING. If not, see +## . +## +######################################################################## + +## -*- texinfo -*- +## @deftypefn {} {@var{mem_fcn_handle} =} memoize (@var{fcn_handle}) +## +## @seealso{clearAllMemoizedCaches} +## @end deftypefn + +function mem_fcn_handle = memoize (fcn_handle) + + if (nargin != 1 || nargout > 1) + print_usage (); + endif + if (! isa (fcn_handle, "function_handle")) + error ("memoize: FCN_HANDLE must be a function handle"); + endif + + mem_fcn_handle = __memoize__ (fcn_handle); + +endfunction + +%!test +%! fcn1 = memoize (@sin); +%! assert (isa (fcn1, "matlab.lang.MemoizedFunction")); +%! fcn1 (pi); +%! fcn2 = memoize (@sin); +%! fcn2 (2*pi); +%! assert (isequal (fcn1, fcn2)) + +%!test +%! fcn = memoize (@rand); +%! a = fcn (); +%! b = fcn (); +%! assert (a, b); +%! fcn2 = memoize (@rand); +%! c = fcn2 (); +%! assert (a, c); + +%!test +%! fcn = memoize (@plus); +%! fcn.stats; +%! stats (fcn); +%! clearCache (fcn); +%! fcn.clearCache; + +# Test input validation +%!error memoize (); +%!error memoize (1, 2); +%!error [a, b] = memoize (1); +%!error memoize (1); diff -r 80a0905905be -r a887ffb997a7 scripts/miscellaneous/module.mk --- a/scripts/miscellaneous/module.mk Wed Sep 28 17:05:06 2022 -0400 +++ b/scripts/miscellaneous/module.mk Tue Sep 27 16:12:45 2022 -0400 @@ -3,6 +3,7 @@ %reldir%/private %canon_reldir%_PRIVATE_FCN_FILES = \ + %reldir%/private/__memoize__.m \ %reldir%/private/__publish_html_output__.m \ %reldir%/private/__publish_latex_output__.m \ %reldir%/private/__w2mpth__.m \ @@ -15,6 +16,7 @@ %reldir%/bunzip2.m \ %reldir%/cast.m \ %reldir%/citation.m \ + %reldir%/clearAllMemoizedCaches.m \ %reldir%/clearvars.m \ %reldir%/compare_versions.m \ %reldir%/computer.m \ @@ -46,6 +48,7 @@ %reldir%/loadobj.m \ %reldir%/ls.m \ %reldir%/ls_command.m \ + %reldir%/memoize.m \ %reldir%/memory.m \ %reldir%/menu.m \ %reldir%/methods.m \ diff -r 80a0905905be -r a887ffb997a7 scripts/miscellaneous/private/__memoize__.m --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/scripts/miscellaneous/private/__memoize__.m Tue Sep 27 16:12:45 2022 -0400 @@ -0,0 +1,57 @@ +######################################################################## +## +## Copyright (C) 2021 The Octave Project Developers +## +## See the file COPYRIGHT.md in the top-level directory of this +## distribution or . +## +## This file is part of Octave. +## +## Octave is free software: you can redistribute it and/or modify it +## under the terms of the GNU General Public License as published by +## the Free Software Foundation, either version 3 of the License, or +## (at your option) any later version. +## +## Octave is distributed in the hope that it will be useful, but +## WITHOUT ANY WARRANTY; without even the implied warranty of +## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +## GNU General Public License for more details. +## +## You should have received a copy of the GNU General Public License +## along with Octave; see the file COPYING. If not, see +## . +## +######################################################################## + +## -*- texinfo -*- +## @deftypefn {} {@var{mem_fcn_handle} =} __memoize__ (@var{fcn_handle}) +## @deftypefn {} {} __memoize__ () +## Internal function used by memoize. +## +## @seealso{clearAllMemoizedCaches, memoize} +## @end deftypefn + +function mem_fcn_handle = __memoize__ (fcn_handle) + persistent cached_mem_fcn_handle + + if (nargin) + + for i=1:numel (cached_mem_fcn_handle) + if (isequal (cached_mem_fcn_handle{i}.Function, fcn_handle)) + mem_fcn_handle = cached_mem_fcn_handle{i}; + return; + endif + endfor + + mem_fcn_handle = matlab.lang.MemoizedFunction (fcn_handle); + cached_mem_fcn_handle{end+1} = mem_fcn_handle; + + else + + for i=1:numel (cached_mem_fcn_handle) + clearCache (cached_mem_fcn_handle{i}); + endfor + + endif + +endfunction