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

[David Kastrup]

Mark H Weaver <address@hidden> writes:

> David Kastrup <address@hidden> writes:
>
>> 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.

[...]

> The issue is not circular lists.  The Scheme standards don't specify
> what happens when expressions are cyclic.  The issue is expressions that
> end with a dotted tail, such as (and x y . z).  The ability to write
> macros that check for such patterns and handle them specially is
> standardized and widely supported and used.

> "y ..." is specified by R5RS, R6RS, and R7RS to match only if the
> final CDR is null, and plenty of existing code depends on this
> behavior.  We can't change this.
>
>>> 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.

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

Possibly followed by a special error-out rule

    ((_ x . y) raise-an-error)

Or preceded by an error-out rule ((_ . x) raise-an-error).

> Well, yes, but there are awkward problems having to do with the fact
> that this is early in the bootstrap, before the module system has been
> booted, and we don't currently have a convenient way to have internal
> helpers at this stage that aren't exported by (guile), which means
> polluting the default namespace.  The end result is that I'm inclined
> to either not worry about good error reporting for things like
> (and x . y) or to rewrite 'and' and 'or' as procedural macros.

>> 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.

> 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, at the very least where
recursive expansion rules are concerned.

I have the suspicion, however, that there are a lot of tutorials/etc in
the wild that do make use of ellipses.  So while avoiding ... will help
with keeping Guile's own internals scalable to large expressions, it
will still likely affect the performance of a significant amount of
third-party code.

-- 
David Kastrup