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

[Mark H Weaver]

David Kastrup <address@hidden> writes:

>> (and x y ...) expands into (if x (and y ...) #f), so your huge 'and'
>> form turns into a very deeply nested expression, and this overflows the
>> compiler's stack on Guile 2.0.x.  Thanks to Andy's recent work on
>> expandable stacks in master, this case works properly there.
>
> I think you are overlooking here that a mere 10000-term expression here
> is taking 80 seconds to complete.  That's 8ms for each term
> corresponding to several million clock cycles.  The only way to arrive
> at such a performance impact is by at least quadratic behavior, and
> quadratic behavior is a bad idea.

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.

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.

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.

     Mark