Wilfred Hughes

Could pre allocate the simple nodes ignoring parents, or try to find a later node that came after, or grouping seen by syntax ID pairs.

478e574141ea8680859e52acc61d8b3a823563ef is probably also effective, but probably slower.

Rebased in accurate_ancestors_v2, 15dc03b820b372545d96fbd9342f7fc51f8d0b37.

This produces substantially nicer results, but explores many more nodes. DFT_GRAPH_LIMIT needs to be 10,000,000 for several of the sample files.

``` 2022-07-20T05:19:32.103Z INFO difft::options > CLI arguments: ["sample_files/javascript_before.js", "sample_files/javascript_after.js"] 2022-07-20T05:19:32.136Z INFO difft::diff::dijkstra > LHS nodes: 150 (1 toplevel), RHS nodes: 329 (1 toplevel) 2022-07-20T05:19:38.575Z DEBUG difft::diff::dijkstra > Found predecessors for...

If two nodes are equal and unique, does it make sense to consider other possibilities? Could we optimise in that case? (Brief testing suggests it's no faster.)

Perhaps only consider additional parents when the subtree is small? Edit: That didn't affect performance at all.

This produces a roughly 5x slowdown on my test files, and an increase in peak hashmap size from 1.3M to 7-8M nodes.

Fixed in c9578185148e04e99497dee9faac902480be0e48.

E.g. if two nodes match and are shared unique, don't recurse