owned this note
owned this note
Published
Linked with GitHub
# Stability of Python bytecode and its compiler for domain-specific extension of Python
## Background
- Growing interest and new libraries that are domain-specific extensions of Python
- optimizing compilers:
- HPC; numeric/loop/array/tensor-oriented programming
- code transformers
- autodiff in machine-learning, deep-learning
- Bytecode is the only program representation that is always available. ([details on why AST is insufficient?](#Why-the-AST-is-insufficient))
- Deep-learning usecases rely on auto-differentiation which become easier if user source code can be accessed or reconstructed.
## Capturing user intent
- Python bytecode perfectly models the execution semantic but optimizing compilers and code transformers operate better when user intent can be reconstructed.
- Optimizing compilers work by removing unneeded effects. Python optimized bytecode blurs the separation of user-intended effects vs internal "plumbing" effects for the Python VM.
- Optimizing compilers and code transformers need to reconstruct the control-flow structure for specific transformations. They may have limited support for structured control-flow constructs. Bytecode optimization can easily convert an accepted control-flow structure into an unsupported structure. When bytecode optimization becomes more advanced, we may lose the ability to reconstruct. (See example [here](#Example-Bytecode-optimization-inlines-return-block) and [here](#Example-Large-dictionary))
## Possible solutions:
1. Exposing an unoptimized IR along with the code object.
- https://bugs.python.org/issue42926 is a related proposal. Splitting the bytecode compiler and allowing access to the unoptimized intermediate representation will help.
- This unoptimized IR is closer to the original user source code.
- This can become the canonical representation of Python source, allowing in other tools. Avoiding the need for AST extension or custom IR, such as `typed_ast`.
2. Providing access to the AST during compilation.
- [PEP-638: Syntactic Macros](https://peps.python.org/pep-0638/) proposes a mechanism for this.
- Less attractive solution because this is less flexible than an always accessible IR.
- Our usecases can be satisfied by just having the compiler plugin portion of the PEP if the syntax change for spelling the macros is too big of a change.
## Extras
### Example: Bytecode optimization inlines return block
Python 3.10 begins to optimize short exiting blocks by duplicating the exit block into originating block. This optimization is the most recent example that complicated the reconstruction of the for-loop because the exit block is fused with the block that `break`. A domain-specific extension may forbid the use of the `return` statement inside a loop.
```python
import dis
def for_loop_inline_exit(n):
x = 1
for i in range(n):
if some_check(i):
x = 2
break
x += i
return x
dis.dis(for_loop_inline_exit)
```
Py3.9
```
5 0 LOAD_CONST 1 (1)
2 STORE_FAST 1 (x)
6 4 LOAD_GLOBAL 0 (range)
6 LOAD_FAST 0 (n)
8 CALL_FUNCTION 1
10 GET_ITER
>> 12 FOR_ITER 28 (to 42)
14 STORE_FAST 2 (i)
7 16 LOAD_GLOBAL 1 (some_check)
18 LOAD_FAST 2 (i)
20 CALL_FUNCTION 1
22 POP_JUMP_IF_FALSE 32
8 24 LOAD_CONST 2 (2)
26 STORE_FAST 1 (x)
9 28 POP_TOP
30 JUMP_ABSOLUTE 42
10 >> 32 LOAD_FAST 1 (x)
34 LOAD_FAST 2 (i)
36 INPLACE_ADD
38 STORE_FAST 1 (x)
40 JUMP_ABSOLUTE 12
11 >> 42 LOAD_FAST 1 (x)
44 RETURN_VALUE
```
Py3.10
Note: There are two `RETURN_VALUE`.
```
5 0 LOAD_CONST 1 (1)
2 STORE_FAST 1 (x)
6 4 LOAD_GLOBAL 0 (range)
6 LOAD_FAST 0 (n)
8 CALL_FUNCTION 1
10 GET_ITER
>> 12 FOR_ITER 15 (to 44)
14 STORE_FAST 2 (i)
7 16 LOAD_GLOBAL 1 (some_check)
18 LOAD_FAST 2 (i)
20 CALL_FUNCTION 1
22 POP_JUMP_IF_FALSE 17 (to 34)
8 24 LOAD_CONST 2 (2)
26 STORE_FAST 1 (x)
9 28 POP_TOP
11 30 LOAD_FAST 1 (x)
32 RETURN_VALUE
10 >> 34 LOAD_FAST 1 (x)
36 LOAD_FAST 2 (i)
38 INPLACE_ADD
40 STORE_FAST 1 (x)
42 JUMP_ABSOLUTE 6 (to 12)
11 >> 44 LOAD_FAST 1 (x)
46 RETURN_VALUE
```
### Example: Large dictionary
Related issue: [numba#7894](https://github.com/numba/numba/issues/7894)
Construction of large dictionary is now written as:
```python
def f():
d = {
"a": 1,
"b": 2,
"c": 3,
"d": 4,
"e": 5,
"f": 6,
"g": 7,
"h": 8,
"i": 9,
"j": 10,
"k": 11,
"l": 12,
"m": 13,
"n": 14,
"o": 15,
"p": 16,
"q": 17,
"r": 18,
"s": 19,
}
return d
```
Python 3.9 bytecode:
```
5 0 LOAD_CONST 1 (1)
6 2 LOAD_CONST 2 (2)
...
23 36 LOAD_CONST 19 (19)
4 38 LOAD_CONST 20 (('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's'))
40 BUILD_CONST_KEY_MAP 19
42 STORE_FAST 0 (d)
25 44 LOAD_FAST 0 (d)
46 RETURN_VALUE
```
In Python 3.9, the dictionary is built from loading constant key-value mapping (`BUILD_CONST_KEY_MAP`).
Python 3.10 bytecode:
```
4 0 BUILD_MAP 0
5 2 LOAD_CONST 1 ('a')
4 LOAD_CONST 2 (1)
4 6 MAP_ADD 1
6 8 LOAD_CONST 3 ('b')
10 LOAD_CONST 4 (2)
4 12 MAP_ADD 1
...
22 104 LOAD_CONST 35 (18)
23 106 LOAD_CONST 36 (19)
4 108 LOAD_CONST 37 (('r', 's'))
110 BUILD_CONST_KEY_MAP 2
112 DICT_UPDATE 1
114 STORE_FAST 0 (d)
25 116 LOAD_FAST 0 (d)
118 RETURN_VALUE
```
In Python 3.10, the dictionary is created by a mix of inserting (`MAP_ADD`) each key-value pair and combining a dictionary following the approach in Python 3.9. With this approach, we cannot easily rule out that the dictionary is never mutated in the code.
### Why the AST is insufficient?
Source code is not always available; e.g. source-stripped packages with only .pyc files, dynamically created code (`exec`), distributed execution of user-defined functions, serialized functions that are reconstituted in another process.