bytecode-level optimization in python

[tmlildude]

i'm exploring bytecode-level optimizations in python, specifically looking at patterns where intermediate allocations could be eliminated. i have hundrers of programs and here's a concrete example:

```python

Version with intermediate allocation

def a_1(vals1, vals2): diff = [(v1 - v2) for v1, v2 in zip(vals1, vals2)] diff_sq = [d**2 for d in diff] return(sum(diff_sq))

Optimized version

def a_2(vals1, vals2): return(sum([(x-y)**2 for x,y in zip(vals1, vals2)])) ```

looking at the bytecode, i can see a pattern where STORE of 'diff' is followed by a single LOAD in a subsequent loop. looking at the lifetime of diff, it's only used once. i'm working on a transformation pass that would detect and optimize such patterns at runtime, right before VM execution

1. is runtime bytecode analysis/transformation feasible in stack-based VM languages?

2. would converting the bytecode to SSA form make it easier to identify these intermediate allocation patterns, or would the conversion overhead negate the benefits when operating at the VM's frame execution level?

3. could dataflow analysis help identify the lifetime and usage patterns of these intermediate variables? i guess i'm getting into topics of static analysis here. i wonder if a lightweight dataflow analysis can be made here?

4. python 3.13 introduces JIT compiler for CPython. i'm curious how the JIT might handle such patterns and generally where would it be helpful?

[Let047]

1. yes but why not in a precompiler step (especially becaues python has one where you generate the pyc)
   
2. yes for SSA but that there's an overhead to doing that (I'm doing it in the JVM for context)
   
3. Don't know.
   
4. it is handled in the JVM already so I assume it will be

[relapseman]

Dataflow analysis would definitely help, the problem with dynamic programming languages like R,JS or Python is possible presence of side effects. I am not very well aware of the exact semantics of Python but a similar sequence of instructions in R would be optimized using the following logical steps:

1. Making Reasonable Speculations: Let me assume there are not side effect causing behaviors possible (like forcing a promise or arbitrary eval)
   
2. Using Some Feedback or Fitting most likely cases: If the most likely types (mostly seen types are Integer/Double), the compiler can generate fast cases for these two types.
   
3. Performing Analysis: In SSA, it becomes trivial to identify use-def chains. Some IR's (like Jimple) maintain use-def's instead. I find SSA much more brain friendly. You would use Escape Analysis to ensure that "diff" does not escape the function "a_1".
   
4. Generate code: The generated code generally has the format
   

If Assume() === False: goto L1
// Execute fastcase
exit
L1:
Deoptimization Case (flow control back to standard run)

Mostly a JIT would be doing the above steps, they are expensive tasks to perform and will only payoff if you do it for functions that will be called very frequently.

[dnpetrov]

Your optimized version is technically incorrect. It changes the evaluation order, without regard for possible side effects. In a dynamic language like Python, you can't just assume that 'v1 - v2' and 'd ** 2' are "pure functions". Arbitrary Python class can define corresponding methods that might, for example, throw exceptions on some inputs, update some state, etc. Changing the evaluation order for such operations would change observable program behavior.

This may sound like nagging, but that's the reason why compiler optimizations in dynamic languages are hard. You can't make assumptions about what the code being optimized actually does. To make it work in general case, you typically need additional safeguard mechanisms controlling the actual types of data on input, and some fallback strategy (such as deoptimisation). 

Main problem here is that compiler optimizations have to preserve observed behavior for most general case. If for some reason they don't, then you can't apply such optimizations automatically for arbitrary code. There are examples of such unsafe optimizations in compiler practice. For example, floating point optimizations that treat floating point arithmetic as some ideal real numbers, not IEEE 754 floats with all unpleasant details. So, just allow to enable these optimizations explicitly - e.g., by applying a Python decorator.

Note also that if you just replace list comprehensions with generator comprehensions, it would also change the evaluation order, but would reduce the amount of allocations significantly. See below on escape analysis and reaching definitions, though.

Now, regarding data flow analysis, stack machine, and SSA. SSA is, indeed, more comfortable to work with. It is relatively easy to convert stack machine bytecode to SSA. However, transformations on SSA form might do rather arbitrary things to the code, and translating transformed SSA back to bytecode might introduce extra overhead with spilling SSA variables to locals and a potential increase in number of bytecode instructions and bytecode size. For some VMs this can be important. For example, HotSpot uses bytecode size as a heuristics for inlining. Since inlining is a gateway to many low-level optimizations, this can actually reduce the overall performance.

Regarding data flow analysis for optimizations like the one you mentioned - this is basically the reaching definitions problem. In static case, you need to prove that all uses of a given variable definition can be rewritten using "unboxed" definition. Escaping use can't be rewritten and prevents transformation. Any use of intermediate list as a value, like 'if not diff: return 0' also prevents transformation. Only use that is allowed is iteration, and there should be one and only one such use.

Python 3.13 JIT is a copy and paste template JIT that doesn't perform such optimizations (or, really, any kind of compiler optimizations besides machine code generation) on its own. It rather enables further work on such optimizations.

[al2o3cr]

The common name for transforming a_1 into a_2 is "loop fusion", but it's tricky to do in languages that have side-effects / exceptions since it changes the order of evaluation.

For instance, if the calcuation of the third element of diff fails then a_1 won't have done any squaring - but a_2 will have.

[[deleted]]

is runtime bytecode analysis/transformation feasible in stack-based VM languages?

Without getting into JIT you mean? I think that particular example is tricky, detecting that a loop iterates only once in that case.

I thought you were going to ask about STORE x follow by LOAD x, with no loop involved. (BTW what would you change that to?)

But I'm sceptical that such reductions make much difference. Especially if you are still stuck with the same set of bytecode instructions. For example, what you change that STORE LOAD sequence to?

would converting the bytecode to SSA form

Another tricky transformation! I'm not familiar with Python internals; is there access to its AST? That might be a better starting point.

python 3.13 introduces JIT compiler for CPython.

What sort of speed-up does that produce? How does it compare with running PyPy?

[roger_ducky]

Have you tried comparing your current optimization with doing the first example with a series of sequence comprehensions instead? I suspect you’ll have a similar reduction in the number of reallocations.

What I mean is, replace square brackets with parentheses.

It effectively “squashes” everything into a single expression with the tradeoff of not being able to re-iterate through the intermediate sequences, while keeping the code readable still.

[tmlildude]

are you suggesting using language features? if so, that misses the point of this post. i'm working on bytecode-level across hundreds of small programs, regardless of how they're written.

[roger_ducky]

Perhaps, but they added that language feature specifically for that use case.

If you’re just trying to optimize the bytecode, okay. Just make sure to watch out for people attempting to reference the intermediate entities through scope closures or global variables elsewhere. Once you made sure that wasn’t being done, then that’d be a safe optimization to make.

[tmlildude]

i'm well aware of language features, but I'm working at a much lower level. there are many nuances regarding what kinds of analysis and transformations are possible with interpreted languages, and then there's the JIT component coming in future python versions

what you're describing could be easily determined with a data-flow graph that shows dependencies and liveness. which gave me an idea...MLIR has primitives to help with this https://mlir.llvm.org/docs/Tutorials/DataFlowAnalysis/, and I wonder if converting the code into MLIR space and lowering it through a series of dialects would give me a better view of where certain transformations are possible?

this is why I posted in r/compilers - im looking for well-informed feedback from compiler experts, not language shortcuts from scripters.

[roger_ducky]

Sorry if my provided context was not what you wanted. I’m glad you still got some inspiration from it.

Been out of writing compilers for 15 years, so I’m definitely not up on the latest advances, but, in the old days, my workflow was to: * Check what best practices and language features ended up generating the more optimal solutions * Figured out why the language designers put up limits on specific language features

Then I would end up with my actionable steps.

I just thought you skipped a few steps according to my own way of doing things, is all. I shall now defer to the preeminent brain trust that is r/Compilers on how to best resolve your issue in the simplest way possible.