GeezerVison is showing github.com — Improving trace quality by tracking "fitness" and "exit quality" · Issue #146073 · python/cpython
Improving trace quality by tracking "fitness" and "exit quality" #146073DescriptionFeature or enhancement
Proposal:
The performance of the JIT depends heavily on the quality of the traces that the front-end produces. If traces are too short, very long, overlap a lot, or drop into the interpreter too often, performance suffers.
To avoid those cases of poor performance, we should track two values during tracing:
- The fitness of the current trace
- The quality of the end of the trace as a point to stop the trace.
If fitness < exit_quality we should stop the trace.
Fitness:
Fitness should:
- start high
- be reduced by branches, how much depending on the bias of branch
- be reduced (by quite a lot) by backward edges
- be reduced a small amount by each instruction (to discourage excessively long traces)
- start lower for non-branch side exits to reduce code replication
Exit quality
Exit quality should be high for:
- The starting point of the trace (very high for this)
ENTER_EXECUTOR instructions- Merge points in the control flow graph (will need the bytecode compiler to generate this data)
Exit quality should be low for:
- Specializable instructions
Has this already been discussed elsewhere?
This is a minor feature, which does not need previous discussion elsewhere
Links to previous discussion of this feature:
No response
Linked PRs
ActivityFidget-Spinner commented on Mar 24, 2026 Note: we should also consider frame depth in fitness. #146368 henry-the-frog commented on Mar 25, 2026 Fidget-Spinner commented on Mar 31, 2026 @cocolato is doing this apparently. In the future, please let us know if you want to take an issue! cocolato commented on Mar 31, 2026 Hi @Fidget-Spinner @markshannon. I wrote some details about the fitness/exit quality mechanism, I’d love to hear your thoughts or suggestions on this.
Proposal Details
Fitness
Decreases monotonically from an initial value, with additional consumption in specific scenarios:
- Each bytecode instruction: Minor deduction (e.g., 2)
- Conditional branches: The amount deducted is determined by the bias of
RECORD_BRANCH_TAKEN—branches that are fully predictable incur almost no deduction, while 50%/50% branches incur a significant deduction
- Backward jumps (
JUMP_BACKWARD series): Significant deduction, as a backward jump means the trace enters the second iteration of a loop, and the benefits diminish as it continues
- Function Call Inlining: Should be frame depth-dependent; deeper nesting incurs heavier penalties
Root traces and side traces should have different initial values—since side traces are derived from exits, they should be allocated fewer “stamina” points.
Exit Quality
Evaluates how good this location would be as an exit point if the tracer were to stop here:
ENTER_EXECUTOR position (Best): A compiled executor is already available; stopping here allows for direct execution.- Ordinary bytecode location (Normal): Neither particularly good nor particularly bad
- Specializable instruction (Poor): Stopping here means the tracer must re-specialize the instruction the next time it reaches this point
Decision Rule
fitness < exit_quality
Last Known Good Exit
The tracer should continuously record the best exit encountered during tracing. When it needs to stop, it should prioritize reverting to that position rather than stopping at the current location, which might be suboptimal.
This mechanism can also improve existing unsupported and trace_too_long paths—when these situations occur, the tracer can revert to a previously encountered good position.
Implementation
Phase 1: Core Mechanism
Minimum viable version, enabling the tracer to “actively stop at good positions”:
- Implement structures for fitness, best exit, frame depth, etc.
- Implement
update_trace_fitness() — decrement per frame + branch bias penalty + back-edge penalty
- Termination check: fitness < exit_quality
- Record best exit + fallback via try_best_exit_fallback()
- Implement frame depth tracking (detect frame changes to increment/decrement)
Phase 2: Tuning and Enhancement
Further optimization based on real-world data from Phase 1:
- Parameter tuning: Adjust fitness constants based on results from pyperformance and custom benchmarks
Phase 3: Long-Term Evolution
- Merge point: Once the bytecode compiler supports it, assign a higher exit quality at CFG merge points
- Per-executor adaptive parameters: Dynamically adjust fitness parameters based on runtime feedback
added 3 commits that reference this issue on Apr 3, 2026gh-146073: Add fitness/exit quality mechanism for JIT trace frontend (G… markshannon commented on Apr 7, 2026 @cocolato
I'd suggest coming up with a set of inequalities to make sure that the fitness values do not break any invariants.
For example:
- fitness at
MAX_ABSTRACT_FRAME_DEPTH - 1 < min(exit_quality). Note we can change MAX_ABSTRACT_FRAME_DEPTH if needed (although it is probably too high already)
- The fitness after a backwards edge + N instructions ==
exit_quality of the start point. Choose N to allow flow into loops, but avoid excess unrolling, maybe some where in the range of 20 to 50?
- Fitness after ~3 perfectly balanced branches should <
exit_quality of a "good" exit, and after ~4 such branches it should be less than the exit_quality of a "normal instruction" (to avoid too many overlapping traces)
We also need some guidelines to ensure that we get good traces, for example:
- The fitness after a call and return should be close to the fitness if neither call nor return were present.
- Avoid reasons other than fitness and exit quality for ending traces unless unavoidable (like oparg > 0xffff)
Aside:
Only a few instructions can have oparg > 0xffff and they are all branches, packing or unpacking instructions. The branches get converted into exits (with a target not an oparg), so it is really only the packing and unpacking instructions that are a problem. In order to keep stack usage under control, we should eliminate those instructions in the bytecode compiler anyway.
Starting fitness
We want the fitness to allow a few 100s of uops in an optimized trace with branches.
The optimizer will leave about half of the uops (it will leave fewer as we improve it).
Given OPTIMIZER_EFFECTIVENESS = estimate_of(uops_in_recorded_trace/uops_in_optimzed_trace)
A good starting fitness would be MAX_TARGET_LENGTH * OPTIMIZER_EFFECTIVENESS.
I'd suggest MAX_TARGET_LENGTH = 400 to start with, but we can easily change it.
The fitness of side exits traces should probably not be much lower than a rooted trace, but maybe could be lower for longer chains. Maybe (8-chain_depth) * BASE / 8?
Other changes
You might need to remove the close_loop_instr and jump_backward_instr attributes and rely only on the start_instr field for detecting loops. The fitness should prevent overly long traces and excessive loop unrolling. markshannon commented on Sep 23, 2026 This is done well enough, and given the JIT hiatus and general rethink, I'm closing this.
MetadataMetadataDevelopmentNo branches or pull requestsIssue actions
|