Repository navigation
Data structures and code for exits from executors. #644
Description
To support trace stitching we need data for exits embedded into trace objects.
First of all we need an exit struct:
https://github.com/faster-cpython/ideas/blob/main/3.13/engine.md#making-cold-exits-small lists the fields we need.
typedef struct _exit_data {
_PyExecutorObject *executor; // The executor to jump to
uint32_t target; // offset in the code object of the target code unit.
int16_t hotness; // How hot this exit is. Start at a negative number and count up?
} _PyExitData;Since all executors are now micro-ops based, we can get rid of the distinction between _PyExecutorObject and _PyUOpExecutorObject.
The new combined executor struct would look something like:
typedef struct _PyExecutorObject {
PyObject_VAR_HEAD
_PyVMData vm_data;
union {
void *jit_code; // Will be a function pointer
_PyUOpInstruction *trace;
};
_PyExitData exits[1];
} _PyExecutorObject;
We will pre-allocate an array of executors for cold exits, one for each possible index into the exits array. Since there cannot be more exits than the maximum number of uops, the size of the array will be _Py_UOP_MAX_TRACE_LENGTH, currently 512.
Cold exits will be implemented as a single micro-op _COLD_EXIT with oparg set to the index in the array.
_COLD_EXIT needs to do the following:
- Find the exit:
exit = current_executor->exit[oparg] - Increment
exit->hotness - If
exit->hotness == 0then trigger generator on a new executor to replaceexit->executor. - Otherwise drop into tier 1:
next_instr = PyCode_CODE(code) + exit->target; ENTER_TIER1();
The JIT will need to compile the code for these cold exits on start up, but we can static allocate the data structures.
Activity
gvanrossum commentedon Jan 10, 2024
Uh, why?
Why not dynamically allocated based on the size of the trace? (Which we know before we create the executor object (in
make_executor_from_uops()in optimizer.c).I take it that the targets are basically moved from the
_PyOptimizerObjectstruct into the_PyExitDatastruct;exitandhotnesscorrespond to theexecutorsandcountersarrays in my defunct side-exits PR (gh-112902).I'm missing something here. My understanding was that exits are (largely) reached by calls to
DEOPT_IF()(orEXIT_IF()if you wish) included in the C code for the bytecode definition in bytecodes.c. How does a new uop help here? (Fine if that's explained in another design issue, just point me to it.)markshannon commentedon Jan 10, 2024
Because at least half will be
_SET_IP/_CHECK_VALID.There will 256 globally (per-process) as they are
const, so can be shared.Each
EXIT_IFwill have an executor/exit attached (in theexitsarray), which is jumped to unconditionally. It is then the job of that exit to handle counts and further optimization.The
_COLD_EXITmicro-op will perform that task.markshannon commentedon Jan 10, 2024
The
_COLD_EXITcode will look something like this:(This untested, not even compiled)
markshannon commentedon Jan 10, 2024
And the code for
EXIT_IFwill be something like this:indexis computed when creating the executor from the uop IR.gvanrossum commentedon Jan 11, 2024
Oh, I see what I didn't get.
The (dynamically allocated) array of exit structs is part of the executor, and each possibly-deoptimizing uop in the
tracearray (or each group of uops belonging to the same Tier 1 instruction?) has a corresponding exit struct, with its own target and hotness counter.However, the
exitfield in those exit structs initially all point to one of 256 statically allocated executors (i.e., to the one whose index in that static array equals to the index of the exit struct in the array of such structs in the executor). And each of those static executors contains a single_COLD_EXITuop whose oparg is that same index.When the hotness counter warms up, eventually the
exitfield in the exit struct is made to point to a new, dynamically created executor representing the code where the hot side exit continues. (There's the issue of how ownership of that executor is determined, but that's solvable.)I'm not sure I follow the reasoning about how many cold exit executors we need (initially 1/3rd of the uops are
_SET_IPand 1/3rd are_CHECK_VALID, so maybe only MAX/3 instead of MAX/2?) but I can see the attraction in making this array shorter than thetracearray. Possibly the allocation of entries can be different when using the Tier 2 interpreter than for the JIT, since the index can be baked into the JIT code. Anyways, this is a minor detail; we just must be able to calculate the index of the exit struct corresponding to the current micro instruction efficiently in the Tier 2 interpreter. (Echoes of an early, later abandoned, design for the 3.11 Tier 1 "inline" cache. :-)PS 1: I take it that the
targetfield is moved from the UOpInstruction struct to the exit struct?PS 2: Maybe the field referencing an executor in the exit struct should be called
executorinstead ofexit-- the reuse of "exit" added to my confusion.markshannon commentedon Jan 11, 2024
No one need own the executor, we have reference counting. Each
exit->executorfield would be a strong reference to the executor it points to. Since the cold exits are immortal, we don't need to worry about reference counts when initializing the field.1/2 is an approximation.
Currently we only need a 1/3, but some instructions expand to several micro-ops, so we could end up needed more than half.
Maybe we should just make the array
MAXfor safety. As you say, it isn't important for the design.Yes.
gvanrossum commentedon Jan 11, 2024
Makes sense (as does the rest). The destructor for executors needs to know how many exit structs an executor has, and decref the executors in those exits. The static ones can be immortal.
gvanrossum commentedon Jan 11, 2024
I would still plead for renaming the
exitfield.markshannon commentedon Jan 12, 2024
Already done 🙂
gvanrossum commentedon Jan 16, 2024
@markshannon Presumably before we can work on this, we need to implement having separate structs for uops during the trace collection/optimization chain and uops in the executor, right? Because in the executor the 'target' field lives in the exit blocks, but during optimization, 'target' is part of the instruction struct.
markshannon commentedon Feb 22, 2024
Done 🎉