¿La forma más rápida de fijar un valor real (punto fijo/flotante)?
https://stackoverflow.com/questions/427477
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
¿Existe una forma más eficiente de limitar los números reales que usar declaraciones if u operadores ternarios?Quiero hacer esto tanto para dobles como para una implementación de punto fijo de 32 bits (16.16).Soy no solicitar código que pueda manejar ambos casos;serán manejados en funciones separadas.
Obviamente, puedo hacer algo como:
double clampedA;
double a = calculate();
clampedA = a > MY_MAX ? MY_MAX : a;
clampedA = a < MY_MIN ? MY_MIN : a;
o
double a = calculate();
double clampedA = a;
if(clampedA > MY_MAX)
clampedA = MY_MAX;
else if(clampedA < MY_MIN)
clampedA = MY_MIN;
La versión de fixpoint usaría funciones/macros para comparaciones.
Esto se hace en una parte del código crítica para el rendimiento, por lo que estoy buscando una forma lo más eficiente posible de hacerlo (lo que sospecho implicaría manipulación de bits)
EDITAR:Tiene que ser C estándar/portátil, la funcionalidad específica de la plataforma no tiene ningún interés aquí.También, MY_MIN y MY_MAX son del mismo tipo que el valor que quiero fijar (se duplica en los ejemplos anteriores).
Solución
Para la representación 16.16, es poco probable que el ternario simple sea mejorado rápidamente.
Y para los dobles, debido a que lo necesitas C estándar / portátil, los juegos de bits de cualquier tipo terminarán mal.
Incluso si fuera posible un poco de violín (lo cual dudo), dependería de la representación binaria de dobles. ESTO (y su tamaño) ES DEPENDIENTE DE LA IMPLEMENTACIÓN.
Posiblemente podría " adivine " esto usando sizeof (double) y luego comparando el diseño de varios valores dobles contra sus representaciones binarias comunes, pero creo que te estás escondiendo de nada.
La mejor regla es decirle al compilador lo que quiere (es decir, ternario) y dejar que se optimice para usted.
EDITAR: Humilde tiempo de tarta. Acabo de probar la idea de Quinmars (a continuación), y funciona, si tienes flotadores IEEE-754. Esto dio una aceleración de aproximadamente el 20% en el siguiente código. Obviamente no es portátil, pero creo que puede haber una forma estandarizada de preguntarle a su compilador si usa formatos flotantes IEEE754 con un #IF ...?
double FMIN = 3.13;
double FMAX = 300.44;
double FVAL[10] = {-100, 0.23, 1.24, 3.00, 3.5, 30.5, 50 ,100.22 ,200.22, 30000};
uint64 Lfmin = *(uint64 *)&FMIN;
uint64 Lfmax = *(uint64 *)&FMAX;
DWORD start = GetTickCount();
for (int j=0; j<10000000; ++j)
{
uint64 * pfvalue = (uint64 *)&FVAL[0];
for (int i=0; i<10; ++i)
*pfvalue++ = (*pfvalue < Lfmin) ? Lfmin : (*pfvalue > Lfmax) ? Lfmax : *pfvalue;
}
volatile DWORD hacktime = GetTickCount() - start;
for (int j=0; j<10000000; ++j)
{
double * pfvalue = &FVAL[0];
for (int i=0; i<10; ++i)
*pfvalue++ = (*pfvalue < FMIN) ? FMIN : (*pfvalue > FMAX) ? FMAX : *pfvalue;
}
volatile DWORD normaltime = GetTickCount() - (start + hacktime);
Otros consejos
Antigua pregunta, pero hoy estaba trabajando en este problema (con dobles / flotantes).
El mejor enfoque es utilizar SSE MINSS / MAXSS para flotadores y SSE2 MINSD / MAXSD para dobles. Estos no tienen ramificaciones y toman un ciclo de reloj cada uno, y son fáciles de usar gracias a los intrínsecos del compilador. Confieren un aumento de rendimiento de más de un orden de magnitud en comparación con la sujeción con std :: min / max.
Puede que te resulte sorprendente. Ciertamente lo hice! Desafortunadamente, VC ++ 2010 utiliza comparaciones simples para std :: min / max incluso cuando / arch: SSE2 y / FP: fast están habilitados. No puedo hablar por otros compiladores.
Aquí está el código necesario para hacer esto en VC ++:
#include <mmintrin.h>
float minss ( float a, float b )
{
// Branchless SSE min.
_mm_store_ss( &a, _mm_min_ss(_mm_set_ss(a),_mm_set_ss(b)) );
return a;
}
float maxss ( float a, float b )
{
// Branchless SSE max.
_mm_store_ss( &a, _mm_max_ss(_mm_set_ss(a),_mm_set_ss(b)) );
return a;
}
float clamp ( float val, float minval, float maxval )
{
// Branchless SSE clamp.
// return minss( maxss(val,minval), maxval );
_mm_store_ss( &val, _mm_min_ss( _mm_max_ss(_mm_set_ss(val),_mm_set_ss(minval)), _mm_set_ss(maxval) ) );
return val;
}
El código de doble precisión es el mismo, excepto con xxx_sd en su lugar.
Editar: Inicialmente escribí la función de sujeción como comentada. Pero al mirar la salida del ensamblador, noté que el compilador VC ++ no era lo suficientemente inteligente como para eliminar el movimiento redundante. Una instrucción menos. :)
Tanto GCC como clang generan un ensamblaje hermoso para el siguiente código simple, directo y portátil:
double clamp(double d, double min, double max) {
const double t = d < min ? min : d;
return t > max ? max : t;
}
> gcc -O3 -march=native -Wall -Wextra -Wc++-compat -S -fverbose-asm clamp_ternary_operator.c
Ensamblaje generado por GCC:
maxsd %xmm0, %xmm1 # d, min
movapd %xmm2, %xmm0 # max, max
minsd %xmm1, %xmm0 # min, max
ret
> clang -O3 -march=native -Wall -Wextra -Wc++-compat -S -fverbose-asm clamp_ternary_operator.c
Ensamblaje generado por argot:
maxsd %xmm0, %xmm1
minsd %xmm1, %xmm2
movaps %xmm2, %xmm0
ret
Tres instrucciones (sin contar el ret), sin ramas. Excelente.
Esto se probó con GCC 4.7 y clang 3.2 en Ubuntu 13.04 con un Core i3 M 350. En una nota al margen, el código directo de C ++ que llama a std :: min y std :: max generó el mismo ensamblaje.
Esto es para dobles. Y para int, tanto GCC como clang generan ensamblaje con cinco instrucciones (sin contar el ret) y sin ramas. También excelente.
Actualmente no uso el punto fijo, por lo que no voy a dar una opinión sobre el punto fijo.
Si su procesador tiene una instrucción rápida para el valor absoluto (como lo hace el x86), puede hacer un min y max sin ramificación que será más rápido que una instrucción if u operación ternaria.
min(a,b) = (a + b - abs(a-b)) / 2
max(a,b) = (a + b + abs(a-b)) / 2
Si uno de los términos es cero (como suele ser el caso cuando está sujetando) el código se simplifica un poco más:
max(a,0) = (a + abs(a)) / 2
Cuando combina ambas operaciones, puede reemplazar las dos /2 en una sola /4 o *0.25 para guardar un paso.
El siguiente código es más de 3 veces más rápido que el ternario en mi Athlon II X2, cuando uso la optimización para FMIN = 0.
double clamp(double value)
{
double temp = value + FMAX - abs(value-FMAX);
#if FMIN == 0
return (temp + abs(temp)) * 0.25;
#else
return (temp + (2.0*FMIN) + abs(temp-(2.0*FMIN))) * 0.25;
#endif
}
El operador ternario es realmente el camino a seguir, porque la mayoría de los compiladores pueden compilarlos en una operación de hardware nativo que utiliza un movimiento condicional en lugar de una rama (y así evita la penalización de predicción errónea y las burbujas de canalización, etc.). Es probable que la manipulación de bits provoque una carga-hit-store .
En particular, PPC y x86 con SSE2 tienen una operación de hardware que podría expresarse como algo intrínseco como este:
double fsel( double a, double b, double c ) {
return a >= 0 ? b : c;
}
La ventaja es que hace esto dentro de la tubería, sin causar una ramificación. De hecho, si su compilador usa el intrínseco, puede usarlo para implementar su abrazadera directamente:
inline double clamp ( double a, double min, double max )
{
a = fsel( a - min , a, min );
return fsel( a - max, max, a );
}
Le sugiero encarecidamente que evite la manipulación de bits de dobles mediante operaciones con enteros . En la mayoría de las CPU modernas, no existe un medio directo de mover datos entre registros dobles e int que no sea realizar un viaje de ida y vuelta a dcache. Esto provocará un riesgo de datos llamado carga-hit-store que básicamente vacía la tubería de la CPU hasta que la escritura de memoria se haya completado (generalmente alrededor de 40 ciclos más o menos).
La excepción a esto es si los valores dobles ya están en la memoria y no en un registro: en ese caso, no hay peligro de una carga-hit-store. Sin embargo, su ejemplo indica que acaba de calcular el doble y lo devolvió de una función, lo que significa que es probable que todavía esté en XMM1.
Los bits del punto flotante IEEE 754 se ordenan de manera que si compara los bits interpretados como un entero, obtiene los mismos resultados que si los comparara como flotantes directamente. Entonces, si encuentra o conoce una forma de sujetar enteros, también puede usarla para flotadores (IEEE 754). Lo siento, no conozco una forma más rápida.
Si tiene los flotantes almacenados en una matriz, puede considerar usar algunas extensiones de CPU como SSE3, como dijo rkj. Puedes echar un vistazo a liboil, hace todo el trabajo sucio por ti. Mantiene su programa portátil y usa instrucciones de CPU más rápidas si es posible. (No estoy seguro de cómo es la biblioteca independiente del compilador / SO).
En lugar de probar y ramificar, normalmente uso este formato para sujetar:
clampedA = fmin(fmax(a,MY_MIN),MY_MAX);
Aunque nunca he hecho ningún análisis de rendimiento en el código compilado.
Siendo realistas, ningún compilador decente hará una diferencia entre una declaración if () y una expresión?:. El código es lo suficientemente simple como para que puedan detectar las posibles rutas. Dicho esto, tus dos ejemplos no son idénticos. El código equivalente usando?: Sería
a = (a > MAX) ? MAX : ((a < MIN) ? MIN : a);
como eso evite el A < Prueba MIN cuando a & Gt; MAX. Ahora eso podría marcar la diferencia, ya que el compilador de lo contrario tendría que detectar la relación entre las dos pruebas.
Si la sujeción es rara, puede probar la necesidad de sujetar con una sola prueba:
if (abs(a - (MAX+MIN)/2) > ((MAX-MIN)/2)) ...
Por ejemplo. con MIN = 6 y MAX = 10, esto primero desplazará un valor hacia abajo por 8, luego verificará si se encuentra entre -2 y +2. Que esto ahorre algo depende en gran medida del costo relativo de la ramificación.
Aquí hay una implementación posiblemente más rápida similar a La respuesta de @ Roddy :
typedef int64_t i_t;
typedef double f_t;
static inline
i_t i_tmin(i_t x, i_t y) {
return (y + ((x - y) & -(x < y))); // min(x, y)
}
static inline
i_t i_tmax(i_t x, i_t y) {
return (x - ((x - y) & -(x < y))); // max(x, y)
}
f_t clip_f_t(f_t f, f_t fmin, f_t fmax)
{
#ifndef TERNARY
assert(sizeof(i_t) == sizeof(f_t));
//assert(not (fmin < 0 and (f < 0 or is_negative_zero(f))));
//XXX assume IEEE-754 compliant system (lexicographically ordered floats)
//XXX break strict-aliasing rules
const i_t imin = *(i_t*)&fmin;
const i_t imax = *(i_t*)&fmax;
const i_t i = *(i_t*)&f;
const i_t iclipped = i_tmin(imax, i_tmax(i, imin));
#ifndef INT_TERNARY
return *(f_t *)&iclipped;
#else /* INT_TERNARY */
return i < imin ? fmin : (i > imax ? fmax : f);
#endif /* INT_TERNARY */
#else /* TERNARY */
return fmin > f ? fmin : (fmax < f ? fmax : f);
#endif /* TERNARY */
}
Consulte Calcule el mínimo (min) o el máximo ( máx.) de dos enteros sin ramificación y Comparación de números de coma flotante
El flotante IEEE y los formatos dobles fueron diseñado para que los números sean & # 8220; ordenado lexicográficamente & # 8221 ;, que & # 8211; en palabras del arquitecto William IEEE Kahan significa & # 8220; si hay dos puntos flotantes los números en el mismo formato están ordenados (diga x < y), luego se ordenan de la misma manera cuando sus bits son reinterpretado como Sign-Magnitude enteros. & # 8221;
Un programa de prueba:
/** gcc -std=c99 -fno-strict-aliasing -O2 -lm -Wall *.c -o clip_double && clip_double */
#include <assert.h>
#include <iso646.h> // not, and
#include <math.h> // isnan()
#include <stdbool.h> // bool
#include <stdint.h> // int64_t
#include <stdio.h>
static
bool is_negative_zero(f_t x)
{
return x == 0 and 1/x < 0;
}
static inline
f_t range(f_t low, f_t f, f_t hi)
{
return fmax(low, fmin(f, hi));
}
static const f_t END = 0./0.;
#define TOSTR(f, fmin, fmax, ff) ((f) == (fmin) ? "min" : \
((f) == (fmax) ? "max" : \
(is_negative_zero(ff) ? "-0.": \
((f) == (ff) ? "f" : #f))))
static int test(f_t p[], f_t fmin, f_t fmax, f_t (*fun)(f_t, f_t, f_t))
{
assert(isnan(END));
int failed_count = 0;
for ( ; ; ++p) {
const f_t clipped = fun(*p, fmin, fmax), expected = range(fmin, *p, fmax);
if(clipped != expected and not (isnan(clipped) and isnan(expected))) {
failed_count++;
fprintf(stderr, "error: got: %s, expected: %s\t(min=%g, max=%g, f=%g)\n",
TOSTR(clipped, fmin, fmax, *p),
TOSTR(expected, fmin, fmax, *p), fmin, fmax, *p);
}
if (isnan(*p))
break;
}
return failed_count;
}
int main(void)
{
int failed_count = 0;
f_t arr[] = { -0., -1./0., 0., 1./0., 1., -1., 2,
2.1, -2.1, -0.1, END};
f_t minmax[][2] = { -1, 1, // min, max
0, 2, };
for (int i = 0; i < (sizeof(minmax) / sizeof(*minmax)); ++i)
failed_count += test(arr, minmax[i][0], minmax[i][1], clip_f_t);
return failed_count & 0xFF;
}
En la consola:
$ gcc -std=c99 -fno-strict-aliasing -O2 -lm *.c -o clip_double && ./clip_double
Imprime:
error: got: min, expected: -0. (min=-1, max=1, f=0)
error: got: f, expected: min (min=-1, max=1, f=-1.#INF)
error: got: f, expected: min (min=-1, max=1, f=-2.1)
error: got: min, expected: f (min=-1, max=1, f=-0.1)
Probé el enfoque SSE para esto yo mismo, y el resultado del ensamblaje parecía bastante más limpio, por lo que me animé al principio, pero después de cronometrarlo miles de veces, en realidad fue un poco más lento. De hecho, parece que el compilador VC ++ no es lo suficientemente inteligente como para saber lo que realmente está intentando, y parece que mueve las cosas de un lado a otro entre los registros XMM y la memoria cuando no debería. Dicho esto, no sé por qué el compilador no es lo suficientemente inteligente como para usar las instrucciones mínimas / máximas de SSE en el operador ternario cuando parece utilizar las instrucciones SSE para todos los cálculos de coma flotante de todos modos. Por otro lado, si está compilando para PowerPC, puede usar el fsel intrínseco en los registros de FP, y es mucho más rápido.
Si entiendo correctamente, desea limitar un valor " a " a un rango entre MY_MIN y MY_MAX. El tipo de & Quot; a & Quot; Es un doble. No especificó el tipo de MY_MIN o MY_MAX.
La expresión simple:
clampedA = (a > MY_MAX)? MY_MAX : (a < MY_MIN)? MY_MIN : a;
debería hacer el truco.
Creo que puede hacerse una pequeña optimización si MY_MAX y MY_MIN son enteros:
int b = (int)a;
clampedA = (b > MY_MAX)? (double)MY_MAX : (b < MY_MIN)? (double)MY_MIN : a;
Al cambiar a comparaciones de enteros, es posible que obtenga una ligera ventaja de velocidad.
Si desea utilizar instrucciones rápidas de valor absoluto, consulte este fragmento de código que encontré en minicomputadora , que sujeta un flotador al rango [0,1]
clamped = 0.5*(fabs(x)-fabs(x-1.0f) + 1.0f);
(simplifiqué un poco el código). Podemos pensar que toma dos valores, uno reflejado como & Gt; 0
fabs(x)
y el otro reflejaba que 1.0 era < 1.0
1.0-fabs(x-1.0)
Y tomamos el promedio de ellos. Si está dentro del rango, ambos valores serán los mismos que x, por lo que su promedio nuevamente será x. Si está fuera de rango, uno de los valores será x, y el otro será x invertido sobre el & "; Límite &"; punto, por lo que su promedio será precisamente el punto límite.
Como se señaló anteriormente, las funciones fmin / fmax funcionan bien (en gcc, con -ffast-math). Aunque gfortran tiene patrones para usar las instrucciones IA correspondientes a max / min, g ++ no. En icc se debe usar std :: min / max, porque icc no permite abreviar la especificación de cómo funcionan fmin / fmax con operandos no finitos.
Mis 2 centavos en C ++. Probablemente no sea diferente de usar operadores ternarios y, con suerte, no se genera código de ramificación
template <typename T>
inline T clamp(T val, T lo, T hi) {
return std::max(lo, std::min(hi, val));
}
