[Chicken-hackers] [PATCH] Another exponential case: analyze-expression on LET expressions

[Peter Bex]

Hi all,

Still working on this numbers test compilation time, I tried a silly
change to my program generator/compilation measuring program: I changed
it to output (lambda () (print #t)) instead of (print #t), producing a
whole bunch of unused expressions.

Turns out this has exponential compilation time as well.  See the red
line in comparison.png

I tracked this to the analysis phase, analyze-expression in compiler.scm
>From what I understand of it, this procedure tracks the flow of variables
across let, set! and lambda and assigns some properties to these.
The silly program, when compiled, generates deeply nested let forms,
like (let ((x (let ((y ...)))))).  The analyzer loops through all the
variable bindings and when it's done, it adds these to the current
"local environment", with append.  Of course, when lots and lots of 
nested lets occur, somewhere deep down inside the bottom LET, when
there's an actual expression this extremely large "local environment"
gets APPENDed to the "outer environment", which takes a long time
because it needs to cons through the entire list.

If this happens multiple times, there's a lot of time wasted doing that.
Instead, if the LET's local environment is appended to the outer
environment and *only* the newly introduced bindings are passed on as
the body's local environment, this is avoided (the consing happens just
once, as the code recurs on the subexpressions).  If I understand the
code for LAMBDA correctly, the same happens there already, which I think
is the correct behaviour anyway.  See the green line in the graph to see
how this affects performance :)

Since we all know LET is functionally equivalent to a LAMBDA with an
immediate application, I think this discrepancy *should* be able to
trigger a bug somehow, somewhere.  I hammered on it for about two hours
but I couldn't figure out a way to make it produce any different code,
so I'm leaving this for anyone who knows a way or wants to figure it out.

Meanwhile, "make check" still passes and since there doesn't seem to be
an observable difference but it does affect out performance profile in a
positive way, I decided to post the patch to the list.  What could
possibly go wrong?

Cheers,
Peter
-- 
http://sjamaan.ath.cx
--
"The process of preparing programs for a digital computer
 is especially attractive, not only because it can be economically
 and scientifically rewarding, but also because it can be an aesthetic
 experience much like composing poetry or music."
                                                        -- Donald Knuth

0001-In-the-analysis-phase-put-newly-introduced-let-bindi.patch
Description: Text document

comparison.png
Description: PNG image