Skip to content

gh-112354: Add executor for less-taken branch #112902

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
gvanrossum wants to merge 41 commits into from
Closed

gh-112354: Add executor for less-taken branch #112902

Changes from 1 commit
Commits
Show all changes
41 commits
Select commit Hold shift + click to select a range
36feeb1
Skip ENTER_EXECUTOR as deopt target (use vm_data)
gvanrossum Nov 24, 2023
d12533b
Add an array of 'extras' to UOpExecutor
gvanrossum Nov 23, 2023
f21f2d8
Count side exits per uop loc and print if >= 10
gvanrossum Nov 24, 2023
8463965
Add _PyOptimizer_Anywhere (not yet used)
gvanrossum Nov 25, 2023
6403752
Only jump in ENTER_EXECUTOR if overwriting JUMP_BACKWARD
gvanrossum Nov 25, 2023
329dead
Assert base opcode in _Py_Specialize_ForIter
gvanrossum Nov 25, 2023
f1998c0
Disable curses tests in --fast-ci mode (make test)
gvanrossum Nov 25, 2023
b0944e6
Improve (?) check for executor recursion
gvanrossum Nov 25, 2023
26b5f89
Only generate extra executors for branches
gvanrossum Nov 25, 2023
649581c
Fix Uop -> UOp
gvanrossum Dec 1, 2023
835bf13
WIP
gvanrossum Dec 1, 2023
256b156
Fix where next_instr points upon E_E avoidance
gvanrossum Dec 2, 2023
75c7c32
Allow executors with oparg >= 256
gvanrossum Dec 2, 2023
a94c7f1
Don't try to optimize with default optimizer
gvanrossum Dec 2, 2023
747a3f0
Use separate 'counters' and 'executors' arrays
gvanrossum Dec 11, 2023
682cf5a
Jump directly to side-exit executors
gvanrossum Dec 12, 2023
359c6fc
Remove progress check; clean up the rest a big
gvanrossum Dec 13, 2023
ca6ed3a
Ensure array of executor pointers is 64-bit aligned
gvanrossum Dec 13, 2023
e2a26b5
Check at least two uops; further cleanup
gvanrossum Dec 13, 2023
38c7aab
Move exit_trace up, since it is smaller
gvanrossum Dec 13, 2023
0f64231
Use configured threshold and exp. backoff for counter
gvanrossum Dec 13, 2023
83297df
Add API to access sub-interpreters
gvanrossum Dec 13, 2023
d065a94
Move optimizer/executor tests to new file test_capi/test_opt.py
gvanrossum Dec 13, 2023
0f71a03
Merge branch 'test-opt' into uops-extras
gvanrossum Dec 13, 2023
075ab91
In _PyOptimizer_Unanchored, assert not ENTER_EXECUTOR, accept JUMP_BA…
gvanrossum Dec 13, 2023
c54daef
Call DISPATCH() directly from exit_trace
gvanrossum Dec 13, 2023
934a115
Correct comment on deoptimize
gvanrossum Dec 13, 2023
52c49eb
Merge branch 'main' into uops-extras
gvanrossum Dec 13, 2023
8f5e623
Remove enter_tier_one label
gvanrossum Dec 13, 2023
10b98f1
Add test
gvanrossum Dec 13, 2023
1450ca6
Fix memory leak
gvanrossum Dec 13, 2023
dcde4d3
Clear sub-executors array upon dealloc
gvanrossum Dec 13, 2023
15df63f
Add blurb
gvanrossum Dec 13, 2023
c786418
Avoid redundant stack frame saves/restores
gvanrossum Dec 13, 2023
ee0734b
Revert "Disable curses tests in --fast-ci mode (make test)"
gvanrossum Dec 14, 2023
655a841
Merge branch 'main' into uops-extras
gvanrossum Dec 14, 2023
32e36fa
Merge branch 'main' into uops-extras
gvanrossum Dec 14, 2023
f5b317a
Fix compiler warning about int/Py_ssize_t
gvanrossum Dec 14, 2023
4804a3c
Be less casual about incref/decref current executor
gvanrossum Dec 16, 2023
46c7d26
Slightly nicer way to handle refcounts
gvanrossum Dec 16, 2023
b991279
Silence compiler warning
gvanrossum Dec 17, 2023
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
Remove progress check; clean up the rest a big
  • Loading branch information
@gvanrossum
gvanrossum committed Dec 13, 2023
commit 359c6fc379be15e2a6ddb975cec92733a843b8cf
93 changes: 38 additions & 55 deletions Python/ceval.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -752,7 +752,10 @@ _PyEval_EvalFrameDefault(PyThreadState *tstate, _PyInterpreterFrame *frame, int
goto exit_unwind;
}

// Jump here from ENTER_EXECUTOR, and code under the deoptimize label
enter_tier_one:
next_instr = frame->instr_ptr;
Comment thread
gvanrossum marked this conversation as resolved.

resume_frame:
stack_pointer = _PyFrame_GetStackPointer(frame);

Expand Down Expand Up @@ -1063,50 +1066,20 @@ _PyEval_EvalFrameDefault(PyThreadState *tstate, _PyInterpreterFrame *frame, int

// Jump here from DEOPT_IF()
deoptimize:
// On DEOPT_IF we just repeat the last instruction.
// On DEOPT_IF we must repeat the last instruction.
Comment thread
gvanrossum marked this conversation as resolved.
Outdated
// This presumes nothing was popped from the stack (nor pushed).
// There are some other things to take care of first, though.
frame->instr_ptr = next_uop[-1].target + _PyCode_CODE(_PyFrame_GetCode(frame));
DPRINTF(2, "DEOPT: [UOp %d (%s), oparg %d, operand %" PRIu64 ", target %d @ %d -> %s]\n",
uopcode, _PyUOpName(uopcode), next_uop[-1].oparg, next_uop[-1].operand, next_uop[-1].target,
(int)(next_uop - current_executor->trace - 1),
_PyOpcode_OpName[frame->instr_ptr->op.code]);
OPT_HIST(trace_uop_execution_counter, trace_run_length_hist);
UOP_STAT_INC(uopcode, miss);
_Py_CODEUNIT *src, *dest;
src = dest = frame->instr_ptr;
opcode = src->op.code;
oparg = src->op.arg;
while (opcode == EXTENDED_ARG) {
src++;
opcode = src->op.code;
oparg = (oparg << 8) | src->op.arg;
}
if (opcode == ENTER_EXECUTOR) {
// frame->instr_ptr --> dest --> EXTENDED_ARG
// src --> ENTER_EXECUTOR
// Avoid recursing into the same executor over and over
next_instr = src;
PyCodeObject *code = _PyFrame_GetCode(frame);
_PyExecutorObject *executor = (_PyExecutorObject *)code->co_executors->executors[oparg & 0xff];
if (executor == (_PyExecutorObject *)current_executor) {
opcode = _PyOpcode_Deopt[executor->vm_data.opcode];
DPRINTF(1, "Avoiding ENTER_EXECUTOR %d/%d in favor of underlying base opcode %s %d\n",
oparg, oparg & 0xff, _PyOpcode_OpName[opcode], (oparg & 0xffffff00) | executor->vm_data.oparg);
DPRINTF(1,
" for %s (%s:%d) at byte offset %d\n",
PyUnicode_AsUTF8(code->co_qualname),
PyUnicode_AsUTF8(code->co_filename),
code->co_firstlineno,
2 * (int)(next_instr - _PyCode_CODE(_PyFrame_GetCode(frame))));
Py_DECREF(current_executor);
oparg = (oparg & 0xffffff00) | executor->vm_data.oparg;
PRE_DISPATCH_GOTO();
DISPATCH_GOTO();
}
}
frame->return_offset = 0; // Don't leave this random
_PyFrame_SetStackPointer(frame, stack_pointer);
// Increment side exit counter for this uop

// Check if there is a side-exit executor here already.
int pc = next_uop - 1 - current_executor->trace;
_PyExecutorObject **pexecutor = current_executor->executors + pc;
if (*pexecutor != NULL) {
Expand All @@ -1121,14 +1094,30 @@ _PyEval_EvalFrameDefault(PyThreadState *tstate, _PyInterpreterFrame *frame, int
Py_INCREF(current_executor);
goto enter_tier_two;
}

// Increment and check side exit counter.
uint16_t *pcounter = current_executor->counters + pc;
*pcounter += 1;
if (*pcounter == 32 && // TODO: use resume_threshold
tstate->interp->optimizer != &_PyOptimizer_Default &&
(opcode == POP_JUMP_IF_FALSE ||
opcode == POP_JUMP_IF_TRUE ||
opcode == POP_JUMP_IF_NONE ||
opcode == POP_JUMP_IF_NOT_NONE))
if (*pcounter != 32 || // TODO: use resume_threshold
tstate->interp->optimizer == &_PyOptimizer_Default)
{
goto enter_tier_one;
}

// Decode instruction to look past EXTENDED_ARG.
_Py_CODEUNIT *src, *dest;
src = dest = frame->instr_ptr;
opcode = src->op.code;
if (opcode == EXTENDED_ARG) {
src++;
opcode = src->op.code;
}

// For selected opcodes build a new executor and enter it now.

@markshannon markshannon Dec 13, 2023

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Why "selected opcodes", why not everywhere?

@gvanrossum gvanrossum Dec 13, 2023

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

In an earlier version that somehow didn't work. Right now the check whether the new trace isn't going to immediately deopt again relies on these opcodes. I figured once we have the side exit machinery working we could gradually increase the scope to other deoptimizations. Also, not all deoptimizations are worthy of the effort (e.g. the PEP 523 test).

@markshannon markshannon Dec 14, 2023

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

No special cases, please, it just make the code more complicated and slower.
If we want to treat some exits differently, let's do it properly faster-cpython/ideas#638, not here.

@gvanrossum gvanrossum Dec 17, 2023

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

There are several reasons. First, as I explain below, for bytecodes other than branches, I can't promise an exact check for whether the newly created sub-executor doesn't just repeat the same deoptimizing uop that triggered its creation (in which case the sub-executor would always deopt immediately if it is entered at all).

Second, for most bytecodes other than branches, deoptimization paths are relatively rare (IIRC this is apparent from the pystats data -- with the exception of some LOAD_ATTR specializations).

For branches, we expect many cases where the "common" path is not much more common than the "uncommon" path (e.g. 60/40 or 70/30). Now, it might make sense have a different special case here, where if e.g. _GUARD_IS_TRUE_POP has a hot side-exit, we know that the branch goes the other way, so we can simply create a sub-executor starting at the less-common branch target. The current approach doesn't do this (mostly because I'd have to thread the special case all the way through the various optimizer functions) but just creates a new executor starting at the original Tier 1 branch bytecode -- in the expectation that if the counters are tuned just right, we will have executed the less-common branch in Tier 1 while taking the common branch in Tier 2, so that Tier 1's shift register has changed state and now indicates that the less-common branch is actually taken more frequently. The checks at L1161 and ff. below are a safeguard in case that didn't happen yet (there are all kinds of interesting scenarios, e.g. loops that don't iterate much -- remember that the first iteration each time we enter a loop will be done in Tier 1, where we stay until we hit the JUMP_BACKWARD bytecode at the end of the loop).

I propose this PR as a starting point for futher iterations, not as the ultimate design for side-exits. Let's discuss this Monday.

if (opcode == POP_JUMP_IF_FALSE ||
opcode == POP_JUMP_IF_TRUE ||
opcode == POP_JUMP_IF_NONE ||
opcode == POP_JUMP_IF_NOT_NONE)
{
DPRINTF(2, "--> %s @ %d in %p has %d side exits\n",
_PyUOpName(uopcode), pc, current_executor, (int)(*pcounter));
Expand All @@ -1138,7 +1127,11 @@ _PyEval_EvalFrameDefault(PyThreadState *tstate, _PyInterpreterFrame *frame, int
if (optimized < 0) {
goto error_tier_two;
}
if (optimized) {
if (!optimized) {
DPRINTF(2, "--> Failed to optimize %s @ %d in %p\n",
_PyUOpName(uopcode), pc, current_executor);
}
else {
DPRINTF(1, "--> Optimized %s @ %d in %p\n",
_PyUOpName(uopcode), pc, current_executor);
DPRINTF(1, " T1: %s\n", _PyOpcode_OpName[src->op.code]);
Expand All @@ -1150,28 +1143,18 @@ _PyEval_EvalFrameDefault(PyThreadState *tstate, _PyInterpreterFrame *frame, int
2 * (int)(frame->instr_ptr - _PyCode_CODE(_PyFrame_GetCode(frame))));
Py_DECREF(current_executor);
current_executor = (_PyUOpExecutorObject *)*pexecutor;
Comment thread
gvanrossum marked this conversation as resolved.
Outdated
// TODO: Check at least two uops: _IS_NONE, _POP_JUMP_IF_TRUE/FALSE.
if (current_executor->trace[0].opcode != uopcode) {
Py_INCREF(current_executor);
goto enter_tier_two;
goto enter_tier_two; // Yes!
}
// This is guaranteed to deopt again; forget about it
DPRINTF(2, "It's not an improvement -- discarding trace\n");
DPRINTF(2, "Alas, it's the same uop again -- discarding trace\n");
*pexecutor = NULL;
Py_DECREF(current_executor);
next_instr = frame->instr_ptr;
goto resume_frame;
}
else {
DPRINTF(2, "--> Failed to optimize %s @ %d in %p\n",
_PyUOpName(uopcode), pc, current_executor);
}
}
Py_DECREF(current_executor);
// Fall through
// Jump here from ENTER_EXECUTOR
enter_tier_one:
next_instr = frame->instr_ptr;
goto resume_frame;
goto enter_tier_one;

// Jump here from _EXIT_TRACE
exit_trace:
Expand Down