Runtime Performance Regression in SabreLayout

[mtreinish]

Environment

• Qiskit Terra version: 0.25.0
• Python version: 3.11
• Operating system: Linux

What is happening?

When running SabreLayout with 0.25.0 has a large performance regression between 0.24.x and 0.25.0 that is a function of the number of gates in the circuit. The rust computation of the swap map and initial layout is as fast as before, but when we iterate over that to rewrite the DAGCircuit using that output from rust the runtime performance is significantly slower. For more modestly sized circuits this isn't super noticeable , but as the number of instructions in a circuit increases this overhead can be significantly higher.

How can we reproduce the issue?

You can parse this qasm file from qasmbench: https://github.com/pnnl/QASMBench/blob/master/medium/bwt_n21/bwt_n21.qasm

from qiskit import transpile, QuantumCircuit
from qiskit.providers.fake_provider import FakeCairoV2
import time
import logging
logging.basicConfig(level="INFO")

backend = FakeCairoV2()
for filename in ["bwt_n21.qasm"]:
    start = time.time()
    qc = QuantumCircuit.from_qasm_file(filename)
    parse_stop = time.time()
    print(f"parse {filename}: {parse_stop - start}")
    tqc = transpile(qc, backend, optimization_level=1)
    stop = time.time()
    print(f"{filename}: {stop - start}")

What should happen?

The performance should be roughly equivalent to qiskit-terra < 0.25.0. Looking at 0.24.2 the above example SabreLayout took 22515.55800 ms and 0.23.0 took 18759.72962 ms. But I've been too impatient to wait for 0.25.0 to finish after several minutes.

Any suggestions?

I expect the underlying issue stems from #10366 and specifically the rust<->python boundary doing unnecessary copies or conversions when we access data as we iterate over the circuit.

[mtreinish]

The root cause of this seems to be because of this line: https://github.com/Qiskit/qiskit-terra/blob/main/crates/accelerate/src/sabre_swap/mod.rs#L67 implementing a getter with the attribute macro like this results in map being cloned on each access of SabreResult.map. So we're basically doing a clone() of the full swap map for each node in the dag as we iterate over the output.