Memoization in Factor
Thursday, January 25, 2007
I implemented a simple memoization library in libs/memoize
. If you’re
not familiar with this term, read about Memoization on
Wikipedia.
This library can create memoized forms of words taking between 0 and 4
inputs, and one or more output. Usage is very simple – just replace :
with MEMO:
, and ensure you have a stack effect declaration.
Here is the old inefficient fibonacci:
: fib ( m -- n )
dup 1 <= [ drop 1 ] [ dup 1 - fib swap 2 - fib + ] if ;
[ 34 fib ] time
1842 ms run / 0 ms GC time
Now lets define a memoized version:
MEMO: fib ( m -- n )
dup 1 <= [ drop 1 ] [ dup 1 - fib swap 2 - fib + ] if ;
[ 34 fib ] time
0 ms run / 0 ms GC time
Well, that’s a nice improvement, 1842/0 = infinity times faster ;-) And
only one change was necessary, the replacement of :
with MEMO:
.
I decided to implement this after seeing Dan’s ONCE:
word. Basically
its a restricted form of memoization, where you have a word which
performs a lengthy computation on no inputs the first time, and caches
the result for subsequent calls:
ONCE: big-number 1000 factorial ;
This was used in the XML parser to build up fast lookup bit sets classifying Unicode characters from a more declarative description (see char-class.factor).
My MEMO:
word generalizes ONCE:
; if the word being memoized has no
inputs, then it simply caches the result the first time it is called.
Take a look at libs/memoize/memoize.factor; I think it is pretty elegant.
Update Dan contributed some documentation, and made this work with words producing more than one output. Thanks Dan.