python / python/cpython

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

Ouverte
#151,499 1 commentaire 0 réactions 0 personnes assignées Voir sur GitHub

Personne n'a encore pris cette issue.

interpreter-core performance topic-JIT
Langage dominant
Python
Étoiles
77.2k
Forks
35.9k
Métriques de merge des PR
Métriques de PR en attente

Description

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.

Guide de contribution

Ouvrir le guide de contribution

Par où commencer

  1. Lisez l'issue en entier, puis le guide de contribution du projet.
  2. Signalez en commentaire que vous la prenez — cela évite que deux personnes fassent le même travail.
  3. Forkez le dépôt et travaillez sur une branche.
  4. Ouvrez une pull request qui référence le numéro de l'issue.

Piste de recherche

Commencez par l’instruction _POP_JUMP_IF_FALSE et les implémentations similaires de branchements conditionnels, puis suivez la manière dont leurs données de branchement sont enregistrées pour les traces JIT. La modification est terminée lorsque les compteurs de direction utilisent deux compteurs saturants, sont plafonnés à 255 et fournissent les informations de warmup proposées sans modifier le comportement de l’instruction.

Rédigé par le modèle d'indexation à partir du texte de l'issue.

Évaluation

Stack technique
c, python
Domaine
compilers, performance
Type d'issue
Fonctionnalité
Difficulté
4/5
Temps estimé
3-5 jours
Activité
Calme
Clarté
Plutôt claire
Accessibilité débutants
48/100

Recevez les nouvelles issues par e-mail

Un résumé court des issues GitHub adaptées aux débutants.