python3.13/internal/pycore_backoff.h

0001
0002 #ifndef Py_INTERNAL_BACKOFF_H
0003 #define Py_INTERNAL_BACKOFF_H
0004 #ifdef __cplusplus
0005 extern "C" {
0006 #endif
0007
0008 #ifndef Py_BUILD_CORE
0009 #  error "this header requires Py_BUILD_CORE define"
0010 #endif
0011
0012 #include <assert.h>
0013 #include <stdbool.h>
0014 #include <stdint.h>
0015
0016
0017 typedef struct {
0018     union {
0019         struct {
0020             uint16_t backoff : 4;
0021             uint16_t value : 12;
0022         };
0023         uint16_t as_counter;  // For printf("%#x", ...)
0024     };
0025 } _Py_BackoffCounter;
0026
0027
0028 /* 16-bit countdown counters using exponential backoff.
0029
0030    These are used by the adaptive specializer to count down until
0031    it is time to specialize an instruction. If specialization fails
0032    the counter is reset using exponential backoff.
0033
0034    Another use is for the Tier 2 optimizer to decide when to create
0035    a new Tier 2 trace (executor). Again, exponential backoff is used.
0036
0037    The 16-bit counter is structured as a 12-bit unsigned 'value'
0038    and a 4-bit 'backoff' field. When resetting the counter, the
0039    backoff field is incremented (until it reaches a limit) and the
0040    value is set to a bit mask representing the value 2**backoff - 1.
0041    The maximum backoff is 12 (the number of value bits).
0042
0043    There is an exceptional value which must not be updated, 0xFFFF.
0044 */
0045
0046 #define UNREACHABLE_BACKOFF 0xFFFF
0047
0048 static inline bool
0049 is_unreachable_backoff_counter(_Py_BackoffCounter counter)
0050 {
0051     return counter.as_counter == UNREACHABLE_BACKOFF;
0052 }
0053
0054 static inline _Py_BackoffCounter
0055 make_backoff_counter(uint16_t value, uint16_t backoff)
0056 {
0057     assert(backoff <= 15);
0058     assert(value <= 0xFFF);
0059     _Py_BackoffCounter result;
0060     result.value = value;
0061     result.backoff = backoff;
0062     return result;
0063 }
0064
0065 static inline _Py_BackoffCounter
0066 forge_backoff_counter(uint16_t counter)
0067 {
0068     _Py_BackoffCounter result;
0069     result.as_counter = counter;
0070     return result;
0071 }
0072
0073 static inline _Py_BackoffCounter
0074 restart_backoff_counter(_Py_BackoffCounter counter)
0075 {
0076     assert(!is_unreachable_backoff_counter(counter));
0077     if (counter.backoff < 12) {
0078         return make_backoff_counter((1 << (counter.backoff + 1)) - 1, counter.backoff + 1);
0079     }
0080     else {
0081         return make_backoff_counter((1 << 12) - 1, 12);
0082     }
0083 }
0084
0085 static inline _Py_BackoffCounter
0086 pause_backoff_counter(_Py_BackoffCounter counter)
0087 {
0088     return make_backoff_counter(counter.value | 1, counter.backoff);
0089 }
0090
0091 static inline _Py_BackoffCounter
0092 advance_backoff_counter(_Py_BackoffCounter counter)
0093 {
0094     if (!is_unreachable_backoff_counter(counter)) {
0095         return make_backoff_counter((counter.value - 1) & 0xFFF, counter.backoff);
0096     }
0097     else {
0098         return counter;
0099     }
0100 }
0101
0102 static inline bool
0103 backoff_counter_triggers(_Py_BackoffCounter counter)
0104 {
0105     return counter.value == 0;
0106 }
0107
0108 /* Initial JUMP_BACKWARD counter.
0109  * This determines when we create a trace for a loop.
0110 * Backoff sequence 16, 32, 64, 128, 256, 512, 1024, 2048, 4096. */
0111 #define JUMP_BACKWARD_INITIAL_VALUE 16
0112 #define JUMP_BACKWARD_INITIAL_BACKOFF 4
0113 static inline _Py_BackoffCounter
0114 initial_jump_backoff_counter(void)
0115 {
0116     return make_backoff_counter(JUMP_BACKWARD_INITIAL_VALUE,
0117                                 JUMP_BACKWARD_INITIAL_BACKOFF);
0118 }
0119
0120 /* Initial exit temperature.
0121  * Must be larger than ADAPTIVE_COOLDOWN_VALUE,
0122  * otherwise when a side exit warms up we may construct
0123  * a new trace before the Tier 1 code has properly re-specialized.
0124  * Backoff sequence 64, 128, 256, 512, 1024, 2048, 4096. */
0125 #define COLD_EXIT_INITIAL_VALUE 64
0126 #define COLD_EXIT_INITIAL_BACKOFF 6
0127
0128 static inline _Py_BackoffCounter
0129 initial_temperature_backoff_counter(void)
0130 {
0131     return make_backoff_counter(COLD_EXIT_INITIAL_VALUE,
0132                                 COLD_EXIT_INITIAL_BACKOFF);
0133 }
0134
0135 /* Unreachable backoff counter. */
0136 static inline _Py_BackoffCounter
0137 initial_unreachable_backoff_counter(void)
0138 {
0139     return forge_backoff_counter(UNREACHABLE_BACKOFF);
0140 }
0141
0142 #ifdef __cplusplus
0143 }
0144 #endif
0145 #endif /* !Py_INTERNAL_BACKOFF_H */