Wilfred Hughes

Use interior mutability to represent graph predecessors

1

See the mutable_vertices branch. This might save perf, as we're currently spending most of our time looking up items in hashmaps. It's also worth exploring whether a conventional eager graph...

Model parent nodes accurately

7

See the [accurate_ancestors_with_fallback](https://github.com/Wilfred/difftastic/compare/accurate_ancestors_with_fallback) branch.

Explore 'shared unique' heuristics

1

Try never recursing into a shared unique node. Shared uniqueness is probably a useful property to store in metadata too.

Explore narrowing unchanged singleton lists

1

This would help reduce the maximum nesting that we encounter.

Consider constraining batch size

4

Difftastic scales badly for large single lists. It might be effective to limit how many nodes are considered together, to fix the 'small number of large lists' problem that typing_before.ml...

Explore other routing algorithms

3

https://en.wikipedia.org/wiki/Fringe_search or https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

Try bounding predecessors to not include the full graph

3

Currently we're storing everything in the big hashmap. This takes time to lookup and to insert (21% and 4% respectively). If we stored predecessors in a LRU hashmap, we'd know...

Explore other graph algorithms

10

Bidirectional dijkstra might help, but it's really awkward to implement. It'd be good to explore an explicit visited set for Dijkstra, alongside a priority queue that supports changing priorities. Currently...

Support 24-bit colour

3

This would give us nicer background highlighting and multiple shades (e.g. making certain parts of a change more prominent, similar to git-split-diffs).

Currently they are entirely ignored, leading to queries matching more than they should.