https://github.com/python/cpython/commit/a3b78a3adecf794dc576404b14ed3f2c8401fdf1
commit: a3b78a3adecf794dc576404b14ed3f2c8401fdf1
branch: main
author: Mikhail Efimov <[email protected]>
committer: markshannon <[email protected]>
date: 2025-11-21T17:00:25Z
summary:
gh-141498: Change backoff counter to use prime numbers instead of powers of 2
(GH-141591)
files:
A
Misc/NEWS.d/next/Core_and_Builtins/2025-11-15-14-04-35.gh-issue-141589.VfdMDD.rst
M Include/internal/pycore_backoff.h
M Lib/test/test_opcache.py
diff --git a/Include/internal/pycore_backoff.h
b/Include/internal/pycore_backoff.h
index 71066f1bd9f19b..7f60eb495080ae 100644
--- a/Include/internal/pycore_backoff.h
+++ b/Include/internal/pycore_backoff.h
@@ -22,33 +22,48 @@ 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 some prime value - 1.
+ New values and backoffs for each backoff are calculated once
+ at compile time and saved to value_and_backoff_next table.
+ 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
-
-static inline bool
-is_unreachable_backoff_counter(_Py_BackoffCounter counter)
-{
- return counter.value_and_backoff == UNREACHABLE_BACKOFF;
-}
+#define BACKOFF_BITS 3
+#define BACKOFF_MASK 7
+#define MAX_BACKOFF 6
+#define UNREACHABLE_BACKOFF 7
+#define MAX_VALUE 0x1FFF
+
+#define MAKE_VALUE_AND_BACKOFF(value, backoff) \
+ ((value << BACKOFF_BITS) | backoff)
+
+// For previous backoff b we use value x 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(1, 1),
+ MAKE_VALUE_AND_BACKOFF(6, 2),
+ MAKE_VALUE_AND_BACKOFF(30, 3),
+ MAKE_VALUE_AND_BACKOFF(126, 4),
+ MAKE_VALUE_AND_BACKOFF(508, 5),
+ MAKE_VALUE_AND_BACKOFF(2052, 6),
+ // We use the same backoff counter for all backoffs >= MAX_BACKOFF.
+ MAKE_VALUE_AND_BACKOFF(8190, 6),
+ MAKE_VALUE_AND_BACKOFF(8190, 6),
+};
static inline _Py_BackoffCounter
make_backoff_counter(uint16_t value, uint16_t backoff)
{
- assert(backoff <= 15);
- assert(value <= 0xFFF);
- _Py_BackoffCounter result;
- result.value_and_backoff = (value << BACKOFF_BITS) | backoff;
- return result;
+ assert(backoff <= UNREACHABLE_BACKOFF);
+ assert(value <= MAX_VALUE);
+ return ((_Py_BackoffCounter){
+ .value_and_backoff = MAKE_VALUE_AND_BACKOFF(value, backoff)
+ });
}
static inline _Py_BackoffCounter
@@ -62,14 +77,11 @@ forge_backoff_counter(uint16_t counter)
static inline _Py_BackoffCounter
restart_backoff_counter(_Py_BackoffCounter counter)
{
- assert(!is_unreachable_backoff_counter(counter));
- int backoff = counter.value_and_backoff & 15;
- if (backoff < MAX_BACKOFF) {
- return make_backoff_counter((1 << (backoff + 1)) - 1, backoff + 1);
- }
- else {
- return make_backoff_counter((1 << MAX_BACKOFF) - 1, MAX_BACKOFF);
- }
+ uint16_t backoff = counter.value_and_backoff & BACKOFF_MASK;
+ assert(backoff <= MAX_BACKOFF);
+ return ((_Py_BackoffCounter){
+ .value_and_backoff = value_and_backoff_next[backoff]
+ });
}
static inline _Py_BackoffCounter
@@ -113,7 +125,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)
{
@@ -126,7 +138,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)
diff --git a/Lib/test/test_opcache.py b/Lib/test/test_opcache.py
index c7eea75117de8c..4113b79ef5c80b 100644
--- a/Lib/test/test_opcache.py
+++ b/Lib/test/test_opcache.py
@@ -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
LOOPS = 4
WRITERS = 2
diff --git
a/Misc/NEWS.d/next/Core_and_Builtins/2025-11-15-14-04-35.gh-issue-141589.VfdMDD.rst
b/Misc/NEWS.d/next/Core_and_Builtins/2025-11-15-14-04-35.gh-issue-141589.VfdMDD.rst
new file mode 100644
index 00000000000000..5eb0e0c8b89f7a
--- /dev/null
+++
b/Misc/NEWS.d/next/Core_and_Builtins/2025-11-15-14-04-35.gh-issue-141589.VfdMDD.rst
@@ -0,0 +1,3 @@
+Change ``backoff counter`` to use prime numbers instead of powers of 2.
+Use only 3 bits for ``counter`` and 13 bits for ``value``.
+This allows to support values up to 8191. Patch by Mikhail Efimov.
_______________________________________________
Python-checkins mailing list -- [email protected]
To unsubscribe send an email to [email protected]
https://mail.python.org/mailman3//lists/python-checkins.python.org
Member address: [email protected]
