c++ - sistemas - Multiplicación/división eficientes de dos enteros de 128 bits en x86(sin 64 bits)

sistemas operativos de 32 y 64 bits

Question

Compilador: MinGW / GCC
Problemas: No se permite el código GPL / LGPL (GMP o cualquier biblioteca bignum para el caso, es excesivo para este problema, ya que ya tengo implementada la clase).

He construido mi propia clase de enteros grandes de tamaño fijo de 128 bits (prevista para su uso en un motor de juego, pero puede generalizarse a cualquier caso de uso) y encuentro que el rendimiento de las operaciones actuales de multiplicación y división es bastante abismal (sí, Los he cronometrado, ver más abajo), y me gustaría mejorar (o cambiar) los algoritmos que hacen el crujido de números de bajo nivel.

Cuando se trata de multiplicar y dividir operadores, son insoportablemente lentos en comparación con casi todo lo demás en la clase.

Estas son las medidas aproximadas relativas a mi propia computadora:

Raw times as defined by QueryPerformanceFrequency:
1/60sec          31080833u
Addition:              ~8u
Subtraction:           ~8u
Multiplication:      ~546u
Division:           ~4760u (with maximum bit count)

Como puede ver, simplemente hacer la multiplicación es muchas, muchas veces más lento que sumar o restar. La división es aproximadamente 10 veces más lenta que la multiplicación.

Me gustaría mejorar la velocidad de estos dos operadores porque puede haber una gran cantidad de cálculos por trama (productos de puntos, varios métodos de detección de colisiones, etc.).

La estructura (métodos omitidos) se parece a algo así:

class uint128_t
{
    public:
        unsigned long int dw3, dw2, dw1, dw0;
  //...
}

La multiplicación se realiza actualmente usando el método típico de multiplicación larga (en ensamblaje para poder capturar la salida EDX ) mientras se ignoran las palabras que están fuera de rango (es decir, solo hago 10 mull ''s en comparación con 16).

La división usa el algoritmo shift-restat (la velocidad depende del conteo de bits de los operandos). Sin embargo, no se hace en ensamblaje. Encontré eso un poco demasiado difícil de reunir y decidí dejar que el compilador lo optimizara.

Hace muchos días que busqué en Google las páginas que describen algoritmos como Karatsuba Multiplication , high-radix division y Newton-Rapson Division, pero los símbolos matemáticos están demasiado lejos de mi cabeza. Me gustaría utilizar algunos de estos métodos avanzados para acelerar mi código, pero primero tendría que traducir el "griego" a algo comprensible.

Para aquellos que pueden considerar mis esfuerzos como "optimización prematura"; Considero que este código es un cuello de botella porque las operaciones mismas de matemática elemental se vuelven lentas. Puedo ignorar tales tipos de optimización en el código de nivel superior, pero este código se llamará / usará lo suficiente como para que importe.

Me gustaría sugerencias sobre qué algoritmo debería usar para mejorar multiplicar y dividir (si es posible), y una explicación básica (ojalá fácil de entender) sobre cómo funciona el algoritmo sugerido sería muy apreciada.

EDITAR: Mejoras multiples

Pude mejorar la operación de multiplicar introduciendo el código en operator * = y parece lo más rápido posible.

Updated raw times:
1/60sec          31080833u
Addition:              ~8u
Subtraction:           ~8u
Multiplication:      ~100u (lowest ~86u, highest around ~256u)
Division:           ~4760u (with maximum bit count)

Aquí hay algunos códigos básicos para que los examine (tenga en cuenta que los nombres de mis tipos son realmente diferentes, esto fue editado por simplicidad):

//File: "int128_t.h"
class int128_t
{
    uint32_t dw3, dw2, dw1, dw0;

    // Various constrctors, operators, etc...

    int128_t& operator*=(const int128_t&  rhs) __attribute__((always_inline))
    {
        int128_t Urhs(rhs);
        uint32_t lhs_xor_mask = (int32_t(dw3) >> 31);
        uint32_t rhs_xor_mask = (int32_t(Urhs.dw3) >> 31);
        uint32_t result_xor_mask = (lhs_xor_mask ^ rhs_xor_mask);
        dw0 ^= lhs_xor_mask;
        dw1 ^= lhs_xor_mask;
        dw2 ^= lhs_xor_mask;
        dw3 ^= lhs_xor_mask;
        Urhs.dw0 ^= rhs_xor_mask;
        Urhs.dw1 ^= rhs_xor_mask;
        Urhs.dw2 ^= rhs_xor_mask;
        Urhs.dw3 ^= rhs_xor_mask;
        *this += (lhs_xor_mask & 1);
        Urhs += (rhs_xor_mask & 1);

        struct mul128_t
        {
            int128_t dqw1, dqw0;
            mul128_t(const int128_t& dqw1, const int128_t& dqw0): dqw1(dqw1), dqw0(dqw0){}
        };

        mul128_t data(Urhs,*this);
        asm volatile(
        "push      %%ebp                            /n/
        movl       %%eax,   %%ebp                   /n/
        movl       $0x00,   %%ebx                   /n/
        movl       $0x00,   %%ecx                   /n/
        movl       $0x00,   %%esi                   /n/
        movl       $0x00,   %%edi                   /n/
        movl   28(%%ebp),   %%eax #Calc: (dw0*dw0)  /n/
        mull             12(%%ebp)                  /n/
        addl       %%eax,   %%ebx                   /n/
        adcl       %%edx,   %%ecx                   /n/
        adcl       $0x00,   %%esi                   /n/
        adcl       $0x00,   %%edi                   /n/
        movl   24(%%ebp),   %%eax #Calc: (dw1*dw0)  /n/
        mull             12(%%ebp)                  /n/
        addl       %%eax,   %%ecx                   /n/
        adcl       %%edx,   %%esi                   /n/
        adcl       $0x00,   %%edi                   /n/
        movl   20(%%ebp),   %%eax #Calc: (dw2*dw0)  /n/
        mull             12(%%ebp)                  /n/
        addl       %%eax,   %%esi                   /n/
        adcl       %%edx,   %%edi                   /n/
        movl   16(%%ebp),   %%eax #Calc: (dw3*dw0)  /n/
        mull             12(%%ebp)                  /n/
        addl       %%eax,   %%edi                   /n/
        movl   28(%%ebp),   %%eax #Calc: (dw0*dw1)  /n/
        mull              8(%%ebp)                  /n/
        addl       %%eax,   %%ecx                   /n/
        adcl       %%edx,   %%esi                   /n/
        adcl       $0x00,   %%edi                   /n/
        movl   24(%%ebp),   %%eax #Calc: (dw1*dw1)  /n/
        mull              8(%%ebp)                  /n/
        addl       %%eax,   %%esi                   /n/
        adcl       %%edx,   %%edi                   /n/
        movl   20(%%ebp),   %%eax #Calc: (dw2*dw1)  /n/
        mull              8(%%ebp)                  /n/
        addl       %%eax,   %%edi                   /n/
        movl   28(%%ebp),   %%eax #Calc: (dw0*dw2)  /n/
        mull              4(%%ebp)                  /n/
        addl       %%eax,   %%esi                   /n/
        adcl       %%edx,   %%edi                   /n/
        movl   24(%%ebp),  %%eax #Calc: (dw1*dw2)   /n/
        mull              4(%%ebp)                  /n/
        addl       %%eax,   %%edi                   /n/
        movl   28(%%ebp),   %%eax #Calc: (dw0*dw3)  /n/
        mull               (%%ebp)                  /n/
        addl       %%eax,   %%edi                   /n/
        pop        %%ebp                            /n"
        :"=b"(this->dw0),"=c"(this->dw1),"=S"(this->dw2),"=D"(this->dw3)
        :"a"(&data):"%ebp");

        dw0 ^= result_xor_mask;
        dw1 ^= result_xor_mask;
        dw2 ^= result_xor_mask;
        dw3 ^= result_xor_mask;
        return (*this += (result_xor_mask & 1));
    }
};

En cuanto a la división, examinar el código es bastante inútil, ya que necesitaré cambiar el algoritmo matemático para ver los beneficios sustanciales. La única opción viable parece ser la división de alto radio, pero aún tengo que resolver (en mi opinión) cómo funcionará.

Answer 1

No me preocuparía mucho sobre la multiplicación. Lo que estás haciendo parece bastante eficiente. Realmente no seguí el Griego en la Multiplicación Karatsuba, pero mi sensación es que sería más eficiente solo con números mucho más grandes de lo que estás tratando.

Una sugerencia que tengo es tratar de usar los bloques más pequeños de ensamblaje en línea, en lugar de codificar su lógica en el ensamblaje. Podrías escribir una función:

struct div_result { u_int x[2]; };
static inline void mul_add(int a, int b, struct div_result *res);

La función se implementará en ensamblado en línea y la invocará desde el código C ++. Debe ser tan eficiente como el ensamblaje puro, y mucho más fácil de codificar.

Sobre la división, no sé. La mayoría de los algoritmos que vi hablan de la eficiencia asintótica, lo que puede significar que solo son eficientes para un gran número de bits.

Answer 2

¿Entiendo correctamente sus datos que está ejecutando su prueba en una máquina de 1.8 GHz y la "u" en sus tiempos son ciclos de procesador?

Si es así, 546 ciclos para 10 MULTI de 32x32 bits me parecen un poco lentos. Tengo mi propia marca de bignums aquí en un Core2 Duo de 2GHz y un MUL de 128x128 = 256 bit se ejecuta en aproximadamente 150 ciclos (hago todos los 16 MULs pequeños), es decir, unas 6 veces más rápido. Pero eso podría ser simplemente una CPU más rápida.

Asegúrese de desenrollar los bucles para guardar esa sobrecarga. Haga tan poco registro de guardar como sea necesario. Tal vez sea útil si publica el código ASM aquí, para que podamos revisarlo.

Karatsuba no lo ayudará, ya que comienza a ser eficiente solo a partir de unas 20-40 palabras de 32 bits.

La división siempre es mucho más costosa que la multiplicación. Si se divide por una constante o por el mismo valor muchas veces, puede ser útil precomputar el recíproco y luego multiplicarlo.