python / python/cpython

Use saturating counters for branch taken counters in `_POP_JUMP_IF_FALSE` and similar instructions.

Offen
#151,499 1 Kommentar 0 Reaktionen 0 zugewiesene Personen Auf GitHub ansehen

Dieses Issue hat noch niemand übernommen.

interpreter-core performance topic-JIT
Vorherrschende Sprache
Python
Sterne
77.2k
Forks
35.9k
PR-Merge-Kennzahlen
PR-Kennzahlen ausstehend

Beschreibung

Each conditional branch instruction contains a 16 bit field for recording the direction of the last 16 jumps.

    uint16_t *branches;
    uint16_t val = *branches;
    val = (val << 1) | direction;
    *branches =val;

This tells the direction of the last 16 branches.
When recording traces for the JIT, 16 branches is not a lot of information to guide region selection.

Instead, we could record the count of the two directions instead using a pair of saturating 8 bit counters.

    uint8_t branches[2];
    branches[direction] += (branches[direction] != 255);

Which is only one extra ALU instruction for most C compilers, and no extra memory accesses.

With a JIT warmup of up 500, we can get precise numbers of the branches taken.
With a warmup of a 1000, the saturating counters can still distinguish between branches that are rarely taken and those which are more balanced.

For example, if a branch switches direction every 20 times, the current counter might show a perfectly biased branch, but the saturating counter approach will show that the branch is roughly balanced.

Beitragsleitfaden

Beitragsleitfaden öffnen

Erste Schritte

  1. Lies das ganze Issue und danach den Beitragsleitfaden des Projekts.
  2. Schreib ins Issue, dass du es übernimmst — das erspart doppelte Arbeit.
  3. Forke das Repository und arbeite in einem Branch.
  4. Öffne einen Pull Request, der die Issue-Nummer nennt.

Rechercherichtung

Beginne bei der Anweisung _POP_JUMP_IF_FALSE und ähnlichen Implementierungen bedingter Sprünge und verfolge anschließend, wie deren Sprungdaten für JIT-Traces aufgezeichnet werden. Die Änderung ist abgeschlossen, wenn Richtungszähler zwei saturierende Zähler verwenden, bei 255 gedeckelt sind und die vorgeschlagenen Warmup-Informationen bereitstellen, ohne das Verhalten der Anweisung zu ändern.

Vom Indexierungsmodell aus dem Issue-Text verfasst.

Bewertung

Tech-Stack
c, python
Bereich
compilers, performance
Issue-Typ
Feature
Schwierigkeit
4/5
Geschätzter Aufwand
3-5 Tage
Aktivitätsstatus
Ruhig
Klarheit
Größtenteils klar
Anfängerfreundlichkeit
48/100

Neue Issues direkt in Ihr Postfach

Eine kurze Übersicht über anfängerfreundliche GitHub-Issues.