Fusion interne sans branche plus lente que la fusion interne avec branche

Question

J'ai récemment posé une question sur la Révision du Code de revoir un algorithme de tri nommé QuickMergeSort. Je ne rentrerai pas dans les détails, mais à un certain point, l'algorithme effectue un interne mergesort: au lieu d'utiliser de la mémoire supplémentaire pour stocker les données à fusionner, il permute les éléments à fusionner avec les éléments d'une autre partie de la séquence d'origine, ce qui n'est normalement pas concernées par la fusion. Ici est la partie de l'algorithme que je suis concerné, avec: la fonction qui effectue la fusion:

template<
    typename InputIterator1,
    typename InputIterator2,
    typename OutputIterator,
    typename Compare = std::less<>
>
auto half_inplace_merge(InputIterator1 first1, InputIterator1 last1,
                        InputIterator2 first2, InputIterator2 last2,
                        OutputIterator result, Compare compare={})
    -> void
{
    for (; first1 != last1; ++result) {
        if (first2 == last2) {
            std::swap_ranges(first1, last1, result);
            return;
        }

        if (compare(*first2, *first1)) {
            std::iter_swap(result, first2);
            ++first2;
        } else {
            std::iter_swap(result, first1);
            ++first1;
        }
    }
    // first2 through last2 are already in the right spot
}

Cette fonction a été adapté à partir de l'éponyme en fonction de la libc++ mise en œuvre de l' std::inplace_merge; cette nouvelle version swaps éléments avec une autre partie du tableau d'origine au lieu de déplacer des éléments à partir de l'auxiliaire de tableau.

Depuis la fusion est interne, j'ai réalisé que je n'avais pas réellement besoin d'avoir deux types d'entrée: InputIterator1 et InputIterator2 sont toujours les mêmes. Puis je suis venu à réaliser que, puisque les opérations sur first1 et first2 étaient toujours les mêmes, j'ai pu stocker dans un tableau à deux éléments et d'utiliser le résultat de la comparaison à l'indice de la matrice de savoir qui itérateur pour échanger et pour incrémenter. Avec cette petite astuce, je me débarrasser de la direction générale et obtenir une surtout sans branches algorithme de fusion:

template<
    typename InputIterator,
    typename OutputIterator,
    typename Compare = std::less<>
>
auto half_inplace_merge(InputIterator first1, InputIterator last1,
                        InputIterator first2, InputIterator last2,
                        OutputIterator result, Compare compare={})
    -> void
{
    InputIterator store[] = { first1, first2 };

    for (; store[0] != last1; ++result) {
        if (store[1] == last2) {
            std::swap_ranges(store[0], last1, result);
            return;
        }

        bool cmp = compare(*store[1], *store[0]);
        std::iter_swap(result, store[cmp]);
        ++store[cmp];
    }
    // first2 through last2 are already in the right spot
}

Maintenant, le truc, c'est: avec ce nouveau half_inplace_merge de la fonction, l'ensemble de l'algorithme de tri est de 1,5 fois plus lent que l'original à l' half_inplace_merge, et j'ai aucune idée de pourquoi. J'ai essayé plusieurs compilateur niveaux d'optimisation, plusieurs astuces pour éviter d'éventuels problèmes d'aliasing, mais il semble que le problème vient de l'dépourvu de branches tromper lui-même.

Donc, est ce que quelqu'un en mesure d'expliquer pourquoi le sans branches code est plus lent?

---

Addendum: pour ceux qui veulent courir la même référence que j'ai fait... eh bien, il sera un peu difficile: j'ai utilisé les points de référence à partir d'une bibliothèque personnelle, qui comprennent beaucoup de choses, vous aurez besoin de télécharger la bibliothèque, pour ajouter ce fichier quelque part, et pour exécuter ce test après avoir ajouté la ligne nécessaires pour invoquer quick_merge_sort près de la section en surbrillance (vous aurez besoin de rediriger la sortie standard du programme vers un fichier dans un profiles sous-répertoire). Ensuite, vous aurez besoin pour exécuter ce script Python pour voir les résultats, l'ajout d' quick_merge_sort de la ligne en surbrillance. Notez que NumPy et matplotlib besoin d'être installé.

Answer 1

Cette grande différence est le produit de deux conditions.

La première condition est relative au code original. La fusion est très efficace, il y aurait de la difficulté à concevoir quelque chose de beaucoup plus rapide, même si le codage manuellement à l'assemblée, le niveau de langue. L'application des génériques est simple, de sorte que le compilateur ** produit de la même assemblée, avec ou sans elle. Parce que l'implémentation de l'algorithme est efficace, à seulement quelques instructions machine ajouté dans la boucle est capable de produire de la variation significative de proportionnelle indiqué dans la question.

** Compilation des détails tout au long de cette réponse ont été à l'aide de g++ 6.2.1 20160916, la valeur par défaut de Fedora 24 dnf paquet, avec le noyau LINUX 4.8.8-200.fc24.x86_64. D'exécution a été Intel core i7-2600 8M cache. Aussi Atmel SAM3X8E ARM Cortex-M3 avec arm-none-eabi-g++ 4.8.3-2014q1.

La deuxième condition est liée à l'élaboration de la deuxième astuce décrite à l'alinéa 3, phrase 2 de la question. La première astuce, la réduction de types dans le modèle, n'a produit aucun changement significatif dans la langue de l'assembly. La deuxième astuce produit flop-affectant le niveau de l'assemblée des différences dans la sortie du compilateur pour les deux appels.

Cette précompilateur hack peut faciliter les tests.

#ifdef ORIG
#define half_inplace_merge half_inplace_merge_orig
#else // ORIG
#define half_inplace_merge half_inplace_merge_slow
#endif // ORIG
...
half_inplace_merge(niInA.begin(), niInA.end(),
        niInB.begin(), niInB.end(),
        niOut.begin(), compare);

D'exécution et de les comparer à l'aide de ces commandes dans un shell bash exploite le précompilateur hack.

g++ -DORIG -S -fverbose-asm -o /tmp/qq.orig.s /tmp/qq.cpp
g++ -DSLOW -S -fverbose-asm -o /tmp/qq.slow.s /tmp/qq.cpp
araxis.sh /tmp/qq.orig.s /tmp/qq.slow.s  # to run Araxis Merge in Wine

Ces instructions sont un résultat de l'initialisation de la InputIterator store[ ], mais qui est en dehors de la boucle.

leaq    -48(%rbp), %rax #, _4
movq    -64(%rbp), %rdx # first1, tmp104
movq    %rdx, (%rax)    # tmp104, *_5
leaq    8(%rax), %rdx   #, _9
movq    -96(%rbp), %rax # first2, tmp105
movq    %rax, (%rdx)    # tmp105, *_9

Le principal ralentir vient d'être déréférencé les deux éléments contenus dans le magasin[ ], en tant que de besoin par la comparaison et l'échange, et qui est à l'intérieur de la boucle. Ces instructions n'existent pas dans la version sans le second tour.

movb    %al, -17(%rbp)  # _27, cmp
movzbl  -17(%rbp), %eax # cmp, _29
cltq
...
movzbl  -17(%rbp), %edx # cmp, _31
leaq    -48(%rbp), %rax #, tmp121
movslq  %edx, %rdx  # _31, tmp122
salq    $3, %rdx    #, tmp123
addq    %rdx, %rax  # tmp123, _32

Bien que, il y a duplication de code dans le corps de la condition, pour la version sans la tromper, que seuls les impacts de la compacité du code, l'ajout de deux appels, cinq coups, et on compare l'instruction. Le nombre de cycles de PROCESSEUR requis pour effectuer la fusion est la même entre les branches résultant de la comparaison, et la fois d'un manque les instructions énumérées ci-dessus.

Pour chacune de plusieurs syntaxe permutations essayé, en supprimant la redondance dans les branches d'améliorer la compacité inévitablement conduit à des instructions supplémentaires requis le long du chemin d'exécution.

Les détails de l'instruction de séquences pour les différentes permutations abordés jusqu'à présent varient d'un compilateur de compilateur, option d'optimisation de la sélection, et même les conditions de l'appel de fonctions.

Il est théoriquement possible pour un compilateur pour employer un AST (abstract symbole de l'arbre) refactoring de la règle (ou l'équivalent) afin de détecter et de réduire à la fois la mémoire de programme et de cycle du PROCESSEUR exigences pour l'une ou l'autre version de la fonction. Ces règles ont des antécédents (les modèles de recherche) qui correspondent au modèle d'être optimisé dans le code.

L'optimisation de la vitesse pour le code de la deuxième astuce aurait besoin d'un antécédent de la règle qui correspond à la atypique score[ ] l'abstraction à la fois à l'intérieur et à l'extérieur de la boucle. La détection de la direction générale de la redondance sans le deuxième truc, c'est plus objectif raisonnable.

L'intégration de ces deux états à l'intérieur de chaque branche, on peut voir comment les deux comme des modèles dans l'AST peut être assez simple pour un refactoring antécédent de la règle de correspondance et d'exécuter le code désiré réduction de la taille. Il y aurait très peu de gain en vitesse pour ce cas de figure, le cas échéant.

if (compare(*first2, *first1)) {
    std::iter_swap(result, first2 ++);
} else {
    std::iter_swap(result, first1 ++);
}

Answer 2

Ce qui suit est seulement une courte explication intuitive:

Si nous avons à l'échelle loin de tout et de supposer que les itérateurs sont normales pointeurs que nous pouvons dans le premier exemple de stocker toutes les itérateurs dans les registres.

Dans la branche-moins de code on ne peut pas facilement le faire, en raison d' store[cmp], et ++store[cmp] - et cela implique une surcharge de l'utilisation de store[0], et store[1].

Donc (dans ce cas), il est plus important de maximiser l'utilisation des registres d'éviter les branches.