From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Mark H Weaver Newsgroups: gmane.lisp.guile.bugs Subject: bug#17147: Performance regression by 3000000% for evaluating "and" form Date: Mon, 31 Mar 2014 22:55:00 -0400 Message-ID: <878urpn4hn.fsf@yeeloong.lan> References: <87k3ban107.fsf@fencepost.gnu.org> <87r45im25m.fsf@yeeloong.lan> <87mwg6kl90.fsf@fencepost.gnu.org> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: ger.gmane.org 1396321049 15996 80.91.229.3 (1 Apr 2014 02:57:29 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Tue, 1 Apr 2014 02:57:29 +0000 (UTC) Cc: 17147@debbugs.gnu.org To: David Kastrup Original-X-From: bug-guile-bounces+guile-bugs=m.gmane.org@gnu.org Tue Apr 01 04:57:23 2014 Return-path: Envelope-to: guile-bugs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1WUot4-0004RC-41 for guile-bugs@m.gmane.org; Tue, 01 Apr 2014 04:57:18 +0200 Original-Received: from localhost ([::1]:52364 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WUot3-0005t7-Pn for guile-bugs@m.gmane.org; Mon, 31 Mar 2014 22:57:17 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:52523) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WUosv-0005sB-9s for bug-guile@gnu.org; Mon, 31 Mar 2014 22:57:15 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WUosp-0007qx-Dp for bug-guile@gnu.org; Mon, 31 Mar 2014 22:57:09 -0400 Original-Received: from debbugs.gnu.org ([140.186.70.43]:57342) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WUosp-0007qn-8q for bug-guile@gnu.org; Mon, 31 Mar 2014 22:57:03 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.80) (envelope-from ) id 1WUoso-0001eS-Je for bug-guile@gnu.org; Mon, 31 Mar 2014 22:57:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Mark H Weaver Original-Sender: "Debbugs-submit" Resent-CC: bug-guile@gnu.org Resent-Date: Tue, 01 Apr 2014 02:57:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 17147 X-GNU-PR-Package: guile X-GNU-PR-Keywords: Original-Received: via spool by 17147-submit@debbugs.gnu.org id=B17147.13963209656286 (code B ref 17147); Tue, 01 Apr 2014 02:57:02 +0000 Original-Received: (at 17147) by debbugs.gnu.org; 1 Apr 2014 02:56:05 +0000 Original-Received: from localhost ([127.0.0.1]:58524 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WUors-0001dJ-M0 for submit@debbugs.gnu.org; Mon, 31 Mar 2014 22:56:04 -0400 Original-Received: from world.peace.net ([96.39.62.75]:49093) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WUorr-0001dC-EP for 17147@debbugs.gnu.org; Mon, 31 Mar 2014 22:56:04 -0400 Original-Received: from 209-6-91-212.c3-0.smr-ubr1.sbo-smr.ma.cable.rcn.com ([209.6.91.212] helo=yeeloong.lan) by world.peace.net with esmtpsa (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.72) (envelope-from ) id 1WUorf-0007W1-Jg; Mon, 31 Mar 2014 22:55:52 -0400 In-Reply-To: <87mwg6kl90.fsf@fencepost.gnu.org> (David Kastrup's message of "Tue, 01 Apr 2014 01:21:15 +0200") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (gnu/linux) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x X-Received-From: 140.186.70.43 X-BeenThere: bug-guile@gnu.org List-Id: "Bug reports for GUILE, GNU's Ubiquitous Extension Language" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-guile-bounces+guile-bugs=m.gmane.org@gnu.org Original-Sender: bug-guile-bounces+guile-bugs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.bugs:7431 Archived-At: David Kastrup writes: >> (and x y ...) expands into (if x (and y ...) #f), so your huge 'and' >> form turns into a very deeply nested expression, and this overflows the >> compiler's stack on Guile 2.0.x. Thanks to Andy's recent work on >> expandable stacks in master, this case works properly there. > > I think you are overlooking here that a mere 10000-term expression here > is taking 80 seconds to complete. That's 8ms for each term > corresponding to several million clock cycles. The only way to arrive > at such a performance impact is by at least quadratic behavior, and > quadratic behavior is a bad idea. Okay, good point. Indeed, the expansion time of our 'and' and 'or' macros is quadratic in the number of operands. They are implemented in boot-9.scm as follows: (define-syntax and (syntax-rules () ((_) #t) ((_ x) x) ((_ x y ...) (if x (and y ...) #f)))) (define-syntax or (syntax-rules () ((_) #f) ((_ x) x) ((_ x y ...) (let ((t x)) (if t t (or y ...)))))) The problem is that the "y ..." pattern has to iterate down the entire list to verify that it's a proper list, and this is done for each operand. The simplest solution would be to replace all occurrences of "y ..." with ". y" in the two macros above, but that has the slight downside of making the error message much less comprehensible if you use a dotted tail in an 'and' or 'or' form. Maybe that's not worth worrying about though. Alternatively, we could use procedural macros here, but we'd have to limit ourselves to very primitive forms in the code because this is so early in the bootstrap. Mark