c++ - samantha - iñaki urdangarin

En casos especiales: ¿Es más rápido que%?

Question

Vi la respuesta elegida para esta publicación .

Me sorprendió que (x & 255) == (x % 256) si x es un entero sin signo, me preguntaba si tiene sentido siempre reemplazar % con & en x % n para n = 2^a (a = [1, ...]) yx es un entero positivo.

Dado que este es un caso especial en el que yo, como ser humano, puedo decidir porque sé con qué valores tratará el programa y el compilador no. ¿Puedo obtener un aumento de rendimiento significativo si mi programa usa muchas operaciones de módulo?

Claro, podría compilar y mirar el desmontaje. Pero esto solo respondería mi pregunta para un compilador / arquitectura. Me gustaría saber si esto es, en principio, más rápido.

Answer 1

Hice algunas mediciones con gcc, y si el argumento de a / o % es una constante de tiempo compilada que es una potencia de 2, gcc puede convertirla en la operación de bit correspondiente.

Estos son algunos de mis puntos de referencia para las divisiones ¿Qué tiene un mejor rendimiento: multiplicación o división? y como puede ver, los tiempos de ejecución con divisores que son poderes estáticamente conocidos de dos son notoriamente más bajos que con otros divisores estáticos conocidos.

Entonces, si / y % con argumentos de potencia de dos conocidos de manera estática describen su algoritmo mejor que las operaciones de bits, siéntase libre de preferir / y % . No debe perder ningún rendimiento con un compilador decente.

Answer 2

Si su tipo integral no está firmado, el compilador lo optimizará y el resultado será el mismo. Si está firmado, algo es diferente ...

Este programa:

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;
}

será compilado ( por GCC 6.2 con -O3; Clang 3.9 produce código muy similar ) 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

El ensamblaje resultante de mod_signed es diferente porque

Si ambos operandos a una expresión de multiplicación, división o módulo tienen el mismo signo, el resultado es positivo. De lo contrario, el resultado es negativo. El resultado del signo de una operación de módulo está definido por la implementación.

y AFAICT, la mayor parte de la implementación decidió que el resultado de una expresión de módulo siempre es el mismo que el del primer operando. Vea esta documentación .

Por lo tanto, mod_signed está optimizado para (del comentario de nwellnhof ):

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

Lógicamente, podemos demostrar que i % 256 == i & 255 para todos los enteros sin signo, por lo tanto, podemos confiar en que el compilador haga su trabajo.