c++ - lenguaje - multiplicar int por float java

¿Cómo acelerar la conversión de número flotante a número entero?

Question

Esta pregunta ya tiene una respuesta aquí:

• ¿Cuál es la forma más rápida de convertir float a int en x86 10 respuestas

Estamos haciendo una gran cantidad de conversiones de números de punto flotante a entero en nuestro proyecto. Básicamente, algo como esto

for(int i = 0; i < HUGE_NUMBER; i++)
     int_array[i] = float_array[i];

La función C predeterminada que realiza la conversión resulta bastante lenta.

¿Hay alguna solución alternativa (tal vez una función ajustada a mano) que puede acelerar un poco el proceso? No nos importa mucho una precisión.

Answer 1

En Visual C ++ 2008, el compilador genera llamadas SSE2 por sí mismo, si usted hace una compilación de lanzamiento con opciones de optimización al máximo, y mira un desmontaje (aunque se deben cumplir algunas condiciones, juegue con su código).

Answer 2

Es posible que pueda cargar todos los enteros en el módulo SSE de su procesador usando algún código ensamblador mágico, luego haga el código equivalente para establecer los valores en ints, luego léelos como flotantes. Sin embargo, no estoy seguro de que esto sea más rápido. No soy un gurú SSE, así que no sé cómo hacer esto. Tal vez alguien más pueda entrar.

Answer 3

Hay una instrucción FISTTP en el conjunto de instrucciones SSE3 que hace lo que usted desea, pero en cuanto a si podría utilizarse o no y producir resultados más rápidos que libc, no tengo ni idea.

Answer 4

Qué compilador estas usando? En los compiladores C / C ++ más recientes de Microsoft, hay una opción en C / C ++ -> Generación de código -> Modelo de punto flotante, que tiene opciones: rápido, preciso, estricto. Creo que el valor predeterminado es el predeterminado, y funciona emulando las operaciones de FP hasta cierto punto. Si está utilizando un compilador de MS, ¿cómo se establece esta opción? ¿Ayuda establecerlo a "rápido"? En cualquier caso, ¿cómo se ve el desmontaje?

Como dijo treinta y siete arriba, la CPU puede convertir float<->int en esencialmente una instrucción, y no puede ser más rápido que eso (excepto una operación SIMD).

También tenga en cuenta que las CPU modernas usan la misma unidad FP para números FP simples (32 bits) y dobles (64 bits), por lo que a menos que intente guardar memoria almacenando muchos flotadores, realmente no hay razón para favorecer la float sobre el doble.

Answer 5

En Intel, su mejor opción son las llamadas en línea SSE2.

Answer 6

inline int float2int( double d )
{
   union Cast
   {
      double d;
      long l;
    };
   volatile Cast c;
   c.d = d + 6755399441055744.0;
   return c.l;
}

// this is the same thing but it''s
// not always optimizer safe
inline int float2int( double d )
{
   d += 6755399441055744.0;
   return reinterpret_cast<int&>(d);
}

for(int i = 0; i < HUGE_NUMBER; i++)
     int_array[i] = float2int(float_array[i]);

¡El doble parámetro no es un error! Hay una forma de hacer este truco con flotadores directamente, pero se pone feo tratando de cubrir todos los casos de esquina. En su forma actual, esta función redondeará el flotante al número entero más cercano si desea el truncamiento, en su lugar use 6755399441055743.5 (0.5 menos).

Answer 7

¿Es el tiempo lo suficientemente grande como para compensar el costo de comenzar un par de hilos?

Suponiendo que tiene un procesador multi-core o múltiples procesadores en su caja que podría aprovechar, sería una tarea trivial para paralelizar a través de múltiples hilos.

Answer 8

Consulte este artículo de Intel para acelerar las conversiones de enteros:

http://software.intel.com/en-us/articles/latency-of-floating-point-to-integer-conversions/

Según Microsoft, la opción del compilador / QIfist está en desuso en VS 2005 porque se ha acelerado la conversión de entero. Se olvidan de decir cómo se ha acelerado, pero mirar la lista de desmontaje podría dar una pista.

http://msdn.microsoft.com/en-us/library/z8dh4h17(vs.80).aspx

Answer 9

Estoy sorprendido por tu resultado. Qué compilador estas usando? ¿Está compilando con la optimización completa? ¿Has confirmado el uso de valgrind y Kcachegrind que aquí es donde está el cuello de botella? ¿Qué procesador estás usando? ¿Cómo se ve el código ensamblador?

La conversión en sí misma debe compilarse en una sola instrucción. Un buen compilador de optimización debería desenrollar el bucle para que se realicen varias conversiones por prueba y rama. Si eso no sucede, puede desenrollar el ciclo a mano :

for(int i = 0; i < HUGE_NUMBER-3; i += 4) {
     int_array[i]   = float_array[i];
     int_array[i+1] = float_array[i+1];
     int_array[i+2] = float_array[i+2];
     int_array[i+3] = float_array[i+3];
}
for(; i < HUGE_NUMBER; i++)
     int_array[i]   = float_array[i];

Si su compilador es realmente patético, es posible que deba ayudarlo con las subexpresiones comunes, por ejemplo,

int *ip = int_array+i;
float *fp = float_array+i;
ip[0] = fp[0];
ip[1] = fp[1];
ip[2] = fp[2];
ip[3] = fp[3];

¡Reporte con más información!

Answer 10

La clave es evitar la función _ftol (), que es innecesariamente lenta. La mejor opción para largas listas de datos como esta es usar la instrucción SSE2 cvtps2dq para convertir dos flotadores empaquetados a dos int64 comprimidos. Haga esto dos veces (obteniendo cuatro int64s en dos registros SSE) y puede mezclarlos para obtener cuatro int32s (perdiendo los 32 primeros bits de cada resultado de conversión). No necesita ensamblaje para hacer esto; MSVC expone los intrínsecos del compilador a las instrucciones relevantes - _mm_cvtpd_epi32 () si mi memoria me sirve correctamente.

Si hace esto, es muy importante que sus arrays float e int estén alineados en 16 bytes para que los intrínsecos de carga / almacenamiento de SSE2 puedan funcionar con la máxima eficiencia. Además, recomiendo un poco de canalización de software y procesaremos dieciséis flotantes a la vez en cada bucle, por ejemplo (suponiendo que las "funciones" aquí son en realidad llamadas a los intrínsecos del compilador):

for(int i = 0; i < HUGE_NUMBER; i+=16)
{
//int_array[i] = float_array[i];
   __m128 a = sse_load4(float_array+i+0);
   __m128 b = sse_load4(float_array+i+4);
   __m128 c = sse_load4(float_array+i+8);
   __m128 d = sse_load4(float_array+i+12);
   a = sse_convert4(a);
   b = sse_convert4(b);
   c = sse_convert4(c);
   d = sse_convert4(d);
   sse_write4(int_array+i+0, a);
   sse_write4(int_array+i+4, b);
   sse_write4(int_array+i+8, c);
   sse_write4(int_array+i+12, d);
}

La razón de esto es que las instrucciones SSE tienen una latencia larga, por lo que si sigue una carga en xmm0 inmediatamente con una operación dependiente en xmm0, entonces tendrá un bloqueo. Tener varios registros "en vuelo" a la vez oculta un poco la latencia. (Teóricamente, un compilador mágico que todo lo sabe podría aliar su camino alrededor de este problema, pero en la práctica no lo hace).

Al fallar este SSE juju, puede suministrar la opción / QIfist a MSVC, lo que hará que emita el puño de código de operación en lugar de una llamada a _ftol; esto significa que simplemente usará el modo de redondeo que se establezca en la CPU sin asegurarse de que sea la operación truncada específica de ANSI C. Los documentos de Microsoft dicen que / QIfist está en desuso porque su código de punto flotante es rápido ahora, pero un desensamblador le mostrará que esto es injustificadamente optimista. Even / fp: fast simplemente resulta en una llamada a _ftol_sse2, que aunque más rápido que el atroz _ftol sigue siendo una llamada de función seguida de una operación SSE latente, y por lo tanto innecesariamente lenta.

Supongo que estás en x86 arch, por cierto, si estás en PPC hay operaciones equivalentes de VMX, o puedes usar el truco de multiplicación de magia mencionado anteriormente seguido de un vsel (para enmascarar el bits no de mantisa) y una tienda alineada.

Answer 11

la mayoría de los compiladores de c generan llamadas a _ftol o algo por cada conversión de float a int. poner un interruptor de conformidad de coma flotante reducido (como fp: rápido) podría ayudar, SI entiende Y acepta los otros efectos de este interruptor. aparte de eso, coloque la cosa en un ensamblaje ajustado o un lazo intrínseco sse, SI usted está bien Y entienda el comportamiento de redondeo diferente. para bucles grandes como el ejemplo, debe escribir una función que configure palabras de control de coma flotante una vez y luego realice el redondeo al por mayor con solo instrucciones de puño y luego restablezca la palabra de control - SI está bien con una ruta de código solo x86, pero al menos no cambiarás el redondeo. lee las instrucciones fld y fistp fpu y la palabra control fpu.

Answer 12

Realicé algunas pruebas sobre diferentes formas de hacer la conversión float-to-int. La respuesta breve es suponer que su cliente tiene CPU con capacidad SSE2 y establece el / arch: indicador del compilador SSE2. Esto permitirá al compilador usar las instrucciones escalares SSE que son dos veces más rápidas que incluso la técnica del número mágico.

De lo contrario, si tiene largas cadenas de flotadores para moler, use las operaciones empaquetadas SSE2.

Answer 13

Si tiene matrices muy grandes (más grandes que unos pocos MB, el tamaño de la memoria caché de la CPU), programe su código y vea cuál es el rendimiento. Probablemente estás saturando el bus de memoria, no la unidad de FP. Busque el ancho de banda teórico máximo para su CPU y vea qué tan cerca está de usted.

Si estás siendo limitado por el bus de memoria, los hilos adicionales lo empeorarán. Necesita un mejor hardware (por ejemplo, memoria más rápida, CPU diferente, placa base diferente).

En respuesta al comentario de Larry Gritz ...

Está en lo correcto: la FPU es un cuello de botella importante (y usar el truco xs_CRoundToInt permite que uno se acerque demasiado a la saturación del bus de memoria).

Estos son algunos resultados de prueba para un procesador Core 2 (Q6600). El ancho de banda teórico de la memoria principal para esta máquina es de 3.2 GB / s (los anchos de banda L1 y L2 son mucho más altos). El código se compiló con Visual Studio 2008. Resultados similares para 32 bits y 64 bits, y con optimizaciones de / O2 o / Ox.

WRITING ONLY... 1866359 ticks with 33554432 array elements (33554432 touched). Bandwidth: 1.91793 GB/s 154749 ticks with 262144 array elements (33554432 touched). Bandwidth: 23.1313 GB/s 108816 ticks with 8192 array elements (33554432 touched). Bandwidth: 32.8954 GB/s USING CASTING... 5236122 ticks with 33554432 array elements (33554432 touched). Bandwidth: 0.683625 GB/s 2014309 ticks with 262144 array elements (33554432 touched). Bandwidth: 1.77706 GB/s 1967345 ticks with 8192 array elements (33554432 touched). Bandwidth: 1.81948 GB/s USING xs_CRoundToInt... 1490583 ticks with 33554432 array elements (33554432 touched). Bandwidth: 2.40144 GB/s 1079530 ticks with 262144 array elements (33554432 touched). Bandwidth: 3.31584 GB/s 1008407 ticks with 8192 array elements (33554432 touched). Bandwidth: 3.5497 GB/s

Código fuente (Windows):

// floatToIntTime.cpp : Defines the entry point for the console application.
//

#include <windows.h>
#include <iostream>

using namespace std;

double const _xs_doublemagic = double(6755399441055744.0);
inline int xs_CRoundToInt(double val, double dmr=_xs_doublemagic) { 
  val = val + dmr; 
  return ((int*)&val)[0]; 
} 

static size_t const N = 256*1024*1024/sizeof(double);
int    I[N];
double F[N];
static size_t const L1CACHE = 128*1024/sizeof(double);
static size_t const L2CACHE = 4*1024*1024/sizeof(double);

static size_t const Sz[]    = {N,     L2CACHE/2,     L1CACHE/2};
static size_t const NIter[] = {1, N/(L2CACHE/2), N/(L1CACHE/2)};

int main(int argc, char *argv[])
{
  __int64 freq;
  QueryPerformanceFrequency((LARGE_INTEGER*)&freq);

  cout << "WRITING ONLY..." << endl;
  for (int t=0; t<3; t++) {
    __int64 t0,t1;
    QueryPerformanceCounter((LARGE_INTEGER*)&t0);
    size_t const niter = NIter[t];
    size_t const sz    = Sz[t];
    for (size_t i=0; i<niter; i++) {
      for (size_t n=0; n<sz; n++) {
        I[n] = 13;
      }
    }
    QueryPerformanceCounter((LARGE_INTEGER*)&t1);
    double bandwidth = 8*niter*sz / (((double)(t1-t0))/freq) / 1024/1024/1024;
    cout << "  " << (t1-t0) << " ticks with " << sz 
         << " array elements (" << niter*sz << " touched).  " 
         << "Bandwidth: " << bandwidth << " GB/s" << endl;
  }

  cout << "USING CASTING..." << endl;
  for (int t=0; t<3; t++) {
    __int64 t0,t1;
    QueryPerformanceCounter((LARGE_INTEGER*)&t0);
    size_t const niter = NIter[t];
    size_t const sz    = Sz[t];
    for (size_t i=0; i<niter; i++) {
      for (size_t n=0; n<sz; n++) {
        I[n] = (int)F[n];
      }
    }
    QueryPerformanceCounter((LARGE_INTEGER*)&t1);
    double bandwidth = 8*niter*sz / (((double)(t1-t0))/freq) / 1024/1024/1024;
    cout << "  " << (t1-t0) << " ticks with " << sz 
         << " array elements (" << niter*sz << " touched).  " 
         << "Bandwidth: " << bandwidth << " GB/s" << endl;
  }

  cout << "USING xs_CRoundToInt..." << endl;
  for (int t=0; t<3; t++) {
    __int64 t0,t1;
    QueryPerformanceCounter((LARGE_INTEGER*)&t0);
    size_t const niter = NIter[t];
    size_t const sz    = Sz[t];
    for (size_t i=0; i<niter; i++) {
      for (size_t n=0; n<sz; n++) {
        I[n] = xs_CRoundToInt(F[n]);
      }
    }
    QueryPerformanceCounter((LARGE_INTEGER*)&t1);
    double bandwidth = 8*niter*sz / (((double)(t1-t0))/freq) / 1024/1024/1024;
    cout << "  " << (t1-t0) << " ticks with " << sz 
         << " array elements (" << niter*sz << " touched).  " 
         << "Bandwidth: " << bandwidth << " GB/s" << endl;
  }

  return 0;
}

Answer 14

Si no le importa mucho la semántica de redondeo, puede usar la función lrint() . Esto permite una mayor libertad en el redondeo y puede ser mucho más rápido.

Técnicamente, es una función C99, pero su compilador probablemente la expone en C ++. Un buen compilador también lo alineará a una instrucción (lo hará un moderno G ++).

lrint documentación

Answer 15

redondeando solo el truco excelente, solo el uso 6755399441055743.5 (0.5 menos) para redondear no funcionará.

6755399441055744 = 2 ^ 52 + 2 ^ 51 desbordamiento decimales fuera del final de la mantisa dejando el número entero que desea en los bits 51 - 0 del registro fpu.

En IEEE 754
6755399441055744.0 =

signo exponente mantisa
0 10000110011 1000000000000000000000000000000000000000000000000000

6755399441055743.5 también compilará a 0100001100111000000000000000000000000000000000000000000000000000

el 0.5 se desborda del extremo (redondeando hacia arriba) por lo que esto funciona en primer lugar.

para hacer el truncamiento, debe agregar 0.5 a su doble y luego hacer esto. Los dígitos de guardia deben tener cuidado de redondear el resultado correcto hecho de esta manera. también ten cuidado con el gcc linux de 64 bits donde el término bastante molesto significa un entero de 64 bits.

Answer 16

La mayoría de las otras respuestas aquí solo tratan de eliminar la sobrecarga del ciclo.

Solo la respuesta de deft_code llega al corazón de lo que probablemente sea el problema real: convertir el punto flotante en enteros es sorprendentemente caro en un procesador x86. La solución de deft_code es correcta, aunque no da ninguna cita ni explicación.

Aquí está el origen del truco, con algunas explicaciones y también versiones específicas sobre si desea redondear hacia arriba, hacia abajo o hacia cero: conozca su FPU

Lamento proporcionar un enlace, pero realmente todo lo que está escrito aquí, salvo reproducir ese excelente artículo, no va a aclarar las cosas.