Warum der plötzliche Wechsel zur Top-Down-Strategie in std::list::sort()?

In Visual Studio 2015 (VS2015) hat Microsoft die Sortierstrategie von std::list::sort() von der traditionellen Bottom-Up-Merge-Sortierung auf eine umgestellt Top-Down-Ansatz. Durch diese Änderung entfiel die Verwendung eines internen Listenarrays und es wurden Iteratoren übernommen, um sortierte Laufgrenzen innerhalb der ursprünglichen Liste zu verfolgen.

Gründe für die Änderung

Stephan T. Lavavej , der Entwickler des Top-Down-Ansatzes, verwies auf die Notwendigkeit, die Speicherzuweisung und den Aufbau nicht standardmäßiger Allokatoren zu vermeiden. VS2015 führte Allokatoren ein, die nicht mehr standardmäßig konstruierbar und zustandsbehaftet waren, was bei Verwendung des vorherigen Bottom-Up-Ansatzes zu Problemen führte.

Implementierung des Top-Down-Ansatzes

Die Oberseite Der -down-Ansatz verwendet einen rekursiven Algorithmus, der die Liste rekursiv in Hälften teilt, bis Basisfälle erreicht werden, in denen die Listen leer sind oder ein einzelnes Element enthalten. Die Funktion _Sort unterteilt die Liste in drei Segmente: Linkslauf, Rechtslauf und den Enditerator. Die Zusammenführungslogik wird mithilfe von std::list::splice ausgeführt, um Knoten innerhalb der ursprünglichen Liste zu verschieben und dabei die Ausnahmesicherheit aufrechtzuerhalten.

Überlegungen zur Leistung

Während der Top-Down-Methode Der Ansatz behebt die Bedenken hinsichtlich der Speicherzuordnung, bringt jedoch im Vergleich zur ursprünglichen Bottom-up-Merge-Sortierung einen Leistungsverlust mit sich. Bei großen Listen mit verstreuten Knoten leidet der Top-Down-Ansatz unter einer erhöhten Anzahl von Cache-Fehlern, was zu langsameren Ausführungszeiten führt. In solchen Fällen kann es schneller sein, die Liste in ein Array oder einen Vektor zu verschieben, sie zu sortieren und aus dem sortierten Array oder Vektor eine neue Liste zu erstellen.