GNU bug report logs - #17147
Performance regression by 3000000% for evaluating "and" form

Previous Next

Full log

Message #34 received at 17147 <at> debbugs.gnu.org (full text, mbox):

From: David Kastrup <dak <at> gnu.org>
To: 17147 <at> debbugs.gnu.org
Subject: Another idea
Date: Mon, 12 May 2014 08:08:02 +0200

Maybe the problem is just a choice of bad primitives for going to
tree-il.  Constructs like and/or/cond translate to deeply nested if
statements.  If the primitive retains the nesting level, then syntax
translation can be done in one go instead of recursive matching.
Example: use a primitive %cond that does the same as cond but without
any of its syntax niceties.  If really necessary, we can implement %cond
as an unchecked procedural macro mapping to (if ...) again in a first
iteration and it should still help us get out the complexity trap.

Then
(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 ...))))))

translates into

(define-syntax and
  (syntax-rules ()
    ((_) #t)
    ((_ x ... y) (%cond ((not x) #f) ... (#t y)))))

(define-syntax or
  (syntax-rules ()
    ((_) #f)
    ((_ x ... y) (%cond (x) ... (#t y)))))

and we have no inherently quadratic behavior here since the rules are
not applied recursively and the ... pattern is just matched once per
construct.

-- 
David Kastrup

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.