Qiskit / qiskit / 28036664609

88%

Build Type

push

github

Committed by web-flow

Commit Message

Fix cache and prediction misses in `Target::qargs` (#16476)

In 2.5.0rc1 we noticed a significant slowdown in VF2-dominated
all-to-all connectivity transpilation benchmarks, which this fixes.

Background
----------

We recently changed the internal hash-map data structures in the
`Target` to consolidate various properties, and avoid `IndexSet`
tracking overhead in the qargs tracking[^1]; it wasn't generally needed
for determinism.  However, randomising the iteration order of the
`Qargs` means that graphs constructed from them (like
`Target::coupling_graph` or VF2's custom graph build) add their edges in
random orders.  Edge and neighbour search/iteration methods on graphs
involve following a linked-list-like edge list, which is highly
susceptible to cache and branch-prediction problems; it's far faster if
these accesses are predictable.  For our purposes here with all-to-all
targets, it's the cache properties that matter, and the
branch-prediction is about the same.

Swapping the `qargs_gate_map` back to `IndexSet` does not _itself_
enforce structure in the edge list, but in practice, a `Target` will be
constructed programmatically, and there will be some logical structure
in the construction.  `IndexMap` preserves this, whereas randomisation
is almost guaranteed to be worse.  We could attempt to optimise the edge
list, but sorting arbitrary lists would likely have worse overhead and
not significantly improve on most normal constructions.

Timing
------

Using the `wstate_n380.qasm` file from QASMBench[^2], we have the
following minimised benchmark reproducing the problem:

```python
from qiskit.circuit import QuantumCircuit
from qiskit.transpiler import (
    generate_preset_pass_manager,
    CouplingMap,
    passes,
)
from qiskit.providers.fake_provider import GenericBackendV2

cmap = CouplingMap.from_full(380)
backend = GenericBackendV2(
    cmap.size(),
    coupling_map=cmap,
    basis_gates=["id", "sx", "x", "rz", "cz"],
    seed=42,
)
dag = Quan... (continued)

Coverage Stats

2 of 2 new or added lines in 1 file covered. (100.0%)

16 existing lines in 3 files now uncovered.

112771 of 128684 relevant lines covered (87.63%)

997096.84 hits per line