Look Inside

Multithreading

Lors de mes errances sur le net, je suis tombé sur un article de Eric Grange concernant les performances de Delphi face à Javascript. Le constat est là, en utilisant le même code sous Delphi et Javascript, c'est Javascript le plus rapide !

Ouch ! ça fait mal !

Comment est-il possible qu'un script interprété soit plus rapide qu'un code compilé en natif ?!

Première chose, Javascript est bien un script, mais il n'est pas réellement interprété; il est lui-même compilé "Just In Time" (JIT) avant d'être exécuté. C'est particulièrement vrai dans la démo en question qui consiste en un calcul mathématique pour afficher un Ensemble de Mandelbrot.

img/mandelbrot1.jpg

L'expression mathématique "x = x0 * x0 - y0 * y0 + p" sera compilée en instructions Intel voisines, que ce soit avec Delphi ou le compilateur JIT de Javascript. Eric en propose une version SSE sensiblement plus performante, mais le résultat n'est pas à la hauteur pour autant.

Pourtant le problème est bien là, le coeur du programme se trouve dans la fonction ComputeMandel dont voici la version d'Eric (sans SSE):

procedure TForm20.ComputeMandelDelphi;
const
   kmax = 256;
var
   xstep, ystep : Double;
   x, y, r : Double;
   sx, sy, k : Integer;
   p, q, x0, y0 : Double;
begin
   xstep := (pmax - pmin) / FBitmap.Width;
   ystep := (qmax - qmin) / FBitmap.Height;

   for sx := 0 to FBitmap.Width-1 do begin
      for sy := 0 to FBitmap.Height-1 do begin

         p := pmin + xstep * sx;
         q := qmax - ystep * sy;
         k := 0;
         x0 := 0;
         y0 := 0;

         repeat
            x := x0 * x0 - y0 * y0 + p;
            y := 2 * x0 * y0 + q;
            x0 := x;
            y0 := y;
            r := x * x + y * y;
            Inc(k);
         until ((r > iterLimit) or (k >= kmax));

         if k >= kmax then
            k := 0;

         DrawPixel(sx, sy, k);
      end;
   end;
end;

Pour améliorer les choses j'ai bien tenté de Manipuler des pixels autrement, mais ça ne change pas grand chose, c'est bien le calcul lui-même qui prend du temps.

Optimisation du code

Quand on regarde de près le code, il comprend 3 boucles (sx, sy et un repeat), mais rien n'est superflu ! On ne peut sortir aucun calcul de la boucle, xstep et ystep sont bien calculés avant, il semble difficile d'optimiser quoi que ce soit.

J'en suis arrivé à la conclusion que s'il n'était pas possible de calculer mieux, il fallait calculer moins !

Oui d'accord, mais si l'image de base possède une symétrie verticale évidente, ce n'est q'un cas particulier, dans la plus part du temps on n'aura aucun moyen de s'affranchir du calcul de chaque pixel.

A propos de pixels, on constatera que le code peut facilement être écrit différemment :

var
   xstep, ystep : Double;

procedure ComputePixel(sx, sy: Integer);
const
   kmax = 256;
var
   x, y, r : Double;
   k : Integer;
   p, q, x0, y0 : Double;
begin
  p := pmin + xstep * sx;
  q := qmax - ystep * sy;
  k := 0;
  x0 := 0;
  y0 := 0;

  repeat
    x := x0 * x0 - y0 * y0 + p;
    y := 2 * x0 * y0 + q;
    x0 := x;
    y0 := y;
    r := x * x + y * y;
    Inc(k);
  until ((r > iterLimit) or (k >= kmax));

  if k >= kmax then
    k := 0;

  DrawPixel(sx, sy, k);
end;

procedure TForm20.ComputeMandelDelphi;
var
   sx, sy : Integer;
begin
   xstep := (pmax - pmin) / FBitmap.Width;
   ystep := (qmax - qmin) / FBitmap.Height;

   for sx := 0 to FBitmap.Width-1 do begin
      for sy := 0 to FBitmap.Height-1 do begin
         ComputePixel(sx, sy);

end;

C'est à dire que le calcul de chaque pixel est totalement indépendant du reste de l'image. Dès lors on va pouvoir paralléliser le code !

Le multithreading

Et oui, si nous devons bien calculer tous les pixels, on peut très bien répartir ce travail sur l'ensemble des coeurs de notre CPU.

Pour commencer, on va numéroter les pixels de 0..WIDTH * HEIGHT - 1 afin de ne conserver qu'une seule boucle

var
  ofs: Integer;
begin
  for ofs := 0 to (FBitmap.Width * FBitmap.Height) - 1 do
    ComputePixel(ofs mod FBitmap.Width, ofs div FBitmap.Width);
end;

On peut maintenant déclarer une simple variable globale offset qui sera partagée par les différents Thread afin de savoir quel pixel il faut calculer:

function MandelThread(id: Integer): Integer; stdcall;
var
  ofs: Integer;
begin
  ofs := InterlockedIncrement(offset);
  while ofs < IMAGE_SIZE * IMAGE_SIZE do
  begin
    ComputePixel(ofs mod IMAGE_SIZE, ofs div IMAGE_SIZE);
    ofs := InterlockedIncrement(offset);
  end;
  InterlockedDecrement(tasks);
end;

Cette fonction en stdcall peut être utilisée avec CreateThread de l'API Windows, elle correspond à la méthode Execute d'une classe TThread.

La fonction InterlockedIncrement permet d'incrémenter une variable sans conflit entre thread. Ainsi chaque thread pourra traiter, sans conflit, le "prochain" pixel. La variable tasks est utilisée quand à elle pour connaître le nombre de tâche en cours d'exécution.

La fonction Compute ci-dessous lance autant de thread additionnels qu'indiqué en paramètre, le thread principal se chargeant lui aussi de calculer quelques pixels : MandelThread(0).

procedure Compute(AdditionalThreadCount: Integer);
var
  i : Integer;
  id: Cardinal;
begin
  xstep := (pmax - pmin) / IMAGE_SIZE;
  ystep := (qmax - qmin) / IMAGE_SIZE;

  offset := -1; // will be 0 after the first InterlockedIncrement call
  tasks := AdditionalThreadCount;

  IsMultiThread := True; // required by RTL !
  for i := 1 to AdditionalThreadCount  do
    CreateThread(nil, 0, @MandelThread, Pointer(i), 0, id);

  MandelThread(0); // the main thread compute some pixels also

  while tasks > 0 do  // should no be too long, there's no more pixel to compute
    Sleep(0);
end;

Voilà, presque tout est en place, il reste à savoir combien de thread additionnels il faut utiliser. Avec l'application donnée en fin d'article, vous pouvez tester jusque 10 threads. Sans surprise, avec mon quadri-coeur, j'obtiens le meilleur résultat en choisissant 3 threads additionnels.

En zoomant sur une partie de l'image un peu plus complexe à calculer, voici les scores obtenus :

1 seul thread : 450ms
2 threads: 250 ms
3 threads: 190 ms
4 threads: 180 ms
5 threads: 190 ms

)

Afin de déterminer la répartition du calcul entre les thread, j'ai ajouté un tableau d'entiers counters qui est mis à jour par chaque thread.

voici le nombre de pixels traités par chaque thread (valeurs approximatives moyennes observées sur plusieurs calculs)

1 seul thread : 450ms, 230400 pixels
2 threads: 250 ms, 134583 et 95817 pixels
3 threads: 190 ms, 82620, 96141 et 51639 pixels
4 threads: 180 ms, 69010, 89545, 25007 et 46838 pixels
5 threads: 190 ms, 70262, 90352, 47631, 22155 et 0 pixels
10 threads: 180ms, 2868, 57084, 45675, 70010, 54763, 0, 0, 0, 0, 0 pixels

Quand on indique plus de thread que de coeurs, on se trouve avec des threads qui ne calculent aucun pixel !

Mais avec 4 threads sur un quadri-coeur, on obtient enfin de meilleurs performances que Javascript (185ms contre 227)!

img/mandelbrot3.jpg

Conclusion

Or donc, le compilateur JIT de Javascript est suffisamment intelligent pour détecter un cas de parallélisme (c'est en tout cas mon hypothèse). Il se charge automatiquement de répartir les itérations de la bouche sur plusieurs coeurs.

C'est magique ! pourquoi donc Delphi ne fait-il pas de même ? Je pense que la grosse différence entre Javascript et Delphi, c'est que le langage Javascript ne permet pas de gérer les threads; il appartient donc totalement au compilateur d'optimiser le code et - au besoin - d'en paralléliser l'exécution. De son côté Delphi permet - comme on vient de le voir - de gérer pleinement l'aspect multitâche de Windows. On ne peut donc laisser le compilateur jouer avec les threads alors que le code lui-même est susceptible de le faire. La seule alternative serait d'avoir un mot clé réservé indiquant au compilateur de paralléliser le code tout seul ... ou de créer une classe spécifique :

type
  TIterationEvent = procedure(Sender: TObject; Index: Integer) of object;

  TParallelizer = class
  private
    ...
  public
    constructor Create;
    procedure Iterate(Count: Integer);
    property OnIteration: TIterationEvent read FOnIteration write FOnIteration;
  end;

implementation
...
end.

Pour utiliser cette classe il suffit d'instancier un TParallelizer, de définir l'événement OnIteration et d'appeler Iterate()

procedure TMainForm.Button2Click(Sender: TObject);
var
  P: TParallelizer;
begin
  P := TParallelizer.Create;
  try
    P.OnIteration := NextPixel;
    P.Iterate(480 * 480);
  finally
    P.Free;
  end;
end;

procedure TMainForm.NextPixel(Sender: TObject; Index: Integer);
begin
  Mandelbrot.ComputePixel(Index mod 480, Index div 480);
end;

Et voilà comment on passe d'un code spécifique à un classe orientée objet réutilisable !

Code source

Téléchargez l'application compilée et le source complet, y compris le composant TParallelizer Mandelbrot.zip.

NB: si vous êtes fan des clicodrômes, ajoutez en début d'unité Parallelisation.pas le {$DEFINE CLICK_FAN} pour pouvoir l'installer comme un composant visuel.

mise à jour !

Suite à la publication de ce billet, j'ai contacté Eric (je trouve ça normal vu que je parle de sa page), et en fait il me dit que Javascript n'est pas multithreadé ... et à la vu de l'activité de ma CPU je pense qu'il a en effet raison...ceci dit la démo reste intéressante.
Et puisqu'on est dans le sujet des performances, je vous invite aussi à consulter les performances du nouveau compilateur JIT de DWScript.

Seconde mise à jour !

Une petite comparaison du même source compilé sous Delphi 6, Delphi XE2 en 32 et 64 Bits Mandelbrot-bin.zip

Delphi 6 32 bits, 1 thread 190ms
Delphi XE2 32 bits, 1 thread 190ms
Delphi XE2 64 bits, 1 thread 90ms !!!
Delphi XE2 64 bits, 4 thread 40ms !!!

Il y a donc une grosse amélioration du calcul flottant sur Delphi XE2 en mode 64bits !

Date de dernière modification : 01/06/2013