Exercise 4.24

Source code for Exercise 4.24.
I already ran timings to compare the two versions of the evaluator in Exercise 4.22 but I’ll try something else here. I’m timing how long it takes to define 2 procedures and then to call those procedures in a loop.

   (run-interpreter '(define (factorial n)
                       (if (< n 2)
                           (* (factorial (- n 1)) n))))
   (run-interpreter '(define (fib n)
                       (cond ((= n 0) 0)
                             ((= n 1) 1)
                             (else (+ (fib (- n 1)) (fib (- n 2)))))))
   (do ((i 1 (+ i 1)))
     ((> i 500) 'complete)
     (run-interpreter '(factorial 50)))
   (do ((j 1 (+ j 1)))
     ((> j 20) 'complete)
     (run-interpreter '(fib 20)))))

Without analysis over 3 runs I get:

cpu time: 23649 real time: 23699 gc time: 906
cpu time: 23612 real time: 23619 gc time: 893
cpu time: 23255 real time: 23269 gc time: 895

With analysis over 3 runs I get:

cpu time: 9322 real time: 9334 gc time: 950
cpu time: 9416 real time: 9431 gc time: 955
cpu time: 9256 real time: 9257 gc time: 940

That’s quite an improvement on highly iterative procedures. That’s not so surprising though as each recursive call forces the version without analysis to re-interpret the procedure again rather than just evaluate the procedure created by analysis. In short re-interpreting the same code over and over is less efficient than analysing it once and transforming it into a procedure.


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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s