[Chicken-hackers] [PATH] Use hash table instead of flat list for lambda literals

[Peter Bex]

Hi!

Here's another pretty straightforward patch. This one cuts the code
generation time in half for the numbers test (I'm lazy today, I didn't
bother to figure out a synthetic program that gets the same behavior, but
theoretically this should be exponential in the worst case, too)

The change is pretty simple; prepare-for-code-generation walks the node
tree, assembles a list of all lambda literals and returns it, which
generate-code then consumes to generate a list of all lambdas.
In two places it uses an internal FIND-LAMBDA helper procedure, which
loops through the list and tries to find a lambda literal that has
the same ID as a reference to it in a call site.

Instead of looping through the entire list, it could just use a hash
table, which requires us to modify prepare-for-code-generation to
create one.  The hash table size is initialized to the analysis database
size, perhaps this could be tweaked further to save on memory usage
as this is most likely way too much since there are usually more
"normal" variables than lambdas.  For example, the numbers test has
14051 lambdas, and the program size is about 10 times as big.

OTOH, theoretically a program could be "lambdas all the way down",
in which case the guess is right on the mark.  That's why I kept it
the way it is for now (and it's a convenient number to use since
it's already being calculated and it's never going to be too small).

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-Convert-flat-lambda-literals-list-into-hash-table-to.patch
Description: Text document