ventajas - C: ¿Acceder más rápido a las tablas de búsqueda?
usar indices en consulta sql (4)
Tengo un trozo de código que rastrea 4 senos a la vez.
Mi código original estaba realizando aproximadamente 12000 llamadas a la función sin () por fotograma y se estaba ejecutando a 30 fps.
Intenté optimizarlo generando tablas de búsqueda. Terminé con 16 tablas de búsqueda diferentes. Los declaré y los cargué en un archivo de encabezado separado en la parte superior de mi programa. Cada tabla se declara así:
static const float d4_lookup[800] {...};
Ahora, con este nuevo método realmente perdí fps ?! Ahora estoy corriendo a 20 fps en lugar de 30. Cada cuadro ahora solo tiene que hacer 8 llamadas sin / cos y 19200 llamadas de búsqueda frente a 12000 llamadas sin (). Compilo usando gcc con el indicador -O3 activado. En este momento, las tablas de búsqueda se incluyen en la parte superior y forman parte del alcance global del programa.
Supongo que no los estoy cargando en la memoria correcta o algo por el estilo. ¿Cómo puedo acelerar el tiempo de búsqueda?
** EDITAR 1 **
Según lo solicitado, aquí está la función que utiliza las llamadas de búsqueda, se llama una vez por fotograma:
void
update_sines(void)
{
static float c1_sin, c1_cos;
static float c2_sin, c2_cos;
static float c3_sin, c3_cos;
static float c4_sin, c4_cos;
clock_gettime(CLOCK_MONOTONIC, &spec);
s = spec.tv_sec;
ms = spec.tv_nsec * 0.0000001;
etime = concatenate((long)s, ms);
c1_sin = sinf(etime * 0.00525);
c1_cos = cosf(etime * 0.00525);
c2_sin = sinf(etime * 0.007326);
c2_cos = cosf(etime * 0.007326);
c3_sin = sinf(etime * 0.0046);
c3_cos = cosf(etime * 0.0046);
c4_sin = sinf(etime * 0.007992);
c4_cos = cosf(etime * 0.007992);
int k;
for (k = 0; k < 800; ++k)
{
sine1[k] = a1_lookup[k] * ((bx1_sin_lookup[k] * c1_cos) + (c1_sin * bx1_cos_lookup[k])) + d1_lookup[k];
sine2[k] = a2_lookup[k] * ((bx2_sin_lookup[k] * c2_cos) + (c2_sin * bx2_cos_lookup[k])) + d2_lookup[k] + 50;
sine3[k] = a3_lookup[k] * ((bx3_sin_lookup[k] * c3_cos) + (c3_sin * bx3_cos_lookup[k])) + d3_lookup[k];
sine4[k] = a4_lookup[k] * ((bx4_sin_lookup[k] * c4_cos) + (c4_sin * bx4_cos_lookup[k])) + d4_lookup[k] + 50;
}
}
** ACTUALIZACIÓN **
Para cualquiera que lea este hilo, renuncié a este problema. Intenté usar kernels OpenCL, estructuras, instrucciones SIMD y todas las soluciones que se muestran aquí. Al final, el código original que calculó el sinf () 12800 por cuadro funcionó más rápido que las tablas de búsqueda, ya que las tablas de búsqueda no encajaban en el caché. Sin embargo, todavía estaba haciendo solo 30 fps. Simplemente tenía demasiadas cosas para mantener mis expectativas de 60 fps. He decidido tomar una dirección diferente. Gracias a todos los que contribuyeron a este hilo. La mayoría de estas soluciones probablemente funcionarán para obtener mejoras a la mitad de la velocidad decente, pero nada como la aceleración del 200% que necesitaba aquí para que las tablas de búsqueda funcionen como yo quería.
El uso de una tabla de búsqueda de sin simple producirá> 20% de aumento de velocidad en mi máquina linux (vm, gcc, 64bit). Curiosamente, el tamaño de la tabla de búsqueda (dentro de los valores razonables de <tamaño de caché L1) no influye en la velocidad de ejecución.
Usando una implementación simple de ayuno desde aquí obtuve una mejora de> 45%.
Código:
#include <math.h>
#include <stdio.h>
#include <stdint.h>
#include <sys/time.h>
#include <time.h>
#define LOOKUP_SIZE 628
uint64_t currentTimestampUs( void )
{
struct timeval tv;
time_t localTimeRet;
uint64_t timestamp = 0;
//time_t tzDiff = 0;
struct tm when;
int64_t localeOffset = 0;
{
localTimeRet = time(NULL);
localtime_r ( &localTimeRet, &when );
localeOffset = when.tm_gmtoff * 1000000ll;
}
gettimeofday ( &tv, NULL );
timestamp = ((uint64_t)((tv.tv_sec) * 1000000ll) ) + ( (uint64_t)(tv.tv_usec) );
timestamp+=localeOffset;
return timestamp;
}
const double PI = 3.141592653589793238462;
const double PI2 = 3.141592653589793238462 * 2;
static float sinarr[LOOKUP_SIZE];
void initSinArr() {
int a =0;
for (a=0; a<LOOKUP_SIZE; a++) {
double arg = (1.0*a/LOOKUP_SIZE)*((double)PI * 0.5);
float sinval_f = sin(arg); // double computation earlier to avoid losing precision on value
sinarr[a] = sinval_f;
}
}
float sinlookup(float val) {
float normval = val;
while (normval < 0) {
normval += PI2;
}
while (normval > PI2) {
normval -= PI2;
}
int index = LOOKUP_SIZE*(2*normval/PI);
if (index > 3*LOOKUP_SIZE) {
index = -index + 4*LOOKUP_SIZE;//LOOKUP_SIZE - (index-3*LOOKUP_SIZE);
return -sinarr[index];
} else if (index > 2*LOOKUP_SIZE) {
index = index - 2*LOOKUP_SIZE;
return -sinarr[index];
} else if (index > LOOKUP_SIZE) {
index = 2*LOOKUP_SIZE - index;
return sinarr[index];
} else {
return sinarr[index];
}
}
float sin_fast(float x) {
while (x < -PI)
x += PI2;
while (x > PI)
x -= PI2;
//compute sine
if (x < 0)
return 1.27323954 * x + .405284735 * x * x;
else
return 1.27323954 * x - 0.405284735 * x * x;
}
int main(void) {
initSinArr();
int a = 0;
float val = 0;
const int num_tries = 100000;
uint64_t startLookup = currentTimestampUs();
for (a=0; a<num_tries; a++) {
for (val=0; val<PI2; val+=0.01) {
float compval = sinlookup(val);
(void)compval;
}
}
uint64_t startSin = currentTimestampUs();
for (a=0; a<num_tries; a++) {
for (val=0; val<PI2; val+=0.01) {
float compval = sin(val);
(void)compval;
}
}
uint64_t startFastSin = currentTimestampUs();
for (a=0; a<num_tries; a++) {
for (val=0; val<PI2; val+=0.01) {
float compval = sin_fast(val);
(void)compval;
}
}
uint64_t end = currentTimestampUs();
int64_t lookupMs = (startSin - startLookup)/1000;
int64_t sinMs = (startFastSin - startSin)/1000;
int64_t fastSinMs = (end - startFastSin)/1000;
printf(" lookup: %lld ms/n", lookupMs );
printf(" sin: %lld ms/n", sinMs );
printf(" diff: %lld ms/n", sinMs-lookupMs);
printf(" diff%: %lld %/n", 100*(sinMs-lookupMs)/sinMs);
printf("fastsin: %lld ms/n", fastSinMs );
printf(" sin: %lld ms/n", sinMs );
printf(" diff: %lld ms/n", sinMs-fastSinMs);
printf(" diff%: %lld %/n", 100*(sinMs-fastSinMs)/sinMs);
}
Resultado de la muestra:
lookup: 2276 ms
sin: 3004 ms
diff: 728 ms
diff%: 24 %
fastsin: 1500 ms
sin: 3004 ms
diff: 1504 ms
diff%: 50 %
Intenta desenrollar tus bucles de esta manera:
for (k = 0; k < 800; ++k)
{
sine1[k] = a1_lookup[k];
sine2[k] = a2_lookup[k];
sine3[k] = a3_lookup[k];
sine4[k] = a4_lookup[k];
}
for (k = 0; k < 800; ++k)
{
sine1[k] *= ((bx1_sin_lookup[k] * c1_cos) + (c1_sin * bx1_cos_lookup[k]));
sine2[k] *= ((bx2_sin_lookup[k] * c2_cos) + (c2_sin * bx2_cos_lookup[k]));
sine3[k] *= ((bx3_sin_lookup[k] * c3_cos) + (c3_sin * bx3_cos_lookup[k]));
sine4[k] *= ((bx4_sin_lookup[k] * c4_cos) + (c4_sin * bx4_cos_lookup[k]));
}
for (k = 0; k < 800; ++k)
{
sine1[k] += d1_lookup[k];
sine2[k] += d2_lookup[k] + 50;
sine3[k] += d3_lookup[k];
sine4[k] += d4_lookup[k] + 50;
}
Al acceder a menos tablas de búsqueda en cada bucle, debería poder permanecer en el caché. El bucle central también podría dividirse, pero deberá crear una tabla intermedia para una de las subexpresiones.
Los procesadores Intel pueden predecir el acceso en serie (y realizar una captación previa) para hasta 4 arreglos, tanto para el desplazamiento hacia adelante como hacia atrás. Al menos esto fue cierto en los días Core 2 Duo. Dividir su para en:
for (k = 0; k < 800; ++k)
sine1[k] = a1_lookup[k] * ((bx1_sin_lookup[k] * c1_cos) + (c1_sin * bx1_cos_lookup[k])) + d1_lookup[k];
for (k = 0; k < 800; ++k)
sine2[k] = a2_lookup[k] * ((bx2_sin_lookup[k] * c2_cos) + (c2_sin * bx2_cos_lookup[k])) + d2_lookup[k] + 50;
for (k = 0; k < 800; ++k)
sine3[k] = a3_lookup[k] * ((bx3_sin_lookup[k] * c3_cos) + (c3_sin * bx3_cos_lookup[k])) + d3_lookup[k];
for (k = 0; k < 800; ++k)
sine4[k] = a4_lookup[k] * ((bx4_sin_lookup[k] * c4_cos) + (c4_sin * bx4_cos_lookup[k])) + d4_lookup[k] + 50;
Supongo que tiene más carga de caché que puntos de referencia en otras respuestas, así que esto sí importa. Te recomiendo que no desenrolles los bucles, los compiladores lo hacen bien.
a veces es difícil saber qué es lo que te está ralentizando, pero potencialmente vas a arruinar tus accesos al caché, puedes intentar buscar una estructura
typedef struct
{
float bx1_sin;
float bx2_sin;
float bx3_sin;
float bx4_sin;
float bx1_cos;
etc etc
including sine1,2,3,4 as well
} lookup_table
entonces
lookup_table lookup[800]
ahora todo en la búsqueda k estará en la misma pequeña parte de la memoria.
también, si usa una macro que toma k como parámetro para hacer el contenido del bucle, digamos SINE_CALC (k), o una función en línea ...
tu puedes hacer
for (k = 0; k < 800; ++k)
{
SINE_CALC(k); k++;
SINE_CALC(k); k++;
SINE_CALC(k); k++;
SINE_CALC(k); k++;
SINE_CALC(k); k++;
}
si haces una macro, asegúrate de que k ++ esté fuera de la llamada de macro como se muestra