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

 
 

bug #60860: Implementation of memoize

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

Add a New Comment Rich Markup
   

Jump to the original submission

Tue 25 Oct 2022 07:59:13 PM UTC, comment #13: 

No further feedback in 3 weeks. Closing as fixed.

Arun Giridhar <arungiridhar>
Group Member
Fri 30 Sep 2022 10:42:56 AM UTC, comment #12: 

Thanks @mmuetzel. I edited the doc here incorporating your points: https://hg.savannah.gnu.org/hgweb/octave/rev/3dae836c598c

Arun Giridhar <arungiridhar>
Group Member
Fri 30 Sep 2022 07:22:40 AM UTC, comment #11: 

I haven't tested yet. Just some general remarks:

  • The help text (`help memoize`) is very sparse. There should be at least a one-line description of what the function does. Better yet a more detailed description of (at least) the relevant input and output parameters.
  • There is no hook (`@DOCSTRING(memoize)`) to that help text in the manual yet. IIUC, that is necessary to open the relevant part of the documentation, e.g., with `doc memoize`. The same is true for the function `clearAllMemoizedCaches`.
  • The added lines in vectorize.txi are very long. Afaict, they should be broken to max. 80 characters.
Markus Mรผtzel <mmuetzel>
Group administrator
Fri 30 Sep 2022 12:38:47 AM UTC, comment #10: 

I've pushed the new patch here under Guillaume's name: https://hg.savannah.gnu.org/hgweb/octave/rev/a887ffb997a7

I pushed an additional documentation patch here: https://hg.savannah.gnu.org/hgweb/octave/rev/43a6be589387

Marking as Ready For Test.

Arun Giridhar <arungiridhar>
Group Member
Tue 27 Sep 2022 08:46:46 PM UTC, comment #9: 

Updated patch attached. Functionality is unchanged from the previous patch in comment #5. The news is now in NEWS.8.md instead of NEWS.

I intend to bring this into Octave 8, as discussed in today's dev meeting. I will be adding a case study to the docs / Discourse in the next few days.


(file #53760)

Arun Giridhar <arungiridhar>
Group Member
Sun 11 Sep 2022 07:46:26 PM UTC, comment #8: 

I accidentally deleted an attachment while trying to download it for testing! I'm so sorry! Guillaume, could you upload the file memoize.zip again please?

Arun Giridhar <arungiridhar>
Group Member
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>
Group 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

https://octave.org/doc/v6.4.0/Vectorization-and-Faster-Code-Execution.html

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>
Group 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));
  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 #53760:  new.patch added by arungiridhar (16KiB - text/x-patch)
file #52341:  bug_60860_memoize.patch added by siko1056 (16KiB - text/x-patch)
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 mmuetzel (Posted a comment)
  • -email is unavailable- added by arungiridhar (Posted a comment)
  • -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)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only group members can vote.

     

    Follow 15 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2022-10-25 arungiridhar StatusReady For Test Fixed
        Open/ClosedOpen Closed
    2022-09-30 arungiridhar StatusPatch Submitted Ready For Test
    2022-09-27 arungiridhar Attached File- Added new.patch, #53760
    2022-09-11 arungiridhar Attached File#51630 Removed
    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.13-f8d8.
    Corresponding source code