Qiskit / qiskit / 27168080069
88%

DEFAULT BRANCH: main
Ran
Jobs 1
Files 946
Run time 2min
Badge
Embed ▾
README BADGES
x

If you need to use a raster PNG badge, change the '.svg' to '.png' in the link

Markdown

Textile

RDoc

HTML

Rst
coverage: 87.547% (+0.02%) from 87.532%
27168080069

push

github

web-flow 
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)

110446 of 126156 relevant lines covered (87.55%)

954554.14 hits per line

Coverage Regressions

Lines Coverage ∆ File
6
92.54
0.0% crates/qasm2/src/lex.rs
4
74.09
-0.08% crates/circuit/src/parameter/symbol_expr.rs
1
91.03
0.0% crates/circuit/src/parameter/parameter_expression.rs
Jobs
ID Job ID Ran Files Coverage
1 27168080069.1 946
87.55
GitHub Action Run
Source Files on build 27168080069