@pytorchbot retest this please

How does this relate to the DynamicDAG data structure that @zou3519 added for autodiff subgraph search? Is this meant to be faster/easier to maintain?

There's a lot of overlap; I think the main difference is that the topological index is located directly in the graph and so it stays updated/correct by construction. This makes things simpler for pass authors, who only have to deal with the graph and its canonical topological ordering.

As it is currently implemented it seems impractical to embed DynamicDAG into the graph, because common operations like node insertion would become quite expensive.

I think a good path to converging would be to optimize DynamicDAG a bit around some of the performance cliffs, and then embed it into the IR so that passes don't have to construct their own copy every time.

Hmmm could you please comment a bit more on the performance characteristics of this solution that are lacking from the DynamicDAG? The algorithm generally is pretty solid, and generally it’s not necessarily true that insertions would become expensive. It’s also fundamentally an online solution with proofs of correctness, so it’s an appealing solution.

@apaszke This solution solves a different problem from DynamicDAG

There is one main difference:

1. moveAfterTopologicalValid/moveBeforeTopologicalValid care about if a node is directly before or after another node. DynamicDAG cares about if nodes come before or after (not necessarily directly before or after) each other.

edit: Sorry, I realized from reading the code that I don't know how moveAfterTopologicalValid/moveBeforeTopologicalValid work at all, so please ignore this comment. I will let @michaelsuo explain.

As it is currently implemented it seems impractical to embed DynamicDAG into the graph, because common operations like node insertion would become quite expensive.

This is not true. We can modify DynamicDAG to have "gaps" between nodes in topological index, just like what you implemented last week, @michaelsuo, to make node insertions fast.

The main performance concern was that addEdge is AR * log (AR), but the ord of new node is set to the end. So if you inserted new nodes anywhere except the end, AR could be quite large and you get quadratic insertion behavior.

My other concerns were around maintainability. I don't think pass authors should have to construct a separate data structure every time they want to do reordering, and having ord be out of sync with the the graph's canonical topological ordering is potentially confusing.

But like I originally said, I think all these problems are fixable by modifying DynamicDAG (adding "gaps" like @zou3519 describes) and then making it part of the graph interface. I think the ideal end state is we basically merge the topological index stuff and DynamicDAG together to implement moveBeforeTopologicallyValid.

I think it is also important to keep in mind that the reason for making these queries about valid moves centralized is because mutability is going to make a bunch of moves that appear to be topologically valid become invalid. We can to limit the number of places that have to interact with the metadata about mutating operators.