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: Fri, 07 Aug 2009 19:27:13 +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 1249666073 19388 80.91.229.12 (7 Aug 2009 17:27:53 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Fri, 7 Aug 2009 17:27:53 +0000 (UTC) Cc: guile-devel To: Ken Raeburn Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Fri Aug 07 19:27:46 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 1MZTEI-0002wV-1H for guile-devel@m.gmane.org; Fri, 07 Aug 2009 19:27:46 +0200 Original-Received: from localhost ([127.0.0.1]:37430 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1MZTEH-0007Pa-G8 for guile-devel@m.gmane.org; Fri, 07 Aug 2009 13:27:45 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1MZTEE-0007PD-6c for guile-devel@gnu.org; Fri, 07 Aug 2009 13:27:42 -0400 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1MZTE7-0007P1-LK for guile-devel@gnu.org; Fri, 07 Aug 2009 13:27:40 -0400 Original-Received: from [199.232.76.173] (port=46844 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1MZTE7-0007Oy-Fi for guile-devel@gnu.org; Fri, 07 Aug 2009 13:27:35 -0400 Original-Received: from mx20.gnu.org ([199.232.41.8]:13345) by monty-python.gnu.org with esmtps (TLS-1.0:RSA_AES_256_CBC_SHA1:32) (Exim 4.60) (envelope-from ) id 1MZTE7-0008QB-5s for guile-devel@gnu.org; Fri, 07 Aug 2009 13:27:35 -0400 Original-Received: from a-pb-sasl-sd.pobox.com ([64.74.157.62] helo=sasl.smtp.pobox.com) by mx20.gnu.org with esmtp (Exim 4.60) (envelope-from ) id 1MZTE5-0004FD-UY for guile-devel@gnu.org; Fri, 07 Aug 2009 13:27:34 -0400 Original-Received: from localhost.localdomain (unknown [127.0.0.1]) by a-pb-sasl-sd.pobox.com (Postfix) with ESMTP id 9013121A96; Fri, 7 Aug 2009 13:26:54 -0400 (EDT) Original-Received: from unquote (unknown [82.123.117.215]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by a-pb-sasl-sd.pobox.com (Postfix) with ESMTPSA id B84DA21A93; Fri, 7 Aug 2009 13:26:52 -0400 (EDT) In-Reply-To: (Andy Wingo's message of "Thu, 06 Aug 2009 17:59:23 +0200") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.0.92 (gnu/linux) X-Pobox-Relay-ID: 805C6FA6-8377-11DE-ACAE-AEF1826986A2-02397024!a-pb-sasl-sd.pobox.com X-Detected-Operating-System: by mx20.gnu.org: Solaris 10 (beta) X-detected-operating-system: by monty-python.gnu.org: GNU/Linux 2.6, seldom 2.4 (older, 4) 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:9038 Archived-At: On Thu 06 Aug 2009 17:59, Andy Wingo writes: > On Wed 05 Aug 2009 12:42, Andy Wingo 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/