bugGNU Octave - Bugs: bug #60860, Implementation of memoize


bug #60860: Implementation of memoize

Submitted by:  Guillaume <gyom>
Submitted on:  Wed 30 Jun 2021 02:48:42 PM UTC  
Category:  Octave Function Severity:  1 - Wish
Priority:  1 - Later Item Group:  Feature Request
Status:  Patch Submitted Assigned to:  None
Originator Name:  Guillaume Open/Closed:  Open
Release:  dev Operating System:  Any

Add a New Comment (Rich Markup)

You are not logged in

Please log in, so followups can be emailed to you.


( Jump to the original submission)

Wed 01 Dec 2021 02:40:34 AM UTC, comment #7: 

Thank you for the feedback Guillaume.

The documentation must not be long and a small explaining example is sufficient.  You can also just post it here as comment and I can complete your great work.

Until then I mark it as "dev".

Kai Torben Ohlhus <siko1056>
Project Member
Tue 30 Nov 2021 12:06:12 PM UTC, comment #6: 

Thank you Kai for the comments and creating a patch.

You are right that this would require further documentation before being pushed. I don't have time for this right now and there doesn't seem to be much interest in that functionality so perhaps it could be considered in a future release and left here if ever someone wanted to use it (as it's pure m-code).

Guillaume <gyom>
Thu 25 Nov 2021 07:02:35 AM UTC, comment #5: 

Thanks for you contribution @gyom.  I created a proper patch from the zip archive (file #52341).

The function looks great, only m-code, thus not much danger for Octave 7 to be added. 👍

I would love push the patch, if more documentation is added to the main function "memoize" and maybe a small documentation section in the manual


could be added.  If you think you cannot make it before the Octave 7 release (beginning of 2022) we should remove the release tag and take more time to document it.

Please also add a good example showing where this function helps speeding up and where most likely not, see my critics below. 😇

Crititcs to the Matlab inventors: After looking at this function, I feel much less excited about it.  The technique seems very dull and maybe useful for Octave/Matlab beginners, lazy programmers, or benchmark forgeries.  In my humble opinion this function supports bad programming practice, e.g. code repetition (plain copy&paste).

Saving an expensively computed output for later usage manually inside a script or function seems to me much faster than saving and compairing input-output pairs for a function in an wrapper object for later replay 😓  This can only be beneficial if input and output are mostly scalars and the function is really often called during a single Octave session...

Kai Torben Ohlhus <siko1056>
Project Member
Thu 08 Jul 2021 09:00:44 AM UTC, comment #4: 

Thanks for testing. I don't think you do anything wrong. I see memoize more useful for caching the output of lengthy computations (taking more time than the caching overhead). You see something similar when running your example in Matlab:

>> NN = 255; x = zeros(1,NN); tic; for i = 1:NN, x(i) = nonmemo(i); end;toc
Elapsed time is 0.004546 seconds.
>> NN = 1023; x = zeros(1,NN); tic; for i = 1:NN, x(i) = nonmemo(i);end;toc
Elapsed time is 0.005433 seconds.
>> NN = 255; x = zeros(1,NN); tic; for i = 1:NN, x(i) = memo(i); end;toc
Elapsed time is 0.090636 seconds.
>> NN = 1023; x = zeros(1,NN); tic; for i = 1:NN, x(i) = memo(i);end;toc
Elapsed time is 0.208253 seconds.

Guillaume <gyom>
Thu 08 Jul 2021 12:35:31 AM UTC, comment #3: 

Hello Guillaume,

Thank you for this feature addition. I tried it and unfortunately it seemed to slow down the execution by roughly 15 times. Please tell me if I am misusing it.

Here is how I set it up, using anonymous functions for both the memoized and nonmemoized versions:

octave:1> addpath ("memoize")
octave:2> nonmemo = @(f) bitcountnaive(f)
nonmemo =

@(f) bitcountnaive (f)

octave:3> memo = memoize (@(g) bitcountnaive(g))
memo =

  matlab.lang.MemoizedFunction m_object with properties:

      CacheSize: [1x1 double]
        Enabled: 1
       Function: [1x1 function_handle]

Test without memoization:

octave:4> NN = 255; x = zeros(1,NN); tic; for i = 1:NN, x(i) = nonmemo(i); end; toc
Elapsed time is 0.01684 seconds.
octave:6> NN = 1023; x = zeros(1,NN); tic; for i = 1:NN, x(i) = nonmemo(i); end; toc
Elapsed time is 0.084712 seconds.

Test with memoization:

octave:5> NN = 255; x = zeros(1,NN); tic; for i = 1:NN, x(i) = memo(i); end; toc
Elapsed time is 0.327858 seconds.
octave:7> NN = 1023; x = zeros(1,NN); tic; for i = 1:NN, x(i) = memo(i); end; toc
Elapsed time is 1.31426 seconds.

The test function bitcountnaive is deliberately chosen to be something that could benefit from memoization because most of its internal calls have identical substructures, so the thinking is that subsequent calls of the same value will make use of the memoization lookup table instead of calling the recursive function:

function retval = bitcountnaive (n)
  if (n <= 0)
    retval = 0;
  elseif (mod(n,2) == 1) # odd
    retval = 1 + bitcountnaive (floor(n/2));
  else # even
    retval = bitcountnaive (floor(n/2));

What am I doing wrong?

Wed 30 Jun 2021 05:40:21 PM UTC, comment #2: 

I attach a new version implementing clearCache() and stats(). I also defined a new undocumented function _memoize_() that stores the persistent array of memoized functions. I think it is now feature complete.

(file #51630)

Guillaume <gyom>
Wed 30 Jun 2021 02:58:04 PM UTC, comment #1: 

I just notice the clearCache function:
the stats functionality:
and the explicit description of the Cache structure in the examples of these functions:

This should be fairly easy to implement. My main question is with respect of the use of the persistent variable.

Guillaume <gyom>
Wed 30 Jun 2021 02:48:42 PM UTC, original submission:  

There is a memoize functionality in Matlab wince R2017a:

I attach an early attempt to implement it and would welcome feedback.

Running the following in Matlab indicates that a handle class matlab.lang.MemoizedFunction has to be defined. To implement the fact that the memoizing the same function handle returns the same object, I store all of them in a persistent variable in the memoize function. That said, the clearAllMemoizedCaches function would require access to that variable too so there could be an undocumented syntax in memoize that could be called from clearAllMemoizedCaches or there need to be a separate function to take on the role of keeping track of all memoized function handles.

>> a = memoize(@sin);
>> whos a
  Name    Size    Bytes    Class
  a       1x1         8    matlab.lang.MemoizedFunction
>> a
a =
  MemoizedFunction with properties:
     Function: @sin
      Enabled: 1
    CacheSize: 10
>> b = a;
>> a.Enabled = 0;
>> b
b =
  MemoizedFunction with properties:
     Function: @sin
      Enabled: 0
    CacheSize: 10
>> c = memoize(@sin)
c =
  MemoizedFunction with properties:
     Function: @sin
      Enabled: 0
    CacheSize: 10
>> struct(c)
ans =
  struct with fields:

            Function: @sin
             Enabled: 0
           CacheSize: 10
               Cache: [1x1 struct]
    PrivateCacheSize: 10
      TracingEnabled: 0
             Version: 1
       CachingPolicy: 'CB'
>> ans.Cache
ans =
  struct with fields:
         Inputs: {}
        Nargout: []
        Outputs: {}
       HitCount: []
           Load: 0
      TotalHits: 0
    TotalMisses: 0

Guillaume <gyom>


(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:

Attached Files
file #52341:  bug_60860_memoize.patch added by siko1056 (16KiB - text/x-patch)
file #51630:  memoize.zip added by gyom (5KiB - application/zip)
file #51629:  memoize.zip added by gyom (4KiB - application/zip)


Depends on the following items: None found

Items that depend on this one: None found


Carbon-Copy List
  • -email is unavailable- added by siko1056 (Updated the item)
  • -email is unavailable- added by jwe (Updated the item)
  • -email is unavailable- added by gyom (Submitted the item)

    Do you think this task is very important?
    If so, you can add your encouragement to it.
    This task has 0 encouragements so far.

    Only project members can vote.




    Follow 10 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2021-12-01 siko1056 Priority5 - Normal => 1 - Later
        StatusNeed Info => Patch Submitted
        Release7.0.90 => dev
    2021-11-25 siko1056 StatusPatch Submitted => Need Info
    2021-11-25 siko1056 Attached File- => Added bug_60860_memoize.patch, #52341
    2021-11-17 siko1056 Releasedev => 7.0.90
    2021-07-26 jwe Severity3 - Normal => 1 - Wish
        StatusNone => Patch Submitted
    2021-06-30 gyom Attached File- => Added memoize.zip, #51630
    2021-06-30 gyom Attached File- => Added memoize.zip, #51629

    Back to the top

    Powered by Savane 3.7