Pourquoi y a-t-il un impact important sur les performances lors du bouclage sur un tableau avec 240 éléments ou plus?

230

Lors de l'exécution d'une boucle de somme sur un tableau dans Rust, j'ai remarqué une énorme baisse de performances lorsque CAPACITY> = 240.CAPACITY = 239 est environ 80 fois plus rapide.

Existe-t-il une optimisation de compilation spéciale que Rust fait pour les tableaux "courts"?

Compilé avec rustc -C opt-level=3.

use std::time::Instant;

const CAPACITY: usize = 240;
const IN_LOOPS: usize = 500000;

fn main() {
    let mut arr = [0; CAPACITY];
    for i in 0..CAPACITY {
        arr[i] = i;
    }
    let mut sum = 0;
    let now = Instant::now();
    for _ in 0..IN_LOOPS {
        let mut s = 0;
        for i in 0..arr.len() {
            s += arr[i];
        }
        sum += s;
    }
    println!("sum:{} time:{:?}", sum, now.elapsed());
}
Guy Korland
la source
4
Peut-être qu'avec 240, vous débordez d'une ligne de cache CPU? Si tel est le cas, vos résultats seraient très spécifiques au processeur.
rodrigo du
11
Reproduit ici . Maintenant, je suppose que cela a quelque chose à voir avec le déroulement de la boucle.
rodrigo

Réponses:

355

Résumé : en dessous de 240, LLVM déroule complètement la boucle intérieure et cela lui permet de remarquer qu'il peut optimiser la boucle de répétition, cassant votre référence.



Vous avez trouvé un seuil magique au-dessus duquel LLVM arrête d'effectuer certaines optimisations . Le seuil est de 8 octets * 240 = 1920 octets (votre tableau est un tableau de usizes, donc la longueur est multipliée par 8 octets, en supposant un processeur x86-64). Dans cette référence, une optimisation spécifique - effectuée uniquement pour la longueur 239 - est responsable de l'énorme différence de vitesse. Mais commençons lentement:

(Tout le code de cette réponse est compilé avec -C opt-level=3)

pub fn foo() -> usize {
    let arr = [0; 240];
    let mut s = 0;
    for i in 0..arr.len() {
        s += arr[i];
    }
    s
}

Ce code simple produira à peu près l'assemblage auquel on s'attendrait: une boucle additionnant des éléments. Cependant, si vous passez 240à 239, l'assemblage émis diffère beaucoup. Voyez-le sur Godbolt Compiler Explorer . Voici une petite partie de l'assemblage:

movdqa  xmm1, xmmword ptr [rsp + 32]
movdqa  xmm0, xmmword ptr [rsp + 48]
paddq   xmm1, xmmword ptr [rsp]
paddq   xmm0, xmmword ptr [rsp + 16]
paddq   xmm1, xmmword ptr [rsp + 64]
; more stuff omitted here ...
paddq   xmm0, xmmword ptr [rsp + 1840]
paddq   xmm1, xmmword ptr [rsp + 1856]
paddq   xmm0, xmmword ptr [rsp + 1872]
paddq   xmm0, xmm1
pshufd  xmm1, xmm0, 78
paddq   xmm1, xmm0

C'est ce qu'on appelle le déroulement de boucle : LLVM colle le corps de la boucle beaucoup de temps pour éviter d'avoir à exécuter toutes ces "instructions de gestion de boucle", c'est-à-dire incrémenter la variable de boucle, vérifier si la boucle est terminée et passer au début de la boucle .

Au cas où vous vous poseriez la question: les paddqinstructions similaires sont des instructions SIMD qui permettent de résumer plusieurs valeurs en parallèle. De plus, deux registres SIMD de 16 octets ( xmm0et xmm1) sont utilisés en parallèle afin que le parallélisme au niveau des instructions du CPU puisse essentiellement exécuter deux de ces instructions en même temps. Après tout, ils sont indépendants les uns des autres. Au final, les deux registres sont additionnés puis additionnés horizontalement au résultat scalaire.

Les processeurs x86 grand public modernes (pas Atom de faible puissance) peuvent vraiment faire 2 charges vectorielles par horloge lorsqu'ils atteignent le cache L1d, et le paddqdébit est également d'au moins 2 par horloge, avec une latence de 1 cycle sur la plupart des CPU. Voir https://agner.org/optimize/ et également ce Q&A sur plusieurs accumulateurs pour masquer la latence (de FP FMA pour un produit scalaire) et le goulot d'étranglement sur le débit à la place.

LLVM petites boucles ne se déroule un peu quand il est pas tout à fait dérouler, et utilise encore plusieurs accumulateurs. Donc, généralement, la bande passante frontale et les goulots d'étranglement de latence back-end ne sont pas un problème énorme pour les boucles générées par LLVM même sans déroulement complet.


Mais le déroulement de boucle n'est pas responsable d'une différence de performance de facteur 80! Du moins pas boucler le déroulement seul. Jetons un coup d'œil au code de référence réel, qui place la boucle dans une autre:

const CAPACITY: usize = 239;
const IN_LOOPS: usize = 500000;

pub fn foo() -> usize {
    let mut arr = [0; CAPACITY];
    for i in 0..CAPACITY {
        arr[i] = i;
    }

    let mut sum = 0;
    for _ in 0..IN_LOOPS {
        let mut s = 0;
        for i in 0..arr.len() {
            s += arr[i];
        }
        sum += s;
    }

    sum
}

( Sur Godbolt Compiler Explorer )

L'assemblage pour CAPACITY = 240semble normal: deux boucles imbriquées. (Au début de la fonction, il y a pas mal de code juste pour l'initialisation, que nous ignorerons.) Pour 239, cependant, cela semble très différent! On voit que la boucle d'initialisation et la boucle interne se sont déroulées: jusqu'ici si attendues.

La différence importante est que pour 239, LLVM a pu comprendre que le résultat de la boucle intérieure ne dépend pas de la boucle extérieure! En conséquence, LLVM émet du code qui, en gros, n'exécute d'abord que la boucle interne (calcul de la somme), puis simule la boucle externe en additionnant plusieurs sumfois!

D'abord, nous voyons presque le même assemblage que ci-dessus (l'assemblage représentant la boucle intérieure). Ensuite, nous voyons cela (j'ai commenté pour expliquer l'assemblage; les commentaires avec *sont particulièrement importants):

        ; at the start of the function, `rbx` was set to 0

        movq    rax, xmm1     ; result of SIMD summing up stored in `rax`
        add     rax, 711      ; add up missing terms from loop unrolling
        mov     ecx, 500000   ; * init loop variable outer loop
.LBB0_1:
        add     rbx, rax      ; * rbx += rax
        add     rcx, -1       ; * decrement loop variable
        jne     .LBB0_1       ; * if loop variable != 0 jump to LBB0_1
        mov     rax, rbx      ; move rbx (the sum) back to rax
        ; two unimportant instructions omitted
        ret                   ; the return value is stored in `rax`

Comme vous pouvez le voir ici, le résultat de la boucle interne est pris, additionné aussi souvent que la boucle externe aurait été exécutée puis retournée. LLVM ne peut effectuer cette optimisation que parce qu'il a compris que la boucle interne est indépendante de la boucle externe.

Cela signifie que l'exécution passe de CAPACITY * IN_LOOPSàCAPACITY + IN_LOOPS . Et cela est responsable de l'énorme différence de performances.


Une note supplémentaire: pouvez-vous faire quelque chose à ce sujet? Pas vraiment. LLVM doit avoir de tels seuils magiques car sans eux, les optimisations LLVM pourraient prendre une éternité pour terminer sur certains codes. Mais nous pouvons également convenir que ce code était hautement artificiel. En pratique, je doute qu'une telle différence se produise. La différence due au déroulement complet de la boucle n'est généralement même pas le facteur 2 dans ces cas. Vous n'avez donc pas à vous soucier des cas d'utilisation réels.

Une dernière remarque sur le code Rust idiomatique: arr.iter().sum()est une meilleure façon de résumer tous les éléments d'un tableau. Et changer cela dans le deuxième exemple ne conduit pas à des différences notables dans l'assemblage émis. Vous devez utiliser des versions courtes et idiomatiques, sauf si vous avez mesuré que cela nuit aux performances.

Lukas Kalbertodt
la source
2
@ lukas-kalbertodt merci pour la bonne réponse! maintenant, je comprends aussi pourquoi le code original mis à jour sumdirectement sur un local sne fonctionnait pas beaucoup plus lentement. for i in 0..arr.len() { sum += arr[i]; }
Guy Korland du
4
@LukasKalbertodt Quelque chose d'autre se passe dans LLVM en activant AVX2 ne devrait pas faire une grande différence. Repris à la rouille aussi
Mgetz
4
@Mgetz Intéressant! Mais cela ne me semble pas trop fou de faire dépendre ce seuil des instructions SIMD disponibles, car cela détermine finalement le nombre d'instructions dans une boucle complètement déroulée. Mais malheureusement, je ne peux pas dire avec certitude. Ce serait bien d'avoir un développeur LLVM répondant à cela.
Lukas Kalbertodt du
7
Pourquoi le compilateur ou le LLVM ne se rendent-ils pas compte que le calcul complet peut être effectué au moment de la compilation? Je m'attendais à ce que le résultat de la boucle soit codé en dur. Ou est-ce utile d' Instantempêcher cela?
Uncreative Name
4
@JosephGarvin: Je suppose que c'est parce que le déroulement complet permet à la dernière optimisation de le voir. Rappelez-vous que l'optimisation des compilateurs se soucie toujours de compiler rapidement, ainsi que de faire un asm efficace, donc ils doivent limiter la complexité la plus défavorable de toute analyse qu'ils font, donc cela ne prend pas des heures / jours pour compiler du code source désagréable avec des boucles compliquées . Mais oui, il s'agit évidemment d'une optimisation manquée pour une taille> = 240. Je me demande si l'optimisation des boucles éloignées à l'intérieur des boucles n'est pas intentionnelle pour éviter de casser des repères simples? Probablement pas, mais peut-être.
Peter Cordes
30

En plus de la réponse de Lukas, si vous souhaitez utiliser un itérateur, essayez ceci:

const CAPACITY: usize = 240;
const IN_LOOPS: usize = 500000;

pub fn bar() -> usize {
    (0..CAPACITY).sum::<usize>() * IN_LOOPS
}

Merci @Chris Morgan pour la suggestion sur le modèle de plage.

L' assemblage optimisé est assez bon:

example::bar:
        movabs  rax, 14340000000
        ret
mja
la source
3
Ou mieux encore, (0..CAPACITY).sum::<usize>() * IN_LOOPSce qui donne le même résultat.
Chris Morgan
11
Je voudrais en fait expliquer que l'assemblage ne fait pas réellement le calcul, mais LLVM a précalculé la réponse dans ce cas.
Josep
Je suis un peu surpris de rustcmanquer l'occasion de faire cette réduction de force. Dans ce contexte spécifique, cependant, cela semble être une boucle de synchronisation, et vous voulez délibérément qu'elle ne soit pas optimisée. Le tout est de répéter le calcul ce nombre de fois à partir de zéro et de le diviser par le nombre de répétitions. En C, l'idiome (non officiel) pour cela est de déclarer le compteur de boucle comme volatile, par exemple le compteur BogoMIPS dans le noyau Linux. Existe-t-il un moyen d'y parvenir à Rust? Il y en a peut-être, mais je ne le sais pas. Appeler un externe fnpeut aider.
Davislor
1
@Davislor: volatileforce cette mémoire à être synchronisée. Son application au compteur de boucle force uniquement le rechargement / stockage réel de la valeur du compteur de boucle. Cela n'affecte pas directement le corps de la boucle. C'est pourquoi une meilleure façon de l'utiliser est normalement d'attribuer le résultat important réel à volatile int sinkquelque chose après la boucle (s'il y a une dépendance portée par la boucle) ou à chaque itération, pour permettre au compilateur d'optimiser le compteur de boucle comme il le souhaite mais le forcer pour matérialiser le résultat souhaité dans un registre afin qu'il puisse le stocker.
Peter Cordes
1
@Davislor: Je pense que Rust a une syntaxe asm en ligne quelque chose comme GNU C. Vous pouvez utiliser asm en ligne pour forcer le compilateur à matérialiser une valeur dans un registre sans le forcer à le stocker. L'utiliser sur le résultat de chaque itération de boucle peut l'empêcher de s'optimiser. (Mais aussi de la vectorisation automatique si vous ne faites pas attention). Par exemple, "Escape" et "Clobber" équivalent dans MSVC explique 2 macros (tout en demandant comment les porter sur MSVC ce qui n'est pas vraiment possible) et des liens vers le discours de Chandler Carruth où il montre leur utilisation.
Peter Cordes du