From eb618d5ff0371efead28a3afa91834e4beebf73d Mon Sep 17 00:00:00 2001
From: Mark Shannon <mark@hotpy.org>
Date: Tue, 31 May 2022 11:58:26 +0100
Subject: GH-93354: Use exponential backoff to avoid excessive specialization
 attempts. (GH-93355)

---
 Include/internal/pycore_code.h | 47 +++++++++++++++++++++++++++++++++++++++---
 1 file changed, 44 insertions(+), 3 deletions(-)

(limited to 'Include/internal/pycore_code.h')

diff --git a/Include/internal/pycore_code.h b/Include/internal/pycore_code.h
index 2cfa319f2d..9d33ed71e7 100644
--- a/Include/internal/pycore_code.h
+++ b/Include/internal/pycore_code.h
@@ -227,9 +227,6 @@ extern void _PyLineTable_InitAddressRange(
 extern int _PyLineTable_NextAddressRange(PyCodeAddressRange *range);
 extern int _PyLineTable_PreviousAddressRange(PyCodeAddressRange *range);
 
-
-#define ADAPTIVE_CACHE_BACKOFF 64
-
 /* Specialization functions */
 
 extern int _Py_Specialize_LoadAttr(PyObject *owner, _Py_CODEUNIT *instr,
@@ -423,6 +420,50 @@ write_location_entry_start(uint8_t *ptr, int code, int length)
 }
 
 
+/** Counters
+ * The first 16-bit value in each inline cache is a counter.
+ * When counting misses, the counter is treated as a simple unsigned value.
+ *
+ * When counting executions until the next specialization attempt,
+ * exponential backoff is used to reduce the number of specialization failures.
+ * The high 12 bits store the counter, the low 4 bits store the backoff exponent.
+ * On a specialization failure, the backoff exponent is incremented and the
+ * counter set to (2**backoff - 1).
+ * Backoff == 6 -> starting counter == 63, backoff == 10 -> starting counter == 1023.
+ */
+
+/* With a 16-bit counter, we have 12 bits for the counter value, and 4 bits for the backoff */
+#define ADAPTIVE_BACKOFF_BITS 4
+/* The initial counter value is 31 == 2**ADAPTIVE_BACKOFF_START - 1 */
+#define ADAPTIVE_BACKOFF_START 5
+
+#define MAX_BACKOFF_VALUE (16 - ADAPTIVE_BACKOFF_BITS)
+
+
+static inline uint16_t
+adaptive_counter_bits(int value, int backoff) {
+    return (value << ADAPTIVE_BACKOFF_BITS) |
+           (backoff & ((1<<ADAPTIVE_BACKOFF_BITS)-1));
+}
+
+static inline uint16_t
+adaptive_counter_start(void) {
+    unsigned int value = (1 << ADAPTIVE_BACKOFF_START) - 1;
+    return adaptive_counter_bits(value, ADAPTIVE_BACKOFF_START);
+}
+
+static inline uint16_t
+adaptive_counter_backoff(uint16_t counter) {
+    unsigned int backoff = counter & ((1<<ADAPTIVE_BACKOFF_BITS)-1);
+    backoff++;
+    if (backoff > MAX_BACKOFF_VALUE) {
+        backoff = MAX_BACKOFF_VALUE;
+    }
+    unsigned int value = (1 << backoff) - 1;
+    return adaptive_counter_bits(value, backoff);
+}
+
+
 #ifdef __cplusplus
 }
 #endif
-- 
cgit v1.2.1