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 01:21:15 +0200 Message-ID: <87mwg6kl90.fsf@fencepost.gnu.org> References: <87k3ban107.fsf@fencepost.gnu.org> <87r45im25m.fsf@yeeloong.lan> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="=-=-=" X-Trace: ger.gmane.org 1396308149 18394 80.91.229.3 (31 Mar 2014 23:22:29 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Mon, 31 Mar 2014 23:22:29 +0000 (UTC) Cc: 17147@debbugs.gnu.org, request@debbugs.gnu.org To: Mark H Weaver Original-X-From: bug-guile-bounces+guile-bugs=m.gmane.org@gnu.org Tue Apr 01 01:22:22 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 1WUlWw-0002Ij-2k for guile-bugs@m.gmane.org; Tue, 01 Apr 2014 01:22:14 +0200 Original-Received: from localhost ([::1]:51842 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WUlWt-0006tp-4l for guile-bugs@m.gmane.org; Mon, 31 Mar 2014 19:22:11 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:50066) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WUlWo-0006sq-MQ for bug-guile@gnu.org; Mon, 31 Mar 2014 19:22:07 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WUlWk-0004oo-T5 for bug-guile@gnu.org; Mon, 31 Mar 2014 19:22:06 -0400 Original-Received: from debbugs.gnu.org ([140.186.70.43]:57287) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WUlWk-0004oi-PX for bug-guile@gnu.org; Mon, 31 Mar 2014 19:22:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.80) (envelope-from ) id 1WUlWk-0003cm-Bh for bug-guile@gnu.org; Mon, 31 Mar 2014 19:22:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: David Kastrup Original-Sender: "Debbugs-submit" Resent-CC: bug-guile@gnu.org Resent-Date: Mon, 31 Mar 2014 23:22: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.139630809113851 (code B ref 17147); Mon, 31 Mar 2014 23:22:02 +0000 Original-Received: (at 17147) by debbugs.gnu.org; 31 Mar 2014 23:21:31 +0000 Original-Received: from localhost ([127.0.0.1]:58465 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WUlWE-0003bK-Vi for submit@debbugs.gnu.org; Mon, 31 Mar 2014 19:21:31 -0400 Original-Received: from fencepost.gnu.org ([208.118.235.10]:45619) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WUlWC-0003b4-Gp; Mon, 31 Mar 2014 19:21:29 -0400 Original-Received: from localhost ([127.0.0.1]:52922 helo=lola) by fencepost.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WUlWB-0004JC-Sa; Mon, 31 Mar 2014 19:21:28 -0400 Original-Received: by lola (Postfix, from userid 1000) id E3E65E04F5; Tue, 1 Apr 2014 01:21:15 +0200 (CEST) In-Reply-To: <87r45im25m.fsf@yeeloong.lan> (Mark H. Weaver's message of "Mon, 31 Mar 2014 18:30:45 -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:7430 Archived-At: --=-=-= Content-Type: text/plain Mark H Weaver writes: > severity 17147 wishlist > thanks > > David Kastrup writes: > >> The following program goes from 2.3ms execution time to 80s execution >> time when going from Guile-1.8 to current master. >> >> (use-modules (srfi srfi-19)) >> (define start-time (current-time)) >> (primitive-eval (cons 'and (make-list 10000 #f))) >> (display (time-difference (current-time) start-time)) > > I suspect the reason this works well on Guile 1.8 is that macros are > expanded lazily, and since the first argument is #f, it doesn't need to > expand the rest. > > Guile 2.0 uses a different macro expander which is vastly superior in > most respects and needed to support modern Scheme programs, but it is > not lazy. Guile 2 is primarily designed to work in a compiled mode > anyway, where laziness is pointless and would most likely slow things > down. > > (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. As a point of reference, the equivalent and just as deeply nested --=-=-= 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 (fold (lambda (a n) (list 'if #f n)) #f (make-list 10000))) (display (time-difference (current-time) start-time)) --=-=-= Content-Type: text/plain takes 100ms. > While it would of course be ideal for our compiler to efficiently > handle expressions 10000 levels deep (if it can be done without > sacrificing maintainability), dealing with such pathological cases > should not be a high priority, IMO. There are many more important > things to work on. > > Is this just an academic exercise, or does Lilypond generate massively > huge expressions like this? LilyPond evaluates a lot of one-shot expressions in the course of its operation, including complex ones. But Guilev2 offers enough other stumbling blocks. We have not yet arrived at a state where it would even be possible to evaluate performance. I tripped over this problem here merely while trying to find a persuasive example for benefits of improving scm_reverse_x performance, as scm_reverse_x is used quite a bit in libguile/expand.c. Since the performance impact of reverse! in this example is indistinguishable from thermal noise, its use seems to be outside of the quadratically behaving code parts. -- David Kastrup --=-=-=--