Un compilateur c/c++ optimise-t-il les divisions constantes par puissance de deux en décalages ?

Question

La question dit tout. Est-ce que quelqu'un sait si les...

size_t div(size_t value) {
    const size_t x = 64;
    return value / x;
}

...est optimisé ?

size_t div(size_t value) {
    return value >> 6;
}

Les compilateurs font-ils cela ? (Mon intérêt se porte sur GCC). Y a-t-il des situations où il le fait et d'autres où il ne le fait pas ?

J'aimerais vraiment le savoir, car chaque fois que j'écris une division qui pourrait être optimisée de la sorte, je dépense de l'énergie mentale à me demander si de précieuses secondes ne sont pas gaspillées à faire une division là où un décalage suffirait.

Answer 1

Même avec g++ -O0 (oui, -O0 !), voici ce qui se passe. Votre fonction se compile en :

_Z3divm:
.LFB952:
        pushq   %rbp
.LCFI0:
        movq    %rsp, %rbp
.LCFI1:
        movq    %rdi, -24(%rbp)
        movq    $64, -8(%rbp)
        movq    -24(%rbp), %rax
        shrq    $6, %rax
        leave
        ret

Notez le shrq $6 ce qui représente un décalage vers la droite de 6 places.

Avec -O1 les déchets inutiles sont supprimés :

_Z3divm:
.LFB1023:
        movq    %rdi, %rax
        shrq    $6, %rax
        ret

Résultats sur g++ 4.3.3, x64.

Answer 2

La plupart des compilateurs vont même au-delà de la réduction de la division par des puissances de 2 en décalages - ils convertissent souvent la division d'un nombre entier par une constante en une série d'instructions de multiplication, de décalage et d'addition pour obtenir le résultat au lieu d'utiliser l'instruction de division intégrée du CPU (si tant est qu'il y en ait une).

Par exemple, MSVC convertit la division par 71 en ce qui suit :

// volatile int y = x / 71;

8b 0c 24        mov ecx, DWORD PTR _x$[esp+8] ; load x into ecx

b8 49 b4 c2 e6  mov eax, -423447479 ; magic happens starting here...
f7 e9           imul ecx            ; edx:eax = x * 0xe6c2b449

03 d1           add edx, ecx        ; edx = x + edx

c1 fa 06        sar edx, 6          ; edx >>= 6 (with sign fill)

8b c2           mov eax, edx        ; eax = edx
c1 e8 1f        shr eax, 31         ; eax >>= 31 (no sign fill)
03 c2           add eax, edx        ; eax += edx

89 04 24        mov DWORD PTR _y$[esp+8], eax

Vous obtenez donc un diviseur par 71 avec un multiplicateur, quelques décalages et quelques additions.

Pour plus de détails sur ce qui se passe, consultez le livre "Hacker's Delight" d'Henry Warren ou la page web correspondante :

• http://www.hackersdelight.org/

Il y a un chapitre ajouté en ligne qui fournit des informations sur l'addition à propos de la division par des constantes en utilisant la multiplication/shift/add avec des nombres magiques, et un avec un petit programme JavaScript qui calculera les chiffres magiques dont vous avez besoin.

Le site d'accompagnement du livre vaut la peine d'être lu (tout comme le livre), en particulier si vous êtes intéressé par les micro-optimisations au niveau du bit.

Un autre article que je viens de découvrir traite de cette optimisation : http://blogs.msdn.com/devdev/archive/2005/12/12/502980.aspx

Answer 3

Seulement lorsqu'il peut déterminer que l'argument est positif. C'est le cas pour votre exemple, mais depuis que C99 a spécifié la sémantique round-towards-zero pour la division d'entiers, il est devenu plus difficile d'optimiser la division par des puissances de deux en décalages, car ils donnent des résultats différents pour les arguments négatifs.

En réaction au commentaire de Michael ci-dessous, voici une façon de diviser le pays. r=x/p; de x par une puissance connue de deux p peut en effet être traduit par le compilateur :

if (x<0)
  x += p-1;
r = x >> (log2 p);

Puisque le PO demandait s'il devait penser à ces choses, une réponse possible serait "seulement si vous connaissez le signe du dividende mieux que le compilateur ou si vous savez que cela n'a pas d'importance si le résultat est arrondi vers 0 ou -∞".

Answer 4

Oui, les compilateurs génèrent le code le plus optimal pour des calculs aussi simplistes. Cependant, la raison pour laquelle vous insistez spécifiquement sur les "shifts" n'est pas claire pour moi. Le code optimal pour une plateforme donnée pourrait facilement s'avérer être quelque chose de différent d'un "shift".

En général, la vieille idée, battue en brèche, selon laquelle un "shift" est en quelque sorte la manière la plus optimale d'implémenter des multiplications et divisions de puissance deux, n'a que très peu de pertinence pratique sur les plateformes modernes. C'est un bon moyen d'illustrer le concept d'"optimisation" aux débutants, mais pas plus que cela.