Thursday, October 26, 2023
A couple of days ago an interesting article was posted about the performance impact of the memoization idiom on modern Ruby. It covers some of the internal changes that have been happening in the last few releases of Ruby and how some “object shape” optimizations have impacted memoization performance.
If you look at the Wikipedia article for memoization, you can see it described as:
In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls to pure functions and returning the cached result when the same inputs occur again.
While I use the memoize vocabulary in some of the posts on this blog and it is used in over 100 words in the Factor standard library, there is an opportunity to talk a bit more about how it works in Factor.
The first example often provided to show the benefit is a recursive definition of the Fibonacci sequence, which could be implemented as:
: fib ( m -- n ) dup 1 > [ [ 2 - fib ] [ 1 - fib ] bi + ] when ;
If you time this, it is quite slow:
IN: scratchpad [ 40 fib ] time . Running time: 1.800567 seconds 102334155
In a similar manner to the functools.cache decorator in
can easily improve this by caching the results of previous computations by
MEMO: syntax which works with any
MEMO: fib ( m -- n ) dup 1 > [ [ 2 - fib ] [ 1 - fib ] bi + ] when ;
And see that it is now much faster:
IN: scratchpad [ 40 fib ] time . Running time: 0.005302375 seconds 102334155
If we wanted to memoize some internal part of a word, we have historically used words like cache or 2cache with a hashtable literal to compute a result by key, storing and returning if it was previously calculated. This is a simple form of memoization – and I realized that we could create a simpler syntax for this that uses the memoize implementation to support arbitrary quotations:
SYNTAX: MEMO[ parse-quotation dup infer memoize-quot append! ;
And then we use it in the middle of a word, pretending that something takes a long time to compute and we need to memoize the computation:
: answer ( a b -- ) "The answer is: " write MEMO[ + 1 seconds sleep ] . ;
Trying it out shows that the first time is slow and the second time is fast:
IN: scratchpad [ 1 2 answer ] time The answer is: 3 Running time: 1.011060583 seconds IN: scratchpad [ 1 2 answer ] time The answer is: 3 Running time: 0.00117075 seconds
That’s a cool syntax word – and it’s available in the memoize.syntax vocabulary!