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

J’ai vu la réponse choisie pour ce post .

J’ai été surpris que (x & 255) == (x % 256) si x est un entier non signé, je me demandais s’il était logique de toujours remplacer % par & dans x % n pour n = 2^a (a = [1, ...]) et x étant un entier positif.

Comme il s’agit d’un cas particulier dans lequel, en tant qu’humain, je peux décider parce que je sais avec quelles valeurs le programme traitera et que le compilateur ne le fera pas. Puis-je obtenir une amélioration significative des performances si mon programme utilise beaucoup d’opérations modulo?

Bien sûr, je pourrais juste comstackr et regarder le déassembly. Mais cela ne ferait que répondre à ma question pour un compilateur / architecture. Je voudrais savoir si cela est en principe plus rapide.

Si votre type intégral n’est pas signé, le compilateur l’optimisera et le résultat sera le même. Si c’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 ) dans:

 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 

Le résultat assemblage de mod_signed est différent car

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

et AFAICT, la majeure partie de l’implémentation a décidé que le résultat d’une expression de module est toujours le même que le signe du premier opérande. Voir cette documentation .

Par conséquent, mod_signed est optimisé pour (d’ après le commentaire de nwellnhof ):

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

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

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

Voici quelques points de repère pour les divisions. Quelles sont les meilleures performances: multiplication ou division? et comme vous pouvez le voir, les temps de fonctionnement avec des diviseurs qui sont des puissances statiquement connues de deux sont notablement inférieurs à ceux d’autres diviseurs connus statiquement.

Donc, si / et % avec des arguments de puissance de deux statiquement connus décrivent votre algorithme mieux que les opérations de bits, n’hésitez pas à préférer / et % . Vous ne devriez perdre aucune performance avec un compilateur décent.