Ajout efficace de 128 bits à l'aide d'un indicateur de report

Question

Je suis avec un cryptage de 128 bits compteur de nombre entier dans la très intérieur des boucles de mon code C++. (Pas pertinent d'arrière-plan: L'application est en train d'évaluer des différences finies équations sur une grille régulière, ce qui implique de façon répétitive l'incrémentation de grands nombres entiers, et même 64 bits n'est pas assez de précision, parce que les petits arrondissement accumule suffisamment pour influer sur les réponses.)

J'ai représenté la entier comme deux 64 bits unsigned longs. J'ai maintenant besoin d'un accroissement de ces valeurs par un cryptage de 128 bits constant. Ce n'est pas difficile, mais vous devez manuellement attraper le report de la faible mot pour mot haut.

J'ai du code qui fonctionne quelque chose comme ceci:

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;
  }

C'est serré et simple code. Elle fonctionne.

Malheureusement, c'est environ 20% de mon temps d'exécution. Le tueur est que loWord test. Si je le supprime, je suis évidemment d'obtenir de mauvaises réponses, mais la gestion d'exécution des gouttes de 20% à 4%! Alors que porter de test est particulièrement cher!

Ma question: est-ce que C++ exposer le matériel à transporter de drapeaux, de même qu'une extension de GCC? Il semble que les ajouts pouvait se faire sans le tester et ajoutez-porter ligne ci-dessus, si le compilé des instructions d'un complément à l'aide de la dernière effectuer des instructions pour l'hiWord plus. Est-il un moyen de reprendre le test-and-add-porter ligne pour obtenir le compilateur d'utiliser la valeur intrinsèque de l'opcode?

Answer 1

En fait gcc va utiliser le réaliser automatiquement si vous écrivez votre code avec soin...

J'ai compilé ce code avec 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                                                                                                               
}

C'est l'assemblée pour 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

...et c'est l'assemblée pour 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

Note de l'absence de branches conditionnelles dans la deuxième version.

[modifier]

Aussi, les références sont souvent mauvais pour la performance, parce que GCC se soucier de l'aliasing... Il est souvent préférable de simplement passer des choses en valeur. Considérer:

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;
}

Assemblée:

        .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

C'est en fait le plus serré du code de la trois.

...OK, donc aucun de ceux qui ont utilisé les transporter automatiquement :-). Mais ils évitez la branche conditionnelle, qui je pari est la partie lente (depuis la direction de la prévision logique se tromper de la moitié du temps).

[edit 2]

Et un de plus, qui je suis tombé en faisant une petite recherche. Saviez-vous GCC a prise en charge intégrée de 128 bits entiers?

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;
}

L'assemblée est à peu près aussi bon qu'il obtient:

        .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

(Pas sûr de l'endroit où le push/pop d' ebx est venu, mais c'est quand même pas mal.)

Tous ces éléments sont avec GCC 4.5.2, par la manière.

Answer 2

La meilleure réponse, bien sûr, est d'utiliser le support intégré __int128_t .

Vous pouvez également utiliser un asm en ligne. Je préfère utiliser la forme d'argument nommé:

 __asm("add %[alo], %[wlo]\n"
      "adc %[ahi], %[whi]"
      : [wlo] "+r" (loWord), [whi] "+r" (hiWord)
      : [alo] "r" (loAdd), [ahi] "r" (hiAdd));