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

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.

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

My results are:

only eval: loop 9.689s, fib 18.880s

analyze + eval: loop 5.528s, fib 10.682s