quantumlib / Cirq

A Python framework for creating, editing, and invoking Noisy Intermediate Scale Quantum (NISQ) circuits.
Apache License 2.0
4.28k stars 1.02k forks source link

Speed up hashing for GridQubit, LineQubit, and NamedQubit #6350

Closed maffoo closed 1 year ago

maffoo commented 1 year ago

This speeds up hashing on GridQubit, GridQid, LineQubit, and LineQid. Instead of using _compat.cached_method, we store an explicit self._hash property to cache computing the hash. We also make the constructors explicit in the concrete classes with no need to call a subperclass constructor. We did some basic benchmarks to compare performance with current master. On this branch GridQubit.__hash__ dropped from 1.3us to 488ns (2.66x speedup), while repeated hashing of the same grid qubit dropped from 150ns to 121ns (1.24x speedup). Similarly, LineQubit.__hash__ dropped from 685uns to 453ns (1.51x speedup), while repeated hashing of the same line qubit dropped from 142ns to 124ns (1.15x speedup).

On master:

In [2]: gq = cirq.GridQubit(1, 2)

In [3]: %timeit hash(gq)
150 ns ± 1.66 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

In [4]: %timeit hash(cirq.GridQubit(1, 2))
1.3 µs ± 25.2 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

In [5]: lq = cirq.LineQubit(3)

In [6]: %timeit hash(lq)
142 ns ± 2.85 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

In [7]: %timeit hash(cirq.LineQubit(3))
685 ns ± 14.1 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

and on this branch:

In [2]: gq = cirq.GridQubit(1, 2)

In [3]: %timeit hash(gq)
121 ns ± 0.737 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

In [4]: %timeit hash(cirq.GridQubit(1, 2))
488 ns ± 2.16 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

In [5]: lq = cirq.LineQubit(3)

In [6]: %timeit hash(lq)
124 ns ± 1.53 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

In [7]: %timeit hash(cirq.LineQubit(3))
453 ns ± 2.19 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
codecov[bot] commented 1 year ago

Codecov Report

All modified and coverable lines are covered by tests :white_check_mark:

Comparison is base (3c81961) 97.84% compared to head (c43f689) 97.84%.

Additional details and impacted files ```diff @@ Coverage Diff @@ ## master #6350 +/- ## ======================================= Coverage 97.84% 97.84% ======================================= Files 1110 1110 Lines 96656 96696 +40 ======================================= + Hits 94572 94612 +40 Misses 2084 2084 ```

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

maffoo commented 1 year ago

Updated to optimized NamedQubit as well; first-time hashing sped up from 1.78us to 553ns (3.2x speedup) and repeated hashing sped up from 220ns to 162ns (1.36x speedup).

On master:

In [2]: nq = cirq.NamedQubit("abc")

In [3]: %timeit hash(nq)
220 ns ± 14.1 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

In [4]: %timeit hash(cirq.NamedQubit("abc"))
1.78 µs ± 13.9 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

On this branch:

In [2]: nq = cirq.NamedQubit("abc")

In [3]: %timeit hash(nq)
162 ns ± 4.14 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

In [4]: %timeit hash(cirq.NamedQubit("abc"))
553 ns ± 1.16 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)