4.3 Memoization

Quite often some time-intensive function is called very frequently on only few values. Easy examples of this are simple recursive processes as the computation of binomial or Fibonacci numbers. In FEMLISP, this occurs at several places, e.g. when computing arbitrary dimensional reference elements and the corresponding refinement rules, when computing finite element data for those reference elements, and so on. A useful technique for accelerating programs in this case is so-called "memoization", which means storing already computed values in a table and retrieving them from there if possible.

Now, in Common Lisp, it is easy to construct a language extension which turns an existing function into a memoized one, see e.g. (Norvig 1992). The code is simply the following:

(defun memoize-symbol (funsym)
  "Memoizes the function named by the given symbol."
  (let ((unmemoized (symbol-function funsym))
        (table (make-hash-table :test #'equalp)))
    (setf (symbol-function funsym)
          #'(lambda (&rest args)
              (multiple-value-bind (value found)
                  (gethash args table)
                (if found
                    value
                    (setf (gethash args table)
                          (apply unmemoized args))))))))

An application of this technique to the recursive computation of Fibonacci numbers then yields something like the following:

* (declaim (notinline fib))
* (defun fib (n)                           * (memoize-symbol 'fib)
    (case n                                * (time (fib 35))                  
      (0 0) (1 1)                          ; Evaluation took:                  
      (t (+ (fib (- n 1))                  ;   0.0 seconds of real time       
            (fib (- n 2))))))              ;   0.0 seconds of user run time   
FIB                                        ;   8 bytes consed.              
* (compile 'fib)                           9227465                            
* (time (fib 35))                          * (time (fib 100))                 
; Evaluation took:                         ; Evaluation took:                 
;   1.31 seconds of real time              ;   0.0 seconds of real time       
;   1.3 seconds of user run time           ;   0.0 seconds of user run time   
;   0 bytes consed.                        ;   8 bytes consed.
9227465                                    354224848179261915075