From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Andy Wingo Newsgroups: gmane.lisp.guile.devel Subject: Re: guile performance - Ackermann function: way slower than emacs, slower still if compiled Date: Wed, 05 Aug 2009 12:42:25 +0200 Message-ID: References: NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: ger.gmane.org 1249469358 2352 80.91.229.12 (5 Aug 2009 10:49:18 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 5 Aug 2009 10:49:18 +0000 (UTC) Cc: guile-devel To: Ken Raeburn Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Wed Aug 05 12:49:11 2009 Return-path: Envelope-to: guile-devel@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.50) id 1MYe3R-0008Bg-FW for guile-devel@m.gmane.org; Wed, 05 Aug 2009 12:49:09 +0200 Original-Received: from localhost ([127.0.0.1]:57847 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1MYe3Q-0004mp-UF for guile-devel@m.gmane.org; Wed, 05 Aug 2009 06:49:08 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1MYe2R-0004G0-0R for guile-devel@gnu.org; Wed, 05 Aug 2009 06:48:07 -0400 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1MYe2M-0004EM-4w for guile-devel@gnu.org; Wed, 05 Aug 2009 06:48:06 -0400 Original-Received: from [199.232.76.173] (port=59585 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1MYe2L-0004EG-Ps for guile-devel@gnu.org; Wed, 05 Aug 2009 06:48:01 -0400 Original-Received: from a-sasl-quonix.sasl.smtp.pobox.com ([208.72.237.25]:52104 helo=sasl.smtp.pobox.com) by monty-python.gnu.org with esmtp (Exim 4.60) (envelope-from ) id 1MYe2L-00073e-3u for guile-devel@gnu.org; Wed, 05 Aug 2009 06:48:01 -0400 Original-Received: from localhost.localdomain (unknown [127.0.0.1]) by a-sasl-quonix.sasl.smtp.pobox.com (Postfix) with ESMTP id C044B214C5; Wed, 5 Aug 2009 06:47:58 -0400 (EDT) Original-Received: from unquote (unknown [82.123.246.238]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by a-sasl-quonix.sasl.smtp.pobox.com (Postfix) with ESMTPSA id 38CE7214C4; Wed, 5 Aug 2009 06:47:57 -0400 (EDT) In-Reply-To: (Ken Raeburn's message of "Tue, 4 Aug 2009 05:28:33 -0400") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.0.92 (gnu/linux) X-Pobox-Relay-ID: 70B25E2E-81AD-11DE-9424-F699A5B33865-02397024!a-sasl-quonix.pobox.com X-detected-operating-system: by monty-python.gnu.org: Solaris 10 (beta) X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.devel:9031 Archived-At: Hi, On Tue 04 Aug 2009 11:28, Ken Raeburn 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/