performance bottleneck: computing a generational graph

[v-nys]

The generational graph is recomputed after every step. Furthermore, the check for recursive calls is expensive.

[v-nys]

Could try this:

• sort verts by ID (so top levels will be traversed first)
• for a relevant target atom
  • for each vertex:
  • check if the vertex is the relevant target atom or if the latter is an ancestor
  • check if it's a renaming with corresponding arguments
  • check if it has multiple direct live lines
  • increment the generation of each descendant by one

It may be possible to stop incrementing when another renaming with corresponding arguments is found and to then, later, increment the descendants of that node by 2, etc. Or there may be other optimizations. Think it through. Also need to think on how to deal with multi in this case.

[v-nys]

A bottom-up solution seems like a better idea. Have an idea that would be pretty feasible in the absence of multi, will need to think on how to generalize it.

[v-nys]

Just implemented mapping from original ID's to encodings based on primes. Could most likely reduce the number of required encodings (e.g. if a node remains identical between levels, use same encoding) which would help to avoid blowup of the numbers. Might be interesting if it turns out computing gcds and next-primes takes too long, but will leave it at this for now.

[v-nys]

Bottom-up method is working and is much faster. Analysis of primes used to take a day, now it takes seconds.