c++ - resta - divisiones para niños

Rápida multiplicación/división por 2 para carrozas y dobles(C/C++)

Question

En el software que estoy escribiendo, estoy haciendo millones de multiplicaciones o divisiones por 2 (o poderes de 2) de mis valores. Realmente me gustaría que estos valores sean int para que pueda acceder a los operadores de bitshift

int a = 1;
int b = a<<24

Sin embargo, no puedo, y tengo que seguir con los dobles.

Mi pregunta es: como hay una representación estándar de dobles (signo, exponente, mantisa), ¿hay alguna manera de jugar con el exponente para obtener multiplicaciones / divisiones rápidas con una potencia de 2 ?

Incluso puedo suponer que se va a corregir el número de bits (el software funcionará en máquinas que siempre tendrán dobles de 64 bits)

PD: Y sí, el algoritmo generalmente solo hace estas operaciones. Este es el cuello de botella (ya está multiproceso).

Edit: ¿O estoy completamente equivocado y los compiladores inteligentes ya optimizan las cosas para mí?

Resultados temporales (con Qt para medir el tiempo, excesivo, pero no me importa):

#include <QtCore/QCoreApplication>
#include <QtCore/QElapsedTimer>
#include <QtCore/QDebug>

#include <iostream>
#include <math.h>

using namespace std;

int main(int argc, char *argv[])
{
QCoreApplication a(argc, argv);

while(true)
{
    QElapsedTimer timer;
    timer.start();

    int n=100000000;
    volatile double d=12.4;
    volatile double D;
    for(unsigned int i=0; i<n; ++i)
    {
        //D = d*32;      // 200 ms
        //D = d*(1<<5);  // 200 ms
        D = ldexp (d,5); // 6000 ms
    }

    qDebug() << "The operation took" << timer.elapsed() << "milliseconds";
}

return a.exec();
}

Las ejecuciones sugieren que D = d*(1<<5); y D = d*32; correr en el mismo tiempo (200 ms) mientras que D = ldexp (d,5); es mucho más lento (6000 ms). Sé que este es un micro punto de referencia, y que, de repente, mi memoria RAM se ha disparado porque Chrome ha pedido de repente calcular Pi en mi espalda cada vez que ejecuto ldexp() , por lo que este benchmark no vale nada. Pero lo mantendré sin embargo.

Por otro lado, tengo problemas para reinterpret_cast<uint64_t *> porque hay una violación const (parece que la palabra clave volatile interfiere)

Answer 1

¿Qué otras operaciones requiere este algoritmo? Podrías dividir tus flotadores en pares int (signo / mantisa y magnitud), procesarlos y reconstituirlos al final.

Answer 2

¿Qué tal ldexp ?

Cualquier compilador medio decente generará código óptimo en su plataforma.

Pero como señala @Clinton, simplemente escribirlo de la manera "obvia" debería funcionar igual de bien. Multiplicar y dividir por potencias de dos es un juego de niños para un compilador moderno.

Vacunar directamente la representación del punto flotante, además de ser no portátil, casi con seguridad no será más rápido (y podría ser más lento).

Y, por supuesto, no debe perder el tiempo ni siquiera pensando en esta pregunta a menos que su herramienta de creación de perfiles lo indique. Pero el tipo de personas que escuchan este consejo nunca lo necesitarán, y los que lo necesitan nunca lo escucharán.

[actualizar]

OK, así que probé ldexp con g ++ 4.5.2. El encabezado cmath lo indica como una llamada a __builtin_ldexp , que a su vez ...

... emite una llamada a la función libm ldexp . Hubiera pensado que sería muy fácil optimizar esta construcción, pero supongo que los desarrolladores de GCC nunca lo hicieron.

Entonces, multiplicar por 1 << p es probablemente tu mejor apuesta, como habrás descubierto.

Answer 3

Aunque hay poco o ningún beneficio práctico para tratar potencias de dos, especialmente para flotación de tipos dobles, hay un caso para este tipo de double-double . La multiplicación y división doble-doble es complicada en general, pero es trivial para multiplicar y dividir por una potencia de dos.

Ej. Para

typedef struct {double hi; double lo;} doubledouble;
doubledouble x;
x.hi*=2, x.lo*=2; //multiply x by 2
x.hi/=2, x.lo/=2; //divide x by 2

De hecho, he sobrecargado << y >> para doubledouble para que sea análogo a enteros.

//x is a doubledouble type
x << 2 // multiply x by four;
x >> 3 // divide x by eight.

Answer 4

Dependiendo de lo que esté multiplicando, si tiene datos que son recurrentes, una tabla de búsqueda podría proporcionar un mejor rendimiento, a expensas de la memoria.

Answer 5

Esta es una de esas cosas específicas de alta aplicación. Puede ayudar en algunos casos y no en otros. (En la gran mayoría de los casos, una multiplicación directa sigue siendo la mejor).

La forma "intuitiva" de hacer esto es simplemente extraer los bits en un entero de 64 bits y agregar el valor de desplazamiento directamente en el exponente. (Esto funcionará siempre que no aciertes NAN o INF)

Entonces algo como esto:

union{
    uint64 i;
    double f;
};

f = 123.;
i += 0x0010000000000000ull;

//  Check for zero. And if it matters, denormals as well.

Tenga en cuenta que este código no cumple con C de ninguna manera, y se muestra solo para ilustrar la idea. Cualquier intento de implementar esto debe hacerse directamente en ensamblador o intrínsecamente SSE.

Sin embargo, en la mayoría de los casos, la sobrecarga de mover los datos de la unidad FP a la unidad entera (y viceversa) costará mucho más que simplemente hacer una multiplicación. Este es especialmente el caso para la era anterior a la ESS, donde el valor debe almacenarse desde la FPU x87 en la memoria y luego volverse a leer en los registros enteros.

En la era de SSE, el entero SSE y FP SSE usan los mismos registros ISA (aunque todavía tienen archivos de registro separados). Según Agner Fog , hay una penalización de 1 a 2 ciclos para mover datos entre las unidades de ejecución SSE enteras y FP SSE. Entonces el costo es mucho mejor que la era x87, pero aún está ahí.

Con todo, dependerá de qué más tenga en su tubería. Pero en la mayoría de los casos, la multiplicación será aún más rápida. Me encontré con este mismo problema exactamente antes, así que estoy hablando de la experiencia de primera mano.

Ahora, con las instrucciones AVX de 256 bits que solo admiten instrucciones de FP, hay incluso menos incentivos para jugar trucos como este.

Answer 6

La manera más rápida de hacer esto es probablemente:

x *= (1 << p);

Este tipo de cosas simplemente se puede hacer llamando a una instrucción de máquina para agregar p al exponente. Si le dice al compilador que extraiga los bits con una máscara y haga algo manualmente, probablemente hará las cosas más lentas, no más rápidas.

Recuerde, C / C ++ no es lenguaje ensamblador. El uso de un operador de desplazamiento de bits no se compila necesariamente en una operación de ensamblaje de cambio de bits, no al usar la multiplicación necesariamente compilar a la multiplicación. Hay todo tipo de cosas raras y maravillosas sucediendo, como qué registros se utilizan y qué instrucciones se pueden ejecutar simultáneamente, lo que no soy lo suficientemente inteligente como para entender. Pero su compilador, con muchos años de conocimiento y experiencia y mucho poder computacional, es mucho mejor para hacer estos juicios.

ps Tenga en cuenta que si sus dobles están en una matriz o en alguna otra estructura de datos plana, su compilador puede ser realmente inteligente y usar SSE para múltiples 2 o incluso 4 dobles al mismo tiempo. Sin embargo, hacer muchos cambios de bit probablemente confundirá tu compilador y evitará esta optimización.

Answer 7

Multiplicar por 2 se puede reemplazar por una suma: x *= 2 es equivalente a x += x .

La división por 2 puede ser reemplazada por la multiplicación por 0.5. La multiplicación suele ser significativamente más rápida que la división.

Answer 8

Puede suponer con bastante seguridad el formato IEEE 754, cuyos detalles pueden ser muy graciosos (especialmente cuando entra en subnormales). En los casos comunes, sin embargo, esto debería funcionar:

const int DOUBLE_EXP_SHIFT = 52;
const unsigned long long DOUBLE_MANT_MASK = (1ull << DOUBLE_EXP_SHIFT) - 1ull;
const unsigned long long DOUBLE_EXP_MASK = ((1ull << 63) - 1) & ~DOUBLE_MANT_MASK; 
void unsafe_shl(double* d, int shift) { 
    unsigned long long* i = (unsigned long long*)d; 
    if ((*i & DOUBLE_EXP_MASK) && ((*i & DOUBLE_EXP_MASK) != DOUBLE_EXP_MASK)) { 
        *i += (unsigned long long)shift << DOUBLE_EXP_SHIFT; 
    } else if (*i) {
        *d *= (1 << shift);
    }
} 

EDITAR: después de hacer un poco de sincronización, este método es extrañamente más lento que el método doble en mi compilador y máquina, incluso despojado del código mínimo ejecutado:

    double ds[0x1000];
    for (int i = 0; i != 0x1000; i++)
        ds[i] = 1.2;

    clock_t t = clock();

    for (int j = 0; j != 1000000; j++)
        for (int i = 0; i != 0x1000; i++)
#if DOUBLE_SHIFT
            ds[i] *= 1 << 4;
#else
            ((unsigned int*)&ds[i])[1] += 4 << 20;
#endif

    clock_t e = clock();

    printf("%g/n", (float)(e - t) / CLOCKS_PER_SEC);

En DOUBLE_SHIFT se completa en 1.6 segundos, con un bucle interno de

movupd xmm0,xmmword ptr [ecx]  
lea    ecx,[ecx+10h]  
mulpd  xmm0,xmm1  
movupd xmmword ptr [ecx-10h],xmm0

De lo contrario, 2.4 segundos, con un bucle interno de:

add dword ptr [ecx],400000h
lea ecx, [ecx+8]  

¡Realmente inesperado!

EDIT 2: ¡Misterio resuelto! Uno de los cambios para VC11 es que siempre vectoriza los bucles de punto flotante, forzando efectivamente / arch: SSE2, aunque VC10, incluso con / arch: SSE2 es aún peor con 3.0 segundos con un bucle interno de:

movsd xmm1,mmword ptr [esp+eax*8+38h]  
mulsd xmm1,xmm0  
movsd mmword ptr [esp+eax*8+38h],xmm1  
inc   eax

VC10 sin / arch: SSE2 (incluso con / arch: SSE) es 5.3 segundos ... ¡ con 1/100 de las iteraciones! , lazo interno:

fld         qword ptr [esp+eax*8+38h]  
inc         eax  
fmul        st,st(1)  
fstp        qword ptr [esp+eax*8+30h]

Sabía que la pila de FP x87 era horrible, pero 500 veces peor es algo ridículo. Probablemente no verá este tipo de aceleraciones convirtiendo, es decir, operaciones de matriz a SSE o hacks int, ya que este es el peor de los casos cargando en la pila de FP, haciendo una operación y almacenándolo, pero es un buen ejemplo de por qué x87 no es el camino a seguir para nada perf. relacionado.