Skip to content

gh-141498: Change backoff counter to use prime numbers instead of powers of 2 #141591

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

Merged
markshannon merged 21 commits into from
Nov 21, 2025
Merged

gh-141498: Change backoff counter to use prime numbers instead of powers of 2 #141591

Show file tree
Hide file tree
Changes from 5 commits
Commits
Show all changes
21 commits
Select commit Hold shift + click to select a range
86de63a
Some refactor
efimov-mikhail Nov 15, 2025
4eb3231
Changes in backoff bit pattern
efimov-mikhail Nov 15, 2025
2581629
Add NEWS
efimov-mikhail Nov 15, 2025
96de415
NEWS fix
efimov-mikhail Nov 15, 2025
ce3e14f
Change ITEMS count in test
efimov-mikhail Nov 15, 2025
e17b195
Refactor restart_backoff_counter
efimov-mikhail Nov 19, 2025
44b4eb8
Remove unneed assertion and function
efimov-mikhail Nov 19, 2025
6d44333
Use lookup_table
efimov-mikhail Nov 19, 2025
0e05712
Use MAKE_BACKOFF_COUNTER macro
efimov-mikhail Nov 19, 2025
f3c9287
Comment change
efimov-mikhail Nov 19, 2025
e16b368
Fix Windows build: remove const keyword
efimov-mikhail Nov 19, 2025
6b1fe66
Simplify obtaining next backoff
efimov-mikhail Nov 19, 2025
2600236
Remove forge_backoff_counter
efimov-mikhail Nov 19, 2025
ec27072
Another try to fix Windows build
efimov-mikhail Nov 19, 2025
401b6da
Revert make_backoff_counter
efimov-mikhail Nov 19, 2025
3418be1
Revert changes to pycore_code.h
efimov-mikhail Nov 19, 2025
ceddb6a
Comment fix
efimov-mikhail Nov 19, 2025
a89d6de
Temporarily disable assert
efimov-mikhail Nov 19, 2025
c7873c2
Revert forge_backoff_counter
efimov-mikhail Nov 19, 2025
5b7bfd9
Fix CI, NEWS updated
efimov-mikhail Nov 19, 2025
dda4cdb
Review addressed: change values and comment
efimov-mikhail Nov 20, 2025
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
30 changes: 16 additions & 14 deletions Include/internal/pycore_backoff.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -22,18 +22,20 @@ extern "C" {
Another use is for the Tier 2 optimizer to decide when to create
a new Tier 2 trace (executor). Again, exponential backoff is used.

The 16-bit counter is structured as a 12-bit unsigned 'value'
and a 4-bit 'backoff' field. When resetting the counter, the
The 16-bit counter is structured as a 13-bit unsigned 'value'
and a 3-bit 'backoff' field. When resetting the counter, the
backoff field is incremented (until it reaches a limit) and the
value is set to a bit mask representing the value 2**backoff - 1.
The maximum backoff is 12 (the number of bits in the value).
value is set to a bit mask representing the value 2**(2*backoff+1) - 1.
The maximum backoff is 6, since 7 is an UNREACHABLE_BACKOFF.

There is an exceptional value which must not be updated, 0xFFFF.
*/

#define BACKOFF_BITS 4
#define MAX_BACKOFF 12
#define UNREACHABLE_BACKOFF 15
#define BACKOFF_BITS 3
#define BACKOFF_MASK 7
#define MAX_BACKOFF 6
#define UNREACHABLE_BACKOFF 7
#define MAX_VALUE 0x1FFF

static inline bool
is_unreachable_backoff_counter(_Py_BackoffCounter counter)
Expand All @@ -44,8 +46,8 @@ is_unreachable_backoff_counter(_Py_BackoffCounter counter)
static inline _Py_BackoffCounter
make_backoff_counter(uint16_t value, uint16_t backoff)
{
assert(backoff <= 15);
assert(value <= 0xFFF);
assert(backoff <= UNREACHABLE_BACKOFF);
assert(value <= MAX_VALUE);
_Py_BackoffCounter result;
result.value_and_backoff = (value << BACKOFF_BITS) | backoff;
return result;
Expand All @@ -63,12 +65,12 @@ static inline _Py_BackoffCounter
restart_backoff_counter(_Py_BackoffCounter counter)
{
assert(!is_unreachable_backoff_counter(counter));
int backoff = counter.value_and_backoff & 15;
int backoff = counter.value_and_backoff & BACKOFF_MASK;
if (backoff < MAX_BACKOFF) {
return make_backoff_counter((1 << (backoff + 1)) - 1, backoff + 1);
return make_backoff_counter((1 << (2 * backoff + 3)) - 1, backoff + 1);

@markshannon markshannon Nov 19, 2025

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.

Since we are changing this, we might as well use a table. It is only 8 entries of 2 bytes each.

See #141498 (comment)
We want 0 to map to 1, and MAX_BACKOFF to map to near 8k.

I think you can make this branchless as well. Something like:

assert(backoff <= MAX_BACKOFF);
value = LOOKUP_TABLE[backoff]
backoff = backoff == MAX_BACKOFF ? backoff : backoff + 1;
return make_backoff_counter(value, backoff);

@markshannon markshannon Nov 19, 2025

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.

In fact, if we store the counter, both value and backoff, in the table. It can be even simpler:

assert(backoff <= MAX_BACKOFF);
return LOOKUP_TABLE[backoff];

And have LOOKUP_TABLE[UNREACHABLE_BACKOFF] == LOOKUP_TABLE[MAX_BACKOFF] so non-debug builds do something sensible.

@efimov-mikhail efimov-mikhail Nov 19, 2025

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.

Of course, I'll add using LOOKUP_TABLE in this PR.

}
else {
return make_backoff_counter((1 << MAX_BACKOFF) - 1, MAX_BACKOFF);
return make_backoff_counter((1 << (2 * MAX_BACKOFF + 1)) - 1, MAX_BACKOFF);
}
}

Expand Down Expand Up @@ -113,7 +115,7 @@ trigger_backoff_counter(void)
// as we always end up tracing the loop iteration's
// exhaustion iteration. Which aborts our current tracer.
#define JUMP_BACKWARD_INITIAL_VALUE 4000
#define JUMP_BACKWARD_INITIAL_BACKOFF 12
#define JUMP_BACKWARD_INITIAL_BACKOFF 6
static inline _Py_BackoffCounter
initial_jump_backoff_counter(void)
{
Expand All @@ -126,7 +128,7 @@ initial_jump_backoff_counter(void)
* otherwise when a side exit warms up we may construct
* a new trace before the Tier 1 code has properly re-specialized. */
#define SIDE_EXIT_INITIAL_VALUE 4000
#define SIDE_EXIT_INITIAL_BACKOFF 12
#define SIDE_EXIT_INITIAL_BACKOFF 6

static inline _Py_BackoffCounter
initial_temperature_backoff_counter(void)
Expand Down
2 changes: 1 addition & 1 deletion Lib/test/test_opcache.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -590,7 +590,7 @@ def make_deferred_ref_count_obj():
class TestRacesDoNotCrash(TestBase):
# Careful with these. Bigger numbers have a higher chance of catching bugs,
# but you can also burn through a *ton* of type/dict/function versions:
ITEMS = 1000
ITEMS = 1400
Comment thread
efimov-mikhail marked this conversation as resolved.
LOOPS = 4
WRITERS = 2

Expand Down
2 changes: 2 additions & 0 deletions Misc/NEWS.d/next/Core_and_Builtins/2025-11-15-14-04-35.gh-issue-141589.VfdMDD.rst
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,2 @@
Change ``backoff counter`` to use powers of 4 instead of powers of 2.
This allows to support values up to 8191. Patch by Mikhail Efimov.
Loading