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:  5 - Normal 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.

 

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));
  end
endfunction

What am I doing wrong?

Anonymous
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:
https://www.mathworks.com/help/matlab/ref/clearcache.html
the stats functionality:
https://www.mathworks.com/help/matlab/ref/stats.html
and the explicit description of the Cache structure in the examples of these functions:
https://www.mathworks.com/help/matlab/ref/memoizedfunction.html
https://www.mathworks.com/help/matlab/ref/clearallmemoizedcaches.html

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:
https://www.mathworks.com/help/matlab/ref/memoize.html

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:
   
   
Comment:
   

Attached Files
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 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 4 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    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.6