Dans des cas particuliers : Est-ce que & est plus rapide que % ?

Question

J'ai vu l'élu réponse à ce poste .

J'ai été surpris que (x & 255) == (x % 256) si x est un entier non signé, je me suis demandé s'il était judicieux de toujours remplacer % avec & sur x % n pour n = 2^a (a = [1, ...]) et x étant un nombre entier positif.

Il s'agit d'un cas particulier dans lequel je peux décider en tant qu'humain, car je sais avec quelles valeurs le programme va traiter et le compilateur ne le sait pas. Puis-je obtenir un gain de performance significatif si mon programme utilise beaucoup d'opérations modulo ?

Bien sûr, je pourrais juste compiler et regarder le désassemblage. Mais cela ne répondrait à ma question que pour un seul compilateur/architecture. J'aimerais savoir si cela est en principe plus rapide.

Answer 1

Si votre type intégral est non signé, le compilateur l'optimisera, et le résultat sera le même. S'il est signé, quelque chose est différent...

Ce programme :

int mod_signed(int i) {
  return i % 256;
}
int and_signed(int i) {
  return i & 255;
}
unsigned mod_unsigned(unsigned int i) {
  return i % 256;
}
unsigned and_unsigned(unsigned int i) {
  return i & 255;
}

sera compilé ( par GCC 6.2 avec -O3 ; Clang 3.9 produit un code très similaire ) en :

mod_signed(int):
        mov     edx, edi
        sar     edx, 31
        shr     edx, 24
        lea     eax, [rdi+rdx]
        movzx   eax, al
        sub     eax, edx
        ret
and_signed(int):
        movzx   eax, dil
        ret
mod_unsigned(unsigned int):
        movzx   eax, dil
        ret
and_unsigned(unsigned int):
        movzx   eax, dil
        ret

L'assemblage de résultats de mod_signed est différent parce que

Si les deux opérandes d'une expression de multiplication, de division ou de modulus ont le même signe, le résultat est positif. Sinon, le résultat est négatif. Le signe du résultat d'une opération modulo est défini par l'implémentation.

et AFAICT, la plupart des implémentations ont décidé que le résultat d'une expression modulo est toujours le même que le signe du premier opérande. Voir cette documentation .

D'où, mod_signed est optimisé à (de nwellnhof ) :

int d = i < 0 ? 255 : 0;
return ((i + d) & 255) - d;

---

Logiquement, on peut prouver que i % 256 == i & 255 pour tous les entiers non signés, donc, nous pouvons faire confiance au compilateur pour faire son travail.

Answer 2

J'ai fait quelques mesures avec gcc, et si l'argument d'un / ou % est une constante de temps compilée qui est une puissance de 2, gcc peut la transformer en l'opération binaire correspondante.

Voici quelques-uns de mes repères pour les divisions Qu'est-ce qui est le plus performant : la multiplication ou la division ? et comme vous pouvez le constater, les temps d'exécution avec des diviseurs qui sont des puissances de deux statiquement connues sont sensiblement plus faibles qu'avec d'autres diviseurs statiquement connus.

Donc si / et % avec des arguments de puissance-deux statiquement connus décrivent mieux votre algorithme que les bit ops, n'hésitez pas à préférer / et % . Vous ne devriez pas perdre en performance avec un compilateur décent.