Qiskit / qiskit / 27684886112

88%

main: 88%

Build Type

push

github

Committed by web-flow

Commit Message

Update Sabre extended set on-the-fly (#14912)

* Update Sabre extended set on-the-fly

Ever since Sabre was first introduced to Qiskit (in [1]), the extended
set has been recalculated from the front layer, every time the front
layer is updated.  Now that the extended set is tracked as a series of
layers, it is easily possible to keep the layer structure updated in the
same way as the front layer, by tracking separate points in the
topological iteration through the interaction graph.

To speed up synchronisation of the layers during updates, a new outer
tracker, `Layers`, now means that a removal can jump immediately to the
correct layer, without having to test multiples.  This outer structure
co-operates with the individual layers to effect faster lookups and
removals; rather than each layer storing its own `IndexMap`, they
instead store only a `Vec`, and the outer `Layers` tracks _where_ in the
`Vec` any given gate is.  On removal, the layer returns which, if any,
gate has moved to occupy the otherwise empty slot (since removals are by
swap, not shift).  This avoids all hash lookups in the layer structures;
everything is simple contiguous indexed access.

With the tracking done elsewhere, and with `VecMap` providing type-safe
indexing, each individual `Layer` now stores its contained gates in
terms of `[VirtualQubit; 2]`; this minimises the amount of data that
needs to be modified on a swap, at the cost that actions that need to
associate actual gates with the current physical qubits (like iterating
over active swaps) now need access to the `NLayout`, rather than the
layout being (implicitly) tracked by each `Layer` via `apply_swap`.
This is a performance improvement; as more overhead is reduced, the cost
of the hash lookups in swap application was ever more visible.

[1]: fab61d21: Sabre layout and routing transpiler passes (gh-4537)

* Add release note

* Fix old terminology in comments

Coverage Stats

360 of 366 new or added lines in 2 files covered. (98.36%)

28 existing lines in 3 files now uncovered.

111489 of 127371 relevant lines covered (87.53%)

1009093.5 hits per line