[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: guile performance - Ackermann function: way slower than emacs, slow
From: |
Andy Wingo |
Subject: |
Re: guile performance - Ackermann function: way slower than emacs, slower still if compiled |
Date: |
Fri, 07 Aug 2009 19:27:13 +0200 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/23.0.92 (gnu/linux) |
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/
- Re: guile performance - Ackermann function: way slower than emacs, slower still if compiled, (continued)
- Re: guile performance - Ackermann function: way slower than emacs, slower still if compiled, Ken Raeburn, 2009/08/05
- entering and leaving guile mode, and GC stack protection (was Re: guile performance - Ackermann function: way slower than emacs, slower still if compiled), Ken Raeburn, 2009/08/06
- Re: entering and leaving guile mode, and GC stack protection, Andy Wingo, 2009/08/12
- Re: entering and leaving guile mode, and GC stack protection, Ludovic Courtès, 2009/08/14
Re: guile performance - Ackermann function: way slower than emacs, slower still if compiled, Ludovic Courtès, 2009/08/08
Re: guile performance - Ackermann function: way slower than emacs, slower still if compiled, Andy Wingo, 2009/08/05
Re: guile performance - Ackermann function: way slower than emacs, slower still if compiled, Andy Wingo, 2009/08/05