Speed up circuit construction when contents are a list of moments #5898
Conversation
tanujkhattar
requested review from
a team,
vtomole and
cduck
as code owners
| @@ -1741,11 +1741,15 @@ def __init__( | |||
| circuit. | |||
| """ | |||
| self._moments: List['cirq.Moment'] = [] | |||
| flattened_contents = tuple(ops.flatten_to_ops_or_moments(contents)) | |||
There was a problem hiding this comment.
I'd probably go for list instead, since we don't need immutability here, but it'd be interesting to know if there is any performance difference one way or the other. If not, then up to you whether to use list or tuple.
There was a problem hiding this comment.
Tuples are usually slightly faster than lists because they don't overallocate like lists (to make append faster) so the memory footprint is more compact. Also, tuples don't need to go through an additional level of indirection when accessing elements like lists; see https://stackoverflow.com/a/22140115 for more details
As an example, here are numbers for running the operation by operation construction benchmark (in which the flattened_contents would contain all the operations and hence have a large size).
Using tuples for flattened_contents:
[ 0.00%] ·· Benchmarking existing-py_usr_local_google_home_tanujkhattar_anaconda3_envs_cirq_bin_python
[ 50.00%] ··· Running (circuit_construction.SurfaceCodeRotatedMemoryZ.time_circuit_construction_operations_by_operation--).
[100.00%] ··· circuit_construction.SurfaceCodeRotatedMemoryZ.time_circuit_construction_operations_by_operation ok
[100.00%] ··· ========== ============
distance
---------- ------------
3 2.68±0.1ms
5 18.2±0.7ms
7 72.2±2ms
9 198±6ms
11 464±10ms
13 933±40ms
15 1.68±0.06s
17 2.95±0.09s
19 4.73±0.2s
21 6.39±0.02s
23 9.50±0.03s
25 13.7±0.4s
========== ============
Using lists for flattened_contents:
[ 0.00%] ·· Benchmarking existing-py_usr_local_google_home_tanujkhattar_anaconda3_envs_cirq_bin_python
[ 50.00%] ··· Running (circuit_construction.SurfaceCodeRotatedMemoryZ.time_circuit_construction_operations_by_operation--).
[100.00%] ··· circuit_construction.SurfaceCodeRotatedMemoryZ.time_circuit_construction_operations_by_operation ok
[100.00%] ··· ========== ============
distance
---------- ------------
3 2.81±0.2ms
5 20.3±0.8ms
7 79.9±3ms
9 204±4ms
11 467±10ms
13 934±10ms
15 1.75±0.1s
17 2.92±0.08s
19 4.42±0.1s
21 6.65±0.02s
23 9.85±0.04s
25 13.8±0.2s
========== ============
…antumlib#5898) * Speed up circuit construction when contents are a list of moments * Add explicit cast to fix mypy errors
…antumlib#5898) * Speed up circuit construction when contents are a list of moments * Add explicit cast to fix mypy errors
When the input is a list of moment, we can just assign that list to
self._momentsinstead of using eitherappendor_load_contents_with_earliest_strategy.Circuit.append: This is already essentiallyO(D)if the the input is a list of moments because of the special caseisinstancecheck:Cirq/cirq-core/cirq/circuits/circuit.py
Line 2102 in ff81f80
Circuit._load_contents_with_earliest_strategy: has complexityO(D * Q)instead ofO(D), even if input is allMoments because it iterates on all the qubits that the moment acts on, for each moment; to keep track of the latest used index in case it encounters an operation which is not part of a moment and needs to be inserted using the earliest strategy. SeeCirq/cirq-core/cirq/circuits/circuit.py
Line 1825 in ff81f80
The fact that introducing
_load_contents_with_earliest_strategyslowed down moment-by-moment circuit construction toO(D * Q)instead ofO(D)is also visible from the regressions in circuit construction asv benchmarks:After this change, the moment-by-moment circuit construction time for a distance 25 surface code is again ~30ms instead of > 3 seconds. The output for
asv runon a local copy is as follows:compared to the current master version:
cc @dabacon @dstrain115 @maffoo @dkothari11