search

v-nys / cclp

A rewrite of my implementation of the Compiling Control technique, in Racket.
MIT License
1 stars 0 forks source link

speed improvement #14

Closed v-nys closed 8 years ago

v-nys commented 8 years ago

As the analysis tree grows, unfolding becomes slower and slower. Building genealogical trees only slows things down further. Profiling may help to uncover and fix performance bottlenecks.

v-nys commented 8 years ago

The bottleneck seems to be in replace-first-subtree and replace-last-subtree. The logic behind the current version of those functions can be optimized for the abstract analysis scenario: replace-first-subtree is only ever applied recursively to a) the last child which already has an index b) the first child which does not yet have an index. All other children can simply be copied without being checked. For replace-last-subtree, the same observation holds (but we should check the first child without an index first).

Hopefully, this will speed the whole thing up considerably.

v-nys commented 8 years ago

This won't lead to any major improvement for primes, because there we only get two children for each node so far. Contracts on map-accumulatel and map-accumulater seem to be a major bottleneck. Option contracts may provide a clean way to deal with this...

v-nys commented 8 years ago

Found the problem! Was doing an expensive computation twice in a recursive function. With expressive contracts, proceeding on laptop takes at most a few seconds at depth 40-ish in primes program. That'll do for now.