Exercise 4.29

Source code for Exercise 4.29.
We know that recursive procedures benefit greatly from memoisation and so our old friend fib would be a good candidate to show the benefits of a memoised force-it

(display-line "Defining the fib procedure")
(collect-garbage)
(time 
 (run-interpreter '(define (fib n)
                     (cond ((= n 0) 0)
                           ((= n 1) 1)
                           (else (+ (fib (- n 1))
                                    (fib (- n 2))))))))
(display-line "Calling fib 3 times")
(let loop ((i 3))
  (cond ((zero? i) 'done)
        (else (collect-garbage)
              (time (run-interpreter '(fib 17)))
              (loop (- i 1)))))

The non-memoised results.

Defining the fib procedure
cpu time: 3 real time: 1 gc time: 0
'ok
Calling fib 3 times
cpu time: 1463 real time: 1464 gc time: 0
cpu time: 1473 real time: 1473 gc time: 0
cpu time: 1456 real time: 1457 gc time: 0

The memoised results.

Defining the fib procedure
cpu time: 0 real time: 2 gc time: 0
'ok
Calling fib 3 times
cpu time: 364 real time: 363 gc time: 0
cpu time: 380 real time: 384 gc time: 0
cpu time: 380 real time: 380 gc time: 0

Note that there is no garbage collection taking place in the timings and so this is a fairly good indication of the difference memoisation makes. But in a real world program, memoisation would cause the creation of far more data, causing more space to be used. It’s very likely that this would cause a lot more garbage collection to take place as space is more limited for storing data.

For the non-memoised version of square the value of count is 2, but for the memoised version the value of count is 1.

The reason is that within square, the argument (id 10) is bound to x as a thunk and when evaluating (* x x), the thunk is evaluated twice, once for each reference to x. In the memoising evaluator (id 10) is also bound to x as a thunk, but the first time it is referenced in the expression (* x x) it’s value is calculated and memoised. The second reference simply returns it’s value and so doesn’t evaluate the body of (id 10) a second time.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s