Audit code for use of list comprehensions where generators would be faster

[rileyjmurray]

While reviewing PR #445 I noticed that pyGSTi often uses patterns like tuple([ ... ]), or all([ ... ]), or sum([ ... ]), where [...] is a list comprehension. For most (all?) of these situations it should be sufficient to just drop the brackets. The resulting code would use Python's more efficient generator abstraction rather than list comprehensions.

A quick sort of the pyGSTi codebase shows ...

• 210 hits for all([
• 70 hits for any([
• 161 hits for sum([
• 38 results for prod([
• 89 results for tuple([
• 32 results for set([
• 76 results for dict([

^ Those counts are slight overestimates since they don't restrict to .py files and they don't consider if an offending line is commented-out.

[coreyostrove]

Replying to the related comments from #445 here. I originally had a similar intuition to yours, that switching to a generator comprehension would be faster. I.e. that creating a list from an iterable and then passing it into a constructor for a tuple or set or whatnot would be slower, since you'd be wastefully instantiating an extra object and doing all of the memory operations associated with that. But when I implemented that change in the circuit code and profiled it I actually found it was noticeably slower in practice to use the generator expressions compared to using list comprehensions.

I no longer have the line_profiler results from when I had A/B tested this in situ within pyGSTi, so you'll have to take my word for it in that context, but I did whip up some quick synthetic benchmarks which are shown below.

Here is the code used for generating the benchmarks:

import matplotlib.pyplot as plt
from timeit import timeit

def list_comprehension_benchmark(outer_loop_count, inner_loop_count):
    def benchmark_func():
        for _ in range(outer_loop_count):
            tuple([i for i in range(inner_loop_count)])
    return benchmark_func

def generator_benchmark(outer_loop_count, inner_loop_count):
    def benchmark_func():
        for _ in range(outer_loop_count):
            tuple(i for i in range(inner_loop_count))
    return benchmark_func

list_comp_timings = [timeit(list_comprehension_benchmark(100, i), number=100) for i in range(1,1000,5)]
generator_timings = [timeit(generator_benchmark(100, i), number=100) for i in range(1,1000,5)]

plt.plot([i for i in range(1,1000,5)], list_comp_timings, label='List Comp')
plt.plot([i for i in range(1,1000,5)], generator_timings, label='Generator')
plt.legend()
plt.savefig('list_comp_vs_generator')

plt.plot([i for i in range(1,1000,5)], [list_time/gen_time for list_time,gen_time in zip(list_comp_timings, generator_timings)], label='List Comp to Gen Ratio')
plt.legend()
plt.savefig('list_comp_vs_generator_ratio')

Here are the results:

Based on these results using the list comprehension is ~30% faster than using the generator, and iirc this is in line with what I saw in practical use with the pyGSTi A/B testing. I also found this to be true for the set constructor and for things like sum and all (I don't recall testing any or prod, but suspect they would be similar). Your mileage may vary in terms of the actual relative difference, however. E.g. here is the same benchmark but for the set constructor instead of the tuple constructor.

Here we're looking at more like ~15% difference, so somewhat less significant than before.

And, since I have the benchmarking code already written, screw it, here is the results for sum as well:

Of course, when it comes to things like sum and prod perhaps a more productive thing to look into is whether we should be using numpy instead. This isn't always a net win, for example if using numpy to do a sum involves casting to an array first then depending on the amount of data I have found this is often a net loss. But if the data in question already is an ndarray, or we could otherwise refactor the code to use ndarrays throughout instead of lists, then that would likely be meaningfully better.

I couldn't tell you for sure why the list comprehensions are faster, but it is clear that they are allowing the underlying C implementations in CPython to make use of a faster codepath (perhaps because it knows a priori more about the size of the objects it is instantiating). Similarly, it is also worth noting that for the above benchmarks I was using CPython 3.9.13. This is undoubtedly implementation specific, so for all I know the situation is reversed in PyPy (though even if that was true it is very unlikely to enter into our development considerations). Caveat emptor!

P.S. What isn't put into question by any of the above is that generator expressions are much more memory efficient. So we should absolutely use them regardless of the performance considerations in situations where we're dealing with very large objects and/or where intermediate memory usage is a big concerns. In the context of #445 I wasn't concerned about the additional memory overhead.

P.P.S. I should have mentioned this in the above discussion, but 90% of the time everything I've stated above about the performance difference will genuinely not matter. I would only advocate strongly for using the list comprehension versions in particularly hot parts of the code, and specifically where the constructors in question are a meaningful contribution to the runtime of those subroutines. The circuit code happens to hit both of those criteria, but the majority of the codebase doesn't. Stylistically I actually prefer the generator version and am cool with using it so long as we make those changes with these considerations in mind, but that probably means we can't do so automagically.

[rileyjmurray]

Wow! Now that's surprising!

Thanks for digging into this so deeply and reporting back. As far as #445 goes, please feel free to mark any comments I left on this subject as resolved.

Two small notes

• I suspect that memory savings for a generator over a list comprehension will vary with list length much more than with the size of constituent objects. But in any case, if it isn't a clear win to switch then it isn't worth the development effort.
• I'm fine not making any design decisions based on what PyPy does. Although it might be useful to know that CPython 3.11 has substantial backend refactoring that can speed things up by 10%-50% (as reported in the Python 3.11 release notes).