Fully port CheckMap to Rust

mtreinish commented 2 months ago

Summary

This commit migrates the entirety of the CheckMap analysis pass to Rust. The pass operates solely in the rust domain and returns an Option<(String, [u32; 2])> to Python which is used to set the two property set fields appropriately. All the analysis of the dag is done in Rust. There is still Python interaction required though because control flow operations are only defined in Python. However the interaction is minimal and only to get the circuits for control flow blocks and converting them into DAGs (at least until #13001 is complete).

Details and comments

~This commit is based on top of #12959 and will need to be rebased after that merges. In the meantime you can see the contents of this PR at: https://github.com/Qiskit/qiskit/commit/41fe4539bad0b7c313db54a562c3d699a4cd14b6~ Rebased

Closes #12251 Part of #12208

qiskit-bot commented 2 months ago

One or more of the following people are relevant to this code:

@Qiskit/terra-core
@kevinhartman
@mtreinish

mtreinish commented 2 months ago

I was inspired to quickly do this transpiler pass because asv showed a runtime regression in this pass after #12550 merged. Comparing this PR against main (with that regression) shows a huge speedup:

Benchmarks that have improved:

| Change   | Before [d3040a0b] <main>            | After [41fe4539]    |   Ratio | Benchmark (Parameter)                                        |
|----------|-------------------------------------|---------------------|---------|--------------------------------------------------------------|
| -        | 1.81±0.01ms                         | 32.7±0.1μs          |    0.02 | mapping_passes.PassBenchmarks.time_check_map(5, 1024)        |
| -        | 4.41±0.2ms                          | 101±5μs             |    0.02 | mapping_passes.RoutedPassBenchmarks.time_check_map(5, 1024)  |
| -        | 5.38±0.08ms                         | 33.6±0.7μs          |    0.01 | mapping_passes.PassBenchmarks.time_check_map(14, 1024)       |
| -        | 20.9±0.2ms                          | 289±10μs            |    0.01 | mapping_passes.RoutedPassBenchmarks.time_check_map(14, 1024) |
| -        | 38.6±0.6ms                          | 459±8μs             |    0.01 | mapping_passes.RoutedPassBenchmarks.time_check_map(20, 1024) |
| -        | 8.21±0.3ms                          | 32.9±0.05μs         |    0    | mapping_passes.PassBenchmarks.time_check_map(20, 1024)       |

SOME BENCHMARKS HAVE CHANGED SIGNIFICANTLY.
PERFORMANCE INCREASED.

(I'm not sure I've ever seen asv report a ratio of 0 before)

mtreinish commented 2 months ago

Comparing against 1.2.0 without the regression caused by #12550:

Benchmarks that have improved:

| Change   | Before [7e2e835e] <1.2.0^0>   | After [41fe4539]    |   Ratio | Benchmark (Parameter)                                        |
|----------|-------------------------------|---------------------|---------|--------------------------------------------------------------|
| -        | 341±0.6μs                     | 32.7±0.1μs          |    0.1  | mapping_passes.PassBenchmarks.time_check_map(5, 1024)        |
| -        | 866±5μs                       | 33.0±0.3μs          |    0.04 | mapping_passes.PassBenchmarks.time_check_map(14, 1024)       |
| -        | 2.33±0.01ms                   | 99.3±4μs            |    0.04 | mapping_passes.RoutedPassBenchmarks.time_check_map(5, 1024)  |
| -        | 1.24±0.01ms                   | 33.1±0.2μs          |    0.03 | mapping_passes.PassBenchmarks.time_check_map(20, 1024)       |
| -        | 12.0±0.1ms                    | 281±5μs             |    0.02 | mapping_passes.RoutedPassBenchmarks.time_check_map(14, 1024) |
| -        | 20.2±0.4ms                    | 454±7μs             |    0.02 | mapping_passes.RoutedPassBenchmarks.time_check_map(20, 1024) |

SOME BENCHMARKS HAVE CHANGED SIGNIFICANTLY.
PERFORMANCE INCREASED.

coveralls commented 2 months ago

Pull Request Test Coverage Report for Build 10744272901

Details

74 of 76 (97.37%) changed or added relevant lines in 4 files are covered.
4 unchanged lines in 1 file lost coverage.
Overall coverage increased (+0.03%) to 89.158%

Changes Missing Coverage	Covered Lines	Changed/Added Lines	%
crates/accelerate/src/check_map.rs	65	67	97.01%
<!--	Total:	74	76	97.37%	-->

Files with Coverage Reduction	New Missed Lines	%
crates/qasm2/src/lex.rs	4	92.48%
<!--	Total:	4		-->

Totals
Change from base Build 10742451788:	0.03%
Covered Lines:	72795
Relevant Lines:	81647

Qiskit / qiskit