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

Le compilateur ne peut généralement pas transformer

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

dans

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

car ce dernier pourrait conduire à un débordement d'entiers signés là où l'ancien ne l'est pas. Même avec un comportement de -1294967296 pour le débordement des entiers de complément à deux signés, cela changerait le résultat (si data[c] est 30000, le produit deviendrait -1294967296 pour les int 32-bit typiques avec wrap around et 100000 fois Ajouter 30000 à la sum , si cela ne déborde pas, augmente la sum de 3000000000). Notez que la même chose vaut pour des quantités non signées, avec des nombres différents, un dépassement de 100000 * data[c] introduirait généralement un modulo de réduction 2^32 qui ne doit pas apparaître dans le résultat final.

Il pourrait le transformer en

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

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

Pourquoi il ne fait pas cela, je ne peux pas dire, je suppose que c'est ce que Mysticial a dit , "apparemment, il ne fait pas passer une boucle en boucle après l'échange de boucle".

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

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

peut conduire à un 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 serait pas. C'est kasher ici, puisque la condition garantit que toutes les data[c] qui sont ajoutées ont le même signe, donc si on déborde, les deux le font.

Je ne suis pas sûr que le compilateur en ait tenu compte (@Mysticial, pourriez-vous essayer avec une condition comme data[c] & 0x80 ou plus, ce qui peut être vrai pour les valeurs positives et négatives?). Les compilateurs ont fait des optimisations non valides (par exemple, il y a quelques années, j'avais un ICC (11.0, iirc) utilisant la conversion signée en 32 bits en 1.0/n où n était un unsigned int . à peu près deux fois plus vite que la sortie de gcc Mais mal, beaucoup de valeurs étaient supérieures à 2^31 , oups.).

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

Le compilateur contient différentes passes qui font l’optimisation. Habituellement, à chaque passage, une optimisation des instructions ou des optimisations de boucle est effectuée. À l’heure actuelle, il n’existe pas de modèle permettant d’optimiser le corps de la boucle en fonction des en-têtes de boucle. C’est difficile à détecter et moins fréquent.

L’optimisation effectuée était un mouvement de code invariant en boucle. Cela peut être fait en utilisant un ensemble de techniques.

Il existe une barrière conceptuelle à ce type d’optimisation. Les auteurs de compilateurs consacrent beaucoup d’efforts à la réduction de la force , par exemple en remplaçant les multiplications par des ajouts et des décalages. Ils s’habituent à penser que les multiplications sont mauvaises. Ainsi, un cas où l’on devrait aller dans l’autre sens est surprenant et contre-intuitif. Donc, personne ne pense à le mettre en œuvre.

Eh bien, je suppose que certains compilateurs pourraient effectuer ce type d’optimisation, en supposant que nous parlions d’arithmétique en nombres entiers.

Dans le même temps, certains compilateurs peuvent refuser de le faire, car le remplacement d’une addition répétitive par une multiplication peut modifier le comportement de débordement du code. Pour les types intégraux unsigned cela ne devrait pas faire de différence, car leur comportement de débordement est entièrement spécifié par le langage. Mais pour ceux qui sont signés, cela pourrait être le cas (probablement pas sur la plate-forme complémentaire de 2). Il est vrai que le débordement signé conduit en fait à un comportement indéfini dans C, ce qui signifie qu’il convient parfaitement d’ignorer cette sémantique de débordement, mais tous les compilateurs ne sont pas assez courageux pour le faire. Il suscite souvent beaucoup de critiques de la part du groupe “C est juste un langage d’assemblage de niveau supérieur”. (Rappelez-vous ce qui s’est passé lorsque GCC a introduit des optimisations basées sur la sémantique de l’aliasing ssortingct?)

Historiquement, GCC s’est montré comme un compilateur qui a ce qu’il faut pour prendre des mesures aussi drastiques, mais d’autres compilateurs peuvent préférer s’en tenir au comportement «conçu par l’utilisateur», même s’il n’est pas défini par le langage.

Les personnes qui développent et gèrent des compilateurs ont un temps et une énergie limités à consacrer à leur travail. Ils souhaitent donc généralement se concentrer sur ce qui intéresse le plus leurs utilisateurs: transformer du code bien écrit en code rapide. Ils ne veulent pas passer leur temps à essayer de trouver des moyens de transformer un code stupide en code rapide. Dans un langage de haut niveau, il peut exister un code “idiot” qui exprime une idée importante, ce qui en fait un outil précieux pour les développeurs. Par exemple, la déforestation de courte durée et la fusion de stream permettent aux programmes Haskell produit des structures de données à comstackr dans des boucles serrées qui n’allouent pas de mémoire. Mais ce type d’incitation ne s’applique tout simplement pas à transformer les ajouts en boucle en multiplication. Si vous voulez que ce soit rapide, écrivez-le simplement avec la multiplication.