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 :

image

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 :

SNAGHTMLa03046

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

About JP Gouigoux

Jean-Philippe Gouigoux est Architecte Logiciel, MVP Connected Systems Developer. Il intervient régulièrement à l'Université de Bretagne Sud ainsi qu'à l'Agile Tour. Plus de détails sur la page "Curriculum Vitae" de ce blog.
This entry was posted in Parallélisation and tagged . Bookmark the permalink.

2 Responses to Parallélisation de QuickSort

  1. Fabske says:

    Il ne manque pas le lien vers l’article en question ?
    Merci

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Captcha Captcha Reload