c - representar - ¿La forma más rápida de fijar un valor real(fijo/punto flotante)?
punto flotante plc (15)
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 Calcular el mínimo (mínimo) o máximo (máximo) de dos enteros sin ramificación y Comparación de números de coma flotante
Los formatos IEEE float y double se diseñaron para que los números estén "ordenados lexicográficamente", lo que - en palabras del arquitecto de IEEE William Kahan significa "si se ordenan dos números de punto flotante en el mismo formato (digamos x <y), entonces se ordenan de la misma manera cuando sus bits se reinterpretan como enteros de magnitud de signo ".
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 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)
¿Hay una manera más eficiente de fijar números reales que usar sentencias if o operadores ternarios? Quiero hacer esto tanto para dobles como para una implementación de punto fijo de 32 bits (16.16). No estoy pidiendo un código que pueda manejar ambos casos; se manejarán 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 las comparaciones.
Esto se hace en una parte crítica del rendimiento del código, por lo que estoy buscando una forma tan eficiente de hacerlo como sea posible (que sospecho que involucraría la 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í. Además, MY_MIN y MY_MAX son del mismo tipo que el valor que quiero fijar (se duplica en los ejemplos anteriores).
Como se señaló anteriormente, las funciones fmin / fmax funcionan bien (en gcc, con -ffast-math). Aunque gfortran tiene patrones para usar instrucciones de IA correspondientes a max / min, g ++ no lo hace. En icc uno debe usar en cambio std :: min / max, porque icc no permite abreviar la especificación de cómo fmin / fmax funciona con operandos no finitos.
Creo que podrías usar SSE3 o alguna tecnología similar para esto, pero no sabes exactamente qué comandos / cómo ... Puedes echar un vistazo a: Aritmética de saturación
De manera realista, ningún compilador decente hará la diferencia entre una declaración if () y una expresión?:. El código es lo suficientemente simple como para poder detectar los posibles caminos. Dicho eso, tus dos ejemplos no son idénticos. El código equivalente usando?: Sería
a = (a > MAX) ? MAX : ((a < MIN) ? MIN : a);
ya que eso evita la prueba A <MIN cuando a> MAX. Ahora eso podría marcar la diferencia, ya que el compilador tendría que detectar la relación entre las dos pruebas.
Si el pinzamiento es raro, 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 cambiará un down por 8, luego verificará si está entre -2 y +2. Si esto ahorra algo depende mucho del costo relativo de la bifurcación.
El operador ternario es realmente el camino a seguir, porque la mayoría de los compiladores pueden compilarlos en una operación de hardware nativa que utiliza un movimiento condicional en lugar de una bifurcación (y así evita la penalización errónea y las burbujas de la tubería, etc.). Es probable que la manipulación de bits cause 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 derivación. De hecho, si su compilador usa el intrínseco, puede usarlo para implementar su pinza directamente:
inline double clamp ( double a, double min, double max )
{
a = fsel( a - min , a, min );
return fsel( a - max, max, a );
}
Recomiendo encarecidamente evitar la manipulación de bits de dobles utilizando operaciones de enteros . En la mayoría de las CPU modernas no hay medios directos para mover datos entre los registros dobles e int a excepción de tomar un viaje de ida y vuelta a la memoria caché. Esto causará un riesgo de datos llamado carga-hit-store que básicamente vacía la tubería de la CPU hasta que la escritura de la 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ó desde una función, lo que significa que es probable que todavía esté en XMM1.
En lugar de probar y ramificar, normalmente uso este formato para pinzar:
clampedA = fmin(fmax(a,MY_MIN),MY_MAX);
Aunque nunca he realizado ningún análisis de rendimiento en el código compilado.
Los bits del punto flotante IEEE 754 se ordenan de forma que si compara los bits interpretados como un número entero obtiene los mismos resultados que si los comparara directamente como flotadores. Por lo tanto, si encuentra o conoce una forma de fijar números enteros, también puede usarlo para flotantes (IEEE 754). Lo siento, no sé de una manera más rápida.
Si tiene los flotadores almacenados en un arrays, puede considerar usar algunas extensiones de CPU como SSE3, como dijo rkj. Puedes echarle un vistazo a liboil y hace todo el trabajo sucio por ti. Mantiene su programa portátil y utiliza instrucciones de CPU más rápidas si es posible. (No estoy seguro de cómo es libre de OS / compilador liboil).
Mis 2 centavos en C ++. Probablemente no sea diferente a los operadores ternarios de uso y con suerte no se genera código de bifurcación
template <typename T>
inline T clamp(T val, T lo, T hi) {
return std::max(lo, std::min(hi, val));
}
Para la representación de 16.16, es poco probable que el ternario simple sea mejorado a velocidad.
Y para los dobles, porque lo necesita estándar / portátil C, el toque de bits de cualquier tipo terminará mal.
Incluso si fuera posible un poco de violín (lo que dudo), estarías confiando en la representación binaria de los dobles. ESTO (y su tamaño) ES IMPLEMENTACIÓN-DEPENDIENTE.
Posiblemente podría "adivinar" esto usando sizeof (double) y luego comparar el diseño de varios valores dobles con sus representaciones binarias comunes, pero creo que no se está ocultando a nada.
La mejor regla es DECIRLE AL COMPILADOR LO QUE QUIERES (es decir, ternario), y dejar que se optimice para ti.
EDITAR: tiempo de tarta humilde. Acabo de probar la idea de quinmars (abajo), y funciona, si tienes flotadores IEEE-754. Esto dio una aceleración de aproximadamente 20% en el código a continuación. IOnevitablemente no 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);
Probé el enfoque SSE para esto yo mismo, y la salida de montaje parecía bastante más limpia, así 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 de VC ++ no es lo suficientemente inteligente como para saber qué es lo que realmente pretendes, y parece mover las cosas hacia adelante y hacia atrás entre los registros de 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 min / max de SSE en el operador ternario cuando parece que usa las instrucciones SSE para todos los cálculos de coma flotante de todos modos. Por otro lado, si está compilando para PowerPC, puede usar la herramienta intrínseca en los registros FP, y es mucho más rápido.
Si desea utilizar instrucciones rápidas de valor absoluto, consulte este código cortado que encontré en el minicomputer , que sujeta un flotador al rango [0,1]
clamped = 0.5*(fabs(x)-fabs(x-1.0f) + 1.0f);
(Simplifiqué el código un poco). Podemos pensar que toma dos valores, uno reflejado para ser> 0
fabs(x)
y el otro reflejó aproximadamente 1.0 para ser <1.0
1.0-fabs(x-1.0)
Y tomamos el promedio de ellos. Si está dentro del rango, ambos valores serán iguales a x, por lo que su promedio volverá a ser x. Si está fuera del rango, entonces uno de los valores será x, y el otro será x volteado sobre el punto "límite", por lo que su promedio será precisamente el punto límite.
Si lo entiendo correctamente, quiere limitar un valor "a" a un rango entre MY_MIN y MY_MAX. El tipo de "a" 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 haber una pequeña optimización si MY_MAX y MY_MIN resultan ser enteros:
int b = (int)a;
clampedA = (b > MY_MAX)? (double)MY_MAX : (b < MY_MIN)? (double)MY_MIN : a;
Al cambiar a comparaciones enteras, es posible que obtenga una ligera ventaja de velocidad.
Si su procesador tiene una instrucción rápida para el valor absoluto (como lo hace el x86), puede hacer un mínimo y un máximo sin ramas, que será más rápido que una instrucción if o una 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ás pinzando) el código se simplifica un poco más:
max(a,0) = (a + abs(a)) / 2
Cuando combine 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 ternario en mi Athlon II X2, cuando se usa 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
}
Tanto GCC como clang generan un hermoso ensamblaje 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
Conjunto 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
Montaje generado por Clang:
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 lateral, el código directo de C ++ que llama a std :: min y std :: max genera el mismo conjunto.
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, así que no daré una opinión sobre el punto fijo.
Una vieja pregunta, pero hoy estaba trabajando en este problema (con dobles / flotadores).
El mejor enfoque es usar SSE MINSS / MAXSS para flotadores y SSE2 MINSD / MAXSD para dobles. Estos son sin sucursales y toman un ciclo de reloj cada uno, y son fáciles de usar gracias a los intrínsecos del compilador. Confieren un aumento en el rendimiento de más de un orden de magnitud en comparación con el bloqueo con std :: min / max.
Puede encontrar eso sorprendente. ¡Ciertamente lo hice! Desafortunadamente VC ++ 2010 usa comparaciones simples para std :: min / max incluso cuando / arch: SSE2 y / FP: rápido 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 pinza como se comentó. Pero mirando la salida del ensamblador noté que el compilador de VC ++ no era lo suficientemente inteligente como para descartar el movimiento redundante. Una instrucción menos. :)