sicp-ex-4.24



<< Previous exercise (4.23) | Index | Next exercise (4.25) >>


felix021

Below are 2 simple tests, loops and calculating fibonacci numbers.

 ; 4-24.test1.scm 
  
 (define (loop n) 
     (if (> n 0) 
         (loop (- n 1)))) 
  
 (loop 1000000) 
 (exit) 
 ; 4-24.test2.scm 
  
 (define (fib n) 
     (if (<= n 2) 
         1 
         (+ (fib (- n 1)) (fib (- n 2))))) 
  
 (fib 30) 
 (exit) 

My results are:

only eval: loop 9.689s, fib 18.880s

analyze + eval: loop 5.528s, fib 10.682s


master

I wanted to really put our interpreter to the test and see how long it would take it to compute A(4,1), i.e. the Ackermann function and I believe the highest value which is practical to compute. Well, after 40 minutes of waiting for the slow interpreter to finish I decided that it was not going to happen anytime soon. Therefore, I made it compute A(3,8) instead, and after that A(3, 10), which was as high as I was willing to go. Here's some data, including benchmarks from Chez Scheme for reference (which I've heard is the fastest Scheme implementation, it's certainly up there):

 (A 3 8) 
 Slow: ~26.47s 
 Fast: ~15.06s 
 Chez Scheme: basically instantaneous 
  
 (A 3 10) 
 Slow: ~6m32.40s 
 Fast: ~3m33.66s 
 Chez Scheme: basically instantaneous 
  
 (A 4 1) 
 Slow: at least 40m 
 Fast: at least 15m (probably much more, wasn't willing to wait longer) 
 Chez Scheme: ~5.25s 

For reference, unoptimized C takes 15.681s to compute A(4,1); with full compiler optimizations (well, -O3 anyway) it only takes 1.583s. Still, not bad, Chez! Our interpreter, on the other hand, obviously extremely inefficient. But the extra work at "compile time" really pays off, the analyzing interpreter is roughly twice as fast.