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

[Mark H Weaver <mhw@netris.org>]

David Kastrup <dak@gnu.org> writes:

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

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.

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.

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

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

    Regards,
      Mark