c performance optimization unsigned signed

En C, ¿por qué "signatura int" es más rápido que "int firmada"?



performance optimization (4)

En C, ¿por qué se signed int más rápido que unsigned int ? Es cierto, sé que esto se ha pedido y se ha respondido varias veces en este sitio web (enlaces a continuación). Sin embargo, la mayoría de la gente dice que no hay diferencia. He escrito un código y accidentalmente he encontrado una diferencia significativa en el rendimiento.

¿Por qué la versión "sin firmar" de mi código sería más lenta que la versión "firmada" (incluso cuando se prueba el mismo número)? (Tengo un procesador Intel x86-64).

Enlaces similares

Comando de compilación: gcc -Wall -Wextra -pedantic -O3 -Wl,-O3 -g0 -ggdb0 -s -fwhole-program -funroll-loops -pthread -pipe -ffunction-sections -fdata-sections -std=c11 -o ./test ./test.c && strip --strip-all --strip-unneeded --remove-section=.note --remove-section=.comment ./test

versión signed int

NOTA: No hay diferencia si declaro explícitamente un signed int en todos los números.

int isprime(int num) { // Test if a signed int is prime int i; if (num % 2 == 0 || num % 3 == 0) return 0; else if (num % 5 == 0 || num % 7 == 0) return 0; else { for (i = 11; i < num; i += 2) { if (num % i == 0) { if (i != num) return 0; else return 1; } } } return 1; }

versión unsigned int

int isunsignedprime(unsigned int num) { // Test if an unsigned int is prime unsigned int i; if (num % (unsigned int)2 == (unsigned int)0 || num % (unsigned int)3 == (unsigned int)0) return 0; else if (num % (unsigned int)5 == (unsigned int)0 || num % (unsigned int)7 == (unsigned int)0) return 0; else { for (i = (unsigned int)11; i < num; i += (unsigned int)2) { if (num % i == (unsigned int)0) { if (i != num) return 0; else return 1; } } } return 1; }

Prueba esto en un archivo con el siguiente código:

int main(void) { printf("%d/n", isprime(294967291)); printf("%d/n", isprime(294367293)); printf("%d/n", isprime(294967293)); printf("%d/n", isprime(294967241)); // slow printf("%d/n", isprime(294967251)); printf("%d/n", isprime(294965291)); printf("%d/n", isprime(294966291)); printf("%d/n", isprime(294963293)); printf("%d/n", isprime(294927293)); printf("%d/n", isprime(294961293)); printf("%d/n", isprime(294917293)); printf("%d/n", isprime(294167293)); printf("%d/n", isprime(294267293)); printf("%d/n", isprime(294367293)); // slow printf("%d/n", isprime(294467293)); return 0; }

Resultados ( time ./test ):

Signed - real 0m0.949s Unsigned - real 0m1.174s

De la especificación de instrucciones en AMD / Intel tenemos (para K7):

Instruction Ops Latency Throughput DIV r32/m32 32 24 23 IDIV r32 81 41 41 IDIV m32 89 41 41

Para i7, la latencia y el rendimiento son los mismos para IDIVL y DIVL , existe una ligera diferencia para los µops.

Esto puede explicar la diferencia, ya que los códigos de ensamblaje de -O3 solo difieren por la firmeza (DIVL vs IDIVL) en mi máquina.

Prueba de candidato wiki alternativo que puede / no mostrar una diferencia de tiempo significativa.

#include <stdio.h> #include <time.h> #define J 10 #define I 5 int main(void) { clock_t c1,c2,c3; for (int j=0; j<J; j++) { c1 = clock(); for (int i=0; i<I; i++) { isprime(294967241); isprime(294367293); } c2 = clock(); for (int i=0; i<I; i++) { isunsignedprime(294967241); isunsignedprime(294367293); } c3 = clock(); printf("%d %d %d/n", (int)(c2-c1), (int)(c3-c2), (int)((c3-c2) - (c2-c1))); fflush(stdout); } return 0; }

Salida de muestra

2761 2746 -15 2777 2777 0 2761 2745 -16 2793 2808 15 2792 2730 -62 2746 2730 -16 2746 2730 -16 2776 2793 17 2823 2808 -15 2793 2823 30

Su pregunta es realmente intrigante, ya que la versión sin firma produce de manera consistente un código que es 10 a 20% más lento. Sin embargo, hay múltiples problemas en el código:

  • Ambas funciones devuelven 0 para 2 , 3 , 5 y 7 , lo cual es incorrecto.
  • La prueba if (i != num) return 0; else return 1; if (i != num) return 0; else return 1; es completamente inútil ya que el cuerpo del bucle solo se ejecuta para i < num . Una prueba de este tipo sería útil para las pruebas de cebado pequeñas, pero no es realmente útil para el encofrado especial.
  • Las conversiones en la versión sin firmar son redundantes.
  • El código de referencia que produce resultados textuales en el terminal no es confiable, debe usar la función clock() para cronometrar las funciones intensivas de la CPU sin ninguna intervención de E / S.
  • el algoritmo para la prueba principal es completamente ineficiente ya que el bucle se ejecuta num / 2 veces en lugar de sqrt(num) .

Simplifiquemos el código y ejecutemos algunos puntos de referencia precisos:

#include <stdio.h> #include <time.h> int isprime_slow(int num) { if (num % 2 == 0) return num == 2; for (int i = 3; i < num; i += 2) { if (num % i == 0) return 0; } return 1; } int unsigned_isprime_slow(unsigned int num) { if (num % 2 == 0) return num == 2; for (unsigned int i = 3; i < num; i += 2) { if (num % i == 0) return 0; } return 1; } int isprime_fast(int num) { if (num % 2 == 0) return num == 2; for (int i = 3; i * i <= num; i += 2) { if (num % i == 0) return 0; } return 1; } int unsigned_isprime_fast(unsigned int num) { if (num % 2 == 0) return num == 2; for (unsigned int i = 3; i * i <= num; i += 2) { if (num % i == 0) return 0; } return 1; } int main(void) { int a[] = { 294967291, 0, 294367293, 0, 294967293, 0, 294967241, 1, 294967251, 0, 294965291, 0, 294966291, 0, 294963293, 0, 294927293, 1, 294961293, 0, 294917293, 0, 294167293, 0, 294267293, 0, 294367293, 0, 294467293, 0, }; struct testcase { int (*fun)(); const char *name; int t; } test[] = { { isprime_slow, "isprime_slow", 0 }, { unsigned_isprime_slow, "unsigned_isprime_slow", 0 }, { isprime_fast, "isprime_fast", 0 }, { unsigned_isprime_fast, "unsigned_isprime_fast", 0 }, }; for (int n = 0; n < 4; n++) { clock_t t = clock(); for (int i = 0; i < 30; i += 2) { if (test[n].fun(a[i]) != a[i + 1]) { printf("%s(%d) != %d/n", test[n].name, a[i], a[i + 1]); } } test[n].t = clock() - t; } for (int n = 0; n < 4; n++) { printf("%21s: %4d.%03dms/n", test[n].name, test[n].t / 1000), test[n].t % 1000); } return 0; }

El código compilado con clang -O2 en OS / X produce esta salida:

isprime_slow: 788.004ms unsigned_isprime_slow: 965.381ms isprime_fast: 0.065ms unsigned_isprime_fast: 0.089ms

Estos tiempos son consistentes con el comportamiento observado del OP en un sistema diferente, pero muestran la mejora dramática causada por la prueba de iteración más eficiente: ¡ 10000 veces más rápido!

Respecto a la pregunta ¿Por qué la función es más lenta si no está firmada? , echemos un vistazo al código generado ( gcc 7.2 -O2 ):

isprime_slow(int): ... .L5: movl %edi, %eax cltd idivl %ecx testl %edx, %edx je .L1 .L4: addl $2, %ecx cmpl %esi, %ecx jne .L5 .L6: movl $1, %edx .L1: movl %edx, %eax ret unsigned_isprime_slow(unsigned int): ... .L19: xorl %edx, %edx movl %edi, %eax divl %ecx testl %edx, %edx je .L22 .L18: addl $2, %ecx cmpl %esi, %ecx jne .L19 .L20: movl $1, %eax ret ... .L22: xorl %eax, %eax ret

Los bucles internos son muy similares, el mismo número de instrucciones, instrucciones similares. Aquí hay sin embargo algunas explicaciones potenciales:

  • cltd extiende el signo del registro eax registro edx , lo que puede estar causando un retraso en la instrucción porque eax es modificado por la instrucción inmediatamente anterior movl %edi, %eax . Sin embargo, esto haría que la versión firmada fuera más lenta que la no firmada, no más rápida.
  • Las instrucciones iniciales de los bucles pueden estar desalineadas para la versión sin firmar, pero es poco probable que el cambio de orden en el código fuente no tenga efecto en los tiempos.
  • Aunque los contenidos del registro son idénticos para los idivl división firmados y no firmados, es posible que la instrucción idivl tome menos ciclos que la instrucción divl . De hecho, la división firmada opera con un poco menos de precisión que la división no firmada, pero la diferencia parece bastante grande para este pequeño cambio.
  • Sospecho que se hizo un mayor esfuerzo en la implementación de silicio de idivl porque las divisiones firmadas son más comunes que las divisiones no firmadas (medida por los años de codificación de las estadísticas en Intel).
  • Como comentó rcgldr, al observar las tablas de instrucciones para el proceso Intel, para Ivy Bridge, DIV de 32 bits toma 10 microoperaciones, 19 a 27 ciclos, IDIV 9 micro operaciones, 19 a 26 ciclos. Los tiempos de referencia son consistentes con estos tiempos. La microoperación adicional puede deberse a los operandos más largos en DIV (64/32 bits) en oposición a IDIV (63/31 bits).

Este sorprendente resultado debería enseñarnos algunas lecciones:

  • Optimizar es un arte difícil, ser humilde y posponer las cosas.
  • la corrección a menudo se rompe por optimizaciones.
  • Elegir un mejor algoritmo supera la optimización por mucho tiempo.
  • siempre referencia el código, no confíe en sus instintos.