Re: Factor

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 Python, you can easily improve this by caching the results of previous computations by using the MEMO: syntax which works with any arity function:

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!