Re: guile performance - Ackermann function: way slower than emacs, slower still if compiled

[Andy Wingo]

On Thu 06 Aug 2009 17:59, Andy Wingo <address@hidden> writes:

> On Wed 05 Aug 2009 12:42, Andy Wingo <address@hidden> 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/