Quel est le moyen le plus rapide pour mettre à jour une variable sur une condition?

Question

J'ai un pointeur, ptr, et une condition, cond. J'ai besoin le plus rapidement possible pour réinitialiser ptr si cond est true, ou de conserver ptr inchangée si l' cond est false. L'implémentation actuelle est, trivialement:

void reset_if_true(void*& ptr, bool cond)
{
    if (cond)
        ptr = nullptr;
}

Je suis conscient que le code ci-dessus, le rendement est bon, et je ne peut pas s'attendre à une importante augmentation des performances de l'optimisation. Cependant, ce code est appelé à plusieurs millions de fois par seconde, et chaque nanoseconde enregistré est pertinent.

Je pensais à quelque chose que de se débarrasser de la branche, par exemple:

void* p[] = { ptr, nullptr };
ptr = p[cond];

mais je ne suis pas sûr que c'est la meilleure façon de procéder.

Answer 1

void reset_if_true(void*& ptr, bool cond)
{
    if (cond)
        ptr = nullptr;
}

Le naïf solution sera sans aucun doute la manière la plus rapide dans la majorité des cas. Bien qu'il dispose d'une succursale, qui peut être lent sur moderne pipeline processeurs, il n'est lente si la branche est mispredicted. Depuis la direction générale, les indicateurs sont très bon, de nos jours, à moins que la valeur de cond est extrêmement imprévisible, il est probable qu'une simple branche conditionnelle est le moyen le plus rapide pour écrire le code.

Et si elle ne l'est pas, un bon compilateur doit savoir et être en mesure d'optimiser le code pour quelque chose de mieux, compte tenu de l'architecture cible. Qui va à gnasher729 point: il suffit d'écrire le code de la manière la plus simple et de laisser l'optimisation dans les mains de l'optimiseur.

Tout cela est de bon conseil en général, il est parfois poussée à l'extrême. Si vous soucier de la vitesse de ce code, vous devez vérifier et voir ce que le compilateur est en train de faire avec elle. Vérifiez le code de l'objet qu'il génère, et assurez-vous qu'il est raisonnable et que le code de fonction est prise en inline.

Un tel examen peut être assez révélateur. Par exemple, considérons x86-64, où les branches peuvent être très coûteux dans le cas où la direction de la prévision est déjouée (qui est vraiment le seul moment où c'est une question intéressante, supposons donc qu' cond est totalement imprévisible). Presque tous les compilateurs vont générer à la suite de l'implémentation naïve:

reset_if_true(void*&, bool):
    test   sil, sil              ; test 'cond'
    je     CondIsFalse
    mov    QWORD PTR [rdi], 0    ; set 'ptr' to nullptr, and fall through
  CondIsFalse:
    ret

C'est sur que serré de code que vous pouvez imaginer. Mais si vous mettez de la branche prédicteur dans un cas pathologique, il pourrait finir par être plus lent que d'utiliser un conditionnel déplacer:

reset_if_true(void*&, bool):
    xor    eax, eax              ; pre-zero the register RAX
    test   sil, sil              ; test 'cond'
    cmove  rax, QWORD PTR [rdi]  ; if 'cond' is false, set the register RAX to 'ptr'
    mov    QWORD PTR [rdi], rax  ; set 'ptr' to the value in the register RAX
    ret                          ;  (which is either 'ptr' or 0)

Conditionnel se déplace relativement élevé de temps de latence, de sorte qu'ils sont beaucoup plus lentes que bien prédit une branche, mais ils peuvent être plus rapides qu'un de totalement imprévisible de la branche. Vous attendez un compilateur de savoir ce lors du ciblage de l'architecture x86, mais il n'a pas (au moins dans ce simple exemple) ont aucune connaissance sur le cond's de la prévisibilité. Il suppose le cas simple, que la direction de la prévision sera de votre côté, et génère Un code à la place de code B.

Si vous décidez que vous voulez encourager le compilateur de générer sans branches code à cause de l'imprévisible condition, vous pouvez essayer ce qui suit:

void reset_if_true_alt(void*& ptr, bool cond)
{
    ptr = (cond) ? nullptr : ptr;
}

Il réussit à persuader les versions modernes de Clang pour générer sans branches code B, mais est un pessimization dans GCC et MSVC. Si vous n'avez pas coché l'assembly généré, vous n'auriez pas connu que. Si vous voulez forcer la GCC et MSVC pour générer sans branches code, vous aurez à travailler plus dur. Par exemple, vous pouvez utiliser la variante publié dans la question:

void reset_if_true(void*& ptr, bool cond)
{
    void* p[] = { ptr, nullptr };
    ptr = p[cond];
}

Lorsque le ciblage des x86, tous les compilateurs génèrent sans branches code, mais il n'est pas spécialement joli code. En fait, aucun d'entre eux génèrent conditionnelle se déplace. Au lieu de cela, vous obtenez plusieurs accès à la mémoire dans l'ordre pour construire le tableau:

reset_if_true_alt(void*&, bool):
    mov     rax, QWORD PTR [rdi]
    movzx   esi, sil
    mov     QWORD PTR [rsp-16], 0
    mov     QWORD PTR [rsp-24], rax
    mov     rax, QWORD PTR [rsp-24+rsi*8]
    mov     QWORD PTR [rdi], rax
    ret

Laid et très probablement inefficace. J'avais prédire qu'il donne à l'un saut conditionnel version une course pour son argent, même dans le cas où la branche est mispredicted. Vous auriez à l'indice de référence pour être sûr, bien sûr, mais il n'est probablement pas un bon choix.

Si vous étiez encore désespérée pour éliminer la branche sur MSVC ou GCC, vous avez à faire quelque chose de plus laid impliquant réinterpréter le pointeur de bits et de se tourner. Quelque chose comme:

void reset_if_true_alt(void*& ptr, bool cond)
{
    std::uintptr_t p = reinterpret_cast<std::uintptr_t&>(ptr);
    p &= -(!cond);
    ptr = reinterpret_cast<void*>(p);
}

Qui vous donnera les éléments suivants:

reset_if_true_alt(void*&, bool):
    xor   eax, eax
    test  sil, sil
    sete  al
    neg   eax
    cdqe
    and   QWORD PTR [rdi], rax
    ret

Encore une fois, ici, nous avons des instructions plus qu'une simple branche, mais au moins ils sont relativement faible temps de latence des instructions. Un test sur des données réalistes vous dira si le compromis est en vaut la peine. Et vous donner la justification, vous devez mettre un commentaire si vous allez en fait le check-in code comme celui-ci.

Une fois que je suis descendu de la bit-tourner trou de lapin, j'ai été en mesure de forcer MSVC et de la GCC à l'utilisation conditionnelle de déplacer les instructions. Apparemment ils ne le faisaient pas cette optimisation, parce que nous nous intéressions à un pointeur:

void reset_if_true_alt(void*& ptr, bool cond)
{
    std::uintptr_t p = reinterpret_cast<std::uintptr_t&>(ptr);
    ptr = reinterpret_cast<void*>(cond ? 0 : p);
}

reset_if_true_alt(void*&, bool):
    mov    rax, QWORD PTR [rdi]
    xor    edx, edx
    test   sil, sil
    cmovne rax, rdx
    mov    QWORD PTR [rdi], rax
    ret

Compte tenu de la latence de CMOVNE et le même nombre d'instructions, je ne sais pas si ce serait réellement plus rapide que la version précédente. L'indice de référence que vous avez couru vous dirais si elle l'était.

De même, si nous avons peu-l'ornement de l'état, de nous sauver nous-mêmes un accès à la mémoire:

void reset_if_true_alt(void*& ptr, bool cond)
{
   std::uintptr_t c = (cond ? 0 : -1);
   reinterpret_cast<std::uintptr_t&>(ptr) &= c;
}

reset_if_true_alt(void*&, bool):
     xor    esi, 1
     movzx  esi, sil
     neg    rsi
     and    QWORD PTR [rdi], rsi
     ret

(C'est GCC. MSVC fait quelque chose de légèrement différent, préférant le son caractéristique de la séquence de neg, sbb, neg, et dec des instructions, mais les deux sont moralement équivalent. Clang transforme dans le même conditionnelle déplacement que nous avons vu générer ci-dessus). Cela peut être le meilleur code pourtant, si nous avons besoin pour éviter les branches, considérant qu'il génère sane de sortie sur tous testé les compilateurs tout en préservant (dans une certaine mesure) de la lisibilité dans le code source.

Answer 2

Le plus faible fruits mûrs, ici, n'est-ce pas ce que vous pensez qu'elle est. Comme discuté dans plusieurs autres réponses, en reset_if_true va être compilé en code machine qui est aussi rapide que vous pouvez raisonnablement s'attendre à obtenir pour ce qu'il fait. Si ce n'est pas assez rapide, vous devez commencer à penser à changer ce qu'il fait. Je vois deux options, l'une simple, l'un n'est pas si facile:

1. Modifier la convention d'appel:

   template <class T>
   inline T* reset_if_true(T* ptr, bool condition)
   {
       return condition ? nullptr : ptr;
   }
   

   et puis changement de l'appelant(s) à lire quelque chose comme

   ptr_var = reset_if_true(ptr_var, expression);
   

   Ce que ce n'est plus de chance d' ptr_var aurez à vivre dans un registre au cours de la critique la plus intime de la boucle qui appelle reset_if_true millions de fois par seconde, et il n'y aura pas accès à la mémoire associée. ptr_var prise en contraints à la mémoire est le plus cher dans votre code, la façon dont il est aujourd'hui, encore plus cher que potentiellement mispredicted branches. (Suffisamment bon compilateur peut faire de cette transformation pour vous fournis reset_if_true est inlinable, mais il n'est pas toujours possible pour lui de le faire.)

2. Modifier les environs de l'algorithme, de sorte qu' reset_if_true n'est pas appelé millions de fois par seconde de plus.

   Puisque vous ne nous dites pas ce que les environs de l'algorithme est, je ne peux pas vous aider avec ça. Je peux cependant vous dire que de faire quelque chose impliquant la vérification d'une condition millions de fois par seconde, probablement indique un algorithme d'une complexité quadratique du temps ou pour le pire, et toujours des moyens, vous devriez au moins penser à trouver un meilleur. (Il peut ne pas être un meilleur, hélas.)

Answer 3

Tant que nous sommes en sizeof(size_t) == sizeof(void*), nullptr représenté en binaire 0 et size_t à l'aide de tous les bits (ou std::uintptr_t), vous pouvez faire ceci:

// typedef std::uintptr_t ptrint_t; // uncomment if you have it
typedef size_t ptrint_t; // comment out if you have std::uintptr_t

void reset_if_true(void*& ptr, bool cond)
{
    ((ptrint_t&)ptr) &= -ptrint_t( !cond );
}

Notez, cependant, que le moment de la fonte à partir de bool de size_t prend est très dépendant de l'implémentation et peut prendre une branche en lui-même.

Answer 4

Le code est absolument simple.

Vous avez certainement rendre les choses beaucoup plus rapidement par l'in-lining la fonction (si le compilateur n'a pas l'inclure sur son propre). Par exemple, l'in-lining, pourrait signifier que le pointeur de variable que vous êtes paramètre à null pourrait rester dans un registre.

Autre que cela, ce code est si simple, si il y a des trucs qui pourraient être utilisés pour le rendre plus rapide, le compilateur pourrait les utiliser.

Answer 5

Mise à jour: j'ai ré-implémenté ma réponse.

Dans le code suivant, l'idée est de convertir le pointeur dans un certain nombre et en le multipliant par un nombre (cond). Note inline utilisé. La Multiplication peuvent aider à l'aide d'une architecture qui utilise un pipeline.

#include <cstdint>

template <typename T>
inline T* reset_if_true(T* p, bool cond) {
  void* ptr = (void*)p; // The optimising compiler (-O3) will get rid of unnecessary variables.
  intptr_t ptrint;
  // This is an unrecommended practice.
  ptrint = (intptr_t)ptr;
  ptrint = ptrint * cond;  // Multiply the integer
  void* ptr2 = (void*)ptrint;
  T* ptrv = (T*)ptr2;
  return ptrv;
}

Exemple d'utilisation:

#include <iostream>
#include <vector>

void test1(){
    //doulbe d = 3.141592;
    //typedef std::vector<double> mytype;
    std::vector<double> data = {3,1,4};
    auto ptr = &data;
    std::cout << (void*)ptr << std::endl;
    auto ptr2 = reset_if_true(ptr, 1);
    //auto ptr2 = (mytype*)reset_if_true(ptr, 1);
    std::cout << reset_if_true(ptr, 1) << " -> " << (*(reset_if_true(ptr, 1))).size() << std::endl;
    std::cout << reset_if_true(ptr, 2) << " -> "<< (*(reset_if_true(ptr, 2))).size() << std::endl;
    std::cout << reset_if_true(ptr, 0) <<
        " is null? " << (reset_if_true(ptr, 0) == NULL) <<  // Dont dereference a null.
        std::endl;
}


void test2(){
    double data = 3.141500123;
    auto ptr = &data;
    std::cout << (void*)ptr << std::endl;
    auto ptr2 = reset_if_true(ptr, 1);
    //auto ptr2 = (mytype*)reset_if_true(ptr, 1);
    std::cout << reset_if_true(ptr, 1) << " -> " << (*(reset_if_true(ptr, 1))) << std::endl;
    std::cout << reset_if_true(ptr, 2) << " -> "<< (*(reset_if_true(ptr, 2))) << std::endl;
    std::cout << reset_if_true(ptr, 0) <<
        " is null? " << (reset_if_true(ptr, 0) == NULL) <<  // Dont dereference a null.
        std::endl;

}

int main(){ test1(); test2(); }

Compiler à l'aide de ces indicateurs: -O3 -std=c++14. La sortie est:

0x5690
0x5690 -> 3
0x5690 -> 3
0 is null? 1
0x5690
0x5690 -> 3.1415
0x5690 -> 3.1415
0 is null? 1

Il pourrait avoir de la mémoire des problèmes d'alignement lorsque ces options sont utilisés dans le compilateur de ligne de commande -s FORCE_ALIGNED_MEMORY=1 . Voir aussi reinterpret_cast. N'oubliez pas d'utiliser -O3.

Cond peut être n'importe quelle valeur non nulle. Il y a de la place pour l'amélioration de la performance ici si nous savons qu'il n'est autre que 0 ou 1. Dans ce cas, vous pouvez utiliser int un autre type entier pour cond.

PS. C'est une mise à jour de réponse. La réponse précédente, comme je l'ai déjà mentionné dans ma réponse, a eu des problèmes. La solution est d'utiliser intptr_t, et bien sûr, inline.

Options du compilateur utilisé:

 em++ reset_if_true.cpp -O3 -std=c++14 -o reset_if_true.js
 node reset_if_true.js