search

larcenists / larceny

Larceny Scheme implementation
Other
202 stars 32 forks source link

macro expander stresses symbol table #810

Open WillClinger opened 7 years ago

WillClinger commented 7 years ago

After figuring out why the sample implementation of SRFI 148 doesn't work in Larceny (it assumes a lack of hygiene when distinguishing between pattern variables and literals), I looked into why it and other macro-intensive SRFIs take so long to compile. It turns out that compilation, mostly macro expansion, creates about 800000 symbols, of which only 5000 or so need to be retained following compilation.

Reclaiming those symbols via gctwa takes about ten minutes on our main Linux machine, which is about six times as long as the compilation itself. Calling gctwa a second time takes only 75 ms.

The colors generated during macro expansion don't have to be symbols, but using symbols to represent colors appears to increase the number of generated symbols by only 10% or so.

lars-t-hansen commented 7 years ago

gctwa's filtering looks like it's quadratic in the length of the oblist :(

WillClinger commented 7 years ago

Changeset 1a062963bd6575de053cb7d720ff607a7fa3b918 makes gctwa run in linear time, reducing the ten minutes to 600 ms, a hundred-fold speedup.

WillClinger commented 7 years ago

Changeset 3bef27e4af5432897f2b32b5052f66990667d78e makes gctwa interruptible by using a crude hash table instead of property lists. With property lists, a user interrupt would prevent marked symbols from being reclaimed by a subsequent gctwa.

Using a hash table also appears to be slightly faster, but that's much less important.

Improving the performance of gctwa doesn't solve the problem identified by this issue ticket, but it should make the problem easier to deal with.