From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: David Kastrup Newsgroups: gmane.lisp.guile.bugs Subject: bug#17147: Performance regression by 3000000% for evaluating "and" form Date: Tue, 01 Apr 2014 08:17:01 +0200 Message-ID: <87fvlxlgki.fsf@fencepost.gnu.org> References: <87k3ban107.fsf@fencepost.gnu.org> <87r45im25m.fsf@yeeloong.lan> <87mwg6kl90.fsf@fencepost.gnu.org> <878urpn4hn.fsf@yeeloong.lan> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="=-=-=" X-Trace: ger.gmane.org 1396333097 28928 80.91.229.3 (1 Apr 2014 06:18:17 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Tue, 1 Apr 2014 06:18:17 +0000 (UTC) Cc: 17147@debbugs.gnu.org To: Mark H Weaver Original-X-From: bug-guile-bounces+guile-bugs=m.gmane.org@gnu.org Tue Apr 01 08:18:11 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 1WUs1Q-0000Zb-N3 for guile-bugs@m.gmane.org; Tue, 01 Apr 2014 08:18:08 +0200 Original-Received: from localhost ([::1]:52751 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WUs1Q-00060C-7n for guile-bugs@m.gmane.org; Tue, 01 Apr 2014 02:18:08 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:42351) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WUs1L-0005zu-RH for bug-guile@gnu.org; Tue, 01 Apr 2014 02:18:04 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WUs1K-0006r0-9K for bug-guile@gnu.org; Tue, 01 Apr 2014 02:18:03 -0400 Original-Received: from debbugs.gnu.org ([140.186.70.43]:57414) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WUs1K-0006qw-5d for bug-guile@gnu.org; Tue, 01 Apr 2014 02:18:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.80) (envelope-from ) id 1WUs1J-0006bK-Q7 for bug-guile@gnu.org; Tue, 01 Apr 2014 02:18:01 -0400 X-Loop: help-debbugs@gnu.org Resent-From: David Kastrup Original-Sender: "Debbugs-submit" Resent-CC: bug-guile@gnu.org Resent-Date: Tue, 01 Apr 2014 06:18:01 +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.139633306725352 (code B ref 17147); Tue, 01 Apr 2014 06:18:01 +0000 Original-Received: (at 17147) by debbugs.gnu.org; 1 Apr 2014 06:17:47 +0000 Original-Received: from localhost ([127.0.0.1]:58596 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WUs14-0006aq-T8 for submit@debbugs.gnu.org; Tue, 01 Apr 2014 02:17:47 -0400 Original-Received: from fencepost.gnu.org ([208.118.235.10]:51013) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WUs12-0006ah-EB for 17147@debbugs.gnu.org; Tue, 01 Apr 2014 02:17:45 -0400 Original-Received: from localhost ([127.0.0.1]:58320 helo=lola) by fencepost.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WUs11-0007Ym-Cn; Tue, 01 Apr 2014 02:17:43 -0400 Original-Received: by lola (Postfix, from userid 1000) id 0BAA1E04F5; Tue, 1 Apr 2014 08:17:01 +0200 (CEST) In-Reply-To: <878urpn4hn.fsf@yeeloong.lan> (Mark H. Weaver's message of "Mon, 31 Mar 2014 22:55:00 -0400") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.4.50 (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:7432 Archived-At: --=-=-= Content-Type: text/plain Mark H Weaver writes: > 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. Why would it have to do that? It cannot be anything valid else if it is a pair. Note that the compiler does not bother to do this for other cases: if I write --=-=-= Content-Type: text/plain Content-Disposition: inline; filename=zorpo.scm (use-modules (srfi srfi-19) (srfi srfi-1)) (define start-time (current-time)) (primitive-eval (cons '+ (circular-list 0))) (display (time-difference (current-time) start-time)) --=-=-= Content-Type: text/plain then I get dak@lola:/usr/local/tmp/guile$ meta/guile /tmp/zorpo.scm ;;; note: source file /tmp/zorpo.scm ;;; newer than compiled /usr/local/tmp/guile/cache/guile/ccache/2.2-LE-4-3.4/tmp/zorpo.scm.go ;;; note: auto-compilation is enabled, set GUILE_AUTO_COMPILE=0 ;;; or pass the --no-auto-compile argument to disable. ;;; compiling /tmp/zorpo.scm ;;; compiled /usr/local/tmp/guile/cache/guile/ccache/2.2-LE-4-3.4/tmp/zorpo.scm.go Warning: Unwind-only `stack-overflow' exception; skipping pre-unwind handler. Warning: Unwind-only `stack-overflow' exception; skipping pre-unwind handler. and what of it? If you really, really must, do one recursive top-level check of everything before starting. But re-verifying structural integraty after applying every single rule is madness. Actually, replacing '+ by 'and in that example will lead to the same bomb-out. So it does not look like structural integrity verification is happening anyway. > 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. If you care about nice error messages, do a single upfront check. > 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. I don't think it's worth it just for and/or (the form generated by or actually seems more prone to buildup and churn). But for syntax replacements in general? Sure. You don't want quadratic behavior in bare-bones replacements like these. -- David Kastrup --=-=-=--