Qiskit / qiskit / 13055798857

88%

Build Type

push

github

Committed by web-flow

Commit Message

Add merging of `Interner`s (#13752)

* Add merging of `Interner` instances

This makes it possible to merge one interner into another, using a
map-and-filter function to explain how the values should be considered
afterwards.  The main use-case for this is in DAG and circuit
substitution methods, where we want to be able to map
`PackedInstruction`s from a small circuit to new ones on a larger
circuit, without having to unwrap and re-hash the interned slices once
for instruction; instead, we do that once _per interner key_, and then
have a no-hash direct lookup table to remap the interner keys directly.

The methods here are designed to directly allow the reuse of the heap
allocations used to track the interner key mappings, to help reduce the
number of small-scale allocations done in substitution methods.

The filtering part of the mapping is because one cannot typically be
certain that an `Interner` contains the minimally necessary keys,
especially for DAGs; it can well be that substitutions and bit removals
cause old data to be present.

* Use new `Interner` merging in `DAGCircuit::from_circuit`

This converts one obvious candidate for the new interner-merging
functionality.  There are several others in the codebase (all uses of
`DAGCircuit::extend`, for example, and several other full rebuilds), but
the structure of their code wasn't designed with this in mind, so the
modifications would typically be far more involved and more suitable for
separate patches.

Using a timing script:

```python
        import itertools
        from qiskit.circuit import QuantumCircuit
from qiskit.converters import circuit_to_dag

qc = QuantumCircuit(100, 100)
for pair in itertools.permutations(qc.qubits, 2):
    qc.rz(0, pair[0])
    qc.sx(pair[0])
    qc.rz(0, pair[0])
    qc.rz(0, pair[1])
    qc.sx(pair[1])
    qc.rz(0, pair[1])
    qc.cx(*pair)

%timeit circuit_to_dag(qc, copy_operations=False)
```

this patch showed an improvement from 18.5(6)ms to 14.4(5)ms on m... (continued)

Run Details

123 of 253 new or added lines in 2 files covered. (48.62%)

6 existing lines in 2 files now uncovered.

79771 of 89806 relevant lines covered (88.83%)

349012.2 hits per line