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

[Felix]

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

I think this change is not correct - "lambda" and "let" are not
equivalent at this stage of the compiler: "let" introduces local
variables and "lambda" creates a procedure. The distinction is
important when determining whether a variable is "captured", i.e. when
it is referenced or assigned from a different procedure (lambda)
body. If I understand this patch correctly, every "let" would be
treated like a nested lambda and references to variables from outer
"let" expressions would be marked as "captured". The optimizer makes
various assumptions about this (and the scrutinizer will, in a patch
that is currently prepared).


cheers,
felix