Skip to content

Improving trace quality by tracking "fitness" and "exit quality" #146073

Closed
Closed
Improving trace quality by tracking "fitness" and "exit quality"#146073
Labels
3.15bugs and security fixesperformancePerformance or resource usagetopic-JITtype-featureA feature request or enhancement

Description

@markshannon
markshannon
opened on Mar 17, 2026

Feature 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

Activity

  1. markshannon
    added
    type-featureA feature request or enhancement
    performancePerformance or resource usage
    topic-JIT
    3.15bugs and security fixes
    on Mar 17, 2026

  2. Fidget-Spinner commented on Mar 24, 2026

    @Fidget-Spinner
    Fidget-Spinner
    on Mar 24, 2026
    Member

    Note: we should also consider frame depth in fitness. #146368

  3. henry-the-frog commented on Mar 25, 2026

    @henry-the-frog
    henry-the-frog
    on Mar 25, 2026 · Hidden as spam

  4. Fidget-Spinner commented on Mar 31, 2026

    @Fidget-Spinner
    Fidget-Spinner
    on Mar 31, 2026
    Member

    @cocolato is doing this apparently. In the future, please let us know if you want to take an issue!

  5. cocolato
    marked JIT: Introducing a fitness/exit quality control mechanism for the trace frontend #147942 as a duplicate of this issue on Mar 31, 2026

  6. cocolato commented on Mar 31, 2026

    @cocolato
    cocolato
    on Mar 31, 2026
    Member

    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
  7. Fidget-Spinner
    added 3 commits that reference this issue on Apr 3, 2026

    gh-146073: Add fitness/exit quality mechanism for JIT trace frontend (G…

    198b04b

    Revert "pythongh-146073: Add fitness/exit quality mechanism for JIT t…

    b9b2282

    gh-146073: Revert "gh-146073: Add fitness/exit quality mechanism for …

    328da67

  8. markshannon commented on Apr 7, 2026

    @markshannon
    markshannon
    on Apr 7, 2026
    MemberAuthor

    @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.

  9. markshannon
    added 2 commits that reference this issue on Apr 22, 2026

    GH-146073: Add example script for dumping JIT traces (GH-148840)

    f93834f

    gh-146073: Add fitness/exit quality mechanism for JIT trace frontend (G…

    618b726
  10. ljfp
    added 4 commits that reference this issue on Apr 25, 2026

    pythongh-146073: Add fitness/exit quality mechanism for JIT trace fro…

    4afd0c6

    pythongh-146073: Revert "pythongh-146073: Add fitness/exit quality me…

    15229de

    pythonGH-146073: Add example script for dumping JIT traces (pythonGH-…

    894df80

    pythongh-146073: Add fitness/exit quality mechanism for JIT trace fro…

    2df1782
  11. markshannon
    added a commit that references this issue on Apr 27, 2026

    GH-146073: Add fitness to executor dumps. (GH-148959)

    276f474

  12. markshannon commented on Sep 23, 2026

    @markshannon
    markshannon
    on Sep 23, 2026
    MemberAuthor

    This is done well enough, and given the JIT hiatus and general rethink, I'm closing this.

  13. markshannon
    closed this as completedon Sep 23, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    3.15bugs and security fixesperformancePerformance or resource usagetopic-JITtype-featureA feature request or enhancement

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions