Pourquoi le compilateur ne peut-il pas (ou ne pas) optimiser une boucle d'addition prévisible dans une multiplication?

Question

C'est une question qui vient à l'esprit lors de la lecture de la brillante réponse par Mysticial à cette question.

Contexte pour les types impliqués:

const unsigned arraySize = 32768;
int data[arraySize];
long long sum = 0;

Dans sa réponse, il explique que le Compilateur Intel (CPI) optimise ce:

for (int i = 0; i < 100000; ++i)
    for (int c = 0; c < arraySize; ++c)
        if (data[c] >= 128)
            sum += data[c];

...en quelque chose d'équivalent à ceci:

for (int c = 0; c < arraySize; ++c)
    if (data[c] >= 128)
        for (int i = 0; i < 100000; ++i)
            sum += data[c];

L'optimiseur est de reconnaître que les deux sont équivalents et est, par conséquent, l'échange de la boucle, le déplacement de la branche à l'extérieur de la boucle interne. Très intelligent!

Mais pourquoi ne pas le faire?

for (int c = 0; c < arraySize; ++c)
    if (data[c] >= 128)
        sum += 100000 * data[c];

Espérons que Mysticial (ou quelqu'un d'autre) peut donner une tout aussi brillant réponse. Je n'ai jamais appris à propos de la optimisations discuté dans cet autre question avant, donc je suis très reconnaissant pour cela.

Answer 1

Le compilateur ne peut pas généralement transformer

for (int c = 0; c < arraySize; ++c)
    if (data[c] >= 128)
        for (int i = 0; i < 100000; ++i)
            sum += data[c];

en

for (int c = 0; c < arraySize; ++c)
    if (data[c] >= 128)
        sum += 100000 * data[c];

parce que cette dernière pourrait conduire à un débordement d'entiers signés, où l'ancienne qui ne fonctionne pas. Même avec des garanties de wrap-around comportement pour le débordement de l'signé en complément à deux entiers, il serait de changer le résultat (si data[c] est 30000, le produit deviendra -1294967296 pour le type 32 bits ints avec une pellicule autour, alors que 100000 fois l'ajout de 30000 à sum serait, si ce n'est pas de débordement, d'accroître sum par 3000000000). Notez que l'en est de même pour les quantités, avec des numéros différents, le débordement d' 100000 * data[c] généralement introduire une réduction modulo 2^32 qui ne doivent pas apparaître dans le résultat final.

Il pouvait se transformer en

for (int c = 0; c < arraySize; ++c)
    if (data[c] >= 128)
        sum += 100000LL * data[c];  // resp. 100000ull

si, si, comme d'habitude, long long est suffisamment plus grand que int.

Pourquoi il ne le fait pas, je ne peux pas dire, je suppose que c'est ce que Mysticial dit, "apparemment, il n'a pas d'exécuter une boucle-effondrement passe après la boucle-échange".

Notez que la boucle de l'échangeur lui-même n'est généralement pas valide (pour les entiers signés), depuis

for (int c = 0; c < arraySize; ++c)
    if (condition(data[c]))
        for (int i = 0; i < 100000; ++i)
            sum += data[c];

peut conduire à débordement où

for (int i = 0; i < 100000; ++i)
    for (int c = 0; c < arraySize; ++c)
        if (condition(data[c]))
            sum += data[c];

ne le soit pas. C'est casher ici, depuis que l'état garantit à tous data[c] qui sont ajoutés ont le même signe, donc si on déborde, tous les deux.

Je ne serais pas trop sûr que le compilateur a pris cela en compte, si (@Mysticial, pourriez-vous essayer avec un état comme la data[c] & 0x80 ou de sorte que peut-être vrai pour les valeurs positives et négatives?). J'ai eu des compilateurs de rendre non valide optimisations (par exemple, il y a quelques années, j'ai eu un CPI (11.0, iirc) utiliser signé sur 32 bits-int-de-double conversion en 1.0/n où n était unsigned int. A été deux fois plus rapide que gcc est de sortie. Mais mal, beaucoup de valeurs ont été plus grand que 2^31, oups.).

Answer 2

Cette réponse ne s'applique pas au cas spécifique lié, mais elle s'applique au titre de la question et peut intéresser les futurs lecteurs:

En raison de la précision finie, l’addition répétée en virgule flottante n’équivaut pas à la multiplication . Considérer:

 float const step = 1e-15;
float const init = 1;
long int const count = 1000000000;

float result1 = init;
for( int i = 0; i < count; ++i ) result1 += step;

float result2 = init;
result2 += step * count;

cout << (result1 - result2);
 

Démo: http://ideone.com/7RhfP

Answer 3

Le compilateur contient divers passages qui optimisent. Habituellement, dans chaque passe, une optimisation des instructions ou une optimisation de boucle sont effectuées. À l'heure actuelle, aucun modèle n'optimise le corps de la boucle en fonction des en-têtes de boucle. C'est difficile à détecter et moins commun.

L'optimisation qui a été faite était un mouvement de code invariant de la boucle. Cela peut être fait en utilisant un ensemble de techniques.

Answer 4

Eh bien, je suppose que certains compilateurs peuvent faire ce genre d'optimisation, en supposant que nous parlons entier arithmétique.

Dans le même temps, certains compilateurs peuvent refuser de le faire parce que le remplacement répétitif plus avec la multiplication peut changer le dépassement de comportement du code. Pour unsigned types intégraux, il ne devrait pas faire une différence, puisque leur débordement comportement est complètement définie par la langue. Mais pour la signature de celles qu'il pourrait (probablement pas le 2 en complément de la plateforme tout de même). Il est vrai que signée de dépassement de fait conduit à un comportement indéfini dans C, ce qui signifie qu'il doit être parfaitement OK pour ignorer que le trop-plein de la sémantique tout à fait, mais pas tous les compilateurs sont assez courageux pour le faire. Il attire souvent beaucoup de critiques de la "C est juste un plus haut niveau de l'assemblée de la langue" de la foule. (Rappelez-vous ce qui s'est passé lors de la GCC introduit optimisations basées sur le strict-aliasing sémantique?)

Historiquement, la GCC a montré lui-même comme un compilateur qui a ce qu'il faut pour prendre de telles mesures drastiques, mais d'autres compilateurs peuvent préférer rester avec la perception de l'utilisateur"," l'intention de comportement, même si elle n'est pas définie par la langue.

Answer 5

Il y a une barrière conceptuelle à ce type d'optimisation. Les auteurs de compilateurs consacrent beaucoup d'efforts à la réduction de la force - par exemple, remplacer les multiplications par des ajouts et des décalages. Ils s'habituent à penser que les multiplications sont mauvaises. Donc, un cas où il faut aller dans le sens inverse est surprenant et paradoxal. Donc, personne ne pense à le mettre en œuvre.