On Thu 06 Aug 2009 17:59, Andy Wingo <wi...@pobox.com> writes:
> On Wed 05 Aug 2009 12:42, Andy Wingo <wi...@pobox.com> writes:
>
>> The simple stack formulation of Ackermann's function is faster of
>> course:
>>
>> (define (A m n)
>> (if (= m 0)
>> (+ n 1)
>> (if (= n 0)
>> (A (- m 1) 1)
>> (A (- m 1) (A m (- n 1))))))
>>
>> (A 3 9) completes in 1.45 seconds for me.
>>
>> Curiously, the letrec case takes more time:
>>
>> (define (A m n)
>> (let A ((m m) (n n))
>> (if (= m 0)
>> (+ n 1)
>> (if (= n 0)
>> (A (- m 1) 1)
>> (A (- m 1) (A m (- n 1)))))))
>>
>> It should be faster, because we don't have to deref the toplevel
>> variable for A, but the compiler needs to be a little smarter. This
>> version takes about 1.6 seconds for me.
>
> I have fixed this issue. The letrec version now takes slightly less time
> than the version that recurses through the toplevel.
So, I couldn't stop, being so close -- I went ahead and implemented
mutual tail-recursion as Steele did in the Lambda: The Ultimate GOTO
paper. It doesn't have any effect in this case, but in Daniel's
tight-loop code it should have an effect. Here was that code:
(define (test to)
(let ((i 0))
(while (< i to)
(set! i (1+ i)))))
Daniel said this was the result:
> Tight loop, (test 1000000):
> Scheme: 0.72s
That's with 1 million iterations. But I just tried it with 10 million
iterations, with current Guile from this afternoon, and got the same
timing. Daniel can you test again? This would be a pleasant surprise :)
It doesn't help the ackermann case, though. That will come later.
Unfortunately the letrec case is actually taking more time it used to
before this patch; alack.
It doesn't look like I'll get to dynamic-wind until next thursday or so.
Until then, happy hacking, and keep up the great bug reports!
A
--
http://wingolog.org/
