gh-141498: Change backoff counter to use prime numbers instead of powers of 2 #141591
Conversation
markshannon
left a comment
markshannon
left a comment
There was a problem hiding this comment.
Looks good, but I think it is worth using a table.
Using a table allows us to tweak the values to get better performance profile in future, and is easier to understand.
Include/internal/pycore_backoff.h
Outdated
| 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); |
There was a problem hiding this comment.
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);There was a problem hiding this comment.
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.
There was a problem hiding this comment.
Of course, I'll add using LOOKUP_TABLE in this PR.
efimov-mikhail
changed the title
Include/internal/pycore_backoff.h
Outdated
| // We only use values x and backoffs b such that | ||
| // x + 1 is near to 2**(2*b+1) and x + 1 is prime. | ||
| static const uint16_t value_and_backoff_next[] = { | ||
| MAKE_VALUE_AND_BACKOFF(6, 1), |
There was a problem hiding this comment.
This needs to be MAKE_VALUE_AND_BACKOFF(1, 1) so that code is re-specialized quickly when the cooldown counter expires.
See https://github.com/python/cpython/blob/main/Include/internal/pycore_code.h#L445
|
A Python core developer has requested some changes be made to your pull request before we can consider merging it. If you could please address their requests along with any other requests in other reviews from core developers that would be appreciated. Once you have made the requested changes, please leave a comment on this pull request containing the phrase |
|
Oops, sorry for this mistake. |
3 participants
Uh oh!
There was an error while loading. Please reload this page.