Parallélisation de QuickSort

J’ai récemment lu un article très intéressant sur les performances du tri QuickSort implémenté dans .NET, que vous pouvez retrouver ici.

Je pense que le tri est un bon moyen de faire comprendre à un non-développeur la réalité de notre métier, et pourquoi des applications sans bogues ne sont qu’un doux rêve de politicien (dont on n’entend heureusement plus parler) : sachant qu’il a fallu une dizaine d’années aux chercheurs en informatique pour optimiser le tri dans la plupart des conditions et que l’algorithme final ne prend que quelques dizaines de lignes, comment peut-on s’attendre à la perfection lorsqu’un progiciel en contient 100 000 ?

L’article cité ci-dessus montre d’ailleurs que nous ne sommes pas au bout de la quête. Je me permettrais de rajouter mon grain de sel, d’ailleurs, sur la parallélisation des algorithmes. Je me demandai si l’implémentation de Sort dans .NET parallélisait proprement. Un petit bout de code comme ceci va nous permettre de voir ce qu’il se passe :

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace ConsoleApplication4
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = 40 * 1000 * 1000;

            List<double> nombres = new List<double>();
            Random r = new Random();
            for (inti = 0; i < n; i++)
                nombres.Add(r.NextDouble());

            Stopwatch chrono = Stopwatch.StartNew();
            nombres.Sort();
            chrono.Stop();
            Console.WriteLine(chrono.Elapsed);
        }
    }
}

Visiblement, il n’y a pas de parallélisme :

Devoirs du week-end : imaginer un algorithme de tri fortement parallélisable, tout en restant performant sur un seul thread.

Et juste pour montrer qu’un Xeon, ça pousse :

Pour 40 millions d’entrées, ce n’est pas mal !