[Cuis-dev] memoizing a method

[Mark Volkmann]

Thanks for the feedback! I added this class method in Object so I can clear
the memoized values for a given class and/or method:

clearMemo: aString
    "Delete all memoized entries from Smalltalk Dictionary whose keys
    begin with 'memo-' followed by a given string."
    | prefix |

    prefix := 'memo-', aString.
    Smalltalk keys do: [ :key |
        key isSymbol and: [key asString beginsWith: prefix] :: ifTrue: [
Smalltalk removeKey: key ].
   ].

Of course we can still run out of memory if this is not used at some point
and the results of a large number of argument combinations get cached.

I changed the key prefix from 'cache-' to 'memo-' to more clearly
associate them with the memoize method.

The key I'm using does capture the class, selector, and the arguments, but
not a specific receiver object. Here's an example key for calls to the
class method indentDepth in the class ParseTree: #'memo-ParseTree
class>>indentDepth:'

Would it be more appropriate to add the memoize: and clearMemo: methods to
the Behavior class instead of the Object class? Perhaps the answer is that
they shouldn't be added to either of those.

On Fri, Dec 6, 2024 at 12:39 AM Luciano Notarfrancesco <luchiano at gmail.com>
wrote:

> It’s an interesting idea, but this implementation could cause problems.
> For example, the cache only grows, and over time you run out of memory. And
> the symbol you create should uniquely identify with the message (receiver,
> selector, arguments), maybe you should use the message itself as key
> instead? But even considering those things, I’m not sure this is a
> practical idea that I’d use in my code.
>
> Have you used a Smalltalk with support for instance-specific methods? I
> have some objects that are immutable in some sense (equality is invariant
> over the instances lifetime, but they can change state as long as it
> doesn’t break that invariant, for example to cache computations, or to do
> lazy initialization and let some data be computed only when needed). These
> objects often implement some unary messages that are “pure functions”, i.e.
> they will always compute the same value for a given instance, so they could
> be cached. I normally cache them in a properties dictionary that each
> instance has, sometimes in an instance variable, but if we had
> instance-specific methods I could just use that. For example, say you want
> to do this for the average of #(1 2 3), then you implement the method
> >>#average so that at the end, before returning the computed value, adds a
> new instance method #average to the receiver that stores that value as a
> literal and just returns that value, i.e. a method that decompiled would
> look like this:
>
> average
>     ^ 2
>
> The next time you send #average to #(1 2 3) it it will just return the
> stored value, only for the instance #(1 2 3).
>
> I don’t think there’s any plan to support this in Cuis or the
> OpenSmalltalk VM, tho.
>
> Cheers,
> Luciano
>
>
> On Fri, Dec 6, 2024 at 04:24 Mark Volkmann via Cuis-dev <
> cuis-dev at lists.cuis.st> wrote:
>
>> Certainly it's not common to want to memoize a method, but I was
>> wondering if it would be easy to do. I came up with the following that
>> works well. I'd be interested in hearing whether there is a better approach
>> and whether something like this is already in the base image and I just
>> haven't found it yet.
>>
>> I added the Object instance method memoize: which takes a block.
>> This caches previously computed values in an IdentityDictionary
>> that is saved in Smalltalk which is also an IdentityDictionary.
>>
>> memoize: aBlock
>>     | cache cacheKey sender valueKey |
>>
>>     sender := thisContext sender.
>>
>>     "Smalltalk is a SystemDictionary which is an IdentityDictionary.
>>     That is why cacheKey must be a Symbol."
>>     cacheKey := ('cache-', sender name) asSymbol.
>>
>>     cache := Smalltalk at: cacheKey ifAbsentPut: [ IdentityDictionary new
>> ].
>>     valueKey := thisContext name, sender arguments asString :: asSymbol.
>>
>>     ^ cache at: valueKey ifAbsentPut: [ aBlock value ].
>>
>> Using the memoize: method is demonstrated in the class method average:
>> below
>> (added to any class) which takes an array of numbers.
>>
>> average: numberArray
>>     ^ self memoize: [
>>         | sum |
>>         'computing average' print.
>>         sum := numberArray fold: [:acc :n | acc + n].
>>         sum / numberArray size.
>>     ].
>>
>>
>> --
>> R. Mark Volkmann
>> Object Computing, Inc.
>> --
>> Cuis-dev mailing list
>> Cuis-dev at lists.cuis.st
>> https://lists.cuis.st/mailman/listinfo/cuis-dev
>>
>

-- 
R. Mark Volkmann
Object Computing, Inc.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cuis.st/mailman/archives/cuis-dev/attachments/20241206/b66d7c19/attachment-0001.htm>