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

C'est une question qui m'est venue à l'esprit en lisant la brillante réponse de Mysticial à la question: pourquoi est-il plus rapide de traiter un tableau trié qu'un tableau non trié ?

Contexte des types concernés:

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

Dans sa réponse, il explique que le compilateur Intel (ICC) optimise ceci:

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 reconnaît que celles-ci sont équivalentes et échange donc les boucles , déplaçant la branche hors de la boucle interne. Très intelligent!

Mais pourquoi ne fait-il pas cela?

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

Espérons que Mysticial (ou n'importe qui d'autre) puisse donner une réponse tout aussi brillante. Je n'ai jamais entendu parler des optimisations évoquées dans cette autre question auparavant, donc j'en suis vraiment reconnaissant.

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 entraîner un débordement d'entiers signés alors que le premier ne le fait pas. Même avec un comportement de bouclage garanti pour le dépassement des entiers du complément à deux signés, cela changerait le résultat (si data[c]c'est 30000, le produit deviendrait -1294967296pour les 32 bits typiques intavec un bouclage, tandis que 100000 fois en ajoutant 30000 au sumserait, si cela ne déborde pas, augmente sumde 3000000000). Notez que la même chose vaut pour les quantités non signées, avec des nombres différents, un dépassement de 100000 * data[c]capacité introduirait généralement un modulo de réduction 2^32qui ne doit pas apparaître dans le résultat final.

Cela 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, long longest suffisamment plus grand que int.

Pourquoi ça ne fait pas ça, je ne peux pas dire, je suppose que c'est ce que Mysticial a dit , "apparemment, il n'exécute pas de passe de boucle après é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];

pas. C'est casher ici, car la condition garantit data[c]que tout ce qui est ajouté a le même signe, donc si l'un déborde, les deux le font.

Je ne serais pas trop sûr que le compilateur ait pris cela en compte (@Mysticial, pourriez-vous essayer avec une condition comme data[c] & 0x80ou alors qui peut être vraie pour les valeurs positives et négatives?). J'ai demandé à des compilateurs de faire des optimisations non valides (par exemple, il y a quelques années, j'avais une conversion ICC (11.0, iirc) avec une conversion signée-32-bit-int-to-double dans 1.0/noù nétait un unsigned int. Était environ deux fois plus rapide que gcc Mais faux, beaucoup de valeurs étaient plus grandes que 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, une addition à virgule flottante répétée n'est pas équivalente à une 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

Le compilateur contient plusieurs passes qui effectuent l'optimisation. Habituellement, à chaque passe, une optimisation des instructions ou des optimisations de boucle sont effectuées. À l'heure actuelle, il n'y a pas de modèle qui effectue une optimisation du corps de la boucle basée sur les en-têtes de boucle. Ceci est difficile à détecter et moins courant.

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

Eh bien, je suppose que certains compilateurs pourraient faire ce type d'optimisation, en supposant que nous parlons d'arithmétique entière.

Dans le même temps, certains compilateurs peuvent refuser de le faire car le remplacement de l'addition répétitive par la multiplication peut modifier le comportement de débordement du code. Pour les types entiers non signés, 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 signés, cela pourrait (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 en C, ce qui signifie qu'il devrait être parfaitement OK d'ignorer complètement 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 "C est juste un langage d'assemblage de plus haut niveau". (Vous vous souvenez de ce qui s'est passé lorsque GCC a introduit des optimisations basées sur une sémantique d'aliasing strict?)

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

C'est le cas maintenant - du moins, clang fait :

long long add_100k_signed(int *data, int arraySize)
{
    long long sum = 0;

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

compile avec -O1 pour

add_100k_signed:                        # @add_100k_signed
        test    esi, esi
        jle     .LBB0_1
        mov     r9d, esi
        xor     r8d, r8d
        xor     esi, esi
        xor     eax, eax
.LBB0_4:                                # =>This Inner Loop Header: Depth=1
        movsxd  rdx, dword ptr [rdi + 4*rsi]
        imul    rcx, rdx, 100000
        cmp     rdx, 127
        cmovle  rcx, r8
        add     rax, rcx
        add     rsi, 1
        cmp     r9, rsi
        jne     .LBB0_4
        ret
.LBB0_1:
        xor     eax, eax
        ret

Le débordement d'entier n'a rien à voir avec cela; s'il y a un débordement d'entier qui provoque un comportement indéfini, cela peut se produire dans les deux cas. Voici le même type de fonction utilisant intau lieu delong :

int add_100k_signed(int *data, int arraySize)
{
    int sum = 0;

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

compile avec -O1 pour

add_100k_signed:                        # @add_100k_signed
        test    esi, esi
        jle     .LBB0_1
        mov     r9d, esi
        xor     r8d, r8d
        xor     esi, esi
        xor     eax, eax
.LBB0_4:                                # =>This Inner Loop Header: Depth=1
        mov     edx, dword ptr [rdi + 4*rsi]
        imul    ecx, edx, 100000
        cmp     edx, 127
        cmovle  ecx, r8d
        add     eax, ecx
        add     rsi, 1
        cmp     r9, rsi
        jne     .LBB0_4
        ret
.LBB0_1:
        xor     eax, eax
        ret

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, en remplaçant les multiplications par des ajouts et des décalages. Ils s'habituent à penser que les multiplications sont mauvaises. Donc, un cas où l'on devrait aller dans l'autre sens est surprenant et contre-intuitif. Personne ne pense donc à le mettre en œuvre.

Les personnes qui développent et maintiennent des compilateurs ont un temps et une énergie limités à consacrer à leur travail, ils veulent donc généralement se concentrer sur ce qui intéresse le plus leurs utilisateurs: transformer un code bien écrit en code rapide. Ils ne veulent pas passer leur temps à essayer de trouver des moyens de transformer un code idiot en code rapide - c'est à cela que sert la révision du code. Dans un langage de haut niveau, il peut y avoir du code «idiot» qui exprime une idée importante, ce qui vaut le temps des développeurs pour faire cela rapidement - par exemple, la déforestation raccourcie et la fusion de flux permettent aux programmes Haskell structurés autour de certains types de paresseux produit des structures de données à compiler en boucles serrées qui n'allouent pas de mémoire. Mais ce genre d'incitation ne s'applique tout simplement pas à transformer l'addition en boucle en multiplication. Si vous voulez que ce soit rapide,