Pourquoi ce code s'exécute-t-il plus lentement après avoir réduit les multiplications à des additions portées par la boucle ?

Question

Je suis en train de lire les manuels d'optimisation d'Agner Fog, et je suis tombé sur cet exemple :

double data[LEN];

void compute()
{
    const double A = 1.1, B = 2.2, C = 3.3;

    int i;
    for(i=0; i<LEN; i++) {
        data[i] = A*i*i + B*i + C;
    }
}

Agner indique qu'il existe un moyen d'optimiser ce code - en réalisant que la boucle peut éviter d'utiliser des multiplications coûteuses, et utiliser plutôt les "deltas" qui sont appliqués par itération.

J'utilise une feuille de papier pour confirmer la théorie, d'abord...

...et bien sûr, il a raison - à chaque itération de la boucle, nous pouvons calculer le nouveau résultat sur la base de l'ancien, en ajoutant un "delta". Ce delta commence à la valeur "A+B", et est ensuite incrémenté de "2*A" à chaque étape.

Nous mettons donc à jour le code pour qu'il ressemble à ceci :

void compute()
{
    const double A = 1.1, B = 2.2, C = 3.3;
    const double A2 = A+A;
    double Z = A+B;
    double Y = C;

    int i;
    for(i=0; i<LEN; i++) {
        data[i] = Y;
        Y += Z;
        Z += A2;
    }
}

En termes de complexité opérationnelle, la différence entre ces deux versions de la fonction est en effet frappante. Les multiplications ont la réputation d'être significativement plus lentes dans nos CPUs, comparées aux additions. Et nous avons remplacé 3 multiplications et 2 additions... par seulement 2 additions !

Donc j'y vais et j'ajoute une boucle pour exécuter compute un grand nombre de fois - et ensuite garder le temps minimum qu'il a fallu pour l'exécuter :

unsigned long long ts2ns(const struct timespec *ts)
{
    return ts->tv_sec * 1e9 + ts->tv_nsec;
}

int main(int argc, char *argv[])
{
    unsigned long long mini = 1e9;
    for (int i=0; i<1000; i++) {
        struct timespec t1, t2;
        clock_gettime(CLOCK_MONOTONIC_RAW, &t1);
        compute();
        clock_gettime(CLOCK_MONOTONIC_RAW, &t2);
        unsigned long long diff = ts2ns(&t2) - ts2ns(&t1);
        if (mini > diff) mini = diff;
    }
    printf("[-] Took: %lld ns.\n", mini);
}

Je compile les deux versions, je les exécute... et je vois ceci :

# gcc -O3 -o 1 ./code1.c

# gcc -O3 -o 2 ./code2.c

# ./1
[-] Took: 405858 ns.

# ./2
[-] Took: 791652 ns.

Eh bien, c'est inattendu. Comme nous rapportons le temps d'exécution minimum, nous éliminons le "bruit" causé par diverses parties du système d'exploitation. Nous avons également pris soin de l'exécuter dans une machine qui ne fait absolument rien. Et les résultats sont plus ou moins reproductibles - la ré-exécution des deux binaires montre que le résultat est cohérent :

# for i in {1..10} ; do ./1 ; done
[-] Took: 406886 ns.
[-] Took: 413798 ns.
[-] Took: 405856 ns.
[-] Took: 405848 ns.
[-] Took: 406839 ns.
[-] Took: 405841 ns.
[-] Took: 405853 ns.
[-] Took: 405844 ns.
[-] Took: 405837 ns.
[-] Took: 406854 ns.

# for i in {1..10} ; do ./2 ; done
[-] Took: 791797 ns.
[-] Took: 791643 ns.
[-] Took: 791640 ns.
[-] Took: 791636 ns.
[-] Took: 791631 ns.
[-] Took: 791642 ns.
[-] Took: 791642 ns.
[-] Took: 791640 ns.
[-] Took: 791647 ns.
[-] Took: 791639 ns.

La seule chose à faire ensuite est de voir quel type de code le compilateur a créé pour chacune des deux versions.

objdump -d -S montre que la première version de compute - le code "débile", mais en quelque sorte rapide - a une boucle qui ressemble à ceci :

Qu'en est-il de la deuxième version, optimisée, qui ne fait que deux ajouts ?

Je ne sais pas pour vous, mais en ce qui me concerne, je suis... perplexe. La seconde version a environ 4 fois moins d'instructions, les deux principales étant juste des ajouts basés sur SSE ( addsd ). La première version, non seulement a 4 fois plus d'instructions... elle est aussi pleine (comme prévu) de multiplications ( mulpd ).

J'avoue que je ne m'attendais pas à ce résultat. Non pas parce que je suis un fan d'Agner (je le suis, mais cela n'a rien à voir).

Une idée de ce que j'ai manqué ? Ai-je commis une erreur qui pourrait expliquer la différence de vitesse ? Notez que j'ai fait le test sur un Xeon W5580 et un Xeon E5 1620 - dans les deux cas, la première version (muette) est beaucoup plus rapide que la seconde.

EDIT : Pour faciliter la reproduction des résultats, j'ai ajouté deux gists avec les deux versions du code : Stupide mais en quelque sorte plus rapide y optimisé, mais en quelque sorte plus lent .

P.S. Veuillez ne pas commenter les problèmes de précision de la virgule flottante ; ce n'est pas le but de cette question.

Answer 1

Les multiplications ont la réputation d'être nettement plus lentes dans nos processeurs, par rapport aux additions.

Cela a pu être vrai dans le passé et peut encore l'être pour des unités centrales plus simples et de faible puissance, mais si le concepteur de l'unité centrale est prêt à "jeter des portes sur le problème", la multiplication peut être rendue presque aussi rapide que l'addition.

Les processeurs modernes sont conçus pour traiter plusieurs instructions en même temps, grâce à une combinaison de pipelining et d'unités d'exécution multiples.

Le problème, c'est la dépendance des données. Si une instruction dépend des résultats d'une autre instruction, son exécution ne peut pas commencer avant que l'instruction dont elle dépend soit terminée.

Les processeurs modernes essaient de contourner ce problème grâce à une "exécution hors ordre". Les instructions qui attendent des données peuvent rester en file d'attente pendant que d'autres instructions sont autorisées à s'exécuter.

Mais même avec ces mesures, il arrive que l'unité centrale soit tout simplement à court de nouveaux travaux à programmer.