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


Answers

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

Question

Esta pregunta ya tiene una respuesta aquí:

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.




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;
}



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.




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




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




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.




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




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.






Links