`std :: list :: sort ()` – pourquoi le changement soudain vers une stratégie descendante?

Je me souviens que depuis le début des temps, l’approche la plus populaire pour implémenter std::list::sort() était l’algorithme classique de Merge Sort implémenté de manière ascendante (voir également si vite? ).

Je me souviens avoir vu quelqu’un qualifier cette stratégie de «chaînage d’oignons».

C’est du moins la façon dont GCC implémente la bibliothèque standard C ++ (voir, par exemple, ici ). Et c’est ainsi que se trouvait la vieille STL de Dimkumware dans la version MSVC de la bibliothèque standard, ainsi que dans toutes les versions de MSVC jusqu’à VS2013.

Cependant, la bibliothèque standard fournie avec VS2015 ne suit plus soudainement cette stratégie de sorting. La bibliothèque fournie avec VS2015 utilise une implémentation récursive assez simple du sorting de fusion de haut en bas . Cela me semble étrange, car l’approche descendante nécessite d’accéder au point médian de la liste pour la diviser par deux. Comme std::list ne supporte pas l’access aléatoire, la seule façon de trouver ce point intermédiaire est de parcourir littéralement 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 (qui n’était pas nécessairement une opération 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 voir, ils utilisent simplement nonchalamment std::next pour parcourir la première moitié de la liste et arriver à l’iterator _Mid .

Quelle pourrait être la raison de ce changement, je me le demande? Tout ce que je vois est une inefficacité apparemment évidente des appels répétitifs à std::next à chaque niveau de récursivité. 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’est-ce qu’ils obtiennent alors? Je ne vois pas immédiatement cet algorithme comme ayant un meilleur comportement de cache (par rapport à l’approche ascendante d’origine). Je ne le vois pas immédiatement comme se comportant mieux sur des séquences pré-sortingées.

Certes, c ++ 11 std::list est fondamentalement nécessaire pour stocker son nombre d’éléments, ce qui rend ce qui précède légèrement plus efficace, puisque nous soaps toujours que le nombre d’éléments est anticipé. Mais cela ne semble toujours pas suffisant pour justifier le balayage séquentiel à chaque niveau de récursivité.

(Certes, je n’ai pas essayé de faire des mises en scène les unes contre les autres. Peut-être y a-t-il des sursockets ici.)

update – VS2015 a introduit des allocateurs avec ou sans état, ce qui pose un problème lors de l’utilisation de listes locales, comme cela a été fait avec l’approche ascendante antérieure. J’ai pu résoudre ce problème en utilisant des pointeurs de nœuds au lieu de listes (voir ci-dessous) pour une approche ascendante.

Dans le commentaire de @sbi, il a demandé à l’auteur du top down aprobach, Stephan T. Lavavej, pourquoi ce changement avait été apporté. La réponse de Stephan était “pour éviter l’allocation de mémoire et la construction des allocateurs par défaut”. La nouvelle approche descendante est plus lente que l’ancienne approche ascendante, mais elle n’utilise que des iterators (stockés de manière récursive sur la stack), n’utilise aucune liste locale et évite les problèmes liés aux allocateurs avec ou sans état. @ La réponse de TC va dans ce sens.

En ce qui concerne les performances, s’il y a suffisamment de mémoire, il serait généralement plus rapide de déplacer la liste vers un tableau ou un vecteur, de sortinger, puis de déplacer le tableau ou le vecteur sortingé vers la liste.

Je suis capable de reproduire le problème (l’ancien sorting ne parvient pas à comstackr, un nouveau fonctionne) basé sur une démo de @IgorTandetnik:

 #include  #include  #include  template  class MyAlloc : public std::allocator { public: MyAlloc(T) {} // suppress default constructor template  MyAlloc(const MyAlloc& other) : std::allocator(other) {} template< class U > struct rebind { typedef MyAlloc other; }; }; int main() { std::list> l(MyAlloc(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 à PJ Plauger au sujet de cette modification le 1er août 2016. Un extrait de sa réponse:

Fait intéressant, notre journal des modifications ne reflète pas ce changement. Cela signifie probablement que cela a été “suggéré” par un de nos plus gros clients et obtenu par moi lors de la révision du code. Tout ce que je sais maintenant, c’est que le changement est intervenu vers l’automne 2015. Lorsque j’ai examiné le code, la première chose qui m’a frappé, c’est la ligne:

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

ce qui, bien sûr, peut prendre beaucoup de temps pour une grande liste.

Le code a l’air un peu plus élégant que ce que j’ai écrit au début de 1995 (!), Mais sa complexité est sans doute pire. Cette version a été modélisée d’après l’approche de Stepanov, Lee et Musser dans le STL d’origine. Il est rare qu’ils se trompent dans leur choix d’algorithmes.

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

Je ne sais pas si le retour au code d’origine de PJ Plauger concernait le nouveau problème d’allocation, ou si et 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 constitué d’un entier non signé de 64 bits, en supposant que je finirais avec une liste de nœuds presque séquentiellement serait dynamicment alloué), les remplir avec des nombres aléatoires, puis sortingés. Les nœuds ne bougent pas, seule la liaison est modifiée, mais maintenant, la traversée de la liste accède aux nœuds dans un ordre aléatoire. J’ai ensuite rempli ces noeuds classés au hasard avec un autre ensemble de nombres aléatoires et les ai sortingés à nouveau. J’ai comparé l’approche descendante de 2015 avec l’approche ascendante antérieure modifiée pour correspondre aux autres modifications apscopes pour 2015 (sort () appelle maintenant sort () avec une fonction de comparaison des prédicats, plutôt que d’avoir deux fonctions distinctes). Ce sont les résultats. update – J’ai ajouté une version basée sur un pointeur de nœud et noté également le temps nécessaire pour créer simplement un vecteur à partir d’une liste, d’un vecteur de sorting et d’une copie.

 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 un peu plus rapide, mais pour les nœuds aléatoires, la version précédente est 30% plus rapide et la version du pointeur de nœud 35% plus rapide, et la création d’un vecteur à partir de la liste est 69% plus rapide.

Voici le premier code de remplacement pour std :: list :: sort () J’avais l’habitude de comparer la méthode ascendante précédente avec la méthode de tableau petit (_BinList []) par rapport à l’approche descendante de VS2015. copie de .

  void sort() { // order sequence, using operator< sort(less<>()); } template 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 d’origine conservait la trace du nombre maximal de fichiers dans une variable nommée _Maxbin, mais la surcharge dans la fusion finale est suffisamment faible pour que je supprime le code associé à _Maxbin. Au cours de la construction du tableau, la boucle interne du code d’origine a été fusionnée en un élément _Binlist [], suivi d’un échange dans _Templist, ce qui semblait inutile. J’ai changé la boucle interne pour fusionner dans _Templist, en échangeant une fois qu’un élément _Binlist [] vide est trouvé.

Vous trouverez ci-dessous un remplacement basé sur un pointeur de noeud pour std :: list :: sort () 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 nœuds du tableau et de la liste temporaire (pNode) devront être ajoutés à la liste d’origine, ou une exception de comparaison pourrait être traitée comme une comparaison inférieure.

  void sort() { // order sequence, using operator< sort(less<>()); } template 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 _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; } 

Au lieu du nouveau std :: list :: sort () de VS2015, vous pouvez utiliser cette version autonome.

 template  void listsort(std::list  &dll) { const size_t NUMLISTS = 32; std::list  al[NUMLISTS]; // array of lists std::list  tl; // temp list while (!dll.empty()){ // t1 = next element from dll tl.splice(tl.begin(), dll, dll.begin(), std::next(dll.begin())); // merge element into array size_t i; for (i = 0; i < NUMLISTS && !al[i].empty(); i++){ tl.merge(al[i], std::less()); } if(i == NUMLISTS) // don't go past end of array i -= 1; al[i].swap(tl); // update array list, empty tl } // merge array back into original list for(size_t i = 0; i < NUMLISTS; i++) dll.merge(al[i], std::less()); } 

ou utilisez l’algorithme gcc similaire.

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

Je l’ai fait pour éviter l’allocation de mémoire et la construction des allocateurs par défaut.

J’appendai à cela “la sécurité d’exception de base gratuite”.

Pour élaborer: l’implémentation pré-VS2015 souffre de plusieurs défauts:

  • _Myt _Templist, _Binlist[_MAXBINS]; crée un groupe de list intermédiaires s ( _Myt est simplement un typedef pour l’instanciation actuelle de la list ; une orthographe moins confuse pour ce qui est, bien, list ) pour contenir les noeuds pendant le sorting, mais ces list sont construites par défaut. une multitude de problèmes:
    1. Si l’allocateur utilisé n’est pas par défaut constructible (et qu’il n’est pas nécessaire que les allocateurs soient constructibles par défaut), cela ne comstackra pas, car le constructeur par défaut de list tentera de construire son allocateur par défaut.
    2. Si l’allocateur utilisé est stateful, alors un allocateur construit par défaut peut ne pas être égal à this->get_allocator() , ce qui signifie que les splice et merge ultérieures ont un comportement techniquement indéfini et peuvent se décomposer. (“Techniquement”, car les nœuds sont tous fusionnés à la fin, de sorte que vous ne libérez pas réellement le mauvais allocateur si la fonction se termine avec succès.)
    3. La list de Dinkumware utilise un nœud sentinelle alloué dynamicment, ce qui signifie que ce qui précède effectuera des allocations dynamics _MAXBINS + 1 . Je doute que beaucoup de gens s’attendent à ce que le sort jette potentiellement bad_alloc . Si l’allocateur est à l’état, ces nœuds sentinelles ne peuvent même pas être alloués au bon endroit (voir n ° 2).
  • Le code n’est pas sûr d’exception. En particulier, la comparaison est autorisée à lancer, et si elle lève des éléments dans la list intermédiaire s, ces éléments sont simplement détruits avec la list s lors du déroulement de la stack. Les utilisateurs de sort ne s’attendent pas à ce que la liste soit sortingée si le sort renvoie une exception, bien sûr, mais ils ne s’attendent probablement pas à ce que les éléments disparaissent.
    • Ceci interagit très mal avec # 2 ci-dessus, parce que maintenant ce n’est pas seulement un comportement non défini technique: le destructeur de ces list intermédiaires va désallouer et détruire les noeuds épissés avec le mauvais allocateur.

Ces défauts sont-ils réparables? Probablement. # 1 et # 2 peuvent être corrigés en transmettant get_allocator() au constructeur de la list s:

  _Myt _Templist(get_allocator()); _Myt _Binlist[_MAXBINS] = { _Myt(get_allocator()), _Myt(get_allocator()), _Myt(get_allocator()), /* ... repeat _MAXBINS times */ }; 

Le problème de sécurité des exceptions peut être résolu en entourant la boucle avec un try-catch qui divise tous les nœuds de la list intermédiaire en *this sans tenir compte de l’ordre si une exception est levée.

La correction n ° 3 est plus difficile, car cela signifie ne pas utiliser de list du tout en tant que détenteur de nœuds, ce qui nécessite probablement une certaine quantité de refactoring, mais c’est faisable.

La question qui se pose est la suivante: est-ce que cela vaut la peine de parcourir tous ces obstacles pour améliorer les performances d’un conteneur dont les performances ont été réduites? Après tout, quelqu’un qui se soucie vraiment de la performance n’utilisera probablement pas la list en premier lieu.