c++ - tipo - rendimiento de enteros sin signo vs signo

tipos de datos enteros (11)

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.

¿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?

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 compilador.

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.

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).

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 compilador 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.

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 compiladores modernos pueden usar implícitamente int al realizar cálculos para tipos más cortos en algunos casos.

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

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 compilador que puede funcionar en contra del sentido común. Una cosa para recordar es que los diferentes compiladores pueden compilar el código de manera diferente y ellos mismos tienen diferentes tipos de optimizaciones. Si estamos hablando de un compilador g++ y estamos hablando de maximizar su nivel de optimización utilizando -Ofast , o al menos un indicador -O3 , en mi experiencia puede compilar 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 programa completo y te preocupes por esas cosas solo después de eso, cuando tienes el código real en tus manos y puedes compilarlo 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 compilar con optimizaciones, modifique las cosas para ver qué funciona mejor. Y también debería intentar usar diferentes compiladores para compilar su programa y elegir el que arroje el código máquina más eficiente.

Un programa 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 programa casi 2 veces. Y no, a[x]=b no fue el más rápido.

Aquí está, por ejemplo, NVidia indicando que para programar 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 compilador.

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 compilador 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 compilador 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 arquitecturas 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.

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 observa las tablas de instrucciones de Agner Fog , verá 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 arquitecturas 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.