rendimiento de enteros sin signo vs signo

¿Hay alguna ganancia / pérdida de rendimiento al usar enteros sin signo sobre enteros con signo?

Si es así, ¿esto también funciona por poco tiempo?

    La división por potencias de 2 es más rápida con unsigned int , porque se puede optimizar en una instrucción de cambio único. Con signed int , por lo general requiere más instrucciones de la máquina, porque la división se redondea hacia cero , pero se desplaza hacia abajo a la derecha. Ejemplo:

     int foo(int x, unsigned y) { x /= 8; y /= 8; return x + y; } 

    Aquí está la parte x relevante (división firmada):

     movl 8(%ebp), %eax leal 7(%eax), %edx testl %eax, %eax cmovs %edx, %eax sarl $3, %eax 

    Y aquí está la parte y relevante (división sin signo):

     movl 12(%ebp), %edx shrl $3, %edx 

    En C ++ (y C), el desbordamiento de entero con signo no está definido, mientras que el desbordamiento de entero sin signo está definido para ajustarse. Tenga en cuenta que, por ejemplo, en gcc, puede usar el indicador -fwrapv para definir el desbordamiento firmado (para envolver).

    El desbordamiento de entero con signo indefinido permite al comstackdor suponer que no se producen desbordamientos, lo que puede introducir oportunidades de optimización. Ver, por ejemplo, esta publicación de blog para discusión.

    Esto dependerá de la implementación exacta. En la mayoría de los casos, no habrá diferencia, sin embargo. Si realmente te importa, tienes que probar todas las variantes que consideras y medir el rendimiento.

    unsigned conduce al mismo rendimiento o mejor que el signed . Algunos ejemplos:

    • División por una constante que es una potencia de 2 (ver también la respuesta de FredOverflow )
    • División por un número constante (por ejemplo, mi comstackdor implementa división por 13 usando 2 instrucciones asm para unsigned, y 6 instrucciones para firmado)
    • Comprobando si un número es par (no tengo idea de por qué mi comstackdor de MS Visual Studio lo implementa con 4 instrucciones para números con signed ; gcc lo hace con 1 instrucción, al igual que en el caso unsigned )

    short generalmente conduce al mismo o peor rendimiento que int (suponiendo sizeof(short) < sizeof(int) ). La degradación del rendimiento ocurre cuando asigna un resultado de una operación aritmética (que generalmente es int , nunca short ) a una variable de tipo short , que se almacena en el registro del procesador (que también es de tipo int ). Todas las conversiones de short a int toman tiempo y son molestas.

    Nota: algunos DSP tienen instrucciones de multiplicación rápidas para el tipo signed short ; en este caso específico, short es más rápido que int .

    En cuanto a la diferencia entre int y long , solo puedo adivinar (no estoy familiarizado con las architectures de 64 bits). Por supuesto, si int y long tienen el mismo tamaño (en plataformas de 32 bits), su rendimiento también es el mismo.


    Una adición muy importante, señalada por varias personas:

    Lo que realmente importa para la mayoría de las aplicaciones es la huella de memoria y el ancho de banda utilizado. Debería usar los enteros necesarios más pequeños ( short , quizás incluso con signed/unsigned char ) para arreglos grandes.

    Esto proporcionará un mejor rendimiento, pero la ganancia es no lineal (es decir, no por un factor de 2 o 4) y algo impredecible: depende del tamaño de la memoria caché y de la relación entre los cálculos y las transferencias de memoria en la aplicación.

    Esto es bastante dependiente del procesador específico.

    En la mayoría de los procesadores, hay instrucciones para la aritmética tanto firmada como sin firmar, por lo que la diferencia entre usar enteros con y sin signo se reduce a la que usa el comstackdor.

    Si alguno de los dos es más rápido, es completamente específico del procesador, y lo más probable es que la diferencia sea minúscula, si es que existe.

    La diferencia de rendimiento entre los enteros con signo y sin signo es en realidad más general de lo que sugiere la respuesta de aceptación. La división de un entero sin signo por cualquier constante se puede hacer más rápido que la división de un entero con signo por una constante, independientemente de si la constante es una potencia de dos. Ver http://ridiculousfish.com/blog/posts/labor-of-division-episode-iii.html

    Al final de su publicación, incluye la siguiente sección:

    Una pregunta natural es si la misma optimización podría mejorar la división firmada; desafortunadamente parece que no, por dos razones:

    El incremento del dividendo debe convertirse en un aumento en la magnitud, es decir, incremento si n> 0, decremento si n <0. Esto introduce un gasto adicional.

    La penalización para un divisor que no coopera es solo la mitad en la división firmada, dejando una ventana más pequeña para las mejoras.

    Por lo tanto, parece que el algoritmo de redondeo podría funcionar en la división firmada, pero tendrá un rendimiento inferior al algoritmo de redondeo estándar.

    En resumen, no te molestes antes del hecho. Pero molesta después.

    Si desea tener un rendimiento, debe usar optimizaciones de rendimiento de un comstackdor que puede funcionar en contra del sentido común. Una cosa para recordar es que los diferentes comstackdores pueden comstackr el código de manera diferente y ellos mismos tienen diferentes tipos de optimizaciones. Si estamos hablando de un comstackdor g++ y estamos hablando de maximizar su nivel de optimización utilizando -Ofast , o al menos un indicador -O3 , en mi experiencia puede comstackr código long en código con un rendimiento incluso mejor que cualquier tipo unsigned , o incluso solo int .

    Esto es por mi propia experiencia y te recomiendo que primero escribas tu progtwig completo y te preocupes por esas cosas solo después de eso, cuando tienes el código real en tus manos y puedes comstackrlo con optimizaciones para tratar de elegir los tipos que realmente funcionan mejor. Esta es también una buena sugerencia general sobre la optimización del código para el rendimiento, escriba primero rápidamente, intente comstackr con optimizaciones, modifique las cosas para ver qué funciona mejor. Y también debería intentar usar diferentes comstackdores para comstackr su progtwig y elegir el que arroje el código máquina más eficiente.

    Un progtwig de cálculo de álgebra lineal multiproceso optimizado puede tener fácilmente una diferencia de rendimiento> 10 veces mejor optimizada frente a no optimizada. Entonces esto sí importa

    La salida del optimizador contradice la lógica en muchos casos. Por ejemplo, tuve un caso en el que una diferencia entre a[x]+=b y a[x]=b cambió el tiempo de ejecución del progtwig casi 2 veces. Y no, a[x]=b no fue el más rápido.

    Aquí está, por ejemplo, NVidia indicando que para progtwigr sus GPU:

    Nota: Como ya era la mejor práctica recomendada, la aritmética con signo debe preferirse a la aritmética sin signo siempre que sea posible para obtener el mejor rendimiento en SMM. El estándar de lenguaje C impone más restricciones al comportamiento de desbordamiento para matemática sin signo, lo que limita las oportunidades de optimización del comstackdor.

    No solo la división por potencias de 2 es más rápida con el tipo sin signo, la división por cualquier otro valor también es más rápida con el tipo sin signo. Si miras las tablas de instrucciones de Agner Fog , verás que las divisiones sin firmar tienen un rendimiento similar o mejor que las versiones firmadas

    Por ejemplo, con el AMD K7

     ╔═════════════╤══════════╤═════╤═════════╤═══════════════════════╗ ║ Instruction │ Operands │ Ops │ Latency │ Reciprocal throughput ║ ╠═════════════╪══════════╪═════╪═════════╪═══════════════════════╣ ║ DIV │ r8/m8 │ 32 │ 24 │ 23 ║ ║ DIV │ r16/m16 │ 47 │ 24 │ 23 ║ ║ DIV │ r32/m32 │ 79 │ 40 │ 40 ║ ║ IDIV │ r8 │ 41 │ 17 │ 17 ║ ║ IDIV │ r16 │ 56 │ 25 │ 25 ║ ║ IDIV │ r32 │ 88 │ 41 │ 41 ║ ║ IDIV │ m8 │ 42 │ 17 │ 17 ║ ║ IDIV │ m16 │ 57 │ 25 │ 25 ║ ║ IDIV │ m32 │ 89 │ 41 │ 41 ║ ╚═════════════╧══════════╧═════╧═════════╧═══════════════════════╝ 

    Lo mismo se aplica a Intel Pentium

     ╔═════════════╤══════════╤══════════════╗ ║ Instruction │ Operands │ Clock cycles ║ ╠═════════════╪══════════╪══════════════╣ ║ DIV │ r8/m8 │ 17 ║ ║ DIV │ r16/m16 │ 25 ║ ║ DIV │ r32/m32 │ 41 ║ ║ IDIV │ r8/m8 │ 22 ║ ║ IDIV │ r16/m16 │ 30 ║ ║ IDIV │ r32/m32 │ 46 ║ ╚═════════════╧══════════╧══════════════╝ 

    Por supuesto, esos son bastante antiguos. Las architectures más nuevas con más transistores podrían cerrar la brecha, pero se aplican las cosas básicas: generalmente se necesitan más operaciones macro, más lógica, más latencia para hacer una división firmada.

    Tradicionalmente int es el formato entero nativo de la plataforma de hardware de destino. Cualquier otro tipo de entero puede incurrir en penalizaciones de rendimiento.

    EDITAR:

    Las cosas son ligeramente diferentes en los sistemas modernos:

    • int puede de hecho ser de 32 bits en sistemas de 64 bits por razones de compatibilidad. Creo que esto sucede en los sistemas de Windows.

    • Los comstackdores modernos pueden usar implícitamente int al realizar cálculos para tipos más cortos en algunos casos.

    IIRC, en x86 firmado / no firmado no debe hacer ninguna diferencia. Corto / largo, por otro lado, es una historia diferente, ya que la cantidad de datos que se tiene que mover a / desde la RAM es mayor para los largos (otras razones pueden incluir operaciones de lanzamiento como extender de corto a largo).

    El entero sin signo es ventajoso porque almacena y trata ambos como flujo de bits, me refiero solo a un dato, sin signo, por lo que la multiplicación, la devision se vuelve más fácil (más rápido) con operaciones de cambio de bit

    Los enteros con signo y sin signo siempre funcionarán como instrucciones de un solo reloj y tendrán el mismo rendimiento de lectura y escritura, pero según el Dr. Andrei Alexandrescu se prefiere el signo no firmado. La razón para esto es que puede caber el doble de la cantidad de números en la misma cantidad de bits porque no está desperdiciando el bit de signo y utilizará menos instrucciones para verificar los números negativos y boostá el rendimiento de la ROM reducida. En mi experiencia con Kabuki VM , que presenta una implementación de script de muy alto rendimiento, es raro que realmente requiera un número firmado cuando trabaja con memoria. He gastado muchos años haciendo aritmética de puntero con números firmados y sin firmar, y no he encontrado ningún beneficio para el firmado cuando no se necesita un bit de signo.

    Donde se prefiere firmar es cuando se usa el cambio de bit para realizar la multiplicación y división de potencias de 2 porque se pueden realizar potencias negativas de 2 divisiones con enteros de complemento con signo 2. Vea más videos de YouTube de Andrei para obtener más técnicas de optimización. También puedes encontrar buena información en mi artículo sobre el algoritmo de conversión de entero a cadena más rápido del mundo .