`std::list<>::sort()` - pourquoi le passage soudain à la stratégie top-down ?

Question

Je me souviens que depuis le début des temps, l'approche la plus populaire pour implémenter std::list<>::sort() était l'algorithme de tri Merge Sort classique implémenté de manière ascendante (bottom-up) (voir aussi Qu'est-ce qui rend l'implémentation du tri std::list de gcc si rapide?).

Je me souviens d'avoir vu quelqu'un qualifier cette stratégie d'approche en "chaînage d'oignons".

C'est du moins la façon dont cela se passe dans l'implémentation de la bibliothèque standard C++ de GCC (voir, par exemple, ici). Et c'est ainsi que cela se passait dans l'ancienne STL de Dimkumware dans la version de bibliothèque standard de MSVC, ainsi que dans toutes les versions de MSVC jusqu'à VS2013.

Cependant, la bibliothèque standard fournie avec VS2015 ne suit soudainement plus cette stratégie de tri. La bibliothèque livrée avec VS2015 utilise une implémentation récursive plutôt directe de Merge Sort ascendant. Cela me semble étrange, car l'approche ascendante nécessite l'accès au point médian de la liste afin de la diviser en deux. Comme std::list<> ne prend pas en charge l'accès aléatoire, le seul moyen de trouver ce point médian est de littéralement parcourir la moitié de la liste. De plus, au tout début, il est nécessaire de connaître le nombre total d'éléments dans la liste (ce qui n'était pas nécessairement une opération en O(1) avant C++11).

Néanmoins, std::list<>::sort() dans VS2015 fait exactement cela. Voici un extrait de cette implémentation qui localise le point médian et effectue des appels récursifs

...
iterator _Mid = _STD next(_First, _Size / 2);
_First = _Sort(_First, _Mid, _Pred, _Size / 2);
_Mid = _Sort(_Mid, _Last, _Pred, _Size - _Size / 2);
...

Comme vous pouvez le constater, ils utilisent simplement std::next pour parcourir la première moitié de la liste et arriver à l'itérateur _Mid.

Quelle pourrait être la raison de ce changement, je me demande? Tout ce que je vois, c'est une inefficacité apparemment évidente des appels répétitifs à std::next à chaque niveau de récursion. La logique naïve dit que c'est plus lent. S'ils sont prêts à payer ce genre de prix, ils s'attendent probablement à obtenir quelque chose en retour. Qu'obtiennent-ils alors? Je ne vois pas immédiatement cet algorithme comme ayant un meilleur comportement de cache (comparé à l'approche ascendante originale). Je ne le vois pas immédiatement non plus comme se comportant mieux sur des séquences pré-triées.

Il est vrai que depuis C++11 std::list<> est essentiellement requis de stocker le nombre de ses éléments, ce qui rend ce qui précède légèrement plus efficace, puisque nous connaissons toujours le nombre d'éléments à l'avance. Mais cela ne semble toujours pas suffisant pour justifier le balayage séquentiel à chaque niveau de récursion.

(Admettons que je n'ai pas essayé de comparer les implémentations l'une contre l'autre. Peut-être qu'il y a des surprises là-bas.)

Answer 1

Notez que cette réponse a été mise à jour pour répondre à tous les problèmes mentionnés dans les commentaires ci-dessous et après la question, en effectuant le même changement d'un tableau de listes à un tableau d'itérateurs, tout en conservant l'algorithme de tri par fusion ascendante plus rapide, et en éliminant le faible risque de débordement de pile dû à la récursion avec l'algorithme de tri par fusion descendante.

La raison pour laquelle je n'avais pas envisagé les itérateurs à l'origine était due au passage de VS2015 à l'algorithme top down, ce qui m'a amené à penser qu'il y avait un problème à essayer de modifier l'algorithme bottom up existant pour utiliser les itérateurs, ce qui nécessitait de passer à l'algorithme top down plus lent. Ce n'est que lorsque j'ai essayé d'analyser moi-même le passage aux itérateurs que j'ai réalisé qu'il y avait une solution pour l'algorithme bottom up.

Dans le commentaire de @sbi, il a demandé à l'auteur de l'approche top down, Stephan T. Lavavej, pourquoi ce changement a été effectué. La réponse de Stephan a été "pour éviter l'allocation de mémoire et les allocateurs constructibles par défaut". VS2015 a introduit les allocateurs non-constructibles par défaut et stateful, ce qui présente un problème lors de l'utilisation du tableau de listes de la version précédente, car chaque instance d'une liste alloue un nœud fictif, et un changement serait nécessaire pour gérer l'absence d'allocateur par défaut.

La solution de Lavavej a été de passer à l'utilisation d'itérateurs pour garder la trace des limites d'exécution dans la liste originale au lieu d'un tableau interne de listes. La logique de fusion a été modifiée pour utiliser 3 paramètres d'itérateurs, le 1er paramètre est l'itérateur au début de l'exécution gauche, le 2ème paramètre est l'itérateur à la fin de l'exécution gauche == itérateur au début de l'exécution droite, le 3ème paramètre est l'itérateur à la fin de l'exécution droite. Le processus de fusion utilise std::list::splice pour déplacer les noeuds dans la liste originale pendant les opérations de fusion. Cela présente l'avantage supplémentaire d'être sans danger pour les exceptions. Si la fonction de comparaison de l'appelant lève une exception, la liste sera réordonnée, mais aucune perte de données ne se produira (en supposant que le splice ne peut pas échouer). Avec le schéma précédent, certaines (ou la plupart) des données se trouveraient dans le tableau interne des listes si une exception se produisait, et des données seraient perdues dans la liste d'origine.

Toutefois, le passage au tri par fusion descendante n'était pas nécessaire. Initialement, pensant qu'il y avait une raison inconnue pour moi pour le passage de VS2015 au tri descendant, je me suis concentré sur l'utilisation des interfaces internes de la même manière que std::list::splice. J'ai ensuite décidé d'étudier la possibilité de passer du bas vers le haut pour utiliser un tableau d'itérateurs. J'ai réalisé que l'ordre des exécutions stockées dans le tableau interne était du plus récent (array[0] = le plus à droite) au plus ancien (array[last] = le plus à gauche), et qu'il pouvait utiliser la même logique de fusion basée sur les itérateurs que l'approche top down de VS2015.

Pour le tri par fusion de bas en haut, array[i] est un itérateur vers le début d'une sous-liste triée avec 2^i noeuds, ou il est vide (en utilisant std::list::end pour indiquer vide). La fin de chaque sous-liste triée sera le début d'une sous-liste triée dans la prochaine entrée antérieure non vide du tableau, ou si elle est au début du tableau, dans un itérateur local (il pointe vers la fin de la dernière exécution). Comme dans l'approche descendante, le tableau d'itérateurs n'est utilisé que pour garder la trace des limites des parcours triés dans la liste liée originale, tandis que le processus de fusion utilise std::list::splice pour déplacer les noeuds dans la liste liée originale.

Si une liste chaînée est grande et que les nœuds sont dispersés, il y aura beaucoup de manques dans le cache. La méthode ascendante sera environ 30% plus rapide que la méthode descendante (ce qui équivaut à dire que la méthode descendante est environ 42% plus lente que la méthode ascendante). Par ailleurs, si la mémoire est suffisante, il est généralement plus rapide de déplacer la liste dans un tableau ou un vecteur, de trier le tableau ou le vecteur, puis de créer une nouvelle liste à partir du tableau ou du vecteur trié.

Exemple de code C++ :

#define ASZ 32

template <typename T>
void SortList(std::list<T> &ll)
{
    if (ll.size() < 2)                  // return if nothing to do
        return;
    std::list<T>::iterator ai[ASZ];     // array of iterators
    std::list<T>::iterator mi;          // middle iterator (end lft, bgn rgt)
    std::list<T>::iterator ei;          // end    iterator
    size_t i;
    for (i = 0; i < ASZ; i++)           // "clear" array
        ai[i] = ll.end();
    // merge nodes into array
    for (ei = ll.begin(); ei != ll.end();) {
        mi = ei++;
        for (i = 0; (i < ASZ) && ai[i] != ll.end(); i++) {
            mi = Merge(ll, ai[i], mi, ei);
            ai[i] = ll.end();
        }
        if(i == ASZ)
            i--;
        ai[i] = mi;
    }
    // merge array into single list
    ei = ll.end();                              
    for(i = 0; (i < ASZ) && ai[i] == ei; i++);
    mi = ai[i++];
    while(1){
        for( ; (i < ASZ) && ai[i] == ei; i++);
        if (i == ASZ)
            break;
        mi = Merge(ll, ai[i++], mi, ei);
    }
}

template <typename T>
typename std::list<T>::iterator Merge(std::list<T> &ll,
                             typename std::list<T>::iterator li,
                             typename std::list<T>::iterator mi,
                             typename std::list<T>::iterator ei)
{
    std::list<T>::iterator ni;
    (*mi < *li) ? ni = mi : ni = li;
    while(1){
        if(*mi < *li){
            ll.splice(li, ll, mi++);
            if(mi == ei)
                return ni;
        } else {
            if(++li == mi)
                return ni;
        }
    }
}

---

Exemple de code de remplacement pour std::list::sort() de VS2019 (la logique de fusion a été transformée en une fonction interne distincte, car elle est maintenant utilisée à deux endroits).

private:
    template <class _Pr2>
    iterator _Merge(_Pr2 _Pred, iterator _First, iterator _Mid, iterator _Last){
        iterator _Newfirst = _First;
        for (bool _Initial_loop = true;;
            _Initial_loop       = false) { // [_First, _Mid) and [_Mid, _Last) are sorted and non-empty
            if (_DEBUG_LT_PRED(_Pred, *_Mid, *_First)) { // consume _Mid
                if (_Initial_loop) {
                    _Newfirst = _Mid; // update return value
                }
                splice(_First, *this, _Mid++);
                if (_Mid == _Last) {
                    return _Newfirst; // exhausted [_Mid, _Last); done
                }
            }
            else { // consume _First
                ++_First;
                if (_First == _Mid) {
                    return _Newfirst; // exhausted [_First, _Mid); done
                }
            }
        }
    }

    template <class _Pr2>
    void _Sort(iterator _First, iterator _Last, _Pr2 _Pred,
        size_type _Size) { // order [_First, _Last), using _Pred, return new first
                           // _Size must be distance from _First to _Last
        if (_Size < 2) {
            return;        // nothing to do
        }
        const size_t _ASZ = 32;         // array size
        iterator _Ai[_ASZ];             // array of   iterators to runs
        iterator _Mi;                   // middle     iterator
        iterator _Li;                   // last (end) iterator
        size_t _I;                      // index to _Ai
        for (_I = 0; _I < _ASZ; _I++)   // "empty" array
            _Ai[_I] = _Last;            //   _Ai[] == _Last => empty entry
        // merge nodes into array
        for (_Li = _First; _Li != _Last;) {
            _Mi = _Li++;
            for (_I = 0; (_I < _ASZ) && _Ai[_I] != _Last; _I++) {
                _Mi = _Merge(_Pass_fn(_Pred), _Ai[_I], _Mi, _Li);
                _Ai[_I] = _Last;
            }
            if (_I == _ASZ)
                _I--;
            _Ai[_I] = _Mi;
        }
        // merge array runs into single run
        for (_I = 0; _I < _ASZ && _Ai[_I] == _Last; _I++);
        _Mi = _Ai[_I++];
        while (1) {
            for (; _I < _ASZ && _Ai[_I] == _Last; _I++);
            if (_I == _ASZ)
                break;
            _Mi = _Merge(_Pass_fn(_Pred), _Ai[_I++], _Mi, _Last);
        }
    }

---

Le reste de cette réponse est historique.

---

J'ai pu reproduire le problème (l'ancien tri ne compile pas, le nouveau fonctionne) en me basant sur une démo de @IgorTandetnik :

#include <iostream>
#include <list>
#include <memory>

template <typename T>
class MyAlloc : public std::allocator<T> {
public:
    MyAlloc(T) {}  // suppress default constructor

    template <typename U>
    MyAlloc(const MyAlloc<U>& other) : std::allocator<T>(other) {}

    template< class U > struct rebind { typedef MyAlloc<U> other; };
};

int main()
{
    std::list<int, MyAlloc<int>> l(MyAlloc<int>(0));
    l.push_back(3);
    l.push_back(0);
    l.push_back(2);
    l.push_back(1);
    l.sort();
    return 0;
}

---

J'ai remarqué ce changement en juillet 2016 et j'ai envoyé un courriel à P.J. Plauger à ce sujet le 1er août 2016. Voici un extrait de sa réponse :

Il est intéressant de noter que notre journal des modifications ne reflète pas ce changement. Cela probablement que cela a été "suggéré" par l'un de nos plus gros clients et qu'il et que je l'ai eu lors de la revue de code. Tout ce que je sais maintenant, c'est que le changement est arrivé aux alentours de l'automne 2015. Quand j'ai revu le code, la première chose qui m'a frappé était la ligne :

    iterator _Mid = _STD next(_First, _Size / 2);

qui, bien sûr, peut prendre un muy longtemps pour une grande liste.

Le code semble un peu plus élégant que ce que j'ai écrit au début de 1995( !), mais sa complexité temporelle est bien pire. Cette version était modelée après l'approche de Stepanov, Lee, et Musser dans la STL originale. Il est rare qu'ils se trompent dans leur choix d'algorithmes.

Je reviens maintenant à notre dernière bonne version connue du code original.

Je ne sais pas si le retour au code d'origine de P.J. Plauger a permis de résoudre le problème du nouvel allocateur, ni si ou comment Microsoft interagit avec Dinkumware.

Pour comparer les méthodes descendantes et ascendantes, j'ai créé une liste chaînée de 4 millions d'éléments, chacun consistant en un entier non signé de 64 bits, en supposant que je me retrouverais avec une liste doublement chaînée de nœuds ordonnés presque séquentiellement (même s'ils seraient alloués dynamiquement), je les ai remplis de nombres aléatoires, puis je les ai triés. Les noeuds ne se déplacent pas, seul le lien est modifié, mais maintenant, en parcourant la liste, on accède aux noeuds dans un ordre aléatoire. J'ai ensuite rempli ces nœuds dans un ordre aléatoire avec un autre ensemble de nombres aléatoires et je les ai triés à nouveau. J'ai comparé l'approche descendante de 2015 avec l'approche ascendante antérieure, modifiée pour correspondre aux autres changements apportés en 2015 (sort() appelle désormais sort() avec une fonction de comparaison de prédicats, au lieu d'avoir deux fonctions distinctes). Voici les résultats. mise à jour - J'ai ajouté une version basée sur les pointeurs de nœuds et j'ai également noté le temps nécessaire pour simplement créer un vecteur à partir de la liste, trier le vecteur, le recopier.

sequential nodes: 2015 version 1.6 seconds, prior version 1.5  seconds
random nodes:     2015 version 4.0 seconds, prior version 2.8  seconds
random nodes:                  node pointer based version 2.6  seconds
random nodes:    create vector from list, sort, copy back 1.25 seconds

Pour les nœuds séquentiels, la version antérieure est à peine plus rapide, mais pour les nœuds aléatoires, la version antérieure est 30 % plus rapide, et la version avec pointeur de nœud 35 % plus rapide, et la création d'un vecteur à partir de la liste, le tri du vecteur, puis la recopie est 69 % plus rapide.

Ci-dessous le premier code de remplacement pour std::list::sort() que j'ai utilisé pour comparer la méthode antérieure bottom up avec petit tableau (_BinList[]) par rapport à l'approche top down de VS2015 Je voulais que la comparaison soit équitable, j'ai donc modifié une copie de < list >.

    void sort()
        {   // order sequence, using operator<
        sort(less<>());
        }

    template<class _Pr2>
        void sort(_Pr2 _Pred)
        {   // order sequence, using _Pred
        if (2 > this->_Mysize())
            return;
        const size_t _MAXBINS = 25;
        _Myt _Templist, _Binlist[_MAXBINS];
        while (!empty())
            {
            // _Templist = next element
            _Templist._Splice_same(_Templist.begin(), *this, begin(),
                ++begin(), 1);
            // merge with array of ever larger bins
            size_t _Bin;
            for (_Bin = 0; _Bin < _MAXBINS && !_Binlist[_Bin].empty();
                ++_Bin)
                _Templist.merge(_Binlist[_Bin], _Pred);
            // don't go past end of array
            if (_Bin == _MAXBINS)
                _Bin--;
            // update bin with merged list, empty _Templist
            _Binlist[_Bin].swap(_Templist);
            }
            // merge bins back into caller's list
            for (size_t _Bin = 0; _Bin < _MAXBINS; _Bin++)
                if(!_Binlist[_Bin].empty())
                    this->merge(_Binlist[_Bin], _Pred);
        }

J'ai fait quelques changements mineurs. Le code original gardait la trace du bac maximum réel dans une variable nommée _Maxbin, mais l'overhead dans la fusion finale est suffisamment faible pour que je supprime le code associé à _Maxbin. Pendant la construction du tableau, la boucle interne du code original fusionnait dans un élément _Binlist[], suivi d'un swap dans _Templist, ce qui semblait inutile. J'ai modifié la boucle interne pour qu'elle se contente de fusionner dans _Templist, et qu'elle ne permute que lorsqu'un élément _Binlist[] vide est trouvé.

Vous trouverez ci-dessous un remplacement de std::list::sort() basé sur les pointeurs de nœuds que j'ai utilisé pour une autre comparaison. Cela élimine les problèmes liés à l'allocation. Si une exception de comparaison est possible et se produit, tous les noeuds du tableau et de la liste temporaire (pNode) devraient être ajoutés à la liste originale, ou éventuellement une exception de comparaison pourrait être traitée comme une comparaison inférieure à la comparaison.

    void sort()
        {   // order sequence, using operator<
        sort(less<>());
        }

    template<class _Pr2>
        void sort(_Pr2 _Pred)
        {   // order sequence, using _Pred
        const size_t _NUMBINS = 25;
        _Nodeptr aList[_NUMBINS];           // array of lists
        _Nodeptr pNode;
        _Nodeptr pNext;
        _Nodeptr pPrev;
        if (this->size() < 2)               // return if nothing to do
            return;
        this->_Myhead()->_Prev->_Next = 0;  // set last node ->_Next = 0
        pNode = this->_Myhead()->_Next;     // set ptr to start of list
        size_t i;
        for (i = 0; i < _NUMBINS; i++)      // zero array
            aList[i] = 0;
        while (pNode != 0)                  // merge nodes into array
            {
            pNext = pNode->_Next;
            pNode->_Next = 0;
            for (i = 0; (i < _NUMBINS) && (aList[i] != 0); i++)
                {
                pNode = _MergeN(_Pred, aList[i], pNode);
                aList[i] = 0;
                }
            if (i == _NUMBINS)
                i--;
            aList[i] = pNode;
            pNode = pNext;
            }
        pNode = 0;                          // merge array into one list
        for (i = 0; i < _NUMBINS; i++)
            pNode = _MergeN(_Pred, aList[i], pNode);
        this->_Myhead()->_Next = pNode;     // update sentinel node links
        pPrev = this->_Myhead();            //  and _Prev pointers
        while (pNode)
            {
            pNode->_Prev = pPrev;
            pPrev = pNode;
            pNode = pNode->_Next;
            }
        pPrev->_Next = this->_Myhead();
        this->_Myhead()->_Prev = pPrev;
        }

    template<class _Pr2>
        _Nodeptr _MergeN(_Pr2 &_Pred, _Nodeptr pSrc1, _Nodeptr pSrc2)
        {
        _Nodeptr pDst = 0;          // destination head ptr
        _Nodeptr *ppDst = &pDst;    // ptr to head or prev->_Next
        if (pSrc1 == 0)
            return pSrc2;
        if (pSrc2 == 0)
            return pSrc1;
        while (1)
            {
            if (_DEBUG_LT_PRED(_Pred, pSrc2->_Myval, pSrc1->_Myval))
                {
                *ppDst = pSrc2;
                pSrc2 = *(ppDst = &pSrc2->_Next);
                if (pSrc2 == 0)
                    {
                    *ppDst = pSrc1;
                    break;
                    }
                }
            else
                {
                *ppDst = pSrc1;
                pSrc1 = *(ppDst = &pSrc1->_Next);
                if (pSrc1 == 0)
                    {
                    *ppDst = pSrc2;
                    break;
                    }
                }
            }
        return pDst;
        }

Answer 2

@sbi asked Stephan T. Lavavej, responsable de la bibliothèque standard de MSVC, qui a répondu:

J'ai fait ça pour éviter l'allocation de mémoire et la construction par défaut des allocateurs.

A cela, j'ajouterai "une sécurité de base contre les exceptions gratuites".

Pour préciser: l'implémentation antérieure à VS2015 souffre de plusieurs défauts:

• _Myt _Templist, _Binlist[_MAXBINS]; crée une série de lists intermédiaires (_Myt est simplement un typedef pour l'instance actuelle de list; une orthographe moins confuse pour cela est, eh bien, list) pour contenir les nœuds pendant le tri, mais ces lists sont construits par défaut, ce qui entraîne une multitude de problèmes:
  1. Si l'allocation utilisée n'est pas constructible par défaut (et il n'est pas obligatoire que les allocateurs soient constructibles par défaut), cela ne compilera tout simplement pas, car le constructeur par défaut de list tentera de construire par défaut son allocateur.
  2. Si l'allocation utilisée est étatique, alors un allocateur construit par défaut peut ne pas être égal à this->get_allocator(), ce qui signifie que les splices et merges ultérieurs sont techniquement un comportement indéfini et peuvent bien se casser dans les versions de débogage. ("Techniquement", car les nœuds sont tous fusionnés à la fin, donc vous ne désallouez pas en réalité avec le mauvais allocateur si la fonction se termine avec succès.)
  3. La list de Dinkumware utilise un nœud sentinelle alloué dynamiquement, ce qui signifie que ce qui précède effectuera _MAXBINS + 1 allocations dynamiques. Je doute que beaucoup de gens s'attendent à ce que sort puisse potentiellement lancer une bad_alloc. Si l'allocation est étatique, alors ces nœuds sentinelles peuvent ne pas être même alloués à partir du bon endroit (voir #2).
• Le code n'est pas sécurisé contre les exceptions. En particulier, la comparaison est autorisée à lancer une exception, et si elle lance une exception alors qu'il y a des éléments dans les lists intermédiaires, ces éléments sont simplement détruits avec les lists lors du déroulement de la pile. Les utilisateurs de sort ne s'attendent pas à ce que la liste soit triée si sort lance une exception, bien sûr, mais ils ne s'attendent probablement pas non plus à ce que les éléments disparaissent.
  • Ceci interagit très mal avec #2 ci-dessus, car maintenant ce n'est pas seulement un comportement indéfini technique : le destructeur de ces lists intermédiaires va désallouer et détruire les nœuds fusionnés en eux avec le mauvais allocateu.

Ces défauts sont-ils corrigeables? Probablement. #1 et #2 peuvent être corrigés en passant get_allocator() au constructeur des lists:

 _Myt _Templist(get_allocator());
 _Myt _Binlist[_MAXBINS] = { _Myt(get_allocator()), _Myt(get_allocator()), 
                             _Myt(get_allocator()),  /* ... répéter _MAXBINS fois */ };

Le problème de la sécurité des exceptions peut être corrigé en entourant la boucle d'un try-catch qui fusionne tous les nœuds dans les lists intermédiaires dans *this sans se soucier de l'ordre si une exception est levée.

Résoudre #3 est plus difficile, car cela signifie ne pas utiliser du tout list comme conteneur de nœuds, ce qui nécessite probablement une refonte importante, mais c'est faisable.

La question est la suivante: vaut-il la peine de sauter à travers tous ces cerceaux pour améliorer les performances d'un conteneur qui a réduit les performances par conception? Après tout, quelqu'un qui se soucie vraiment des performances ne devrait probablement pas utiliser list en premier lieu.