Exécution spéculative vs code sans branches

Exécution spéculative et code sans branchement : compromis de performance cachés

Les processeurs modernes exécutent des milliards d'opérations par seconde, mais la vitesse d'accès à la mémoire progresse plus lentement. Cet écart signifie que l'attente des données devient une source majeure de perte de performance. Les processeurs ont évolué d'exécuteurs passifs à gestionnaires actifs du flux de données : exécution dans le désordre, réorganisation des dépendances et exécution spéculative.

La prédiction de branche permet de démarrer les chargements tôt, masquant la latence mémoire. Une mauvaise prédiction coûte 10 à 20 cycles, mais attendre la L3 ou la DRAM en prend des centaines. Le code sans branchement élimine les mauvaises prédictions mais supprime la capacité du processeur à spéculer.

Évolution de l'exécution séquentielle à l'exécution spéculative

Les premiers systèmes exécutaient les instructions strictement de manière séquentielle. L'IBM System/360 Model 91 a introduit l'algorithme de Tomasulo pour l'exécution dans le désordre : les instructions démarrent lorsque les opérandes sont prêtes.

L'exécution spéculative est apparue plus tard dans les processeurs superscalaires comme l'Intel Pentium Pro (1995). Un pipeline de 40 micro-opérations maintient des dizaines d'instructions en cours d'exécution, prédisant les branches en fonction de l'historique.

for (size_t i = 0; i < n; i++) {
    if (arr[i] >= 0) {
          ... code_true ...;
    } else {
        ... code_false ...;
    }
}

Ici, le chargement de arr[i] peut provoquer un blocage de 10 à 100+ cycles si les données ne sont pas en L1. Le processeur prédit la branche, démarre code_true et initie le préchargement. En cas de mauvaise prédiction—vidage et redémarrage.

Sans branchement vs avec branchement : dépendance au cache

Simplifié avec branchement :

if (arr[i] > 0) {
    result++;
}

Devient :

result += (arr[i] > 0);

• Données en L1 : le sans branchement gagne—pas de mauvaise prédiction, délai minimal.
• L2 : neutre, le coût de la mauvaise prédiction est faible.
• L3/DRAM : le code avec branchement est plus rapide—la spéculation déclenche le préchargement tôt, masquant la latence.

Le code sans branchement déplace le délai dans le chemin critique : le processeur attend les données avant la comparaison, sans chevaucher les calculs.

Recherche de valeur : le coût des chargements inconditionnels

Original :

Value result = default_value;
for (size_t i = 0; i < n; ++i) {
    if (keys[i] == target) {
        result = values[i];
    }
}
return result;

Sans branchement :

Value result = default_value;
for (size_t i = 0; i < n; ++i) {
    result = (keys[i] == target) ? values[i] : result;
}
return result;

Dans le code sans branchement, values[i] se charge à chaque itération, gaspillant la bande passante sur l'ensemble du tableau. L'original ne lit que jusqu'à une correspondance.

Recherche binaire : chaînes de dépendance

Avec branchement :

while (low < high) {
    size_t mid = low + (high - low) / 2;
    if (keys[mid] < target)
        low = mid + 1;
    else
        high = mid;
}

Le processeur calcule spéculativement le prochain mid et précharge keys[mid].

Sans branchement :

while (low < high) {
    size_t mid = low + (high - low) / 2;
    size_t step = (high - low) / 2;
    low  = (keys[mid] < target) ? mid + 1 : low;
    high = (keys[mid] < target) ? high    : mid;
}

Les dépendances sur le résultat de la comparaison bloquent la spéculation : le prochain mid attend les écritures de low/high.

• La moitié des prédictions sont fausses, mais le préchargement anticipé chevauche le vidage.
• Sans branchement : plus d'instructions, chargements plus tardifs, délais mémoire explicites.

Points clés à retenir

• La spéculation masque la latence mémoire en déclenchant le préchargement sur les branches prédites.
• Le code sans branchement élimine les mauvaises prédictions mais aggrave les performances avec l'accès L3/DRAM.
• Profiler sur le matériel cible : L1—sans branchement, grands tableaux—avec branchement.
• Les ports de jeux console souffrent souvent de l'ignorance de ces effets.
• Les dépendances dans les chaînes sans branchement bloquent les optimisations OoO.

Avec des données aléatoires en L1, le code sans branchement domine. Avec des motifs ou de grands volumes, le code avec branchement gagne grâce aux chargements spéculatifs.

— Editorial Team