bug#17147: Performance regression by 3000000% for evaluating "and" form

[David Kastrup]

Mark H Weaver <address@hidden> 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

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

then I get
address@hidden:/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