8000 GH-89480: Document motivation, design and implementation of 3.11 fram… · python/cpython@f6e43e8 · GitHub
[go: up one dir, main page]
Skip to content

Commit f6e43e8

Browse files
markshannonmarkshannon
authored
GH-89480: Document motivation, design and implementation of 3.11 frame stack. (GH-32304)
1 parent 5f2abae commit f6e43e8

File tree

3 files changed

+131
-0
lines changed

3 files changed

+131
-0
lines changed

‎Include/internal/pycore_frame.h

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -7,6 +7,11 @@ extern "C" {
77
#include <stdbool.h>
88
#include <stddef.h>
99

10+
/* See Objects/frame_layout.md for an explanation of the frame stack
11+
* including explanation of the PyFrameObject and _PyInterpreterFrame
12+
* structs. */
13+
14+
1015
struct _frame {
1116
PyObject_HEAD
1217
PyFrameObject *f_back; /* previous frame, or NULL */
@@ -40,12 +45,14 @@ enum _frameowner {
4045
};
4146

4247
typedef struct _PyInterpreterFrame {
48+
/* "Specials" section */
4349
PyFunctionObject *f_func; /* Strong reference */
4450
PyObject *f_globals; /* Borrowed reference */
4551
PyObject *f_builtins; /* Borrowed reference */
4652
PyObject *f_locals; /* Strong reference, may be NULL */
4753
PyCodeObject *f_code; /* Strong reference */
4854
PyFrameObject *frame_obj; /* Strong reference, may be NULL */
55+
/* Linkage section */
4956
struct _PyInterpreterFrame *previous;
5057
// NOTE: This is not necessarily the last instruction started in the given
5158
// frame. Rather, it is the code unit *prior to* the *next* instruction. For
@@ -55,6 +62,7 @@ typedef struct _PyInterpreterFrame {
5562
int stacktop; /* Offset of TOS from localsplus */
5663
bool is_entry; // Whether this is the "root" frame for the current _PyCFrame.
5764
char owner;
65+
/* Locals and stack */
5866
PyObject *localsplus[1];
5967
} _PyInterpreterFrame;
6068

‎Misc/NEWS.d/next/Core and Builtins/2022-04-04-15-12-38.bpo-45317.UDLOt8.rst

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
Add internal documentation explaining design of new (for 3.11) frame stack.

‎Objects/frame_layout.md

Lines changed: 122 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,122 @@
1+
# The Frame Stack
2+
3+
Each call to a Python function has an activation record,
4+
commonly known as a "frame".
5+
Python semantics allows frames to outlive the activation,
6+
so they have (before 3.11) been allocated on the heap.
7+
This is expensive as it requires many allocations and
8+
results in poor locality of reference.
9+
10+
In 3.11, rather than have these frames scattered about memory,
11+
as happens for heap-allocated objects, frames are allocated
12+
contiguously in a per-thread stack.
13+
This improves performance significantly for two reasons:
14+
* It reduces allocation overhead to a pointer comparison and increment.
15+
* Stack allocated data has the best possible locality and will always be in
16+
CPU cache.
17+
18+
Generator and coroutines still need heap allocated activation records, but
19+
can be linked into the per-thread stack so as to not impact performance too much.
20+
21+
## Layout
22+
23+
Each activation record consists of four conceptual sections:
24+
25+
* Local variables (including arguments, cells and free variables)
26+
* Evaluation stack
27+
* Specials: The per-frame object references needed by the VM: globals dict,
28+
code object, etc.
29+
* Linkage: Pointer to the previous activation record, stack depth, etc.
30+
31+
### Layout
32+
33+
The specials and linkage sections are a fixed size, so are grouped together.
34+
35+
Each activation record is laid out as:
36+
* Specials and linkage
37+
* Locals
38+
* Stack
39+
40+
This seems to provide the best performance without excessive complexity.
41+
It needs the interpreter to hold two pointers, a frame pointer and a stack pointer.
42+
43+
#### Alternative layout
44+
45+
An alternative layout that was used for part of 3.11 alpha was:
46+
47+
* Locals
48+
* Specials and linkage
49+
* Stack
50+
51+
This has the advantage that no copying is required when making a call,
52+
as the arguments on the stack are (usually) already in the correct
53+
location for the parameters. However, it requires the VM to maintain
54+
an extra pointer for the locals, which can hurt performance.
55+
56+
A variant that only needs the need two pointers is to reverse the numbering
57+
of the locals, so that the last one is numbered `0`, and the first in memory
58+
is numbered `N-1`.
59+
This allows the locals, specials and linkage to accessed from the frame pointer.
60+
We may implement this in the future.
61+
62+
#### Note:
63+
64+
> In a contiguous stack, we would need to save one fewer registers, as the
65+
> top of the caller's activation record would be the same at the base of the
66+
> callee's. However, since some activation records are kept on the heap we
67+
> cannot do this.
68+
69+
### Generators and Coroutines
70+
71+
Generators and coroutines contain a `_PyInterpreterFrame`
72+
The specials sections contains the following pointers:
73+
74+
* Globals dict
75+
* Builtins dict
76+
* Locals dict (not the "fast" locals, but the locals for eval and class creation)
77+
* Code object
78+
* Heap allocated `PyFrameObject` for this activation record, if any.
79+
* The function.
80+
81+The pointer to the function is not strictly required, but it is cheaper to
82+
store a strong reference to the function and borrowed references to the globals
83+
and builtins, than strong references to both globals and builtins.
84+
85+
### Frame objects
86+
87+
When creating a backtrace or when calling `sys._getframe()` the frame becomes
88+
visible to Python code. When this happens a new `PyFrameObject` is created
89+
and a strong reference to it placed in the `frame_obj` field of the specials
90+
section. The `frame_obj` field is initially `NULL`.
91+
92+
The `PyFrameObject` may outlive a stack-allocated `_PyInterpreterFrame`.
93+
If it does then `_PyInterpreterFrame` is copied into the `PyFrameObject`,
94+
except the evaluation stack which must be empty at this point.
95+
The linkage section is updated to reflect the new location of the frame.
96+
97+
This mechanism provides the appearance of persistent, heap-allocated
98+
frames for each activation, but with low runtime overhead.
99+
100+
### Generators and Coroutines
101+
102+
103+
Generator objects have a `_PyInterpreterFrame` embedded in them.
104+
This means that creating a generator requires only a single allocation,
105+
reducing allocation overhead and improving locality of reference.
106+
The embedded frame is linked into the per-thread frame when iterated or
107+
awaited.
108+
109+
If a frame object associated with a generator outlives the generator, then
110+
the embedded `_PyInterpreterFrame` is copied into the frame object.
111+
112+
113+
All the above applies to coroutines and async generators as well.
114+
115+
### Field names
116+
117+
Many of the fields in `_PyInterpreterFrame` were copied from the 3.10 `PyFrameObject`.
118+
Thus, some of the field names may be a bit misleading.
119+
120+
For example the `f_globals` field has a `f_` prefix implying it belongs to the
121+
`PyFrameObject` struct, although it belongs to the `_PyInterpreterFrame` struct.
122+
We may rationalize this naming scheme for 3.12.

0 commit comments

Comments
 (0)
0