Replace pauli expectation value cython with multithreaded rust implementation #7702

mtreinish · 2022-02-23T16:02:45Z

Summary

This commit replaces the cython implementation of the pauli expectation
value functions with a multithreaded rust implementation. This was done
primarily for two reasons, the first and primary reason for this change
is because after #7658 this module was the only cython code left in the
qiskit-terra repository so unifying on a single compiled language will
reduce the maintanence burden in qiskit-terra. The second reason is
similar to the rationale in #7658 around why using rust over cython for
multi-threaded hybrid python module. The difference here though is
unlike in stochastic swap this module isn't as performance critical as
it's not nearly as widely used.

Details and comments

Wait for Implement multithreaded stochastic swap in rust #7658 to merge and rebase
Add release notes
Add docstrings for exported python function
More benchmarking and tuning

mtreinish · 2022-02-23T16:09:36Z

To quickly compare the performance with this PR vs the previous implementation I ran this script:

import time

import numpy as np
from qiskit.quantum_info import random_statevector
from qiskit.quantum_info import random_density_matrix
from qiskit.quantum_info import Pauli
import matplotlib.pyplot as plt

size = []
x_times = []
random_operator_times = []

for n in range(1, 30):
    size.append(2**n)
    statevector = random_statevector(2**n)
    pauli_local_times = []
    pauli_x = Pauli("X")
    for i in range(5):
        start = time.time()
        statevector.expectation_value(pauli_x)
        stop = time.time()
        pauli_local_times.append(stop - start)
    x_times.append(np.mean(pauli_local_times))

plt.loglog(size, x_times)
plt.title('Random Statevector Expectation value time for Pauli("X") observable')
plt.savefig("test.png")

With this PR applied:

vs the current main branch:

coveralls · 2022-02-23T16:38:53Z

Pull Request Test Coverage Report for Build 1964856018

3 of 3 (100.0%) changed or added relevant lines in 3 files are covered.
No unchanged relevant lines lost coverage.
Overall coverage increased (+0.002%) to 83.465%

Totals
Change from base Build 1964131760:	0.002%
Covered Lines:	52438
Relevant Lines:	62826

💛 - Coveralls

mtreinish · 2022-02-25T16:45:31Z

After writing 3751216 I reran the benchmarks to compare the performance I graphed the ratio compared to cython:

Which shows that 3751216 significantly improves the single threaded performance and it's faster than cython almost everywhere now. Then once we hit 19 qubits and start running multithreaded it's even faster. (in the graph above I'm running on my workstation with 32 physical cores and 64 logical cores, the scaling might not be as good on smaller systems)

I also tweaked the benchmark script I used to collect the data to be a bit more realistic:

import io
import time

import numpy as np
from qiskit.quantum_info import random_statevector
from qiskit.quantum_info import random_density_matrix
from qiskit.quantum_info import random_pauli
import matplotlib.pyplot as plt

size = []
x_times = []
random_operator_times = []

rng = np.random.default_rng(seed=42)
PAULI_CHOICES = ["I", "X", "Y", "Z"]

for n in range(1, 30):
    size.append(2**n)
    statevector = random_statevector(2**n)
    pauli_local_times = []
    pauli_x = random_pauli(n, seed=rng)
    for i in range(5):
        start = time.time()
        statevector.expectation_value(pauli_x)
        stop = time.time()
        pauli_local_times.append(stop - start)
    x_times.append(np.mean(pauli_local_times))

This commit replaces the cython implementation of the pauli expectation value functions with a multithreaded rust implementation. This was done primarily for two reasons, the first and primary reason for this change is because after Qiskit#7658 this module was the only cython code left in the qiskit-terra repository so unifying on a single compiled language will reduce the maintanence burden in qiskit-terra. The second reason is similar to the rationale in Qiskit#7658 around why using rust over cython for multi-threaded hybrid python module. The difference here though is unlike in stochastic swap this module isn't as performance critical as it's not nearly as widely used.

This commit tunes the sum for the single threaded path. Using the iterator sum() method is very convienent but for the single threaded path it doesn't create the most efficient output. This was causing a regression in performance over the previous cython version. To address that issue, this commit adds a new tuned function which does a chunked sum which the compiler can handle better. It more closely models how we'd do this with vectorized SIMD instructions. As a future step we can look at using simdeez https://github.com/jackmott/simdeez to further optimize this by doing runtime CPU feature detection and leveraging SIMD instrinsics (we might want to look at using `fast_sum()` in the multithreaded path if we do that too).

This commit updates the asv configuration to support two recent changes in the terra repo. The first is updating the supported python version list to reflect the current versions supported by terra. Python 3.6 is no longer supported and python 3.10 is now supported. Additionally, after Qiskit/qiskit#7658 merged setuptools-rust and Rust are now being used to build compiled extensions. While cython is still being used, it's use will be removed soon with Qiskit/qiskit#7702. This commit updates the build configuration to build the rust extension and then build a wheel from it instead of building the cython extension.

With Qiskit/qiskit#7658 and Qiskit/qiskit#7702 not far behind the requiremetns for building terra from source will be changed. A C++ compiler is no longer required and instead a rust compiler is needed. This commit updates the instructions on building from source and also removes so old out of date notes from the document at the same time.

mtreinish · 2022-03-01T18:37:21Z

This should be ready for review now

src/pauli_exp_val.rs

src/lib.rs

src/pauli_exp_val.rs

Co-authored-by: Kevin Hartman <kevin@hart.mn>

The functions only work for at most for number of qubits < usize bits anything larger would cause an overflow. While rust provides overflow checking in debug mode it disables this for performance in release mode. Sice we ship binaries in release mode this commit adds an overflow check for the num_qubits argument to ensure that we don't overflow and produce incorrect results.

setup.py

The setup_requires field in the setup.py is deprecated and has been superseded by the pyproject.toml to define build system dependencies. Since we're already relying on the pyproject.toml to install setuptools-rust for us having the setup_requires line will do nothing but potentially cause issues as it will use an older install mechanism that will potentially conflict with people's environments.

kevinhartman

Looks good!

Do we think it's an issue for these algorithms to be capped at ~63 qubits when porting to Rust? I suppose they'd've had the same limit in Cython?

src/pauli_exp_val.rs

mtreinish · 2022-03-10T17:01:53Z

Looks good!

Do we think it's an issue for these algorithms to be capped at ~63 qubits when porting to Rust? I suppose they'd've had the same limit in Cython?

In practice they're capped much lower than 63 qubits, these are only called internally by the statevector and density matrix classes. A statevector requires ~16 bytes * 2^num qubits of memory (and a density matrix is that squared because it's 2d) we'll hit either insufficient memory or the max number of array elements trying to build the objects. We probably don't need the overflow guard here because in practice I don't think we'll ever see it, I added it because an int comparison is quick and just in case something decided to call this outside of quantum_info.

src/pauli_exp_val.rs

kevinhartman

LGTM!

kevinhartman · 2022-03-10T22:29:01Z

Taking this moment (PR with this number being merged) to also commemorate the Bode 7702 Vocoder.

As part of Qiskit#7702 we added a function for performing a sum over an array/Vec of f64 values that is optimized to let the compiler use SIMD instructions to speed up the computation. The stochastic swap rust module performs a very similar sum multiple times as part of each swap trial. This commit moves the fast_sum() function used in the pauli expectation value functions to a common location and updates stochastic swap to use it too.

This follows up on Qiskit#7702, which removed the last of the Cython code. The current change was was presumably intended to be part of that PR, I think, based on the release note added there: > Cython is no longer a build dependency of Qiskit Terra and is no > longer required to be installed when building Qiskit Terra from > source.

This follows up on #7702, which removed the last of the Cython code. The current change was was presumably intended to be part of that PR, I think, based on the release note added there: > Cython is no longer a build dependency of Qiskit Terra and is no > longer required to be installed when building Qiskit Terra from > source.

* Update building from source instructions With Qiskit/qiskit#7658 and Qiskit/qiskit#7702 not far behind the requiremetns for building terra from source will be changed. A C++ compiler is no longer required and instead a rust compiler is needed. This commit updates the instructions on building from source and also removes so old out of date notes from the document at the same time. * Apply suggestions from code review * Consistently capitalise "Rust" * Add section on modifying rust extension * Fix typos * Empty-Commit to retrigger ci after outage Co-authored-by: Jake Lishman <jake@binhbar.com>

…kage#1437) This commit updates the asv configuration to support two recent changes in the terra repo. The first is updating the supported python version list to reflect the current versions supported by terra. Python 3.6 is no longer supported and python 3.10 is now supported. Additionally, after Qiskit#7658 merged setuptools-rust and Rust are now being used to build compiled extensions. While cython is still being used, it's use will be removed soon with Qiskit#7702. This commit updates the build configuration to build the rust extension and then build a wheel from it instead of building the cython extension.

) * Update building from source instructions With Qiskit#7658 and Qiskit#7702 not far behind the requiremetns for building terra from source will be changed. A C++ compiler is no longer required and instead a rust compiler is needed. This commit updates the instructions on building from source and also removes so old out of date notes from the document at the same time. * Apply suggestions from code review * Consistently capitalise "Rust" * Add section on modifying rust extension * Fix typos * Empty-Commit to retrigger ci after outage Co-authored-by: Jake Lishman <jake@binhbar.com>

…kage#1437) This commit updates the asv configuration to support two recent changes in the terra repo. The first is updating the supported python version list to reflect the current versions supported by terra. Python 3.6 is no longer supported and python 3.10 is now supported. Additionally, after Qiskit#7658 merged setuptools-rust and Rust are now being used to build compiled extensions. While cython is still being used, it's use will be removed soon with Qiskit#7702. This commit updates the build configuration to build the rust extension and then build a wheel from it instead of building the cython extension.

) * Update building from source instructions With Qiskit#7658 and Qiskit#7702 not far behind the requiremetns for building terra from source will be changed. A C++ compiler is no longer required and instead a rust compiler is needed. This commit updates the instructions on building from source and also removes so old out of date notes from the document at the same time. * Apply suggestions from code review * Consistently capitalise "Rust" * Add section on modifying rust extension * Fix typos * Empty-Commit to retrigger ci after outage Co-authored-by: Jake Lishman <jake@binhbar.com>

mtreinish added the on hold Can not fix yet label Feb 23, 2022

mtreinish added this to the 0.20 milestone Feb 23, 2022

mtreinish requested review from a team and ikkoham as code owners February 23, 2022 16:02

mtreinish added the performance label Feb 23, 2022

mtreinish added 2 commits February 28, 2022 16:54

mtreinish force-pushed the rust-pauli-expval branch from 3751216 to 1a973ef Compare February 28, 2022 21:54

Add release notes

f30314b

mtreinish changed the title ~~[WIP] Replace pauli expectation value cython with multithreaded rust implementation~~ Replace pauli expectation value cython with multithreaded rust implementation Feb 28, 2022

mtreinish added Changelog: New Feature Include in the "Added" section of the changelog Changelog: Removal Include in the Removed section of the changelog and removed on hold Can not fix yet labels Feb 28, 2022

mtreinish mentioned this pull request Mar 1, 2022

Update asv.conf.json to support recent changes Qiskit/qiskit-metapackage#1437

Merged

mtreinish added 3 commits March 1, 2022 10:47

Fix lint

4fd11f5

Add docstring and signature to rust functions

601ad69

Merge branch 'main' into rust-pauli-expval

d162b7d

mtreinish mentioned this pull request Mar 1, 2022

Update building from source instructions Qiskit/qiskit-metapackage#1439

Merged

mtreinish added the Rust This PR or issue is related to Rust code in the repository label Mar 3, 2022

Merge remote-tracking branch 'origin/main' into rust-pauli-expval

e3ee85b

mtreinish mentioned this pull request Mar 8, 2022

Reimplement DenseLayout as a Parallel Algorithm in Rust #7740

Merged

4 tasks