-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Ken Raeburn wrote: > 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... A(0,n) takes > constant time to compute assuming bounded integer sizes, A(1,n) takes > linear time, A(2,n) is quadratic, A(3,n) is exponential... A(4,n) takes > a really long time if n=1, and for anything higher you can just give up > now. (A(4,2) is in the neighborhood of 2**65536, and A(4,3) is about 2 > raised to that power. And it gets there by adding or subtracting 1 in > each invocation.) Optimizations are possible, like A(1,n)=n+2, > A(2,n)=2n+3, A(3,n)=2**(n+3)-3, but I didn't encode those optimizations. > > 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. My time-test function here > counts seconds of real time (on an 8-core Mac without a lot of other > stuff going on, so CPU usage is probably very close): > > ELISP> (time-test '(ackermann 3 1)) > 1.6e-05 > ELISP> (time-test '(ackermann 3 6)) > 0.036018 > ELISP> (time-test '(ackermann 3 7)) > 0.16574899999999998 > ELISP> (time-test '(ackermann 3 8)) > 0.6457170000000001 > ELISP> (time-test '(ackermann 3 9)) > 2.482042 > ELISP> (time-test '(ackermann 4 0)) > 1.4e-05 > ELISP> (time-test '(ackermann 4 1)) > 642.746514 > ELISP> > > With the installed guile-1.8.7 binary and the interpreted Scheme version > of the code, performance was worse: > > % time guile -l ack.scm -c '(ackermann 3 1)' > 0.009u 0.003s 0:00.01 0.0% 0+0k 0+0io 0pf+0w > % time guile -l ack.scm -c '(ackermann 3 6)' > 0.409u 0.078s 0:00.52 90.3% 0+0k 0+0io 0pf+0w > % time guile -l ack.scm -c '(ackermann 3 9)' > 25.300u 4.540s 0:29.85 99.9% 0+0k 0+0io 0pf+0w > % time guile -l ack.scm -c '(ackermann 4 1)' > 6016.150u 1122.109s 1:58:59.32 99.9% 0+0k 8+4io 149pf+0w > % > > Yes, that's just shy of two hours for the last one, where Emacs took > less than 11 minutes. > > (Did I make some silly mistake in translating, that causes the Scheme > version to be far less efficient?) > > It's not a terribly fair comparison, for various reasons, but moving on... > > I built and installed 1.9.1, so I could test with more recent code: > > % time guile -l ack.scm -c '(ackermann 3 1)' > 0.026u 0.006s 0:00.03 66.6% 0+0k 0+0io 0pf+0w > % time guile -l ack.scm -c '(ackermann 3 6)' > 0.761u 0.141s 0:00.90 100.0% 0+0k 0+0io 0pf+0w > % time guile -l ack.scm -c '(ackermann 3 9)' > 47.242u 8.644s 0:55.89 99.9% 0+0k 0+0io 0pf+0w > % > > Since this behaved worse than 1.8.6, I skipped the 4,1 test. I tested > the compiled version: > > % time guile -c '(begin (load-compiled "ack.go") (ackermann 3 1))' > 0.012u 0.004s 0:00.01 100.0% 0+0k 0+0io 0pf+0w > % time guile -c '(begin (load-compiled "ack.go") (ackermann 3 6))' > 0.772u 0.333s 0:01.10 100.0% 0+0k 0+0io 0pf+0w > % 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 > % > > Not much better than loading the .scm file, and only better for small > values of n... in fact, with m=3 and n>=6 the performance seems worse in > the precompiled case: > > % time guile -l ack.scm -c '(ackermann 3 10)' > 181.997u 34.928s 3:36.94 99.9% 0+0k 0+0io 0pf+0w > % time guile -c '(begin (load-compiled "ack.go") (ackermann 3 10))' > 196.678u 85.618s 4:42.34 99.9% 0+0k 0+0io 0pf+0w > % > > Poking at it a couple of times with Apple's process sampling tool, it > does seem to be spending a bit of time in garbage collection -- but > scm_leave_guile (called from scm_async_click via scm_pthread_mutex_lock) > and getrusage (called from scm_c_get_internal_run_time via mytime) also > seem to show up on the stack a significant fraction of the time, and > each of those appears to be a comparable if not bigger time sink. > > According to the execution timing with the compiled code, GC actually > doesn't seem to be a huge fraction of the run time, maybe 8-9%: > > scheme@(guile-user)> ,t (ackermann 3 8) > 2045 > clock utime stime cutime cstime gctime > 18.43 12.96 5.47 0.00 0.00 1.66 > scheme@(guile-user)> ,t (ackermann 3 9) > 4093 > clock utime stime cutime cstime gctime > 73.47 51.61 21.85 0.00 0.00 5.95 > scheme@(guile-user)> > > The latter is the case that took under three seconds in Emacs, remember. > > Garbage collection is much more of a factor in the non-compiled version: > > scheme@(guile-user)> (load "ack.scm") > scheme@(guile-user)> ,t (ackermann 3 8) > 2045 > clock utime stime cutime cstime gctime > 21.97 19.74 2.21 0.00 0.00 7.76 > scheme@(guile-user)> ,t (ackermann 3 9) > 4093 > clock utime stime cutime cstime gctime > 86.26 77.37 8.88 0.00 0.00 30.20 > scheme@(guile-user)> > > It also looks like execution time measurements may add more to the > non-compiled execution time, as with the measurements the compiled code > was still faster at 3,9. > > In retrospect, this is much heavier on the interpretation or execution > of some of the simple operations than I intended, and Emacs benefits a > lot from opcodes like "add1", and I'm more interested specifically in > exercising allocation and GC at the moment, so it's not that useful a > test for me after all. But I thought I'd send this along anyways in > case someone was interested. In particular the fact that the > performance of the precompiled version gets worse as n grows might be > something to investigate, unless the cause is already known....
A more idiomatic way to implement it that also works in other Schemes is: ; $ larceny -- acker.scm -e "(time (pretty-print (A 3 9)))" -e "(quit)" ; $ mzscheme -f acker.scm -e "(time (display (A 3 9))(newline))" ; $ time guile -l acker.scm -c "(display (A 3 9))(newline)" ; $ gsi acker.scm -e "(time (pp (A 3 9)))" (define (A m n) (let loop ((m+ (list m)) (n n)) (if (null? m+) n (let loop1 ((m (car m+)) (m* (cdr m+)) (n n)) (if (= m 0) (loop m* (+ n 1)) (if (= n 0) (loop1 (- m 1) m* 1) (loop1 m (cons (- m 1) m*) (- n 1)) )))))) On my machine larceny computes (A 3 9) in 83 ms and (A 4 1) in less than 22 seconds. In guile-1.8.6 this version is also twice as fast as your version for (A 3 9); they run 9s and 18s respectively. I haven't tried the new guile compiler yet. Marijn - -- If you cannot read my mind, then listen to what I say. Marijn Schouten (hkBst), Gentoo Lisp project, Gentoo ML <http://www.gentoo.org/proj/en/lisp/>, #gentoo-{lisp,ml} on FreeNode -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.11 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iEYEARECAAYFAkp4ONoACgkQp/VmCx0OL2wCmwCgh4a3N6mifoRKuQXG/eaylTqb yzQAn0Kb6YRQy6CXyAEcs8t+yBZsHWLa =6wJR -----END PGP SIGNATURE-----