c++ - inc - mov byte eax

Eficiente adición de 128 bits utilizando la marca de transporte

Question

Estoy usando un contador entero de 128 bits en los bucles muy internos de mi código C ++. (Antecedentes irrelevantes: la aplicación real está evaluando ecuaciones de diferencias finitas en una cuadrícula regular, lo que implica incrementar repetidamente números enteros grandes, e incluso 64 bits no es suficiente precisión porque el redondeo pequeño se acumula lo suficiente como para afectar las respuestas).

He representado el número entero como dos largos sin firmar de 64 bits. Ahora necesito incrementar esos valores por una constante de 128 bits. Esto no es difícil, pero tienes que capturar manualmente el acarreo de la palabra baja a la palabra alta.

Tengo un código de trabajo como este:

inline void increment128(unsigned long &hiWord, unsigned long &loWord)
  {
    const unsigned long hiAdd=0x0000062DE49B5241;
    const unsigned long loAdd=0x85DC198BCDD714BA;

    loWord += loAdd;
    if (loWord < loAdd) ++hiWord; // test_and_add_carry
    hiWord += hiAdd;
  }

Este es un código estricto y simple. Funciona.

Lamentablemente, esto es aproximadamente el 20% de mi tiempo de ejecución. La línea asesina es esa prueba LoWord. Si lo elimino, obviamente obtengo las respuestas incorrectas, pero la sobrecarga del tiempo de ejecución cae del 20% al 4%. ¡Entonces esa prueba de transporte es especialmente costosa!

Mi pregunta: ¿Expone C ++ las marcas de transporte de hardware, incluso como una extensión de GCC? Parece que las adiciones podrían realizarse sin la línea de prueba y carga-acarreo anterior si las instrucciones compiladas realmente usaran un agregado usando la última instrucción de acarreo para la adición de la palabra clave. ¿Hay alguna manera de reescribir la línea test-and-add-carry para que el compilador use el opcode intrínseco?

Answer 1

En realidad, gcc usará el acarreo automáticamente si escribe su código cuidadosamente ...

gcc -O2 -Wall -Werror -S este código con gcc -O2 -Wall -Werror -S :

void increment128_1(unsigned long &hiWord, unsigned long &loWord)
{
    const unsigned long hiAdd=0x0000062DE49B5241;
    const unsigned long loAdd=0x85DC198BCDD714BA;

    loWord += loAdd;
    if (loWord < loAdd) ++hiWord; // test_and_add_carry                                                                                                             
    hiWord += hiAdd;
}

void increment128_2(unsigned long &hiWord, unsigned long &loWord)
{
    const unsigned long hiAdd=0x0000062DE49B5241;
    const unsigned long loAdd=0x85DC198BCDD714BA;

    loWord += loAdd;
    hiWord += hiAdd;
    hiWord += (loWord < loAdd); // test_and_add_carry                                                                                                               
}

Este es el conjunto para increment128_1:

.cfi_startproc
        movabsq     $-8801131483544218438, %rax
        addq        (%rsi), %rax
        movabsq     $-8801131483544218439, %rdx
        cmpq        %rdx, %rax
        movq        %rax, (%rsi)
        ja  .L5
        movq        (%rdi), %rax
        addq        $1, %rax
.L3:
        movabsq     $6794178679361, %rdx
        addq        %rdx, %rax
        movq        %rax, (%rdi)
        ret

... y este es el conjunto para increment128_2:

        movabsq     $-8801131483544218438, %rax
        addq        %rax, (%rsi)
        movabsq     $6794178679361, %rax
        addq        (%rdi), %rax
        movabsq     $-8801131483544218439, %rdx
        movq        %rax, (%rdi)
        cmpq        %rdx, (%rsi)
        setbe       %dl
        movzbl      %dl, %edx
        leaq        (%rdx,%rax), %rax
        movq        %rax, (%rdi)
        ret

Tenga en cuenta la falta de ramas condicionales en la segunda versión.

[editar]

Además, las referencias a menudo son malas para el rendimiento, porque GCC tiene que preocuparse por el aliasing ... A menudo es mejor simplemente pasar cosas por valor. Considerar:

struct my_uint128_t {
    unsigned long hi;
    unsigned long lo;
};

my_uint128_t increment128_3(my_uint128_t x)
{
    const unsigned long hiAdd=0x0000062DE49B5241;
    const unsigned long loAdd=0x85DC198BCDD714BA;

    x.lo += loAdd;
    x.hi += hiAdd + (x.lo < loAdd);
    return x;
}

Montaje:

        .cfi_startproc
        movabsq     $-8801131483544218438, %rdx
        movabsq     $-8801131483544218439, %rax
        movabsq     $6794178679362, %rcx
        addq        %rsi, %rdx
        cmpq        %rdx, %rax
        sbbq        %rax, %rax
        addq        %rcx, %rax
        addq        %rdi, %rax
        ret

Este es en realidad el código más ajustado de los tres.

... Bien, ninguno de ellos usó el acarreo automáticamente :-). Pero sí evitan la rama condicional, que apuesto a que es la parte lenta (ya que la lógica de predicción de bifurcación se equivocará la mitad del tiempo).

[editar 2]

Y uno más, con el que tropecé haciendo un poco de búsqueda. ¿Sabía que GCC tiene soporte integrado para enteros de 128 bits?

typedef unsigned long my_uint128_t __attribute__ ((mode(TI)));

my_uint128_t increment128_4(my_uint128_t x)
{
    const my_uint128_t hiAdd=0x0000062DE49B5241;
    const unsigned long loAdd=0x85DC198BCDD714BA;

    return x + (hiAdd << 64) + loAdd;
}

El montaje de este es casi tan bueno como se puede obtener:

        .cfi_startproc
        movabsq     $-8801131483544218438, %rax
        movabsq     $6794178679361, %rdx
        pushq       %rbx
        .cfi_def_cfa_offset 16
        addq        %rdi, %rax
        adcq        %rsi, %rdx
        popq        %rbx
        .cfi_offset 3, -16
        .cfi_def_cfa_offset 8
        ret

(No estoy seguro de dónde proviene el push / pop de ebx , pero esto todavía no está mal).

Todos estos son con GCC 4.5.2, por cierto.

Answer 2

La mejor respuesta, por supuesto, es usar el soporte __int128_t .

Alternativamente, use un asm en línea. Prefiero usar el formulario de argumento con nombre:

__asm("add %[src_lo], %[dst_lo]/n"
      "adc %[src_hi], %[dst_hi]"
      : [dst_lo] "+&r" (loWord), [dst_hi] "+r" (hiWord)
      : [src_lo] "erm" (loAdd), [src_hi] "erm" (hiAdd)
      : );

loWord se marca como un operando primitivo , porque está escrito antes de que se lean algunos de los otros operandos. Esto evita el código incorrecto para hiAdd = loWord , porque impedirá que gcc use el mismo registro para contener ambos. Sin embargo, impide que el compilador use el mismo registro para el caso loAdd = loWord , donde es seguro.

Tal como lo señala la pregunta temprana, el asm en línea es realmente fácil de equivocarse (en formas difíciles de depurar que solo causan problemas después de algún cambio en el código en el que está incluido).

Se supone que los asm en línea x86 y x86-64 golpean las banderas, por lo que no se necesita un código explícito de "cc".