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

[Andy Wingo <wingo@pobox.com>]

Hi,

On Tue 04 Aug 2009 11:28, Ken Raeburn <raeburn@raeburn.org> writes:

> I implemented Ackermann's function A(m,n), a recursive function with
> scary performance characteristics, based on the definition given at
> wikipedia involving lots of +1 and -1 operations...

I have now added 1+ and 1- ops to Guile's VM. They don't seem to make a
terrible difference for your case however -- I get similar timings both
with Marijn's code and with yours.

One issue is that Guile's `while' macro provides continue and break
constructs, which involve consing up those closures when you enter a
while block. The compiler should be able to note when those vars are not
referenced, but it does not do so now. That will have to wait for our
inliner.

> I wrote both elisp and scheme versions; I changed the recursion to an
> explicitly-managed stack of values, to avoid some of the dynamic-vs- 
> lexical argument binding issues, turn the native stack usage into large
> numbers of cell allocations and discards, and avoid exceeding  the
> maximum Lisp evaluation depth Emacs permits.  Not surprisingly,  it's
> not too fast, and Emacs spends a lot of time in garbage  collection
> passes even with the byte-compiled version.

Indeed, moving to an explicitly-managed stack tests GC much more than a
recursive solution.

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.

For comparison, your elisp version computes A(3,9) in 2.9 seconds on
this box. Apples and oranges, of course, due to the different
implementation strategies.

> ELISP> (time-test '(ackermann 3 9))
> 2.482042

I suppose this is the comparison, then.

> ELISP> (time-test '(ackermann 4 1))
> 642.746514

And the stack-based version overflows for this one. We need to implement
overflow handlers for the VM stack.

> % time guile -c '(begin (load-compiled "ack.go") (ackermann 3 9))'
> 48.728u 22.016s 1:10.75 99.9%	0+0k 0+0io 0pf+0w

Indeed, I get similar times (44 seconds; presumably some of the
compilation fixes actually had an effect).

I'm running this under valgrind now, I'll see what pops up. Very
interesting test, thanks.

Cheers,

Andy
-- 
http://wingolog.org/