Add more efficient bit packing functions for BitArray

chriseclectic commented 1 month ago

Summary

This adds internal utility functions for improved bit-packing, unpacking, and slicing for internal use by BitArray.

Details and comments

These functions give additional functionality for packing and unpacking arbitrary indexes bits in larger arrays by only working with the non-zero bytes, rather than having to pack or unpack the full array as was previous done.

The functions can also be used independently for working with byte and boolean arrays outside of BitArray, since they don't assume the shot-axis formatting required by BitArray. These helper functions might be a good candidate for porting to Rust in the future.

qiskit-bot commented 1 month ago

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

@Qiskit/terra-core
@ajavadia
@levbishop
@t-imamichi

coveralls commented 1 month ago

Pull Request Test Coverage Report for Build 10579730063

Warning: This coverage report may be inaccurate.

This pull request's base commit is no longer the HEAD commit of its target branch. This means it includes changes from outside the original pull request, including, potentially, unrelated coverage changes.

For more information on this, see Tracking coverage changes with pull request builds.
To avoid this issue with future PRs, see these Recommended CI Configurations.
For a quick fix, rebase this PR at GitHub. Your next report should be accurate.

Details

187 of 201 (93.03%) changed or added relevant lines in 4 files are covered.
365 unchanged lines in 10 files lost coverage.
Overall coverage decreased (-0.02%) to 89.198%

Changes Missing Coverage	Covered Lines	Changed/Added Lines	%
qiskit/primitives/containers/bit_packing.py	166	180	92.22%
<!--	Total:	187	201	93.03%	-->

Files with Coverage Reduction	New Missed Lines	%
qiskit/primitives/containers/bit_array.py	1	95.9%
crates/qasm2/src/expr.rs	1	94.02%
qiskit/transpiler/passes/synthesis/unitary_synthesis.py	2	88.43%
crates/circuit/src/interner.rs	4	92.0%
qiskit/synthesis/two_qubit/xx_decompose/decomposer.py	6	90.84%
crates/qasm2/src/lex.rs	7	91.73%
crates/circuit/src/packed_instruction.rs	8	96.56%
crates/qasm2/src/parse.rs	18	96.69%
crates/circuit/src/circuit_data.rs	26	92.18%
crates/circuit/src/dag_circuit.rs	292	89.34%
<!--	Total:	365	-->

Totals
Change from base Build 10563485346:	-0.02%
Covered Lines:	71781
Relevant Lines:	80474

💛 - Coveralls

t-imamichi commented 1 month ago

Thank you for the improvement. I tested it with the following script and confirmed the performance improvement for slice_bits.

from timeit import timeit
import numpy as np
from qiskit.primitives.containers import BitArray

def bench_from_bool_array(num_shots: int, num_qubits: int, seed: int):
    rng = np.random.default_rng(seed)
    arr = rng.integers(2, size=(num_shots, num_qubits), dtype=bool)
    print("from_bool_array")
    print(f"{timeit(lambda: BitArray.from_bool_array(arr), number=1)} sec\n")
    ba = BitArray.from_bool_array(arr)
    return ba

def bench_slice_bits(ba: BitArray):
    indices = [1] * 4
    print("slice_bits")
    print(ba.slice_bits(indices).get_counts())
    print(f"{timeit(lambda: ba.slice_bits(indices), number=1)} sec\n")

def bench_concatenate(ba: BitArray):
    print("concatenate")
    print(f"{timeit(lambda: BitArray.concatenate([ba] * 10), number=1)} sec\n")

ba = bench_from_bool_array(100_000, 100_000, 123)
ba = ba.reshape(1, ba.size)
bench_slice_bits(ba)
bench_concatenate(ba)

main branch

from_bool_array
0.8163162080018083 sec

slice_bits
{'0000': 49992, '1111': 50008}
1.7400712500020745 sec

concatenate
1.5998445830045966 sec

this PR

from_bool_array
0.8202344169985736 sec

slice_bits
{'0000': 49992, '1111': 50008}
0.003202332998625934 sec

concatenate
1.6464810420002323 sec

Qiskit / qiskit