Movatterモバイル変換

[0]ホーム
URL:

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

 Sign up
Appearance settings

Commit060a96f

Browse files
authored
gh-116968: Reimplement Tier 2 counters (#117144)
Introduce a unified 16-bit backoff counter type (``_Py_BackoffCounter``),shared between the Tier 1 adaptive specializer and the Tier 2 optimizer. TheAPI used for adaptive specialization counters is changed but the behavior is(supposed to be) identical.The behavior of the Tier 2 counters is changed:- There are no longer dynamic thresholds (we never varied these).- All counters now use the same exponential backoff.- The counter for ``JUMP_BACKWARD`` starts counting down from 16.- The ``temperature`` in side exits starts counting down from 64.
1 parent63bbe77 commit060a96f

File tree

19 files changed

+313
-235
lines changed

19 files changed

+313
-235
lines changed

‎Include/cpython/code.h

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -24,6 +24,16 @@ typedef struct _Py_GlobalMonitors {
2424
uint8_ttools[_PY_MONITORING_UNGROUPED_EVENTS];
2525
}_Py_GlobalMonitors;
2626

27+
typedefstruct {
28+
union {
29+
struct {
30+
uint16_tbackoff :4;
31+
uint16_tvalue :12;
32+
};
33+
uint16_tas_counter;// For printf("%#x", ...)
34+
};
35+
}_Py_BackoffCounter;
36+
2737
/* Each instruction in a code object is a fixed-width value,
2838
* currently 2 bytes: 1-byte opcode + 1-byte oparg. The EXTENDED_ARG
2939
* opcode allows for larger values but the current limit is 3 uses
@@ -39,6 +49,7 @@ typedef union {
3949
uint8_tcode;
4050
uint8_targ;
4151
}op;
52+
_Py_BackoffCountercounter;// First cache entry of specializable op
4253
}_Py_CODEUNIT;
4354

4455

‎Include/cpython/optimizer.h

Lines changed: 1 addition & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -89,7 +89,7 @@ static inline uint16_t uop_get_error_target(const _PyUOpInstruction *inst)
8989

9090
typedefstruct_exit_data {
9191
uint32_ttarget;
92-
int16_ttemperature;
92+
_Py_BackoffCountertemperature;
9393
conststruct_PyExecutorObject*executor;
9494
}_PyExitData;
9595

@@ -115,11 +115,6 @@ typedef int (*optimize_func)(
115115
struct_PyOptimizerObject {
116116
PyObject_HEAD
117117
optimize_funcoptimize;
118-
/* These thresholds are treated as signed so do not exceed INT16_MAX
119-
* Use INT16_MAX to indicate that the optimizer should never be called */
120-
uint16_tresume_threshold;
121-
uint16_tside_threshold;
122-
uint16_tbackedge_threshold;
123118
/* Data needed by the optimizer goes here, but is opaque to the VM */
124119
};
125120

@@ -151,14 +146,6 @@ extern void _Py_Executors_InvalidateAll(PyInterpreterState *interp, int is_inval
151146
PyAPI_FUNC(PyObject*)PyUnstable_Optimizer_NewCounter(void);
152147
PyAPI_FUNC(PyObject*)PyUnstable_Optimizer_NewUOpOptimizer(void);
153148

154-
#defineOPTIMIZER_BITS_IN_COUNTER 4
155-
/* Minimum of 16 additional executions before retry */
156-
#defineMIN_TIER2_BACKOFF 4
157-
#defineMAX_TIER2_BACKOFF (15 - OPTIMIZER_BITS_IN_COUNTER)
158-
#defineOPTIMIZER_BITS_MASK ((1 << OPTIMIZER_BITS_IN_COUNTER) - 1)
159-
/* A value <= UINT16_MAX but large enough that when shifted is > UINT16_MAX */
160-
#defineOPTIMIZER_UNREACHABLE_THRESHOLD UINT16_MAX
161-
162149
#define_Py_MAX_ALLOWED_BUILTINS_MODIFICATIONS 3
163150
#define_Py_MAX_ALLOWED_GLOBALS_MODIFICATIONS 6
164151

‎Include/internal/pycore_backoff.h

Lines changed: 128 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,128 @@
1+
2+
#ifndefPy_INTERNAL_BACKOFF_H
3+
#definePy_INTERNAL_BACKOFF_H
4+
#ifdef__cplusplus
5+
extern"C" {
6+
#endif
7+
8+
#ifndefPy_BUILD_CORE
9+
# error "this header requires Py_BUILD_CORE define"
10+
#endif
11+
12+
#include<assert.h>
13+
#include<stdbool.h>
14+
#include<stdint.h>
15+
16+
/* 16-bit countdown counters using exponential backoff.
17+
18+
These are used by the adaptive specializer to count down until
19+
it is time to specialize an instruction. If specialization fails
20+
the counter is reset using exponential backoff.
21+
22+
Another use is for the Tier 2 optimizer to decide when to create
23+
a new Tier 2 trace (executor). Again, exponential backoff is used.
24+
25+
The 16-bit counter is structured as a 12-bit unsigned 'value'
26+
and a 4-bit 'backoff' field. When resetting the counter, the
27+
backoff field is incremented (until it reaches a limit) and the
28+
value is set to a bit mask representing the value 2**backoff - 1.
29+
The maximum backoff is 12 (the number of value bits).
30+
31+
There is an exceptional value which must not be updated, 0xFFFF.
32+
*/
33+
34+
#defineUNREACHABLE_BACKOFF 0xFFFF
35+
36+
staticinlinebool
37+
is_unreachable_backoff_counter(_Py_BackoffCountercounter)
38+
{
39+
returncounter.as_counter==UNREACHABLE_BACKOFF;
40+
}
41+
42+
staticinline_Py_BackoffCounter
43+
make_backoff_counter(uint16_tvalue,uint16_tbackoff)
44+
{
45+
assert(backoff <=15);
46+
assert(value <=0xFFF);
47+
return (_Py_BackoffCounter){.value=value, .backoff=backoff};
48+
}
49+
50+
staticinline_Py_BackoffCounter
51+
forge_backoff_counter(uint16_tcounter)
52+
{
53+
return (_Py_BackoffCounter){.as_counter=counter};
54+
}
55+
56+
staticinline_Py_BackoffCounter
57+
restart_backoff_counter(_Py_BackoffCountercounter)
58+
{
59+
assert(!is_unreachable_backoff_counter(counter));
60+
if (counter.backoff<12) {
61+
returnmake_backoff_counter((1 << (counter.backoff+1))-1,counter.backoff+1);
62+
}
63+
else {
64+
returnmake_backoff_counter((1 <<12)-1,12);
65+
}
66+
}
67+
68+
staticinline_Py_BackoffCounter
69+
pause_backoff_counter(_Py_BackoffCountercounter)
70+
{
71+
returnmake_backoff_counter(counter.value |1,counter.backoff);
72+
}
73+
74+
staticinline_Py_BackoffCounter
75+
advance_backoff_counter(_Py_BackoffCountercounter)
76+
{
77+
if (!is_unreachable_backoff_counter(counter)) {
78+
returnmake_backoff_counter((counter.value-1)&0xFFF,counter.backoff);
79+
}
80+
else {
81+
returncounter;
82+
}
83+
}
84+
85+
staticinlinebool
86+
backoff_counter_triggers(_Py_BackoffCountercounter)
87+
{
88+
returncounter.value==0;
89+
}
90+
91+
/* Initial JUMP_BACKWARD counter.
92+
* This determines when we create a trace for a loop.
93+
* Backoff sequence 16, 32, 64, 128, 256, 512, 1024, 2048, 4096. */
94+
#defineJUMP_BACKWARD_INITIAL_VALUE 16
95+
#defineJUMP_BACKWARD_INITIAL_BACKOFF 4
96+
staticinline_Py_BackoffCounter
97+
initial_jump_backoff_counter(void)
98+
{
99+
returnmake_backoff_counter(JUMP_BACKWARD_INITIAL_VALUE,
100+
JUMP_BACKWARD_INITIAL_BACKOFF);
101+
}
102+
103+
/* Initial exit temperature.
104+
* Must be larger than ADAPTIVE_COOLDOWN_VALUE,
105+
* otherwise when a side exit warms up we may construct
106+
* a new trace before the Tier 1 code has properly re-specialized.
107+
* Backoff sequence 64, 128, 256, 512, 1024, 2048, 4096. */
108+
#defineCOLD_EXIT_INITIAL_VALUE 64
109+
#defineCOLD_EXIT_INITIAL_BACKOFF 6
110+
111+
staticinline_Py_BackoffCounter
112+
initial_temperature_backoff_counter(void)
113+
{
114+
returnmake_backoff_counter(COLD_EXIT_INITIAL_VALUE,
115+
COLD_EXIT_INITIAL_BACKOFF);
116+
}
117+
118+
/* Unreachable backoff counter. */
119+
staticinline_Py_BackoffCounter
120+
initial_unreachable_backoff_counter(void)
121+
{
122+
returnforge_backoff_counter(UNREACHABLE_BACKOFF);
123+
}
124+
125+
#ifdef__cplusplus
126+
}
127+
#endif
128+
#endif/* !Py_INTERNAL_BACKOFF_H */

‎Include/internal/pycore_code.h

Lines changed: 27 additions & 37 deletions
Original file line numberDiff line numberDiff line change
@@ -31,7 +31,7 @@ extern "C" {
3131
#defineCACHE_ENTRIES(cache) (sizeof(cache)/sizeof(_Py_CODEUNIT))
3232

3333
typedefstruct {
34-
uint16_tcounter;
34+
_Py_BackoffCountercounter;
3535
uint16_tmodule_keys_version;
3636
uint16_tbuiltin_keys_version;
3737
uint16_tindex;
@@ -40,44 +40,44 @@ typedef struct {
4040
#defineINLINE_CACHE_ENTRIES_LOAD_GLOBAL CACHE_ENTRIES(_PyLoadGlobalCache)
4141

4242
typedefstruct {
43-
uint16_tcounter;
43+
_Py_BackoffCountercounter;
4444
}_PyBinaryOpCache;
4545

4646
#defineINLINE_CACHE_ENTRIES_BINARY_OP CACHE_ENTRIES(_PyBinaryOpCache)
4747

4848
typedefstruct {
49-
uint16_tcounter;
49+
_Py_BackoffCountercounter;
5050
}_PyUnpackSequenceCache;
5151

5252
#defineINLINE_CACHE_ENTRIES_UNPACK_SEQUENCE \
5353
CACHE_ENTRIES(_PyUnpackSequenceCache)
5454

5555
typedefstruct {
56-
uint16_tcounter;
56+
_Py_BackoffCountercounter;
5757
}_PyCompareOpCache;
5858

5959
#defineINLINE_CACHE_ENTRIES_COMPARE_OP CACHE_ENTRIES(_PyCompareOpCache)
6060

6161
typedefstruct {
62-
uint16_tcounter;
62+
_Py_BackoffCountercounter;
6363
}_PyBinarySubscrCache;
6464

6565
#defineINLINE_CACHE_ENTRIES_BINARY_SUBSCR CACHE_ENTRIES(_PyBinarySubscrCache)
6666

6767
typedefstruct {
68-
uint16_tcounter;
68+
_Py_BackoffCountercounter;
6969
}_PySuperAttrCache;
7070

7171
#defineINLINE_CACHE_ENTRIES_LOAD_SUPER_ATTR CACHE_ENTRIES(_PySuperAttrCache)
7272

7373
typedefstruct {
74-
uint16_tcounter;
74+
_Py_BackoffCountercounter;
7575
uint16_tversion[2];
7676
uint16_tindex;
7777
}_PyAttrCache;
7878

7979
typedefstruct {
80-
uint16_tcounter;
80+
_Py_BackoffCountercounter;
8181
uint16_ttype_version[2];
8282
union {
8383
uint16_tkeys_version[2];
@@ -93,39 +93,39 @@ typedef struct {
9393
#defineINLINE_CACHE_ENTRIES_STORE_ATTR CACHE_ENTRIES(_PyAttrCache)
9494

9595
typedefstruct {
96-
uint16_tcounter;
96+
_Py_BackoffCountercounter;
9797
uint16_tfunc_version[2];
9898
}_PyCallCache;
9999

100100
#defineINLINE_CACHE_ENTRIES_CALL CACHE_ENTRIES(_PyCallCache)
101101

102102
typedefstruct {
103-
uint16_tcounter;
103+
_Py_BackoffCountercounter;
104104
}_PyStoreSubscrCache;
105105

106106
#defineINLINE_CACHE_ENTRIES_STORE_SUBSCR CACHE_ENTRIES(_PyStoreSubscrCache)
107107

108108
typedefstruct {
109-
uint16_tcounter;
109+
_Py_BackoffCountercounter;
110110
}_PyForIterCache;
111111

112112
#defineINLINE_CACHE_ENTRIES_FOR_ITER CACHE_ENTRIES(_PyForIterCache)
113113

114114
typedefstruct {
115-
uint16_tcounter;
115+
_Py_BackoffCountercounter;
116116
}_PySendCache;
117117

118118
#defineINLINE_CACHE_ENTRIES_SEND CACHE_ENTRIES(_PySendCache)
119119

120120
typedefstruct {
121-
uint16_tcounter;
121+
_Py_BackoffCountercounter;
122122
uint16_tversion[2];
123123
}_PyToBoolCache;
124124

125125
#defineINLINE_CACHE_ENTRIES_TO_BOOL CACHE_ENTRIES(_PyToBoolCache)
126126

127127
typedefstruct {
128-
uint16_tcounter;
128+
_Py_BackoffCountercounter;
129129
}_PyContainsOpCache;
130130

131131
#defineINLINE_CACHE_ENTRIES_CONTAINS_OP CACHE_ENTRIES(_PyContainsOpCache)
@@ -451,18 +451,14 @@ write_location_entry_start(uint8_t *ptr, int code, int length)
451451

452452
/** Counters
453453
* The first 16-bit value in each inline cache is a counter.
454-
* When counting misses, the counter is treated as a simple unsigned value.
455454
*
456455
* When counting executions until the next specialization attempt,
457456
* exponential backoff is used to reduce the number of specialization failures.
458-
* The high 12 bits store the counter, the low 4 bits store the backoff exponent.
459-
* On a specialization failure, the backoff exponent is incremented and the
460-
* counter set to (2**backoff - 1).
461-
* Backoff == 6 -> starting counter == 63, backoff == 10 -> starting counter == 1023.
457+
* See pycore_backoff.h for more details.
458+
* On a specialization failure, the backoff counter is restarted.
462459
*/
463460

464-
/* With a 16-bit counter, we have 12 bits for the counter value, and 4 bits for the backoff */
465-
#defineADAPTIVE_BACKOFF_BITS 4
461+
#include"pycore_backoff.h"
466462

467463
// A value of 1 means that we attempt to specialize the *second* time each
468464
// instruction is executed. Executing twice is a much better indicator of
@@ -480,36 +476,30 @@ write_location_entry_start(uint8_t *ptr, int code, int length)
480476
#defineADAPTIVE_COOLDOWN_VALUE 52
481477
#defineADAPTIVE_COOLDOWN_BACKOFF 0
482478

483-
#defineMAX_BACKOFF_VALUE (16 - ADAPTIVE_BACKOFF_BITS)
479+
// Can't assert this in pycore_backoff.h because of header order dependencies
480+
static_assert(COLD_EXIT_INITIAL_VALUE>ADAPTIVE_COOLDOWN_VALUE,
481+
"Cold exit value should be larger than adaptive cooldown value");
484482

485-
486-
staticinlineuint16_t
483+
staticinline_Py_BackoffCounter
487484
adaptive_counter_bits(uint16_tvalue,uint16_tbackoff) {
488-
return ((value <<ADAPTIVE_BACKOFF_BITS)
489-
| (backoff& ((1 <<ADAPTIVE_BACKOFF_BITS)-1)));
485+
returnmake_backoff_counter(value,backoff);
490486
}
491487

492-
staticinlineuint16_t
488+
staticinline_Py_BackoffCounter
493489
adaptive_counter_warmup(void) {
494490
returnadaptive_counter_bits(ADAPTIVE_WARMUP_VALUE,
495491
ADAPTIVE_WARMUP_BACKOFF);
496492
}
497493

498-
staticinlineuint16_t
494+
staticinline_Py_BackoffCounter
499495
adaptive_counter_cooldown(void) {
500496
returnadaptive_counter_bits(ADAPTIVE_COOLDOWN_VALUE,
501497
ADAPTIVE_COOLDOWN_BACKOFF);
502498
}
503499

504-
staticinlineuint16_t
505-
adaptive_counter_backoff(uint16_tcounter) {
506-
uint16_tbackoff=counter& ((1 <<ADAPTIVE_BACKOFF_BITS)-1);
507-
backoff++;
508-
if (backoff>MAX_BACKOFF_VALUE) {
509-
backoff=MAX_BACKOFF_VALUE;
510-
}
511-
uint16_tvalue= (uint16_t)(1 <<backoff)-1;
512-
returnadaptive_counter_bits(value,backoff);
500+
staticinline_Py_BackoffCounter
501+
adaptive_counter_backoff(_Py_BackoffCountercounter) {
502+
returnrestart_backoff_counter(counter);
513503
}
514504

515505

‎Include/internal/pycore_interp.h

Lines changed: 0 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -239,12 +239,6 @@ struct _is {
239239
_PyOptimizerObject*optimizer;
240240
_PyExecutorObject*executor_list_head;
241241

242-
/* These two values are shifted and offset to speed up check in JUMP_BACKWARD */
243-
uint32_toptimizer_resume_threshold;
244-
uint32_toptimizer_backedge_threshold;
245-
246-
uint16_toptimizer_side_threshold;
247-
248242
_rare_eventsrare_events;
249243
PyDict_WatchCallbackbuiltins_dict_watcher;
250244

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp