Bytecode compile times are O(nlocals**2)

[brandtbucher]

@JelleZijlstra discovered something interesting yesterday: bytecode compile times on main are currently quadratic in the number of local variables (3.11 is still linear). For example, a function with 100,000 assignments to unique local variables takes well over a minute to compile (but is less than 2 seconds on 3.11).

I believe the culprit is the new LOAD_FAST/LOAD_FAST_CHECK stuff. The current implementation appears to loop over every local variable, and for each one, loop over all bytecode instructions. This can probably be refactored to run in one pass for all locals.

CC: @markshannon @sweeneyde

[sweeneyde]

If it proves too complex to track multiple local variable states at the same time, another solution might be to only scan for the first hundred local variables or something like that.

It's not clear to me how easy tracking everything would be. Do we need potentially unbounded stack space, since blocks might need to be processed more than once? Would the approach still be linear in the face of many different del statements in unpredictable places? Maybe we don't care.

But if you manage to do it all linearly, that sounds great.

[sweeneyde]

Here's an example of a "hard" case:

def f():
    a1 = a2 = a3 = a4 = a5 = 1
    for i in range(2):
        if cond1(): use(a1)
        else: del a1
        
        if cond2(): use(a2)
        else: del a2
        
        if cond3(): use(a3)
        else: del a3
        
        if cond4(): use(a4)
        else: del a4
        
        if cond5(): use(a5)
        else: del a5

# (generalize to more than 5 locals...)

For example, the fact that del a3 may have happened has to propagate to the if cond4(), to if cond5(), to for i, to if cond1(), to if cond2(), to if cond3(), to use(a3). Combining that all together with the effects of all other del statements, there are n deletions that we have to move over at least n basicblock linkages each.

That's not a proof that linear time is impossible, just that there may be some cleverness required (moving info across multiple basicblock linkages at once?) if we want linear time in all cases. However, some sort of heuristic may be possible that takes care of most typical cases without many/any del statements.

By the way, the reason to propagate "possible undefinedness" rather than "certain definedness" is that any path with undefinedness leading into a LOAD_FAST is enough to have to use LOAD_FAST_CHECK.

[sweeneyde]

Here's a script that gathered co_nlocals data some from Sympy, which I figured might have some long code objects:

The script

from pathlib import Path
from types import CodeType

def all_code_recursive(code):
    # based on https://github.com/faster-cpython/tools/blob/main/scripts/count_opcodes.py
    yield code
    for x in code.co_consts:
        if isinstance(x, CodeType):
            yield from all_code_recursive(x)

def all_code(root):
    for path in root.glob("**/*.py"):
        text = path.read_text("utf-8")
        code = compile(text, path.name, "exec")
        yield from all_code_recursive(code)

from collections import Counter

import sympy

var_counts = Counter()
init = Path(sympy.__file__)
for code in all_code(init.parent):
    n = code.co_nlocals
    var_counts[code.co_nlocals] += 1
    if code.co_nlocals > 50:
        print(code.co_qualname)

print(dict(sorted(var_counts.items())))

total = var_counts.total()

for bound in [2, 5, 10, 20, 50, 100, 200, 500, 1000]:
    bigger = sum(count for n, count in var_counts.items() if n > bound)
    print(f"{bigger/total:.2%} of code objects have >{bound} locals")

The output

test_DiagramGrid 53
_FixSimplify 144
_SimplifyAntiderivative 57
_TrigSimplifyAux 61
_ExpandIntegrand 200
binomial_products 1044
exponential 330
hyperbolic 1069
integrand_simplification 143
inverse_hyperbolic 1546
inverse_trig 1442
linear_products 485
logarithms 466
miscellaneous_algebraic 1204
miscellaneous_integration 221
miscellaneous_trig 877
piecewise_linear 64
quadratic_products 1291
secant 1727
sine 2836
special_functions 477
tangent 1208
trinomial_products 1022
test_binary_operators 60
test_var_decl 64
test_TransferFunction_functions 58
test_aux_dep 58
test_non_central_inertia 65
test_sub_qdot 59
test_bicycle 109
test_linearize_rolling_disc_kane 59
modgcd_bivariate 52
roots_quintic 67
_vertical_bisection 68
_horizontal_bisection 68
dup_isolate_complex_roots_sqf 71
powsimp 53
_solve 58
_solve_system 55
unrad 63
BinaryQuadratic.solve 57
classify_ode 51
test__classify_linear_system 56
test_sysode_linear_neq_order1_type1 53
test_sysode_linear_neq_order1_type1_slow 103
test_sysode_linear_neq_order1_type2 75
test_DiscreteMarkovChain 52
test_M38 56
{0: 10914, 1: 8656, 2: 13341, 3: 5899, 4: 3445, 5: 2496, 6: 2478, 7: 2358, 8: 2162, 9: 1656, 10: 1221, 11: 904, 12: 515, 13: 329, 
14: 215, 15: 177, 16: 133, 17: 117, 18: 95, 19: 66, 20: 64, 21: 55, 22: 33, 23: 35, 24: 40, 25: 33, 26: 27, 27: 22, 28: 22, 29: 19, 30: 17, 31: 12, 32: 16, 33: 10, 34: 8, 35: 5, 36: 7, 37: 8, 38: 8, 39: 7, 40: 4, 41: 3, 42: 4, 43: 2, 44: 2, 45: 3, 46: 1, 47: 2, 49: 3, 50: 1, 51: 1, 52: 2, 53: 3, 55: 1, 56: 2, 57: 2, 58: 3, 59: 2, 60: 1, 61: 1, 63: 1, 64: 2, 65: 1, 67: 1, 68: 2, 71: 1, 75: 1, 103: 1, 109: 1, 143: 1, 144: 1, 200: 1, 221: 1, 330: 1, 466: 1, 477: 1, 485: 1, 877: 1, 1022: 1, 1044: 1, 1069: 1, 1204: 1, 1208: 1, 1291: 1, 1442: 1, 1546: 1, 1727: 1, 2836: 1}
66.08% of code objects have >1 locals
42.96% of code objects have >2 locals
22.44% of code objects have >5 locals
5.32% of code objects have >10 locals
0.79% of code objects have >20 locals
0.08% of code objects have >50 locals
0.04% of code objects have >100 locals
0.03% of code objects have >200 locals
0.02% of code objects have >500 locals
0.02% of code objects have >1000 locals
0.00% of code objects have >2000 locals
0.00% of code objects have >5000 locals

Summarized output:

For .py files in Sympy distribution:
------------------------------------
66.08% of code objects have >1 locals
42.96% of code objects have >2 locals
22.44% of code objects have >5 locals
5.32% of code objects have >10 locals
0.79% of code objects have >20 locals
0.08% of code objects have >50 locals
0.04% of code objects have >100 locals
0.03% of code objects have >200 locals
0.02% of code objects have >500 locals
0.02% of code objects have >1000 locals
0.00% of code objects have >2000 locals

Data from other places:

For .py files in Numpy distribution:
------------------------------------
66.77% of code objects have >1 locals
44.70% of code objects have >2 locals
15.82% of code objects have >5 locals
3.37% of code objects have >10 locals
0.38% of code objects have >20 locals
0.03% of code objects have >50 locals
0.00% of code objects have >100 locals

For .py files in Lib/test/ (ignoring SytaxError):
-------------------------------------------------
55.63% of code objects have >1 locals  
33.39% of code objects have >2 locals  
8.09% of code objects have >5 locals   
1.10% of code objects have >10 locals  
0.06% of code objects have >20 locals  
0.00% of code objects have >50 locals

For .py files in Django distribution:
-------------------------------------
61.79% of code objects have >1 locals
38.18% of code objects have >2 locals
11.70% of code objects have >5 locals
2.68% of code objects have >10 locals
0.32% of code objects have >20 locals
0.00% of code objects have >50 locals

[JelleZijlstra]

Thanks! The biggest one is https://github.com/sympy/sympy/blob/0e4bab73562d6f90fcdf5fa079731f26a455347c/sympy/integrals/rubi/rules/sine.py#L148, which looks terrifying. It is noticeably slower to compile on 3.12 than 3.11:

% time ./python.exe -m compileall sine.py
Compiling 'sine.py'...
./python.exe -m compileall sine.py  2.66s user 0.09s system 99% cpu 2.763 total
% time ~/py/venvs/311-jun14/bin/python3 -m compileall sine.py
Compiling 'sine.py'...
~/py/venvs/311-jun14/bin/python3 -m compileall sine.py  0.98s user 0.09s system 98% cpu 1.082 total

[sweeneyde]

One speedup might come from doing some precomputation for the "first pass": start by storing i --> array of *basicblocks where DELETE_FAST(i) occurs (often empty). This wouldn't guarantee linear time overall, but it would greatly speed up almost every first pass. A parameter variable with no del ... statements could be completely skipped for free.

The b->b_visited = 0; loop is also quadratic, but faster. We could instead widen b_visited to more than one bit (or add another field) and do something like

#define MAYBE_PUSH(B) do {                          \
        if ((B)->b_visited > target) {              \
            *(*stack_top)++ = (B);                  \
            (B)->b_visited = target + 1;            \
        }                                           \
    } while (0)

Though again, I'm not sure whether it would be better to just limit the number of locals to analyze and set the rest to use LOAD_FAST_CHECK. Or maybe do both.

If someone else hasn't already started a patch, I can work on this.

[markshannon]

It won't reduce the big-O complexity, but handling 64 locals at once (using an int64_t as a vector of 64 booleans) would reduce the constant factor by ~60

[sweeneyde]

This should be fixed now. Thanks for finding this!

(feel free to re-open if I missed something)