una - raiz cuadrada en c++
¿El compilador de ac/c++ optimiza las divisiones constantes por el valor de la potencia de dos en turnos? (4)
Incluso con g++ -O0 (sí, -O0 !), Esto sucede. Su función se compila a:
_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
Tenga en cuenta que shrq $6 , que es un cambio a la derecha en 6 lugares.
Con -O1 , se -O1 la basura innecesaria:
_Z3divm:
.LFB1023:
movq %rdi, %rax
shrq $6, %rax
ret
Resultados en g ++ 4.3.3, x64.
La pregunta lo dice todo. ¿Alguien sabe si lo siguiente ...
size_t div(size_t value) {
const size_t x = 64;
return value / x;
}
... está optimizado en?
size_t div(size_t value) {
return value >> 6;
}
¿Los compiladores hacen esto? (Mi interés radica en GCC). ¿Hay situaciones donde lo hace y otras donde no?
Realmente me gustaría saber, porque cada vez que escribo una división que podría optimizarse así, gasto algo de energía mental preguntándome si no se desperdicia nada precioso haciendo una división en la que un cambio sería suficiente.
La mayoría de los compiladores irán más allá de reducir la división por potencias de 2 en turnos: a menudo convertirán la división de enteros por una constante en una serie de instrucciones de multiplicación, desplazamiento e incorporación para obtener el resultado en lugar de usar la división integrada de la CPU instrucción (si es que hay una)
Por ejemplo, MSVC convierte la división por 71 a lo siguiente:
// 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
Entonces, obtienes una división por 71 con un multiplicador, un par de turnos y un par de puntos.
Para obtener más detalles sobre lo que está sucediendo, consulte el libro "Hacker''s Delight" de Henry Warren o la página web complementaria:
Hay un capítulo agregado en línea que proporciona información adicional acerca de la división por constantes usando la multiplicación / desplazamiento / adición con números mágicos, y una página con un pequeño programa de JavaScript que calculará los números mágicos que necesita.
Merece la pena leer el sitio complementario del libro (como es el libro), especialmente si le interesan las micro optimizaciones a nivel de bit.
Otro artículo que descubrí hace un momento que analiza esta optimización: http://blogs.msdn.com/devdev/archive/2005/12/12/502980.aspx
Sí, los compiladores generan el código más óptimo para tales cálculos simplistas. Sin embargo, no entiendo por qué insiste específicamente en "turnos". El código óptimo para una plataforma dada podría ser algo diferente de un "cambio".
En general, la idea antigua y golpeada hasta la muerte de que un "cambio" es de algún modo la forma más óptima de implementar multiplicaciones y divisiones de potencia de dos tiene muy poca relevancia práctica en las plataformas modernas. Es una buena forma de ilustrar el concepto de "optimización" para los novatos, pero no más que eso.
Su ejemplo original no es realmente representativo, porque utiliza un tipo sin signo, lo que simplifica enormemente la implementación de la operación de división. El requisito de "redondear hacia cero" de los lenguajes C y C ++ hace que sea imposible hacer una división con un simple desplazamiento si el operando está firmado.
Solo cuando puede determinar que el argumento es positivo. Ese es el caso para su ejemplo, pero desde que C99 especificó la semántica de redondeo a cero para la división de enteros, se ha vuelto más difícil optimizar la división por potencias de dos en turnos, porque dan resultados diferentes para los argumentos negativos.
En reacción al comentario de Michael a continuación, aquí hay una forma en que la división r=x/p; de x por una potencia conocida de dos p puede ser traducida por el compilador:
if (x<0)
x += p-1;
r = x >> (log2 p);
Dado que OP estaba preguntando si debería pensar en estas cosas, una respuesta posible sería "solo si conoce mejor el signo del dividendo que el compilador o sabe que no importa si el resultado se redondea hacia 0 o -∞".