From: David Kastrup <dak@gnu.org>
To: 17147@debbugs.gnu.org
Cc: David Kastrup <dak@gnu.org>
Subject: bug#17147: [PATCH] Add versions of and/or avoiding O(n^2) argument matching
Date: Wed, 4 Jun 2014 16:18:29 +0200 [thread overview]
Message-ID: <1401891509-29257-1-git-send-email-dak@gnu.org> (raw)
In-Reply-To: <87k3ban107.fsf@fencepost.gnu.org>
Fixes <http://bugs.gnu.org/17147>
* module/ice-9/boot-9.scm (and, or): Add syntax rules that only do one
pattern matching operation per and/or rather than per argument.
Signed-off-by: David Kastrup <dak@gnu.org>
---
module/ice-9/boot-9.scm | 26 ++++++++++++++++++++++++++
1 file changed, 26 insertions(+)
diff --git a/module/ice-9/boot-9.scm b/module/ice-9/boot-9.scm
index 7f38c4b..d2f34d9 100644
--- a/module/ice-9/boot-9.scm
+++ b/module/ice-9/boot-9.scm
@@ -426,6 +426,8 @@ file with the given name already exists, the effect is unspecified."
;; The binding for `macroexpand' has now been overridden, making psyntax the
;; expander now.
+;; quasisyntax requires simple definitions of and/or for bootstrapping.
+
(define-syntax and
(syntax-rules ()
((_) #t)
@@ -440,6 +442,30 @@ file with the given name already exists, the effect is unspecified."
(include-from-path "ice-9/quasisyntax")
+;; Don't use syntactically recursive definitions of and/or for speed
+;; reasons as they need to match the whole argument list for each
+;; iteration.
+
+(define-syntax and
+ (lambda (expr)
+ (syntax-case expr ()
+ ((_) #'#t)
+ ((_ x y ...)
+ (let loop ((x #'x) (y #'(y ...)))
+ (if (null? y)
+ x
+ #`(if #,x #,(loop (car y) (cdr y)) #f)))))))
+
+(define-syntax or
+ (lambda (expr)
+ (syntax-case expr ()
+ ((_) #'#f)
+ ((_ x y ...)
+ (let loop ((x #'x) (y #'(y ...)))
+ (if (null? y)
+ x
+ #`(let ((t #,x)) (if t t #,(loop (car y) (cdr y))))))))))
+
(define-syntax-rule (when test stmt stmt* ...)
(if test (begin stmt stmt* ...)))
--
1.9.1
next prev parent reply other threads:[~2014-06-04 14:18 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
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 ` David Kastrup [this message]
2014-06-05 1:09 ` bug#17147: [PATCH] Add versions of and/or avoiding O(n^2) argument matching 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=1401891509-29257-1-git-send-email-dak@gnu.org \
--to=dak@gnu.org \
--cc=17147@debbugs.gnu.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).