qiubit
he estado leyendo sobre div y mul operaciones de ensamblaje, y decidí verlas en acción escribiendo un programa simple en C:
División de archivos.c
#include <stdlib.h>
#include <stdio.h>
int main()
{
size_t i = 9;
size_t j = i / 5;
printf("%zu\n",j);
return 0;
}
Y luego generar código en lenguaje ensamblador con:
gcc -S division.c -O0 -masm=intel
Pero mirando generado division.s archivo, ¡no contiene ninguna operación div! En cambio, hace algún tipo de magia negra con cambios de bits y números mágicos. Aquí hay un fragmento de código que calcula i/5:
mov rax, QWORD PTR [rbp-16] ; Move i (=9) to RAX
movabs rdx, -3689348814741910323 ; Move some magic number to RDX (?)
mul rdx ; Multiply 9 by magic number
mov rax, rdx ; Take only the upper 64 bits of the result
shr rax, 2 ; Shift these bits 2 places to the right (?)
mov QWORD PTR [rbp-8], rax ; Magically, RAX contains 9/5=1 now,
; so we can assign it to j
¿Que está pasando aqui? ¿Por qué GCC no usa div en absoluto? ¿Cómo genera este número mágico y por qué funciona todo?
-
Esta respuesta convirtió los inversos multiplicativos modulares de “matemáticas que parecen más complicadas de lo que quiero tomarme el tiempo” en algo que tiene sentido. +1 para la versión fácil de entender. Nunca he tenido que hacer nada más que usar constantes generadas por el compilador, así que solo he leído otros artículos que explican las matemáticas.
– Peter Cordes
17 de diciembre de 2016 a las 4:08
-
No veo nada que ver con la aritmética modular en el código. No sé de dónde sacan eso otros comentaristas.
– lavado de enchufe
17 dic 2016 a las 13:05
-
Es módulo 2^n, como todas las matemáticas de enteros en un registro. es.wikipedia.org/wiki/…
– Peter Cordes
17 dic 2016 a las 16:49
-
Los inversos multiplicativos modulares de @PeterCordes se usan para la división exacta, aunque no son útiles para la división general
– harold
17 dic 2016 a las 23:16
-
¿Multiplicación de @PeterCordes por recíproco de punto fijo? No sé cómo lo llaman todos, pero probablemente yo lo llamaría así, es bastante descriptivo.
– harold
18 dic 2016 a las 21:06
-
No estoy seguro de que sea justo agrupar FP y operaciones enteras en una comparación de velocidad, @fuz. Tal vez Sneftel debería estar diciendo eso división es el mas lento entero operación que puede realizar en un procesador moderno? Además, se han proporcionado algunos enlaces a más explicaciones de esta “magia” en los comentarios. ¿Crees que sería apropiado recopilarlos en tu respuesta para la visibilidad? 1, 2, 3
– Cody gris
♦16 dic 2016 a las 15:00
-
Debido a que la secuencia de operaciones es funcionalmente idéntica… esto es siempre un requisito, incluso en
-O3. El compilador tiene que crear un código que proporcione resultados correctos para todos los valores de entrada posibles. Esto solo cambia para el punto flotante con-ffast-math, y AFAIK no hay optimizaciones enteras “peligrosas”. (Con la optimización habilitada, el compilador podría probar algo sobre el posible rango de valores que le permite usar algo que solo funciona para enteros con signo no negativo, por ejemplo).– Peter Cordes
16 dic 2016 a las 15:55
-
La verdadera respuesta es que gcc -O0 todavía transforma el código a través de representaciones internas como parte de convertir C en código de máquina. Simplemente sucede que los inversos multiplicativos modulares están habilitados por defecto incluso en
-O0(pero no con-Os). Otros compiladores (como clang) usarán DIV para constantes que no sean potencia de 2 en-O0. relacionado: creo que incluí un párrafo sobre esto en mi respuesta asm escrita a mano de la conjetura de Collatz– Peter Cordes
16 dic 2016 a las 16:00
-
@PeterCordes Y sí, creo que GCC (y muchos otros compiladores) se han olvidado de encontrar una buena razón para “qué tipo de optimizaciones se aplican cuando la optimización está deshabilitada”. Habiendo pasado la mayor parte del día rastreando un oscuro error de generación de código, estoy un poco molesto por eso en este momento.
– Sneftel
16 dic 2016 a las 20:19
-
@Sneftel: Probablemente se deba a la cantidad de desarrolladores de aplicaciones que activamente quejar a los desarrolladores del compilador que su código se ejecuta más rápido de lo esperado es relativamente pequeño.
– dan04
16 dic 2016 a las 23:37
-
Ese documento describe su implementación en gcc, por lo que creo que es una suposición segura de que todavía se usa el mismo algoritmo.
– Peter Cordes
20 de diciembre de 2016 a las 4:07
-
Ese documento con fecha de 1994 describe su implementación en gcc, por lo que ha habido tiempo para que gcc actualice su algoritmo. En caso de que otros no tengan tiempo de verificar qué significa el 94 en esa URL.
–Ed Grimm
29 de enero de 2019 a las 5:45
-
Ese documento describe su implementación en gcc, por lo que creo que es una suposición segura de que todavía se usa el mismo algoritmo.
– Peter Cordes
20 de diciembre de 2016 a las 4:07
-
Ese documento con fecha de 1994 describe su implementación en gcc, por lo que ha habido tiempo para que gcc actualice su algoritmo. En caso de que otros no tengan tiempo de verificar qué significa el 94 en esa URL.
–Ed Grimm
29 de enero de 2019 a las 5:45
gcc optimiza las divisiones por constantes, prueba las divisiones por 2,3,4,5,6,7,8 y lo más probable es que veas un código muy diferente para cada caso.
– Jabberwocky
16 de diciembre de 2016 a las 12:03
Nota: número mágico
-3689348814741910323se convierte enCCCCCCCCCCCCCCCDcomo unuint64_to casi (2^64)*4/5.– chux – Reincorporar a Monica
16 de diciembre de 2016 a las 12:17
@qiubit: el compilador no generará de forma perversa código ineficiente solo porque la optimización está deshabilitada. Se realizará una “optimización” trivial que no involucre el reordenamiento del código o la eliminación de variables independientemente, por ejemplo. Esencialmente, una declaración de fuente única se traducirá en el código más eficiente para esa operación de forma aislada. La optimización del compilador tiene en cuenta el código circundante en lugar de solo la declaración única.
– Clifford
16 dic 2016 a las 12:30
Lee este increíble artículo: Mano de obra de división
– bufón
16 de diciembre de 2016 a las 12:32
Algunos compiladores en realidad será generar de forma perversa código ineficiente porque la optimización está deshabilitada. En particular, lo harán para facilitar la depuración, como la capacidad de establecer puntos de interrupción en líneas de código individuales. GCC es, de hecho, bastante inusual en el sentido de que no tiene un verdadero modo “sin optimizaciones”, porque muchas de sus optimizaciones están activadas de forma constitutiva. Este es un ejemplo de dónde puede ver eso con GCC. Clang, por otro lado, y MSVC, será emitir un
divinstrucción en-O0. (cc @ clifford)– Cody gris
♦
16 de diciembre de 2016 a las 15:02