Qiskit / qiskit / 6101751007

87%

main: 89%

push

github

Use `SmallVec` in `NeighborTable` for cache locality (#10784)

* Use `SmallVec` in `NeighborTable` for cache locality

A reasonable chunk of our time in Sabre is spent reading through the
`NeighborTable` to find the candidate swaps for a given layout.  Most
coupling maps that we care about have a relatively low number of edges
between qubits, yet we needed to redirect to the heap for each
individual physical-qubit lookup currently.

This switches from using a `Vec` (which is always a fat pointer to heap
memory) to `SmallVec` with an inline buffer space of four qubits.
With the qubit type being `u32`, the `SmallVec` now takes up the same
stack size as a `Vec` but can store (usually) all the swaps directly
inline in the outer `Vec` of qubits.  This means that most lookups of
the available swaps are looking in the same (up to relatively small
offsets) in memory, which makes the access patterns much easier for
prefetching to optimise for.

* Pickle via `PyList` instead of duplicate conversion

`SmallVec` doesn't have implementations of the PyO3 conversion trait, so
it needs to be done manually.  The previous state used to convert to a
Rust-space `Vec` that then needed to have its data moved from the Python
heap to the Rust heap.  This instead changes the conversions to interact
directly with Python lists, rather than using intermediary structures.

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

74459 of 85297 relevant lines covered (87.29%)

94573.96 hits per line