[Chicken-hackers] [PATCH] Exponential case in the optimizer's handling of replacable variables

[Peter Bex]

Hi all,

Here's another patch that attempts to push down compilation time.

In the analysis phase, variables that are eligible for replacement
are marked as such, and in the database these get a property which
says with which other variable they can be replaced (this happens
in analyze-expression in compiler.scm).  The actual replacement
happens in the optimization step (perform-high-level-optimizations in
optimizer.scm) 

When replacing, the variable referred to might itself be replacable,
so this is looked up too, recursively until we reach a variable that's
no longer replacable for whatever reason.  We use that variable as the
replacement.

During experimentation, I found a pathological example program
which triggers exponential behaviour in this part of the code.
It consists of one big AND statement with any number of read
statements in it:

  (and (read) (read) (read) .... )

This gets rewritten to a lot of LET statements again where variables
are created which refer directly to other variables which refer to
other variables, .....  This long chain of variables gets traversed
every time a variable somewhere on that chain is referred to.
Instead of doing this every time, this patch ensures that after
traversal, the final variable in the chain is picked up and passed
up across the chain and each variable is updated to refer to that
lowest variable.  The next time we see another variable on that chain,
it is looked up immediately and we're done.

See the comparison.png which produces again a crisp picture showing
how effective this is for the silly program I made.

Unfortunately, it only saves 5 seconds on the numbers test so I
guess I'll need to keep at it a bit longer to get to the actual
bottleneck I'm facing ;)

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-While-optimizing-don-t-traverse-the-same-chain-of-re.patch
Description: Text document

comparison.png
Description: PNG image