¿Por qué GCC usa la multiplicación por un número extraño al implementar la división de enteros?

6 minutos de lectura

avatar de usuario
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?

  • 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 -3689348814741910323 se convierte en CCCCCCCCCCCCCCCD como un uint64_t o 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 div instrucción en -O0. (cc @ clifford)

    – Cody gris

    16 de diciembre de 2016 a las 15:02

  • 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

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad