Summing programs takes exponentially long

[bramathon]

Issue Description

In some cases, programs are combined like so:

sum((program for _ in range(100)), Program());

This is used in forest-benchmarking for example. When the program is an object of a significant size, I observe exponential cost to this operation.

On close examination, I also observe exponential cost for pyquil 3, but it's much faster so It's not noticed.

Code Snippet

import pyquil
print(pyquil.__version__)
from pyquil.api import get_qc
from pyquil.quil import Program
from pyquil.gates import RX

qc = get_qc("Aspen-M-3")
calibration_program = qc.compiler.get_calibration_program()

depth = 80

rotation = calibration_program.copy_everything_except_instructions()
rotation += RX(1.57, 0)

%%time
sum((Program(rotation) for _ in range(depth)), Program());

Error Output

The timing of this operation is below. Extrapolating from n=2, n=80 should take 7.2s

# pyquil 4
# num = 2, time = 0.18
# num = 4, time = 0.49
# num = 6, time = 0.88
# num = 10, time = 2.39
# num = 20, time = 7.1
# num = 40, time = 25.1
# num = 80, time = 98

# pyquil 3
# pyquil 3
# num = 2, time = 111us
# num = 20, time = 4.19ms
# num = 40, time = 1.91ms
# num = 80, time = 16.7ms

[MarquessV]

sum uses the __add__ method, so it's not taking advantage of the optimizations we implemented for #1647. A loop that uses the += operator should be faster. Alternatively, you could use reduce to get a similar one liner:

reduce(Program.__iadd__, (Program(rotation) for _ in range(depth)), Program())

I'll explore ways to optimize this path further, but hopefully this is helpful in the interim.

[MarquessV]

4.0.1 includes optimizations from quil that should improve the performance of in-place addition even further.