Qiskit / qiskit / 27168080069

88%

Build Type

push

github

Committed by web-flow

Commit Message

Use toposort instead of topological_op_nodes for DAG reconstruction (#15987)

* Use toposort instead of topological_op_nodes for DAG reconstruction

This commit switches the topological sort function we use in transpiler
passes when reconstructing a dag from scratch. In several passes where
we typically replace or remove a large numbers of gates we iterate over
the input dag in topological order and construct a copy of it making the
alterations as we go. Right now when we do this we rely on
`DAGCircuit::topological_op_nodes` which makes sense because it's or
built-in method for iterating over a dag's op node in topological
ordering. Internally this uses rustworkx's lexicographical topological
sort function with our custom sort function that maintains our desired
tie breaker using the bits of a node. However, since #14762 where we're
asserting structural equality in passes we don't need to use that sort
anymore for these reconstruction cases. We just need a consistent
topological sort. In optimizing #13419 one thing that showed in profiles
was that for very large circuits the overhead of the lexicographical
topological sort for the iteration. The toposort function in petgraph
is lower overhead because it doesn't need to work about the
lexicographical tie breaker. By switching to use this instead we can
reduce the overhead of the final sort in all these passes. In asv
benchmarking this commit speeds up transpiler benchmarks are 2-5%
faster (although without asv flagging it as significant).

* Add a dedicated rebuilder function instead of inlining toposort

This commit adds a new method to DAGCircuit that is designed to replace
the explicit rebuilding of a dag that is done in several passes. The
previous commit updated the common pattern of rebuilding the dag to use
toposort instead of topological_sort, but this wasn't the cleanest
interface and it was resulting in some ugliness between the API
boundaries. To facilitate making the more performant path ea... (continued)

Coverage Stats

47 of 47 new or added lines in 5 files covered. (100.0%)

11 existing lines in 3 files now uncovered.

110446 of 126156 relevant lines covered (87.55%)

954554.14 hits per line