"5 cents" pour parler de Sorts

Dans la suite du sujet, je veux partager mon code, qui dépasse std::sort() des versions actuelles de la bibliothèque GNU C ++ et (environ, il n'y a pas de données exactes) répète le résultat de "Sort Alexandrescu" avec CppCon 2019 .

Conditions de tâche

Dans le code (pas C++ ), il a fallu un effort raisonnable pour obtenir le tri pas pire que std::sort() pour se débarrasser de la surcharge d'utilisation de la bibliothèque qsort() . Y compris, par conséquent, utiliser des macros au lieu de modèles.
À son tour, si vous triez les «souris» et non les «éléphants», les coûts de qsort() assez importants: arithmétique d'adresse supplémentaire et appel indirect à la fonction de comparateur.

Résultat

Selon les informations disponibles, cette combinaison d' algorithmes et de fonctionnalités d'implémentation est plus rapide que de nombreuses autres options dans un sens pratique:

• par le nombre de comparaisons et de mouvements (mesuré en substituant la classe C++ pour compter les comparaisons et les affectations).
• par le volume de code machine (prend peu de place dans le cache).
• par le volume du code source et sa transparence.
• sur de longues séquences aléatoires, le gain tend à 3-5%, selon SORT_THRESHOLD .
• jusqu'à 1,5-2-3 fois plus rapide avec des données ordonnées ou principalement ordonnées.
• une légère perte uniquement sur des séquences très courtes dans l'ordre inverse.

Il est très probable que cette option soit légèrement plus rapide et / ou légèrement plus lente que la grande majorité des sortes, mais le découvrir est littéralement un travail titanesque que je ne peux pas me permettre.

C'est intéressant si quelqu'un compare cette option avec les options actuelles de Tarantool, PostgreSQL, SQLite et MySQL. J'espère que kaamos ne pourra pas passer avec son SysBench .

Comment va Alexandrescu?

Dans le premier commentaire de RPG18, il y avait un lien vers une récente performance d'Andrei Alexandrescu "Speed ​​is Found In The Minds of People" , où il mène à une idée assez similaire, mais va à heap_sort plus près de la finale.

La performance m'a paru un peu prolongée (si l' olegbunin avait donné 90 minutes au moins une fois ...), mais les chiffres ne suffisent pas. En particulier, je veux voir le comportement de tri avec l'augmentation de N , car une augmentation du seuil d'achèvement de QuickSort conduit à une accélération à de grandes tailles et une décélération à de petites, etc.

Néanmoins, à en juger par les chiffres cités par Alexandrescu, l'option décrite donne soudain une accélération similaire. Cependant, jusqu'à ce que je trouve le code montré à Alexandrescu dans sa forme finale, à "prendre et comparer", et il n'y a pas de temps pour encoder par vidéo (écrivez si vous le trouvez ou le faites).

Côté idéologique

Le côté théorique et idéologique de "l'algorithme" est assez simple:

1. Pour les séquences non courtes, nous utilisons QuickSort avec toutes les optimisations acceptables:
   
   • Pas récursivement en utilisant la pile interne de positions sur les pointeurs.
   • Comme élément de support, nous utilisons la médiane du premier, du milieu et du dernier élément.
   • Nous ne trions pas les petites portions, nous le laissons à ShellSort.
   • Après le fractionnement, nous mettons toujours la plus grande partie de la pile; par conséquent, la pile ne peut pas être plus profonde que Log2(N) .
2. Ajouter des données de tri à l'aide de ShellSort:
   
   • nombre minimum de passes.
   • l'étape du premier passage est corrélée avec la taille maximale du segment non trié.
   • totalisez seulement deux passes avec les étapes 8 et (inévitablement) 1.
3. L'utilisation de ShellSort vous permet d'augmenter relativement en toute sécurité le seuil de sortie de QuckSort. En conséquence, nous avons une combinaison de l'une des meilleures options QuickSort avec des économies grâce à une version antérieure et un pré-tri légèrement plus rapide.

Il convient de noter qu'en fonction de l'architecture du processeur et des conditions d'application, vous pouvez augmenter le gain sur les séquences longues jusqu'à 10-15% en choisissant SORT_THRESHOLD entre SORT_THRESHOLD . Cependant, cela ralentit le traitement des séquences avec l'ordre inverse et proche de celui-ci.
Néanmoins, c'est un bon bonus si vous comprenez que l'ordre inverse est peu probable dans vos données, ou si vous pouvez détecter de tels cas à moindre coût et exécuter une branche avec un petit SORT_THRESHOLD .

PS
L'option de tri décrite a été "refaite" pour mon projet libmdbx (base de données clé-valeur intégrée rapide avec ACID), dans lequel l'autre jour le LISEZMOI et la description de l'API ont été mis à jour (en fait réécrits). Par conséquent, je serai reconnaissant à la fois pour la correction des fautes de frappe et pour les conseils et suggestions. Lui-même, en règle générale, n'est pas visible faute d'informations.