From: David Kastrup <dak@gnu.org>
To: Mark H Weaver <mhw@netris.org>
Cc: 17147@debbugs.gnu.org
Subject: bug#17147: Performance regression by 3000000% for evaluating "and" form
Date: Tue, 01 Apr 2014 08:17:01 +0200 [thread overview]
Message-ID: <87fvlxlgki.fsf@fencepost.gnu.org> (raw)
In-Reply-To: <878urpn4hn.fsf@yeeloong.lan> (Mark H. Weaver's message of "Mon, 31 Mar 2014 22:55:00 -0400")
[-- Attachment #1: Type: text/plain, Size: 797 bytes --]
Mark H Weaver <mhw@netris.org> 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
[-- Attachment #2: zorpo.scm --]
[-- Type: text/plain, Size: 177 bytes --]
(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))
[-- Attachment #3: Type: text/plain, Size: 1754 bytes --]
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
next prev parent reply other threads:[~2014-04-01 6:17 UTC|newest]
Thread overview: 14+ messages / expand[flat|nested] mbox.gz Atom feed top
2014-03-31 9:58 bug#17147: Performance regression by 3000000% for evaluating "and" form David Kastrup
2014-03-31 22:30 ` Mark H Weaver
2014-03-31 23:21 ` David Kastrup
2014-04-01 2:55 ` Mark H Weaver
2014-04-01 6:17 ` David Kastrup [this message]
2014-04-01 7:10 ` Mark H Weaver
2014-04-01 8:22 ` David Kastrup
2014-04-01 11:59 ` David Kastrup
2014-04-01 16:19 ` Mark H Weaver
2014-05-12 6:08 ` bug#17147: Another idea David Kastrup
2014-05-13 13:03 ` bug#17147: Scalability front and back David Kastrup
2014-06-04 14:18 ` bug#17147: [PATCH] Add versions of and/or avoiding O(n^2) argument matching David Kastrup
2014-06-05 1:09 ` Mark H Weaver
2014-06-05 4:06 ` David Kastrup
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://www.gnu.org/software/guile/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=87fvlxlgki.fsf@fencepost.gnu.org \
--to=dak@gnu.org \
--cc=17147@debbugs.gnu.org \
--cc=mhw@netris.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).