"5 Cent", um über Sorten zu sprechen

In Fortsetzung des Themas möchte ich meinen Code teilen, der std::sort() aus den aktuellen Versionen der GNU C ++ Library überholt und (ungefähr gibt es keine genauen Daten) das Ergebnis von "Sort Alexandrescu" mit CppCon 2019 wiederholt .

Aufgabenbedingungen

In Code (nicht in C++ ) war ein angemessener Aufwand erforderlich, um die Sortierung nicht schlechter als std::sort() zu machen, um den Aufwand für die Verwendung der Bibliothek qsort() . Verwenden Sie daher Makros anstelle von Vorlagen.
Wenn Sie wiederum die "Mäuse" und nicht die "Elefanten" sortieren, sind die Kosten für qsort() ziemlich hoch: zusätzliche Adressarithmetik und ein indirekter Aufruf der Komparatorfunktion.

Ergebnis

Nach den verfügbaren Informationen ist diese Kombination aus Algorithmen und Implementierungsfunktionen im praktischen Sinne schneller als viele andere Optionen:

• durch die Anzahl der Vergleiche und Verschiebungen (gemessen durch Ersetzen der C++ Klasse zum Zählen von Vergleichen und Zuweisungen).
• durch das Volumen des Maschinencodes (nimmt wenig Platz im Cache ein).
• durch das Volumen des Quellcodes und seine Transparenz.
• Bei langen Zufallssequenzen beträgt die Verstärkung je nach SORT_THRESHOLD 3-5%.
• Bis zu 1,5-2-3 mal schneller mit bestellten oder überwiegend geordneten Daten.
• ein leichter Verlust nur bei sehr kurzen Sequenzen in umgekehrter Reihenfolge.

Es ist sehr wahrscheinlich, dass diese Option etwas schneller und / oder etwas langsamer ist als die allermeisten Arten, aber herauszufinden, dass dies buchstäblich eine titanische Arbeit ist, die ich mir nicht leisten kann.

Es ist interessant, wenn jemand diese Option mit den aktuellen Optionen in Tarantool, PostgreSQL, SQLite und MySQL vergleicht. Ich hoffe, Kaamos wird mit seiner SysBench nicht vorbeikommen können .

Wie geht es Alexandrescu?

Im ersten Kommentar von RPG18 gab es einen Link zu einem kürzlich erschienenen Auftritt von Andrei Alexandrescu „Geschwindigkeit liegt in den Köpfen der Menschen“ , in dem er zu einer ziemlich ähnlichen Idee führt, aber näher an das Finale zu heap_sort geht.

Die Aufführung schien mir etwas länger zu dauern (wenn Olegbunin mindestens einmal 90 Minuten gegeben hätte ...), aber die Zahlen reichen nicht aus. Insbesondere möchte ich das Sortierverhalten mit zunehmendem N , da eine Erhöhung des QuickSort-Abschlussschwellenwerts bei großen Größen zu einer Beschleunigung und bei kleinen zu einer Verzögerung usw. führt.

Nach den von Alexandrescu angeführten Zahlen ergibt die beschriebene Option jedoch plötzlich eine ähnliche Beschleunigung. Bis ich jedoch den Code gefunden habe, der Alexandrescu in seiner fertigen Form gezeigt wurde, um "zu nehmen und zu vergleichen", und es keine Zeit gibt, per Video zu codieren (schreiben, wenn Sie ihn finden oder tun).

Ideologische Seite

Die theoretische und ideologische Seite des "Algorithmus" ist recht einfach:

1. Für nicht kurze Sequenzen verwenden wir QuickSort mit allen akzeptablen Optimierungen:
   
   • Nicht rekursiv unter Verwendung des internen Positionsstapels auf Zeigern.
   • Als unterstützendes Element verwenden wir den Median des ersten, mittleren und letzten Elements.
   • Wir sortieren keine kleinen Portionen, wir überlassen es ShellSort.
   • Nach dem Teilen legen wir immer den größten Teil auf den Stapel, daher kann der Stapel nicht tiefer als Log2(N) .
2. Daten mit ShellSort hinzufügen und sortieren:
   
   • Mindestanzahl von Durchgängen.
   • Der Schritt beim ersten Durchgang korreliert mit der maximalen Größe des unsortierten Segments.
   • Insgesamt nur zwei Durchgänge mit den Schritten 8 und (unweigerlich) 1.
3. Mit ShellSort können Sie den Exit-Schwellenwert für QuckSort relativ sicher erhöhen. Als Ergebnis haben wir eine Kombination aus einer der besten QuickSort-Optionen mit Einsparungen aufgrund eines früheren Exits und einer etwas schnelleren Vorsortierung.

Es ist zu beachten, dass Sie abhängig von der Prozessorarchitektur und den Anwendungsbedingungen die Verstärkung bei langen Sequenzen um bis zu 10-15% erhöhen können, indem Sie SORT_THRESHOLD innerhalb von SORT_THRESHOLD wählen. Dies verlangsamt jedoch die Verarbeitung von Sequenzen in umgekehrter Reihenfolge und in deren Nähe.
Dies ist jedoch ein guter Bonus, wenn Sie verstehen, dass die umgekehrte Reihenfolge in Ihren Daten unwahrscheinlich ist, oder wenn Sie solche Fälle kostengünstig erkennen und eine Verzweigung mit einem kleinen SORT_THRESHOLD ausführen SORT_THRESHOLD .

PS
Die beschriebene Sortieroption wurde für mein libmdbx- Projekt (schnell eingebettete Schlüsselwertdatenbank mit ACID) " überarbeitet ", in dem neulich die README- und API-Beschreibung aktualisiert (tatsächlich neu geschrieben) wurden. Daher bin ich sowohl für die Korrektur von Tippfehlern als auch für Ratschläge und Vorschläge dankbar. Selbst ist in der Regel kein sichtbarer Mangel an Informationen.