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

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 comstackdas 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 comstackdor use el opcode intrínseco?

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 twigs 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 twig 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 assembly 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.

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 comstackdor 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”.