8000 gh-112320: Implement on-trace confidence tracking for branches (#112321) · python/cpython@7316dfb · GitHub
[go: up one dir, main page]
Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit 7316dfb

Browse files
gvanrossumgvanrossum
authored
gh-112320: Implement on-trace confidence tracking for branches (#112321)
We track the confidence as a scaled int.
1 parent dfaa9e0 commit 7316dfb

File tree

6 files changed

+56
-3
lines changed

6 files changed

+56
-3
lines changed

‎Include/cpython/pystats.h

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -114,6 +114,7 @@ typedef struct _optimization_stats {
114114
uint64_t trace_too_short;
115115
uint64_t inner_loop;
116116
uint64_t recursive_call;
117+
uint64_t low_confidence;
117118
UOpStats opcode[512];
118119
uint64_t unsupported_opcode[256];
119120
uint64_t trace_length_hist[_Py_UOP_HIST_SIZE];

‎Lib/test/test_capi/test_misc.py

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2985,6 +2985,37 @@ def testfunc(n, m):
29852985
uops = {opname for opname, _, _ in ex}
29862986
self.assertIn("_FOR_ITER_TIER_TWO", uops)
29872987

2988+
def test_confidence_score(self):
2989+
def testfunc(n):
2990+
bits = 0
2991+
for i in range(n):
2992+
if i & 0x01:
2993+
bits += 1
2994+
if i & 0x02:
2995+
bits += 1
2996+
if i&0x04:
2997+
bits += 1
2998+
if i&0x08:
2999+
bits += 1
3000+
if i&0x10:
3001+
bits += 1
3002+
if i&0x20:
3003+
bits += 1
3004+
return bits
3005+
3006+
opt = _testinternalcapi.get_uop_optimizer()
3007+
with temporary_optimizer(opt):
3008+
x = testfunc(20)
3009+
3010+
self.assertEqual(x, 40)
3011+
ex = get_first_executor(testfunc)
3012+
self.assertIsNotNone(ex)
3013+
ops = [opname for opname, _, _ in ex]
3014+
count = ops.count("_GUARD_IS_TRUE_POP")
3015+
# Because Each 'if' halves the score, the second branch is
3016+
# too much already.
3017+
self.assertEqual(count, 1)
3018+
29883019

29893020
@unittest.skipUnless(support.Py_GIL_DISABLED, 'need Py_GIL_DISABLED')
29903021
class TestPyThreadId(unittest.TestCase):

‎Misc/NEWS.d/next/Core and Builtins/2023-11-22-13-17-54.gh-issue-112320.EddM51.rst

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,4 @@
1+
The Tier 2 translator now tracks the confidence level for staying "on trace"
2+
(i.e. not exiting back to the Tier 1 interpreter) for branch instructions
3+
based on the number of bits set in the branch "counter". Trace translation
4+
ends when the confidence drops below 1/3rd.

‎Python/optimizer.c

Lines changed: 17 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -409,6 +409,9 @@ BRANCH_TO_GUARD[4][2] = {
409409

410410
#define TRACE_STACK_SIZE 5
411411

412+
#define CONFIDENCE_RANGE 1000
413+
#define CONFIDENCE_CUTOFF 333
414+
412415
/* Returns 1 on success,
413416
* 0 if it failed to produce a worthwhile trace,
414417
* and -1 on an error.
@@ -431,6 +434,7 @@ translate_bytecode_to_trace(
431434
_Py_CODEUNIT *instr;
432435
} trace_stack[TRACE_STACK_SIZE];
433436
int trace_stack_depth = 0;
437+
int confidence = CONFIDENCE_RANGE; // Adjusted by branch instructions
434438

435439
#ifdef Py_DEBUG
436440
char *python_lltrace = Py_GETENV("PYTHON_LLTRACE");
@@ -513,7 +517,6 @@ translate_bytecode_to_trace(
513517
uint32_t oparg = instr->op.arg;
514518
uint32_t extras = 0;
515519

516-
517520
if (opcode == EXTENDED_ARG) {
518521
instr++;
519522
extras += 1;
@@ -543,11 +546,22 @@ translate_bytecode_to_trace(
543546
int counter = instr[1].cache;
544547
int bitcount = _Py_popcount32(counter);
545548
int jump_likely = bitcount > 8;
549+
if (jump_likely) {
550+
confidence = confidence * bitcount / 16;
551+
}
552+
else {
553+
confidence = confidence * (16 - bitcount) / 16;
554+
}
555+
if (confidence < CONFIDENCE_CUTOFF) {
556+
DPRINTF(2, "Confidence too low (%d)\n", confidence);
557+
OPT_STAT_INC(low_confidence);
558+
goto done;
559+
}
546560
uint32_t uopcode = BRANCH_TO_GUARD[opcode - POP_JUMP_IF_FALSE][jump_likely];
547561
_Py_CODEUNIT *next_instr = instr + 1 + _PyOpcode_Caches[_PyOpcode_Deopt[opcode]];
548-
DPRINTF(4, "%s(%d): counter=%x, bitcount=%d, likely=%d, uopcode=%s\n",
562+
DPRINTF(2, "%s(%d): counter=%x, bitcount=%d, likely=%d, confidence=%d, uopcode=%s\n",
549563
_PyUOpName(opcode), oparg,
550-
counter, bitcount, jump_likely, _PyUOpName(uopcode));
564+
counter, bitcount, jump_likely, confidence, _PyUOpName(uopcode));
551565
ADD_TO_TRACE(uopcode, max_length, 0, target);
552566
if (jump_likely) {
553567
_Py_CODEUNIT *target_instr = next_instr + oparg;

‎Python/specialize.c

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -233,6 +233,7 @@ print_optimization_stats(FILE *out, OptimizationStats *stats)
233233
fprintf(out, "Optimization trace too short: %" PRIu64 "\n", stats->trace_too_short);
234234
fprintf(out, "Optimization inner loop: %" PRIu64 "\n", stats->inner_loop);
235235
fprintf(out, "Optimization recursive call: %" PRIu64 "\n", stats->recursive_call);
236+
fprintf(out, "Optimization low confidence: %" PRIu64 "\n", stats->low_confidence);
236237

237238
print_histogram(out, "Trace length", stats->trace_length_hist);
238239
print_histogram(out, "Trace run length", stats->trace_run_length_hist);

‎Tools/scripts/summarize_stats.py

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -386,6 +386,7 @@ def get_optimization_stats(self) -> dict[str, tuple[int, int | None]]:
386386
trace_too_short = self._data["Optimization trace too short"]
387387
inner_loop = self._data["Optimization inner loop"]
388388
recursive_call = self._data["Optimization recursive call"]
389+
low_confidence = self._data["Optimization low confidence"]
389390

390391
return {
391392
"Optimization attempts": (attempts, None),
@@ -396,6 +397,7 @@ def get_optimization_stats(self) -> dict[str, tuple[int, int | None]]:
396397
"Trace too short": (trace_too_short, attempts),
397398
"Inner loop found": (inner_loop, attempts),
398399
"Recursive call": (recursive_call, attempts),
400+
"Low confidence": (low_confidence, attempts),
399401
"Traces executed": (executed, None),
400402
"Uops executed": (uops, executed),
401403
}

0 commit comments

Comments
 (0)
0