Perform dataflow analysis in the bytecode compiler #306
Replies: 13 comments 10 replies
|
This is basically impossible with the compiler in its current form. |
|
So the bytecode would be converted into SSA form, optimised, and then converted back into stack-machine bytecode? Or what exactly are you proposing? |
|
The IR is stack based, but it isn't bytecode. |
|
AST -> stack-based SSA IR -> bytecode，Is that what you mean? |
|
Something like that. |
|
I think we can get a first level of liveness analysis with a hundred or so lines of code, without transforming everything into SSA, by just walking through the graph of basic blocks and marking things as "unsafe" when it's possible that they haven't been initialized yet. I have a branch here that has all tests passing, except I have yet to deal with the debugger situation, but I was thinking it could convert every |
|
From a complete run through the test suite gathering stats, there were 1000x as many LOAD_FAST_KNOWN as LOAD_FAST. |
|
PyPerformance somehow got "Geometric mean: 1.01x slower" for me Details |
|
Re-running, I got "Geometric mean: 1.01x faster". So it looks like it's within the noise of what my machine can reliably detect on pyperformance. But it might be worth it regardless, I'm not sure. Details |
|
NULL checks are cheap: it is a perfectly predicted branch, testing a value that it is in a register. So I'm not surprised the difference in performance is negligible. Also, I don't think removing the NULL check is safe. Potentially, someone could delete a local in the debugger. |
|
It wouldn't be safe with no other alterations, but I also changed |
|
I ran pyperformance 3 times on main, 3 times on the branch with the https://gist.github.com/sweeneyde/32b69bea8f7e15df7bbd9c41eac85f8d |
|
Some microbenchmarks seem to budge a few percent as well: Script: Detailsfrom pyperf import Runner, perf_counter
from itertools import repeat
runner = Runner()
def bench(func):
runner.bench_time_func(func.__name__, func, inner_loops=100)
return func
@bench
def LOAD_FAST(loops):
rep = repeat(None, loops)
x = None
t0 = perf_counter()
for _ in rep:
x;x;x;x;x; x;x;x;x;x; x;x;x;x;x; x;x;x;x;x;
x;x;x;x;x; x;x;x;x;x; x;x;x;x;x; x;x;x;x;x;
x;x;x;x;x; x;x;x;x;x; x;x;x;x;x; x;x;x;x;x;
x;x;x;x;x; x;x;x;x;x; x;x;x;x;x; x;x;x;x;x;
x;x;x;x;x; x;x;x;x;x; x;x;x;x;x; x;x;x;x;x;
return perf_counter() - t0
@bench
def STORE_FAST__LOAD_FAST(loops):
rep = repeat(None, loops)
x = None
t0 = perf_counter()
for _ in rep:
x=x;x=x;x=x;x=x;x=x; x=x;x=x;x=x;x=x;x=x;
x=x;x=x;x=x;x=x;x=x; x=x;x=x;x=x;x=x;x=x;
x=x;x=x;x=x;x=x;x=x; x=x;x=x;x=x;x=x;x=x;
x=x;x=x;x=x;x=x;x=x; x=x;x=x;x=x;x=x;x=x;
x=x;x=x;x=x;x=x;x=x; x=x;x=x;x=x;x=x;x=x;
x=x;x=x;x=x;x=x;x=x; x=x;x=x;x=x;x=x;x=x;
x=x;x=x;x=x;x=x;x=x; x=x;x=x;x=x;x=x;x=x;
x=x;x=x;x=x;x=x;x=x; x=x;x=x;x=x;x=x;x=x;
x=x;x=x;x=x;x=x;x=x; x=x;x=x;x=x;x=x;x=x;
x=x;x=x;x=x;x=x;x=x; x=x;x=x;x=x;x=x;x=x;
return perf_counter() - t0
@bench
def LOAD_FAST__LOAD_FAST(loops):
rep = repeat(None, loops)
x = None
t0 = perf_counter()
for _ in rep:
x,x=x,x;x,x=x,x;x,x=x,x;x,x=x,x;x,x=x,x; x,x=x,x;x,x=x,x;x,x=x,x;x,x=x,x;x,x=x,x;
x,x=x,x;x,x=x,x;x,x=x,x;x,x=x,x;x,x=x,x; x,x=x,x;x,x=x,x;x,x=x,x;x,x=x,x;x,x=x,x;
x,x=x,x;x,x=x,x;x,x=x,x;x,x=x,x;x,x=x,x; x,x=x,x;x,x=x,x;x,x=x,x;x,x=x,x;x,x=x,x;
x,x=x,x;x,x=x,x;x,x=x,x;x,x=x,x;x,x=x,x; x,x=x,x;x,x=x,x;x,x=x,x;x,x=x,x;x,x=x,x;
x,x=x,x;x,x=x,x;x,x=x,x;x,x=x,x;x,x=x,x; x,x=x,x;x,x=x,x;x,x=x,x;x,x=x,x;x,x=x,x;
x,x=x,x;x,x=x,x;x,x=x,x;x,x=x,x;x,x=x,x; x,x=x,x;x,x=x,x;x,x=x,x;x,x=x,x;x,x=x,x;
x,x=x,x;x,x=x,x;x,x=x,x;x,x=x,x;x,x=x,x; x,x=x,x;x,x=x,x;x,x=x,x;x,x=x,x;x,x=x,x;
x,x=x,x;x,x=x,x;x,x=x,x;x,x=x,x;x,x=x,x; x,x=x,x;x,x=x,x;x,x=x,x;x,x=x,x;x,x=x,x;
x,x=x,x;x,x=x,x;x,x=x,x;x,x=x,x;x,x=x,x; x,x=x,x;x,x=x,x;x,x=x,x;x,x=x,x;x,x=x,x;
x,x=x,x;x,x=x,x;x,x=x,x;x,x=x,x;x,x=x,x; x,x=x,x;x,x=x,x;x,x=x,x;x,x=x,x;x,x=x,x;
return perf_counter() - t0
@bench
def LOAD_FAST__LOAD_CONST(loops):
rep = repeat(None, loops)
x = None
t0 = perf_counter()
for _ in rep:
x,x=x,1;x,x=x,1;x,x=x,1;x,x=x,1;x,x=x,1; x,x=x,1;x,x=x,1;x,x=x,1;x,x=x,1;x,x=x,1;
x,x=x,1;x,x=x,1;x,x=x,1;x,x=x,1;x,x=x,1; x,x=x,1;x,x=x,1;x,x=x,1;x,x=x,1;x,x=x,1;
x,x=x,1;x,x=x,1;x,x=x,1;x,x=x,1;x,x=x,1; x,x=x,1;x,x=x,1;x,x=x,1;x,x=x,1;x,x=x,1;
x,x=x,1;x,x=x,1;x,x=x,1;x,x=x,1;x,x=x,1; x,x=x,1;x,x=x,1;x,x=x,1;x,x=x,1;x,x=x,1;
x,x=x,1;x,x=x,1;x,x=x,1;x,x=x,1;x,x=x,1; x,x=x,1;x,x=x,1;x,x=x,1;x,x=x,1;x,x=x,1;
x,x=x,1;x,x=x,1;x,x=x,1;x,x=x,1;x,x=x,1; x,x=x,1;x,x=x,1;x,x=x,1;x,x=x,1;x,x=x,1;
x,x=x,1;x,x=x,1;x,x=x,1;x,x=x,1;x,x=x,1; x,x=x,1;x,x=x,1;x,x=x,1;x,x=x,1;x,x=x,1;
x,x=x,1;x,x=x,1;x,x=x,1;x,x=x,1;x,x=x,1; x,x=x,1;x,x=x,1;x,x=x,1;x,x=x,1;x,x=x,1;
x,x=x,1;x,x=x,1;x,x=x,1;x,x=x,1;x,x=x,1; x,x=x,1;x,x=x,1;x,x=x,1;x,x=x,1;x,x=x,1;
x,x=x,1;x,x=x,1;x,x=x,1;x,x=x,1;x,x=x,1; x,x=x,1;x,x=x,1;x,x=x,1;x,x=x,1;x,x=x,1;
return perf_counter() - t0
@bench
def LOAD_CONST__LOAD_FAST(loops):
rep = repeat(None, loops)
x = None
t0 = perf_counter()
for _ in rep:
x,x=1,x;x,x=1,x;x,x=1,x;x,x=1,x;x,x=1,x; x,x=1,x;x,x=1,x;x,x=1,x;x,x=1,x;x,x=1,x;
x,x=1,x;x,x=1,x;x,x=1,x;x,x=1,x;x,x=1,x; x,x=1,x;x,x=1,x;x,x=1,x;x,x=1,x;x,x=1,x;
x,x=1,x;x,x=1,x;x,x=1,x;x,x=1,x;x,x=1,x; x,x=1,x;x,x=1,x;x,x=1,x;x,x=1,x;x,x=1,x;
x,x=1,x;x,x=1,x;x,x=1,x;x,x=1,x;x,x=1,x; x,x=1,x;x,x=1,x;x,x=1,x;x,x=1,x;x,x=1,x;
x,x=1,x;x,x=1,x;x,x=1,x;x,x=1,x;x,x=1,x; x,x=1,x;x,x=1,x;x,x=1,x;x,x=1,x;x,x=1,x;
x,x=1,x;x,x=1,x;x,x=1,x;x,x=1,x;x,x=1,x; x,x=1,x;x,x=1,x;x,x=1,x;x,x=1,x;x,x=1,x;
x,x=1,x;x,x=1,x;x,x=1,x;x,x=1,x;x,x=1,x; x,x=1,x;x,x=1,x;x,x=1,x;x,x=1,x;x,x=1,x;
x,x=1,x;x,x=1,x;x,x=1,x;x,x=1,x;x,x=1,x; x,x=1,x;x,x=1,x;x,x=1,x;x,x=1,x;x,x=1,x;
x,x=1,x;x,x=1,x;x,x=1,x;x,x=1,x;x,x=1,x; x,x=1,x;x,x=1,x;x,x=1,x;x,x=1,x;x,x=1,x;
x,x=1,x;x,x=1,x;x,x=1,x;x,x=1,x;x,x=1,x; x,x=1,x;x,x=1,x;x,x=1,x;x,x=1,x;x,x=1,x;
return perf_counter() - t0Result:
|
|
Rather than add a |
|
At least without higher-tier optimizers, wouldn't that add a lot of extra dispatch overhead to our most common opcode? Besides, we can modify the current superinstructions so that My draft here that implements this. |
|
You say that 99.9% of |
|
Ah, I misunderstood -- that would make sense. But then I wouldn't know how to re-insert those checks for cases where locals are deleted or f_lineno is set. |
|
Ah yes, so we do need to a checked form of To avoid having to rename all the superinstructions, and so that the common form has the shorter name, I'd rename |
|
With regard to your draft implementation. 99.9% fewer NULL checks is excellent. Regarding removal of the
|
|
We could do something like python/cpython#93144 for stores. From analysis, we should know (for most cases at least) whether the variable was
This would convert one instruction into three, and would negatively impact the superinstructions, so it isn't clear that it would be worthwhile. |
|
Here are stats results for
Also: Successors and predecessors for STORE_FAST_GENERAL
I'd bet loop-peeling the first iteration of every for-loop would shrink the number of STORE_FAST_GENERAL. But I'm not sure that's worth it for now. |
|
Thanks for trying that out. I think we'll leave loop peeling for the higher tier optimizers (it happens implicitly if the VM is looking for hot backedges). |
Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
There a number of standard compiler analyses that we could implement and would be useful. For example:
Since the 1990s, the conventional way to perform these, and many other, analyses has been SSA form.
SSA form is a bit intimidating to start with, but once you are used to it, it seems natural and easy to work with.
Dataflow analysis would allow us to do less work handling variables and the stack, avoiding some NULL checks.
For example:
LOAD_FASTwill not need a NULL check as the compiler can detect if the variable can be undefined (and insert a check in the rare case that it is necessary)By themselves, these changes might not justify the extra complexity in the compiler, but combined with the refcount improvements in #308, it might.
We would need to take care when modifying local variables in the debugger.
We might have to accept some rare memory leaks, and disallow deletion of local variables (assigning
Noneinstead).All reactions