2010-11-07 8 views
8

El estándar C no está claro acerca de la familia de tipos uint_fast * _t. En un sistema gcc-4.4.4 linux x86_64, los tipos uint_fast16_t y uint_fast32_t son de 8 bytes de tamaño. Sin embargo, la multiplicación de números de 8 bytes parece ser bastante más lenta que la multiplicación de números de 4 bytes. El siguiente fragmento de código demuestra que:x86_64: ¿Por qué es uint_least16_t más rápido que uint_fast16_t (para la multiplicación)

#include <stdio.h> 
#include <stdint.h> 
#include <inttypes.h> 

int 
main() 
{ 
    uint_least16_t p, x; 
    int count; 

    p = 1; 
    for (count = 100000; count != 0; --count) 
    for (x = 1; x != 50000; ++x) 
     p*= x; 

    printf("%"PRIuLEAST16, p); 
    return 0; 
} 

Al ejecutar el comando tiempo en el programa, consigo

real 0m7.606s 
user 0m7.557s 
sys 0m0.019s 

Si cambio el tipo de uint_fast16_t (y el modificador de printf), el tiempo se convierte en

real 0m12.609s 
user 0m12.593s 
sys 0m0.009s 

Por lo tanto, ¿no sería mucho mejor si el uint_fast16_t definido cabecera stdint.h (y también uint_fast32_t) es un tipo de 4 bytes?

+0

Solo un pequeño consejo: no es necesario que incluya ambos, * stdint.h * y * inttypes.h *; de acuerdo con el estándar ISO C, * inttypes.h * siempre debe incluir * stdint.h *, por lo que incluirlo primero es solo una pérdida de tiempo (no es que esté prohibido o sea incorrecto, simplemente innecesario). – Mecki

Respuesta

0

Sí, creo que esto es simplemente un error. Desafortunadamente, no se puede simplemente corregir errores como este sin romper el ABI, pero puede que no importe ya que prácticamente nadie (y ciertamente ninguna función de la biblioteca que conozca) realmente usa los tipos *int_fast*_t.

+0

Si no me equivoco, la biblioteca vorbis sí. Además, cada vez que gcc se actualice de gcc-x.y.z a gcc-x.y + 1.w, el ABI puede romperse, por lo que podríamos hacer ese cambio en ese momento. –

+0

¿Vorbis usa estos tipos en la interfaz pública, o solo internamente? Yo solo espero lo último. Independientemente de la política de gcc, también hay un problema con la política de los mantenedores de la biblioteca. Si gcc rompiera sus ABIs, estarían bastante cabreados, y probablemente instituirían soluciones para bloquear el viejo tipo en lugar de cambiar con gcc. –

+0

@R. Solo por interés, ¿el linux x86_64 ABI incluye los tipos "rápidos" (o para el caso, cualquier cosa de stdint) ?. Me preocupa un poco que los documentos ABI a menudo los ignoren y por lo tanto (uno podría argumentar) que no es seguro pasarlos como parámetros a menos que tenga un enlace estático. –

3

Creo que tal decisión de diseño no es fácil de tomar. Depende de muchos factores. Por el momento, no tomo su experimento como concluyente, vea abajo.

En primer lugar no hay tal cosa como una solo concepto de lo rápido debería significar. Aquí hizo hincapié en la multiplicación en su lugar, que es solo un punto de vista particular.

Entonces x86_64 es una arquitectura y no un procesador. Por lo tanto, los resultados pueden ser bastante diferentes para los diferentes procesadores de esa familia. No creo que sea sensato que gcc tenga la decisión de tipo depender de los conmutadores de línea de comando particulares que optimizan para un procesador determinado.

Ahora, volviendo a su ejemplo. Supongo que también has mirado el código ensamblador? ¿Por ejemplo, usó las instrucciones de SSE para realizar su código? ¿Cambió las opciones específicas del procesador, algo así como -march=native?

Edité: Experimenté un poco con su programa de prueba y si lo dejo exactamente como está puedo básicamente reproducir sus medidas. Pero al modificarlo y jugar con él, estoy aún menos convencido de que es concluyente.

E.g si cambio el lazo interno también para ir hacia abajo, el ensamblador se ve casi igual que antes (pero usando decremento y una prueba en contra de 0) pero la ejecución requiere aproximadamente un 50% más. Así que supongo que el tiempo depende mucho del entorno de la instrucción que desea comparar, puestos de tuberías, lo que sea. Tendría que utilizar códigos de banco de naturaleza muy diferente donde las instrucciones se emiten en diferentes contextos, los problemas de alineamiento y la vectorización entran en juego, para tomar una decisión sobre cuáles son los tipos apropiados para el fasttypedef s.

+0

"No creo que sea sensato que gcc tenga la decisión de tipo depender de los conmutadores de línea de comando particulares que optimizan para un procesador determinado". Como dice R., esa es una pregunta ABI. Si el compilador dice que el ABI es independiente de esos switches, y el ABI especifica los tamaños de esos typedefs, entonces, por supuesto, no puede variar. Si es sensato usar los tipos 'rápidos' en una interfaz de biblioteca también es cuestionable, creo ;-) –

+0

@Steve, estoy completamente de acuerdo.Mi punto era que para un ABI dado que se aplica finalmente a toda una familia de procesadores, no se puede deducir mucho de la validez de una elección particular al hacer una sola prueba, con un tipo de instrucción, en un procesador en particular y con un compilador particular. –

+0

@Jens: sí, yo no tenía la intención de estar en desacuerdo, sólo tiene que añadir que la variación de los tipos de opciones del compilador no es sólo "loco" o el usuario poco amigable en un sentido vago, hay un problema específico con la compatibilidad llamada. –

4

Los compiladores de AFAIK solo definen sus propias versiones de los tipos (u)int_(fast/least)XX_t si aún no están definidos por el sistema. Eso es porque es muy importante que estos tipos estén igualmente definidos en todas las bibliotecas/binarios en un solo sistema.De lo contrario, si los diferentes compiladores definirían esos tipos de manera diferente, una biblioteca construida con CompilerA puede tener un tipo diferente de uint_fast32_t que un binario construido con CompilerB, pero este binario aún puede enlazarse con la biblioteca; no hay requisito estándar formal que todo el código ejecutable de un sistema tenga que ser construido por el mismo compilador (en realidad en algunos sistemas, por ejemplo, Windows, es bastante común que el código haya sido compilado por todo tipo de compiladores diferentes). Si ahora este binario llama a una función de la biblioteca, ¡las cosas se romperán!

Entonces, la pregunta es: ¿realmente GCC está definiendo uint_fast16_t aquí, o es realmente Linux (me refiero al núcleo aquí) o quizás incluso el estándar C Lib (glibc en la mayoría de los casos) que define esos tipos? Ya que si Linux o glibc los define, los GCC basados ​​en ese sistema no tienen más opción que adoptar las convenciones que estos establezcan. Lo mismo es cierto para todos los demás tipos de ancho variable: char, short, int, long, long long; todos estos tipos tienen solo un ancho de bits mínimo garantizado en C Standard (y para int en realidad es de 16 bits, por lo que en plataformas donde int es de 32 bits, ya es mucho más grande de lo que requeriría la norma).


Aparte de eso, en realidad me pregunto qué está mal con su CPU/compilador/sistema. En mi sistema, la multiplicación de 64 bits es igual de rápida que la multiplicación de 32 bits. He modificado el código para poner a prueba 16, 32 y 64 bits:

#include <time.h> 
#include <stdio.h> 
#include <inttypes.h> 

#define RUNS 100000 

#define TEST(type)         \ 
    static type test ## type()      \ 
    {            \ 
     int count;         \ 
     type p, x;         \ 
                \ 
     p = 1;          \ 
     for (count = RUNS; count != 0; count--) { \ 
      for (x = 1; x != 50000; x++) {   \ 
       p *= x;        \ 
      }          \ 
     }           \ 
     return p;         \ 
    } 

TEST(uint16_t) 
TEST(uint32_t) 
TEST(uint64_t) 

#define CLOCK_TO_SEC(clock) ((double)clockTime/CLOCKS_PER_SEC) 

#define RUN_TEST(type)        \ 
    {            \ 
     clock_t clockTime;       \ 
     unsigned long long result;     \ 
                \ 
     clockTime = clock();      \ 
     result = test ## type();     \ 
     clockTime = clock() - clockTime;   \ 
     printf("Test %s took %2.4f s. (%llu)\n", \ 
      #type, CLOCK_TO_SEC(clockTime), result \ 
     );           \ 
    } 

int main() 
{ 
    RUN_TEST(uint16_t) 
    RUN_TEST(uint32_t) 
    RUN_TEST(uint64_t) 
    return 0; 
} 

El uso de código no optimizado (-O0), me sale:

Test uint16_t took 13.6286 s. (0) 
Test uint32_t took 12.5881 s. (0) 
Test uint64_t took 12.6006 s. (0) 

El uso de código optimizado (O3), me sale:

Test uint16_t took 13.6385 s. (0) 
Test uint32_t took 4.5455 s. (0) 
Test uint64_t took 4.5382 s. (0) 

La segunda salida es bastante interesante. @R .. escribió en un comentario anterior:

En x86_64, 32 bits aritmética nunca debe ser más lenta de 64 bits aritmética, y punto.

El segundo resultado muestra que no se puede decir lo mismo para la aritmética de 32/16 bit. La aritmética de 16 bits puede ser significativamente más lenta en una CPU de 32/64 bits, aunque mi CPU x86 puede realizar de forma nativa una aritmética de 16 bits; a diferencia de algunas otras CPU, como un PPC, por ejemplo, que solo puede realizar aritmética de 32 bits. Sin embargo, esto solo parece aplicarse a la multiplicación en mi CPU, al cambiar el código para hacer la suma/resta/división, ya no hay diferencia significativa entre 16 y 32 bits.

Los resultados anteriores provienen de un Intel Core i7 (2,66 GHz), pero si alguien está interesado, puedo ejecutar este benchmark también en un Intel Core 2 Duo (una generación más anterior) y en un Motorola PowerPC G4.

2

El rendimiento real en el tiempo de ejecución es un tema muy complicado. Con muchos factores que van desde memoria RAM, discos duros, sistemas operativos; Y las muchas peculiaridades específicas del procesador.Pero esto le dará un funcionamiento áspero hacia abajo para usted:

N_fastX_t

  • tamaño óptimo para el cálculo de operaciones más (suma y resta) de manera eficiente para el procesador. Esto es específico del hardware, en el que las variables de 32 bits son nativas y más rápidas (y, por lo tanto, se usan) sobre las variables de 16 bits. (por ejemplo)
  • Como no se beneficia tan bien como N_leastX en términos de aciertos de caché, esto se debe usar principalmente cuando solo se necesita una sola variable lo más rápido posible. Si bien no se encuentra en una matriz grande (qué tan grande es óptima para cambiar entre ambos depende tristemente de la plataforma)
  • Tenga en cuenta que rápido contra menor tiene varios casos peculiares, principalmente multiplicación y divisiones. Eso es específico de la plataforma. Sin embargo, si la mayoría de las operaciones son adiciones/sustracciones/o/y. En general, es seguro asumir que rápido es más rápido. (Una vez más en cuenta la caché de la CPU y otra peculiaridad)

N_leastX_t

  • La variable más pequeño que el hardware lo permite, que es al menos del tamaño de X. (algunas plataformas no pueden asignar variables por debajo de 4 bytes, por ejemplo. De hecho, la mayoría de las variables BOOL ocupan al menos un byte, y no un poco)
  • Puede calcularse mediante una costosa emulación de software de CPU si no existe soporte de hardware .
  • Puede tener una penalización de rendimiento debido al soporte parcial de hardware (en comparación con el rápido) en una sola operación.
  • SIN EMBARGO: como ocupa menos espacio variable, puede golpear las líneas de caché con mucha más frecuencia. Esto es mucho más prominente en las matrices. Y como tal será más rápido (costo de la memoria> costo de la CPU) Consulte http://en.wikipedia.org/wiki/CPU_cache para obtener más detalles.

El problema de multiplicación?

También para responder por qué la variable fastX más grande sería más lenta en la multiplicación. Es causa debido a la naturaleza misma de la multiplicación. (Algo similar a lo que se pensaba en la escuela)

http://en.wikipedia.org/wiki/Binary_multiplier

//Assuming 4bit int 
    0011 (3 in decimal) 
x 0101 (5 in decimal) 
====== 
    0011 ("0011 x 0001") 
    0000- ("0011 x 0000") 
0011-- ("0011 x 0001") 
0000--- ("0011 x 0000") 
======= 
    1111 (15 in decimal) 

Sin embargo, es importante saber que una computadora es un "idiota lógica". Mientras que es obvio para nosotros los humanos saltear el paso de los ceros al final. La computadora todavía lo resolverá (es más barato que comprobar condicionalmente y luego resolverlo de todos modos). Por lo tanto, esto crea un capricho para una variable de mayor tamaño del mismo valor

//Assuming 8bit int 
     0000 0011 (3 in decimal) 
    x 0000 0101 (5 in decimal) 
    =========== 
     0000 0011 ("0011 x 0001") 
    0 0000 000- ("0011 x 0000") 
    00 0000 11-- ("0011 x 0001") 
    000 0000 0--- ("0011 x 0000") 
0000 0000 ---- (And the remainders of zeros) 
-------------- (Will all be worked out) 
============== 
     0000 1111 (15 in decimal) 

Mientras que no SPAM a cabo las adiciones resto 0x0 en el proceso de multiplicación. Es importante tener en cuenta que la computadora "los hará". Y, por lo tanto, es natural que una multiplicación variable mayor lleve más tiempo que su contraparte más pequeña. (Por lo tanto, siempre es bueno evitar la multiplicación y las divisiones siempre que sea posible).

Sin embargo, aquí viene la segunda peculiaridad. Es posible que no se aplique a todos los procesadores. Es importante tener en cuenta que todas las operaciones de CPU se cuentan en ciclos de CPU.En el cual en cada ciclo se realizan docenas (o más) de tales operaciones de adiciones pequeñas como se ha visto anteriormente. Como resultado, una adición de 8 bits puede tomar la misma cantidad de tiempo que una multiplicación de 8 bits, y etc. debido a las diversas optimizaciones y peculiaridades específicas de la CPU.

Si te preocupa tanto. Ve a referirse a Intel: http://www.intel.com/content/www/us/en/processors/architectures-software-developer-manuals.html


mención adicional sobre el CPU vs RAM

Como CPU han adelantado a la Ley de Moore a ser varias veces más rápido que la memoria RAM DDR3.

Esto puede dar lugar a situaciones en las que se gasta más tiempo buscando la variable desde el RAM y luego a la CPU "cómpralo". Esto es más prominente en las cadenas de punteros largos.

Por lo tanto, mientras que una memoria caché de CPU existe en la mayoría de los procesadores para reducir el tiempo de "búsqueda RAM". Sus usos se limitan a casos específicos (donde la línea de caché se beneficia más). Y para los casos en los que no encaja. Tenga en cuenta que el tiempo de búsqueda de la RAM> Tiempo de procesamiento de la CPU (excluyendo multiplicación/divisiones/algunas peculiaridades)

1

Solo porque tenía curiosidad por los tipos enteros rápidos que comparaté con un analizador de la vida real que, en su parte semántica, utilizaba un tipo entero para indexar matrices y C++ - contenedores. Se realizó una combinación de operaciones en lugar de un bucle simple y la mayor parte del programa no dependía del tipo de entero elegido. En realidad, para mis datos particulares, cualquier tipo de entero habría estado bien. Entonces, todas las versiones produjeron el mismo resultado.

En el nivel de ensamblaje hay 8 cajas: cuatro para los tamaños y 2 para la firma. Los 24 nombres de tipo ISO C se deben asignar a los ocho tipos básicos. Como Jens ya declaró una asignación "buena" debe considerar el procesador particular y el código particular. Por lo tanto, en la práctica, no deberíamos esperar resultados perfectos aunque los escritores del compilador deberían conocer el código generado.

Se promediaron muchas ejecuciones del ejemplo, de modo que el rango de fluctuación del tiempo de ejecución es aproximadamente 2 del dígito menos dado. Para esta configuración particular, los resultados fueron los siguientes:

  • No hay diferencia entre el tiempo de ejecución int16_t/uint16_t y int64_t/uint64_t respectivamente.
  • Las versiones sin firmar son mucho más rápidas para int8_t/uint8_t y int32_t/uint32_t respectivamente.
  • Las versiones sin firmar son siempre más pequeñas (texto y segmento de datos) que las versiones firmadas.

Compilador: g ++ 4.9.1, Opciones: -O3 mtune = -march genérico = x86-64

CPU: Intel ™ Core ™ 2 Duo E8400 @ 3.00GHz

El mapeo

 
| |Integer|                  | 
|Sign|Size | Types                | 
| |[bits] |                  | 
|:--:|------:|:-------------------------------------------------------------------:| 
| u | 8 | uint8_t uint_fast8_t uint_least8_t        | 
| s | 8 | int8_t int_fast8_t int_least8_t        | 
| u | 16 | uint16_t uint_least16_t            | 
| s | 16 | int16_t int_least16_t            | 
| u | 32 | uint32_t uint_least32_t            | 
| s | 32 | int32_t int_least32_t            | 
| u | 64 | uint64_t uint_fast16_t uint_fast32_t uint_fast64_t uint_least64_t | 
| s | 64 | int64_t int_fast16_t int_fast32_t int_fast64_t int_least64_t | 

Tamaños y sincronizaciones

 
|  | Integer |   |  |  |   | 
| Sign | Size | text | data | bss | Time | 
|  | [bits] | [bytes] |[bytes]|[bytes]| [ms] | 
|:----:|--------:|--------:| -----:|------:|--------:| 
| u | 8 | 1285801 | 3024 | 5704 | 407.61 | 
| s | 8 | 1285929 | 3032 | 5704 | 412.39 | 
| u | 16 | 1285833 | 3024 | 5704 | 408.81 | 
| s | 16 | 1286105 | 3040 | 5704 | 408.80 | 
| u | 32 | 1285609 | 3024 | 5704 | 406.78 | 
| s | 32 | 1285921 | 3032 | 5704 | 413.30 | 
| u | 64 | 1285557 | 3032 | 5704 | 410.12 | 
| s | 64 | 1285824 | 3048 | 5704 | 410.13 | 
Cuestiones relacionadas