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: Tue, 01 Apr 2014 12:19:56 -0400 Message-ID: <87bnwlkonn.fsf@yeeloong.lan> References: <87k3ban107.fsf@fencepost.gnu.org> <87r45im25m.fsf@yeeloong.lan> <87mwg6kl90.fsf@fencepost.gnu.org> <878urpn4hn.fsf@yeeloong.lan> <87fvlxlgki.fsf@fencepost.gnu.org> <87wqf9le3l.fsf@yeeloong.lan> <877g79larq.fsf@fencepost.gnu.org> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: ger.gmane.org 1396369287 6991 80.91.229.3 (1 Apr 2014 16:21:27 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Tue, 1 Apr 2014 16:21:27 +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 18:21:20 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 1WV1R9-0001IR-Ju for guile-bugs@m.gmane.org; Tue, 01 Apr 2014 18:21:19 +0200 Original-Received: from localhost ([::1]:33154 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WV1R9-0006bf-02 for guile-bugs@m.gmane.org; Tue, 01 Apr 2014 12:21:19 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:57052) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WV1Qz-0006bU-8l for bug-guile@gnu.org; Tue, 01 Apr 2014 12:21:15 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WV1Qt-0007HT-5o for bug-guile@gnu.org; Tue, 01 Apr 2014 12:21:09 -0400 Original-Received: from debbugs.gnu.org ([140.186.70.43]:58402) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WV1Qt-0007Gr-2W for bug-guile@gnu.org; Tue, 01 Apr 2014 12:21:03 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.80) (envelope-from ) id 1WV1Qs-0002qa-Ai for bug-guile@gnu.org; Tue, 01 Apr 2014 12:21: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 16:21: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.139636925710919 (code B ref 17147); Tue, 01 Apr 2014 16:21:02 +0000 Original-Received: (at 17147) by debbugs.gnu.org; 1 Apr 2014 16:20:57 +0000 Original-Received: from localhost ([127.0.0.1]:59584 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WV1Qm-0002q2-T1 for submit@debbugs.gnu.org; Tue, 01 Apr 2014 12:20:57 -0400 Original-Received: from world.peace.net ([96.39.62.75]:49715) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WV1Qk-0002pu-V3 for 17147@debbugs.gnu.org; Tue, 01 Apr 2014 12:20:55 -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 1WV1Qc-00017G-M7; Tue, 01 Apr 2014 12:20:46 -0400 In-Reply-To: <877g79larq.fsf@fencepost.gnu.org> (David Kastrup's message of "Tue, 01 Apr 2014 10:22:17 +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:7443 Archived-At: David Kastrup writes: > Actually, if you care about nicer error messages than a complaint about > (and . whatever), you can write the last rule a bit more cumbersome: > > (define-syntax and > (syntax-rules () > ((_) #t) > ((_ x) x) > ((_ x y . z) (if x (and y . z) #f)))) This would improve the error message for (and x . y), but not for (and x y . z), (and x y z . w), etc. > Possibly followed by a special error-out rule > > ((_ x . y) raise-an-error) No need for this. If none of the patterns match, the user will get a reasonable error message. > Or preceded by an error-out rule ((_ . x) raise-an-error). This pattern will match things like (and), (and x), (and x y), etc, so it would have to come last. In order to produce good error messages, 'syntax-rules' macros must detect the errors in the original expression. If the error is not detected until some intermediate expression is expanded, users will see errors about expressions they did not type, which is quite confusing. For procedural macros, there is more flexibility, because 'syntax-violation' can be called when an error is detected, and the original form (and a relevant subform, if desired) can be passed to it explicitly. BTW, whenever I talk about "procedural macros", I'm talking about the so-called 'syntax-case' macros, which are hygienic by default but provide controlled ways to create unhygienic behavior where desired. The old 'define-macro' macros are unhygienic by default, and thus prone to problems of unintended variable capture. IMO, 'define-macro' should never be used in new code unless it cannot be avoided (and I guess LilyPond cannot avoid it until support for 1.8 is dropped, due to the 'void' issue). >>> 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. >> >> Sorry, but there's no easy solution here. The "y ..." pattern _must_ >> fail to match unless the last CDR is null. I could imagine clever >> optimization tricks where all cons cells of the generated (and y ...) >> include an annotation asserting that the final CDR is null, > > As one can expect a lot of user-written code to contain patterns using > an ellipsis, I think that would be an ultimately effective optimization. I suspect it would significantly increase compile time and memory usage in the common case. >> but IMO this would not be worth the added code complexity and the >> extra storage needed by the annotations. I think the best we can >> reasonably do is to be aware of the efficiency characteristics of the >> patterns when writing macros. > > If Guile is not going to optimize ..., I think it would be good if it > led by example (its sources _are_ going to teach people how to program) > and simply avoided using ... altogether, I disagree that we should avoid the use of ... altogether. IMO, writing macros in such a way to produce good error messages is very important, and that means making patterns as strict as they can be, to detect errors as soon as possible. For this reason, I prefer "y ..." to ". y". > at the very least where recursive expansion rules are concerned. If the relevant list being matched might conceivably be large, then it's probably best to have a main macro that is as strict as possible, e.g. using ellipses, and then to do the actual recursion using internal helpers that use ". y" and do no error checking. However, this approach carries a different cost: added code complexity and reduced readability. IMO, it does not make sense to design every macro to efficiently handle huge numbers of operands. There is such a thing as "premature optimization", and as I recall Knuth had some strong words to say about that. For most macros, and for most code in general, I advocate keeping things as simple as possible, and only adding complexity where it is needed. However, I agree that we should make Guile's core forms such as 'and' and 'or' scalable. Regards, Mark