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

[David Kastrup]

Mark H Weaver <address@hidden> writes:

> severity 17147 wishlist
> thanks
>
> David Kastrup <address@hidden> writes:
>
>> The following program goes from 2.3ms execution time to 80s execution
>> time when going from Guile-1.8 to current master.
>>
>> (use-modules (srfi srfi-19))
>> (define start-time (current-time))
>> (primitive-eval (cons 'and (make-list 10000 #f)))
>> (display (time-difference (current-time) start-time))
>
> I suspect the reason this works well on Guile 1.8 is that macros are
> expanded lazily, and since the first argument is #f, it doesn't need to
> expand the rest.
>
> Guile 2.0 uses a different macro expander which is vastly superior in
> most respects and needed to support modern Scheme programs, but it is
> not lazy.  Guile 2 is primarily designed to work in a compiled mode
> anyway, where laziness is pointless and would most likely slow things
> down.
>
> (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.  As a point of reference, the
equivalent and just as deeply nested

(use-modules (srfi srfi-19) (srfi srfi-1))
(define start-time (current-time))
(primitive-eval (fold (lambda (a n) (list 'if #f n)) #f (make-list 10000)))
(display (time-difference (current-time) start-time))

takes 100ms.

> While it would of course be ideal for our compiler to efficiently
> handle expressions 10000 levels deep (if it can be done without
> sacrificing maintainability), dealing with such pathological cases
> should not be a high priority, IMO.  There are many more important
> things to work on.
>
> Is this just an academic exercise, or does Lilypond generate massively
> huge expressions like this?

LilyPond evaluates a lot of one-shot expressions in the course of its
operation, including complex ones.  But Guilev2 offers enough other
stumbling blocks.  We have not yet arrived at a state where it would
even be possible to evaluate performance.

I tripped over this problem here merely while trying to find a
persuasive example for benefits of improving scm_reverse_x performance,
as scm_reverse_x is used quite a bit in libguile/expand.c.

Since the performance impact of reverse! in this example is
indistinguishable from thermal noise, its use seems to be outside of the
quadratically behaving code parts.

-- 
David Kastrup