29
¿El compilador C++ optimiza esta operación?¿Los compiladores modernos optimizan la operación x * 2 a x << 1?
Me encantaría creer que sí.
A
Respuesta
28
En realidad VS2008 optimiza esto a x + x:
01391000 push ecx
int x = 0;
scanf("%d", &x);
01391001 lea eax,[esp]
01391004 push eax
01391005 push offset string "%d" (13920F4h)
0139100A mov dword ptr [esp+8],0
01391012 call dword ptr [__imp__scanf (13920A4h)]
int y = x * 2;
01391018 mov ecx,dword ptr [esp+8]
0139101C lea edx,[ecx+ecx]
En un x 64 construirlo es aún más explícito y usos:
int y = x * 2;
000000013FB9101E mov edx,dword ptr [x]
printf("%d", y);
000000013FB91022 lea rcx,[string "%d" (13FB921B0h)]
000000013FB91029 add edx,edx
Este es la configuración de optimización en 'Maximizar velocidad' (/ O2)
10
No si x es un flotador no lo hará.
+0
Excelente punto. –
+0
Por supuesto, el cambio de bit de un flotador tiene un resultado completamente diferente que la multiplicación por potencias de dos, n'est pas? – wprl
+0
Para una multiplicación por flotante con 2 solo es cuestión de sumar 1 al exponente. Pero no creo que los compiladores optimicen eso. – rslite
0
Sí, lo harán.
4
Sí. También optimizan otras operaciones similares, como la multiplicación por no poderes de dos que pueden reescribirse como sumas de algunos turnos. También optimizarán las divisiones por potencias de 2 en cambios a la derecha, pero ten en cuenta que cuando trabajas con enteros con signo, ¡las dos operaciones son diferentes! El compilador debe emitir algunas instrucciones adicionales para asegurarse de que los resultados sean los mismos para los números positivos y negativos, pero aún así es más rápido que hacer una división. También optimiza de manera similar módulos por potencias de 2.
+0
El compilador en realidad no tiene que emitir ninguna instrucción adicional para una división - para eso es SAL - maneja los números de complemento de dos correctamente. – Branan
+0
Err yeah (donde por SAL te refieres a SAR); es para módulos firmados por potencias de 2 en la que emite código de twiddling extra bit –
12
VS 2008 mina optimizada en x < < 1.
x = x * 2;
004013E7 mov eax,dword ptr [x]
004013EA shl eax,1
004013EC mov dword ptr [x],eax
EDITAR: Esto estaba usando la configuración de "depuración" predeterminada de VS con la optimización deshabilitada (/ Od). El uso de cualquiera de los interruptores de optimización (/ O1,/O2 (VS "Retail") o/Ox) da como resultado la publicación del código de auto propio Rob. Además, solo para una buena medida, he verificado que x = x << 1 es tratado de la misma manera que x = x * 2 por el compilador cl en ambos/Od y/Ox. Por lo tanto, en resumen, cl.exe versión 15.00.30729.01 para x86 trata * 2 y << 1 de forma idéntica y espero que casi todos los demás compiladores recientes hagan lo mismo.
+0
Debería enumerar qué configuración de compilación estaba usando –
-9
Depende de qué compilador tenga. Visual C++, por ejemplo, es notoriamente pobre en la optimización. Si editas tu publicación para decir qué compilador estás utilizando, sería más fácil responderla.
+1
es ? Lo primero que escucho al respecto. En realidad, suelo escuchar que es uno de los mejores compiladores de PC para optimizaciones. –
+2
¿Alguna prueba de que VC++ es "notoriamente pobre en la optimización"? Por ejemplo, muéstranos el código máquina generado de la misma fuente por diferentes compiladores. –
+1
@Juegos: http://www.ddj.com/184405641 <- gran artículo. http://www.ddj.com/showArticle.jhtml?documentID=ddj0405a&pgno=12 <- tabla que resume la conclusión No estoy diciendo que este artículo sea el estándar, pero al estar en la comunidad Linux oigo comentarios negativos sobre VC++ no a menudo, pero suficiente. –
4
La respuesta es "si es más rápido" (o más pequeño). Esto depende en gran medida de la arquitectura de destino, así como del modelo de uso de registro para un compilador determinado. En general, la respuesta es "sí, siempre", ya que se trata de una optimización de mirilla muy simple de implementar y suele ser una victoria decente.
0
A menos que se especifique algo en un estándar de idiomas, nunca obtendrá una respuesta garantizada a dicha pregunta. En caso de duda, su compilador escupió el código de ensamblado y lo verificó. Esa va a ser la única forma de realmente saber.
21
Este artículo de Raymond Chen podría ser interesante:
Cuando es x/2 x diferente de >> 1?: http://blogs.msdn.com/oldnewthing/archive/2005/05/27/422551.aspx
Citando Raymond:
Por supuesto, el compilador es libre de reconocer esto y reescribir su multiplicación o cambiar el funcionamiento.De hecho, es muy probable que haga esto, porque x + x es más fácil de emparejar que una multiplicación o cambio. Su turno o multiplicación por dos probablemente se reescribirá como algo más parecido a una instrucción add eax, eax.
[...]
Incluso si se asume que el cambio se llena con el bit de signo, el resultado del desplazamiento y la división son diferentes si x es negativo.
(-1)/2 ≡ 0
(-1) >> 1 ≡ -1[...]
La moraleja de la historia es escribir lo que quiere decir . Si desea dividir por dos, escriba "/ 2", no ">> 1".
Sólo podemos suponer que es prudente decirle al compilador lo que quiere, no lo que usted quiere que haga: El compilador es mejor que un ser humano es a la optimización de código pequeña escala (gracias por Daemin señala este punto sutil): si realmente desea la optimización, use un generador de perfiles y estudie la eficiencia de sus algoritmos.
+1
Al menos optimizando el código de pequeña escala como la pregunta, el humano todavía debe escribir algotirhm :-) – Daemin
+0
@Daemin: Tiene razón – paercebal
+0
La implementación del operador de desplazamiento en C++ es en realidad específica de la plataforma; algunas plataformas tienen un cambio aritmético. Sin embargo, el que está en el x86 redondea incorrectamente. Esto significa que el compilador no puede usar SAR de forma segura en ese caso, mientras que un ser humano puede (conociendo las consecuencias). –
1
Estoy seguro de que todos hacen este tipo de optimizaciones, pero me pregunto si siguen siendo relevantes. Los procesadores antiguos hacían multiplicaciones cambiando y agregando, lo que podría tomar varios ciclos para completarse. Los procesadores modernos, por otro lado, tienen un conjunto de barril-shifters que pueden hacer todos los cambios necesarios y adiciones simultáneamente en un ciclo de reloj o menos. ¿Alguien realmente ha comparado si estas optimizaciones realmente ayudan?
0
@Ferruccio Barletta
Esa es una buena pregunta. Busqué en Google para tratar de encontrar la respuesta.
No pude encontrar las respuestas para los procesadores Intel directamente, pero la página this tiene a alguien que intentó sincronizar las cosas. Muestra que los turnos son más del doble de rápido que los anuncios y se multiplican. Los cambios de bits son tan simples (donde una multiplicación podría ser un cambio y una adición) que esto tiene sentido.
Así que busqué en Google AMD y encontré una antigua guía de optimización para el Athlon de 2002 que enumera las maneras más rápidas de multiplicar números por contantes entre 2 y 32. Curiosamente, depende del número. Algunos son anuncios, algunos cambios. Está en page 122.
Una guía para el Athlon 64 muestra lo mismo (página 164 más o menos). Dice que las multiplicaciones son 3 (en 32 bits) o 4 (en 64 bits) operaciones de ciclo, donde los cambios son 1 y se suman 2.
Parece que sigue siendo útil como optimización.
Ignorando el ciclo cuenta, este tipo de método evitaría que bloquees las unidades de ejecución de multiplicación (posiblemente), por lo que si haces muchas multiplicaciones en un circuito cerrado donde algunas usan constantes y otras no la sala de programación podría ser útil.
Pero eso es especulación.
4
Eso es solo el comienzo de lo que los optimizadores pueden hacer. Para ver qué hace tu compilador, busca el interruptor que hace que emita el origen del ensamblador. Para los compiladores de Marte Digital, el ensamblador de salida se puede examinar con la herramienta OBJ2ASM.Si desea aprender cómo funciona su compilador, mirar la salida del ensamblador puede ser muy esclarecedor.
Cuestiones relacionadas
- 1. Los resultados de Java son diferentes para (int) Math.pow (2, x) y 1 << x
- 2. Struts 1.x vs Struts 2.x
- 3. Simplificar si (x == 1 || x == 2)
- 4. ¿Qué hace (1U << X)?
- 5. JS regexp (? <! X) A
- 6. ¿Cómo optimizan los compiladores nuestro código?
- 7. C++ allocator <X> :: deallocate (NULL, 1) permitido?
- 8. operador << (ostream Y, X) para la clase X anidado en una plantilla de clase
- 9. ¿Por qué es (1/2) * x diferente de 0.5 * x?
- 10. ¿Es x + = 1 más eficiente que x = x + 1?
- 11. ¿Alguna vez el valor será 0 después de cambiar por "x << = 1" repetidamente?
- 12. scalac -explaintypes: ¿Qué significa "<notype><: X?" ¿media?
- 13. Con IEEE-754, 0 <ABS (const) <1, ¿está garantizado (x/const) * devolver resultados distintos para valores distintos de X?
- 14. En C++, ¿qué es más rápido? (2 * i + 1) o (i << 1 | 1)?
- 15. Encuentra todos los pares (x, y) en una matriz ordenada para que x + y <z
- 16. En la declaración "std :: vector <X> f();", ¿es "std :: vector <X>" una instanciación?
- 17. MySQL - SELECCIONAR DONDE fecha <X
- 18. ¿Qué significa (? <= X) en regex?
- 19. ¿Cómo saben los compiladores dónde encontrar #include <stdio.h>?
- 20. x-y = x + 1 + ¬y problema
- 21. Lista de fundición <x> a la lista <y>
- 22. Ventaja de usar "x * = -1". sobre "x * = -1"?
- 23. C# List <> Ordena por x then y
- 24. ¿`y = x = x + 1;` comportamiento indefinido?
- 25. soporte de idioma para los operadores de comparación encadenados (x <y <z)
- 26. ¿Cómo redacto Linq Expressions? es decir Func <Exp <Func<X, Y>>, Exp <Func<Y, Z>>, Exp <Func<X, Z> >>
- 27. Rendimiento: Python 3.x frente a Python 2.x
- 28. ¿Cómo obtener x de 2^x = 8000?
- 29. ¿Cuáles son las principales diferencias entre Rails 1.X y 2.X
- 30. ¿Es posible emular la plantilla <auto X>?
gcc hace lo mismo (ya lo vi varias veces, usa lea, y compilando tu programa de muestra que usaste agrega ambos con -m32 y -m64). – CesarB
Una forma rápida de ver esta información: poner un punto de interrupción en la línea de interés, ejecutar en modo de depuración. Cuando se detenga en la línea, haga clic derecho y seleccione "Ir al desmontaje". Otros métodos aquí: https://stackoverflow.com/questions/1020498/how-to-view-the-assembly-behind-the-code-using-visual-c – RoG