c++ - mejor - uint16_t que es

¿Cuál es el impacto en el rendimiento del uso de int64_t en lugar de int32_t en sistemas de 32 bits? (4)

Nuestra biblioteca C ++ actualmente usa time_t para almacenar valores de tiempo. Estoy empezando a necesitar una precisión de menos de segundo en algunos lugares, por lo que un tipo de datos más grande será necesario allí de todos modos. Además, podría ser útil sortear el problema del Año 2038 en algunos lugares. Así que estoy pensando en cambiar completamente a una única clase de tiempo con un valor int64_t subyacente, para reemplazar el valor de time_t en todos los lugares.

Ahora me pregunto sobre el impacto en el rendimiento de dicho cambio cuando ejecuto este código en un sistema operativo de 32 bits o una CPU de 32 bits. IIUC el compilador generará código para realizar aritmética de 64 bits utilizando registros de 32 bits. Pero si esto es demasiado lento, podría tener que usar una forma más diferenciada para manejar los valores de tiempo, lo que podría hacer que el software sea más difícil de mantener.

Lo que me interesa:

¿Qué factores influyen en el rendimiento de estas operaciones? Probablemente el compilador y la versión del compilador; pero, ¿el sistema operativo o la marca / modelo de CPU también influyen en esto? ¿Utilizará un sistema normal de 32 bits los registros de 64 bits de las CPU modernas?
¿Qué operaciones serán especialmente lentas cuando se emulan en 32 bits? ¿O que casi no tendrá desaceleración?
¿hay algún resultado de referencia existente para usar int64_t / uint64_t en sistemas de 32 bits?
¿Alguien tiene experiencia propia sobre este impacto en el rendimiento?

Estoy principalmente interesado en g ++ 4.1 y 4.4 en Linux 2.6 (RHEL5, RHEL6) en sistemas Intel Core 2; pero también sería bueno conocer la situación de otros sistemas (como Sparc Solaris + Solaris CC, Windows + MSVC).

¿Qué factores influyen en el rendimiento de estas operaciones? Probablemente el compilador y la versión del compilador; pero, ¿el sistema operativo o la marca / modelo de CPU también influyen en esto?

Principalmente la arquitectura del procesador (y el modelo; lea el modelo donde menciono la arquitectura del procesador en esta sección). El compilador puede tener alguna influencia, pero la mayoría de los compiladores lo hacen bastante bien, por lo que la arquitectura del procesador tendrá una influencia mayor que la del compilador.

El sistema operativo no tendrá influencia alguna (aparte de "si cambia el sistema operativo, necesita usar un tipo diferente de compilador que cambie lo que hace el compilador" en algunos casos, pero eso probablemente sea un efecto pequeño).

¿Utilizará un sistema normal de 32 bits los registros de 64 bits de las CPU modernas?

Esto no es posible. Si el sistema está en modo de 32 bits, actuará como un sistema de 32 bits, los 32 bits adicionales de los registros son completamente invisibles, tal como lo sería si el sistema fuera en realidad un "verdadero sistema de 32 bits". .

¿Qué operaciones serán especialmente lentas cuando se emulan en 32 bits? ¿O que casi no tendrá desaceleración?

La suma y la resta son peores, ya que deben realizarse en secuencia de dos operaciones, y la segunda operación requiere que la primera haya finalizado; este no es el caso si el compilador solo está produciendo dos operaciones de adición en datos independientes.

La multiplicidad empeorará mucho si los parámetros de entrada son realmente de 64 bits, por lo que 2 ^ 35 * 83 es peor que 2 ^ 31 * 2 ^ 31, por ejemplo. Esto se debe al hecho de que el procesador puede producir una multiplicación de 32 x 32 bits en un resultado de 64 bits bastante bien, unos 5-10 ciclos de reloj. Pero una multiplicación de 64 x 64 bits requiere un poco de código adicional, por lo que llevará más tiempo.

La división es un problema similar a la multiplicación, pero aquí está bien tomar una entrada de 64 bits por un lado, dividirla por un valor de 32 bits y obtener un valor de 32 bits. Como es difícil predecir cuándo funcionará, la división de 64 bits es casi siempre lenta.

Los datos también tomarán el doble de espacio de caché, lo que puede afectar los resultados. Y, como consecuencia similar, la asignación general y la transferencia de datos tardarán el doble que un mínimo, ya que hay el doble de datos para operar.

El compilador también necesitará usar más registros.

¿hay algún resultado de referencia existente para usar int64_t / uint64_t en sistemas de 32 bits?

Probablemente, pero no estoy al tanto de ninguno. E incluso si lo hubiera, solo sería significativo para usted, ya que la combinación de operaciones es ALTAMENTE crítica para la velocidad de las operaciones.

Si el rendimiento es una parte importante de su aplicación, compare su código (o una parte representativa de él). Realmente no importa si el Benchmark X arroja resultados de 5%, 25% o 103% más lentos, si su código es una cantidad completamente diferente, más lenta o más rápida en las mismas circunstancias.

¿Alguien tiene experiencia propia sobre este impacto en el rendimiento?

He recompilado un código que usa enteros de 64 bits para la arquitectura de 64 bits, y encontré que el rendimiento mejora en una cantidad sustancial, hasta un 25% en algunos bits de código.

¿Cambiar su sistema operativo a una versión de 64 bits del mismo sistema operativo, podría ayudar, tal vez?

Editar:

Como me gusta averiguar cuál es la diferencia en este tipo de cosas, he escrito un poco de código, y con una plantilla primitiva (todavía estoy aprendiendo ese bit, las plantillas no son exactamente mi tema más candente, debo decir, dame el bitfiddling y la aritmética del puntero, y lo haré (generalmente) bien ...)

Aquí está el código que escribí, tratando de replicar algunos funcionamientos comunes:

#include <iostream> #include <cstdint> #include <ctime> using namespace std; static __inline__ uint64_t rdtsc(void) { unsigned hi, lo; __asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi)); return ( (uint64_t)lo)|( ((uint64_t)hi)<<32 ); } template<typename T> static T add_numbers(const T *v, const int size) { T sum = 0; for(int i = 0; i < size; i++) sum += v[i]; return sum; } template<typename T, const int size> static T add_matrix(const T v[size][size]) { T sum[size] = {}; for(int i = 0; i < size; i++) { for(int j = 0; j < size; j++) sum[i] += v[i][j]; } T tsum=0; for(int i = 0; i < size; i++) tsum += sum[i]; return tsum; } template<typename T> static T add_mul_numbers(const T *v, const T mul, const int size) { T sum = 0; for(int i = 0; i < size; i++) sum += v[i] * mul; return sum; } template<typename T> static T add_div_numbers(const T *v, const T mul, const int size) { T sum = 0; for(int i = 0; i < size; i++) sum += v[i] / mul; return sum; } template<typename T> void fill_array(T *v, const int size) { for(int i = 0; i < size; i++) v[i] = i; } template<typename T, const int size> void fill_array(T v[size][size]) { for(int i = 0; i < size; i++) for(int j = 0; j < size; j++) v[i][j] = i + size * j; } uint32_t bench_add_numbers(const uint32_t v[], const int size) { uint32_t res = add_numbers(v, size); return res; } uint64_t bench_add_numbers(const uint64_t v[], const int size) { uint64_t res = add_numbers(v, size); return res; } uint32_t bench_add_mul_numbers(const uint32_t v[], const int size) { const uint32_t c = 7; uint32_t res = add_mul_numbers(v, c, size); return res; } uint64_t bench_add_mul_numbers(const uint64_t v[], const int size) { const uint64_t c = 7; uint64_t res = add_mul_numbers(v, c, size); return res; } uint32_t bench_add_div_numbers(const uint32_t v[], const int size) { const uint32_t c = 7; uint32_t res = add_div_numbers(v, c, size); return res; } uint64_t bench_add_div_numbers(const uint64_t v[], const int size) { const uint64_t c = 7; uint64_t res = add_div_numbers(v, c, size); return res; } template<const int size> uint32_t bench_matrix(const uint32_t v[size][size]) { uint32_t res = add_matrix(v); return res; } template<const int size> uint64_t bench_matrix(const uint64_t v[size][size]) { uint64_t res = add_matrix(v); return res; } template<typename T> void runbench(T (*func)(const T *v, const int size), const char *name, T *v, const int size) { fill_array(v, size); uint64_t long t = rdtsc(); T res = func(v, size); t = rdtsc() - t; cout << "result = " << res << endl; cout << name << " time in clocks " << dec << t << endl; } template<typename T, const int size> void runbench2(T (*func)(const T v[size][size]), const char *name, T v[size][size]) { fill_array(v); uint64_t long t = rdtsc(); T res = func(v); t = rdtsc() - t; cout << "result = " << res << endl; cout << name << " time in clocks " << dec << t << endl; } int main() { // spin up CPU to full speed... time_t t = time(NULL); while(t == time(NULL)) ; const int vsize=10000; uint32_t v32[vsize]; uint64_t v64[vsize]; uint32_t m32[100][100]; uint64_t m64[100][100]; runbench(bench_add_numbers, "Add 32", v32, vsize); runbench(bench_add_numbers, "Add 64", v64, vsize); runbench(bench_add_mul_numbers, "Add Mul 32", v32, vsize); runbench(bench_add_mul_numbers, "Add Mul 64", v64, vsize); runbench(bench_add_div_numbers, "Add Div 32", v32, vsize); runbench(bench_add_div_numbers, "Add Div 64", v64, vsize); runbench2(bench_matrix, "Matrix 32", m32); runbench2(bench_matrix, "Matrix 64", m64); }

Compilado con:

g++ -Wall -m32 -O3 -o 32vs64 32vs64.cpp -std=c++0x

Y los resultados son: Nota: Vea los resultados de 2016 a continuación : estos resultados son ligeramente optimistas debido a la diferencia en el uso de las instrucciones de SSE en el modo de 64 bits, pero no al uso de SSE en el modo de 32 bits.

result = 49995000 Add 32 time in clocks 20784 result = 49995000 Add 64 time in clocks 30358 result = 349965000 Add Mul 32 time in clocks 30182 result = 349965000 Add Mul 64 time in clocks 79081 result = 7137858 Add Div 32 time in clocks 60167 result = 7137858 Add Div 64 time in clocks 457116 result = 49995000 Matrix 32 time in clocks 22831 result = 49995000 Matrix 64 time in clocks 23823

Como puede ver, la suma y la multiplicación no son mucho peores. La división se pone realmente mal. Curiosamente, la suma de la matriz no es mucha diferencia en absoluto.

Y es más rápido en 64 bits, oigo que algunos de ustedes preguntan: Usando las mismas opciones de compilación, solo -m64 en vez de -m32-yupp, mucho más rápido:

result = 49995000 Add 32 time in clocks 8366 result = 49995000 Add 64 time in clocks 16188 result = 349965000 Add Mul 32 time in clocks 15943 result = 349965000 Add Mul 64 time in clocks 35828 result = 7137858 Add Div 32 time in clocks 50176 result = 7137858 Add Div 64 time in clocks 50472 result = 49995000 Matrix 32 time in clocks 12294 result = 49995000 Matrix 64 time in clocks 14733

Editar, actualizar para 2016 : cuatro variantes, con y sin SSE, en el modo de compilación de 32 y 64 bits.

Normalmente estoy usando clang ++ como mi compilador habitual en estos días. Intenté compilar con g ++ (pero seguiría siendo una versión diferente a la anterior, ya que actualicé mi máquina y también tengo una CPU diferente). Dado que g ++ no compiló la versión no-sse en 64 bits, no vi el punto en eso. (g ++ da resultados similares de todos modos)

Como una tabla corta:

Test name | no-sse 32 | no-sse 64 | sse 32 | sse 64 | ---------------------------------------------------------- Add uint32_t | 20837 | 10221 | 3701 | 3017 | ---------------------------------------------------------- Add uint64_t | 18633 | 11270 | 9328 | 9180 | ---------------------------------------------------------- Add Mul 32 | 26785 | 18342 | 11510 | 11562 | ---------------------------------------------------------- Add Mul 64 | 44701 | 17693 | 29213 | 16159 | ---------------------------------------------------------- Add Div 32 | 44570 | 47695 | 17713 | 17523 | ---------------------------------------------------------- Add Div 64 | 405258 | 52875 | 405150 | 47043 | ---------------------------------------------------------- Matrix 32 | 41470 | 15811 | 21542 | 8622 | ---------------------------------------------------------- Matrix 64 | 22184 | 15168 | 13757 | 12448 |

Resultados completos con opciones de compilación.

$ clang++ -m32 -mno-sse 32vs64.cpp --std=c++11 -O2 $ ./a.out result = 49995000 Add 32 time in clocks 20837 result = 49995000 Add 64 time in clocks 18633 result = 349965000 Add Mul 32 time in clocks 26785 result = 349965000 Add Mul 64 time in clocks 44701 result = 7137858 Add Div 32 time in clocks 44570 result = 7137858 Add Div 64 time in clocks 405258 result = 49995000 Matrix 32 time in clocks 41470 result = 49995000 Matrix 64 time in clocks 22184 $ clang++ -m32 -msse 32vs64.cpp --std=c++11 -O2 $ ./a.out result = 49995000 Add 32 time in clocks 3701 result = 49995000 Add 64 time in clocks 9328 result = 349965000 Add Mul 32 time in clocks 11510 result = 349965000 Add Mul 64 time in clocks 29213 result = 7137858 Add Div 32 time in clocks 17713 result = 7137858 Add Div 64 time in clocks 405150 result = 49995000 Matrix 32 time in clocks 21542 result = 49995000 Matrix 64 time in clocks 13757 $ clang++ -m64 -msse 32vs64.cpp --std=c++11 -O2 $ ./a.out result = 49995000 Add 32 time in clocks 3017 result = 49995000 Add 64 time in clocks 9180 result = 349965000 Add Mul 32 time in clocks 11562 result = 349965000 Add Mul 64 time in clocks 16159 result = 7137858 Add Div 32 time in clocks 17523 result = 7137858 Add Div 64 time in clocks 47043 result = 49995000 Matrix 32 time in clocks 8622 result = 49995000 Matrix 64 time in clocks 12448 $ clang++ -m64 -mno-sse 32vs64.cpp --std=c++11 -O2 $ ./a.out result = 49995000 Add 32 time in clocks 10221 result = 49995000 Add 64 time in clocks 11270 result = 349965000 Add Mul 32 time in clocks 18342 result = 349965000 Add Mul 64 time in clocks 17693 result = 7137858 Add Div 32 time in clocks 47695 result = 7137858 Add Div 64 time in clocks 52875 result = 49995000 Matrix 32 time in clocks 15811 result = 49995000 Matrix 64 time in clocks 15168

La suma / resta básicamente se convierte en dos ciclos cada uno, la multiplicación y la división dependen de la CPU real. El impacto general del rendimiento será bastante bajo.

Tenga en cuenta que Intel Core 2 es compatible con EM64T.

Más de lo que siempre quiso saber sobre matemática de 64 bits en modo de 32 bits ...

Cuando utiliza números de 64 bits en el modo de 32 bits (incluso en la CPU de 64 bits si se compila un código de 32 bits), se almacenan como dos números de 32 bits separados, uno que almacena bits más altos de un número, y otro almacenando bits inferiores El impacto de esto depende de una instrucción. (tl; dr - en general, hacer cálculos matemáticos de 64 bits en una CPU de 32 bits es, en teoría, 2 veces más lento, siempre que no se divida / módulo, sin embargo, en la práctica, la diferencia será menor (1,3x sería mi adivinar), porque generalmente los programas no solo hacen cálculos matemáticos en enteros de 64 bits, y también debido a la canalización, la diferencia puede ser mucho menor en su programa.

Suma resta

Muchas arquitecturas soportan la llamada bandera de acarreo . Se establece cuando el resultado de la suma se desborda, o el resultado de la resta no se desborda. El comportamiento de esos bits se puede mostrar con una larga suma y una larga resta. C en este ejemplo muestra ya sea un poco más alto que el bit representable más alto (durante la operación), o una bandera de acarreo (después de la operación).

C 7 6 5 4 3 2 1 0 C 7 6 5 4 3 2 1 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 + 0 0 0 0 0 0 0 1 - 0 0 0 0 0 0 0 1 = 1 0 0 0 0 0 0 0 0 = 0 1 1 1 1 1 1 1 1

¿Por qué es relevante la bandera de acarreo? Bueno, sucede que las CPU generalmente tienen dos operaciones de suma y resta separadas. En x86, las operaciones de adición se llaman add y adc . add stands para agregar, mientras que adc para agregar con carry. La diferencia entre ellos es que adc considera un bit de acarreo, y si está configurado, agrega uno al resultado.

Del mismo modo, la resta con acarreo resta 1 del resultado si no se establece el bit de acarreo.

Este comportamiento permite implementar fácilmente sumas y restas de tamaño arbitrarias en enteros. El resultado de la suma de xey (suponiendo que sean de 8 bits) nunca es mayor que 0x1FE . Si agrega 1 , obtiene 0x1FF . Por lo tanto, 9 bits es suficiente para representar los resultados de cualquier adición de 8 bits. Si comienza la adición con add , y luego agrega cualquier bit más allá de los iniciales con adc , puede hacer una adición en cualquier tamaño de datos que desee.

La adición de dos valores de 64 bits en la CPU de 32 bits es la siguiente.

Agregue los primeros 32 bits de b a los primeros 32 bits de a .
Agregue con carry más tarde 32 bits de b a 32 bits de a más adelante.

Analógicamente para la resta.

Esto da 2 instrucciones, sin embargo, debido al pipeline de instrucciones , puede ser más lento que eso, ya que un cálculo depende del otro para finalizar, por lo que si la CPU no tiene nada más que hacer que una adición de 64 bits, la CPU puede esperar para la primera adición que se hará.

Multiplicación

Ocurre en x86 que imul y mul se pueden usar de tal manera que el desbordamiento se almacena en el registro edx . Por lo tanto, multiplicar dos valores de 32 bits para obtener un valor de 64 bits es realmente fácil. Tal multiplicación es una instrucción, pero para hacer uso de ella, uno de los valores de multiplicación debe almacenarse en eax .

De todos modos, para un caso más general de multiplicación de dos valores de 64 bits, se pueden calcular con la siguiente fórmula (se supone que la función r elimina bits más allá de 32 bits).

En primer lugar, es fácil notar que los 32 bits más bajos de un resultado serán la multiplicación de 32 bits más bajos de variables multiplicadas. Esto se debe a la relación de congruencia.

a ₁ ≡ b ₁ (mod n )
a ₂ ≡ b ₂ (mod n )
a ₁ a ₂ ≡ b ₁ b ₂ (mod n )

Por lo tanto, la tarea se limita a determinar los 32 bits superiores. Para calcular 32 bits más altos de un resultado, los siguientes valores deben sumarse.

Mayores 32 bits de multiplicación de ambos 32 bits más bajos (desbordamiento que la CPU puede almacenar en edx )
Mayores 32 bits de la primera variable mulitplied con 32 bits más bajos de la segunda variable
Baje 32 bits de la primera variable multiplicada por 32 bits más alta de la segunda variable

Esto da alrededor de 5 instrucciones, sin embargo, debido a la cantidad relativamente limitada de registros en x86 (ignorando las extensiones de una arquitectura), no pueden aprovecharse demasiado de la canalización. Habilite SSE si desea mejorar la velocidad de multiplicación, ya que esto aumenta el número de registros.

División / Módulo (ambos son similares en implementación)

No sé cómo funciona, pero es mucho más complejo que la suma, la resta o incluso la multiplicación. Sin embargo, es probable que sea diez veces más lento que la división en la CPU de 64 bits. Consulte "Arte de la programación de computadoras, Volumen 2: Algoritmos de Seminumerical", página 257 para obtener más detalles si puede entenderlo (no puedo, de ninguna manera, explicarlo, desafortunadamente).

Si divide por una potencia de 2, consulte la sección de desplazamiento, porque eso es a lo que básicamente el compilador puede optimizar la división (además de agregar el bit más significativo antes de cambiar para los números con signo).

O / Y / Xor

Teniendo en cuenta que esas operaciones son operaciones de un solo bit, aquí no sucede nada especial, solo la operación a nivel de bit se realiza dos veces.

Cambiando a la izquierda / derecha

Curiosamente, x86 en realidad tiene una instrucción para realizar un desplazamiento a la izquierda de 64 bits llamado shld , que en lugar de reemplazar los bits de valor menos significativos con ceros, los reemplaza con los bits más significativos de un registro diferente. Del mismo modo, es el caso del cambio a la derecha con la instrucción shrd . Esto haría fácilmente que el cambio de 64 bits sea una operación de dos instrucciones.

Sin embargo, eso es solo un caso de cambios constantes. Cuando un cambio no es constante, las cosas se vuelven más complejas, ya que la arquitectura x86 solo admite el cambio con 0-31 como valor. Cualquier cosa más allá de eso está de acuerdo con la documentación oficial indefinida, y en la práctica, bitwise y la operación con 0x1F se realiza en un valor. Por lo tanto, cuando un valor de desplazamiento es mayor que 31, uno de los almacenamientos de valores se borra por completo (para el desplazamiento a la izquierda, es decir, para bytes más bajos, para el desplazamiento a la derecha, es decir, para bytes mayores). El otro obtiene el valor que estaba en el registro que se borró, y luego se realiza la operación de cambio. Esto en resultado, depende del predictor de bifurcación para hacer buenas predicciones, y es un poco más lento porque se debe verificar un valor.

__builtin_popcount [ll]

__builtin_popcount (inferior) + __builtin_popcount (superior)

Otros builtins

Soy demasiado flojo para terminar la respuesta en este punto. ¿Alguien siquiera usa eso?

Unsigned vs signed

Suma, resta, multiplicación, o, y, xor, shift left generan exactamente el mismo código. Shift right utiliza solo un código ligeramente diferente (desplazamiento aritmético vs. cambio lógico), pero estructuralmente es lo mismo. Sin embargo, es probable que la división genere un código diferente, y es probable que la división firmada sea más lenta que la división sin firmar.

Puntos de referencia

¿Puntos de referencia? En su mayoría, carecen de sentido, ya que la canalización de instrucciones suele llevar a que las cosas sean más rápidas cuando no se repite constantemente la misma operación. Siéntase libre de considerar la división lenta, pero nada más es así, y cuando se sale de los puntos de referencia, puede observar que debido a la canalización, realizar operaciones de 64 bits en la CPU de 32 bits no es para nada lento.

Compare su propia aplicación, no confíe en los micro-puntos de referencia que no hacen lo que hace su aplicación. Las CPU modernas son bastante complicadas, por lo que los puntos de referencia no relacionados pueden y tenderán a mentir.

Tu pregunta suena bastante extraña en su entorno. Usas time_t que usa hasta 32 bits. Necesitas información adicional, lo que significa más bits. Entonces estás obligado a usar algo más grande que int32. No importa cuál sea el rendimiento, ¿verdad? Las opciones irán entre usar 40 bits o seguir hasta int64. A menos que se almacenen millones de instancias, esta última es una elección sensata.

Como otros señalaron, la única forma de conocer el verdadero rendimiento es medirlo con un generador de perfiles (en algunas muestras brutas, un reloj sencillo funcionará). así que adelante y mida. No debe ser difícil reubicar globalmente su time_t usage a un typedef y redefinirlo a 64 bit y arreglar las pocas instancias donde se esperaba time_t real.

Mi apuesta sería la "diferencia no medible" a menos que sus instancias time_t actuales ocupen al menos unos pocos megas de memoria. en las plataformas actuales tipo Intel, los núcleos pasan la mayor parte del tiempo esperando que la memoria externa entre en la memoria caché. Una caché única se bloquea por cientos de ciclos. Lo que hace que el cálculo de las diferencias de 1 tick en las instrucciones no sea factible. Su rendimiento real puede disminuir debido a que su estructura actual solo encaja en una línea de caché y la más grande necesita dos. Y si nunca midió su rendimiento actual, es posible que descubra que puede obtener una aceleración extrema de algunos funcitons simplemente agregando alguna alineación o orden de intercambio de algunos miembros en una estructura. O empaque (1) la estructura en lugar de usar el diseño predeterminado ...