Parallel.For et Parallel.ForEach en 5 min

Parallel.For() et Parallel.ForEach() permettent de paralléliser l’exécution d’une boucle. La syntaxe de ces instructions est très proche de celles des boucles for et foreach, toutefois leur utilisation est loin d’être anodine. Il faut observer certaines précautions et avoir toujours en tête que l’exécution du corps des boucles se fait en parallèle et non séquentiellement.

Parallélisation de boucles

Dans un contexte de processeurs multi-coeur, la parallélisation permet de tirer plus avantageusement les capacités du processeur. Une exécution séquentielle d’une boucle s’effectue sur un seul thread à la fois (par forcément le même). Avec un processeur multi-cœur, le thread s’exécutera sur un seul cœur et les autres cœurs resteront inactifs.

Comparaison des performances entre une exécution séquentielle et en parallèle

L’exécution en parallèle d’une boucle n’est pas forcément plus performant qu’une exécution séquentielle principalement pour plusieurs raisons:

Le changement de contexte entre threads

Même avec des architectures multi-cœur, tous les threads ne sont pas exécutés au même moment par le processeur. Pour des threads ayant la même priorité et pour que les threads avancent de la même façon, le processeur alloue un certain temps-processeur à chaque thread. Pendant ce laps de temps, le thread est exécuté, en dehors de ce laps le thread ne s’exécute pas et c’est un autre thread qui sera exécuté.

Pour passer d’un thread à l’autre, le processeur doit stocker les ressources liées au thread à désactiver et charger les ressources liées au thread à activer. Cette étape permet de charger tout le contexte lié à l’exécution du thread. Ce changement de contexte est assez couteux en temps par rapport à l’exécution d’instructions par le processeur car il nécessite d’effectuer des lectures et écritures en mémoire.

L’exécution séquentielle des boucles limite le nombre de changement de contexte par rapport à une exécution en parallèle. Si les changements de contexte sont trop nombreux par rapport à une exécution séquentielle, une exécution en parallèle peut s’avérer moins performante.

Création de threads

Pour exécuter des instructions en parallèle, une solution consiste à créer plusieurs threads, de les exécuter en parallèle puis de les détruire. La création de threads prends du temps et peut rendre l’exécution peu performante si beaucoup de threads sont créés et qu’ils exécutent peu d’instructions.

Pour palier à ce problème et permettre une exécution en parallèle d’instructions, une possibilité est d’utiliser un “pool de threads”. Ce “pool” permet de créer un certain nombre de threads et d’exécuter les instructions sur ces threads sans les détruire.

En .Net, le “pool” de threads est disponible avec la classe statique System.Threading.ThreadPool. Plus de détails à propos de cette classe sur MSDN.

Synchronisation des objets partagés par plusieurs threads

Lorsque des threads partagent des objets communs, et pour éviter les accès concurrents à ces objets, il faut synchroniser les threads pour qu’ils n’effectuent pas de lectures et des écritures en même temps dans ces objets.

Beaucoup de mécanismes existent pour synchroniser l’exécution des threads. On peut trouver une liste exhaustive de ces mécanismes dans Threading en C# de Joe Albahari.

D’une façon générale, les mécanismes de synchronisation ralentissent l’exécution puisque des threads doivent attendre que d’autres threads terminent leur exécution. Une bonne implémentation des mécanismes de synchronisation minimise le temps d’attente des threads de façon à ce qu’ils exécutent le plus d’instructions possibles dans un laps de temps.

Une exécution séquentielle ne nécessite pas de mécanisme de synchronisation par rapport à une exécution en parallèle.

Préparer l’implémentation pour utiliser Parallel.For() ou Parallel.ForEach()

Partitionnement

Le partitionnement permet d’affecter une tâche à exécuter à un thread. Comme indiqué plus haut, dans le cas où on a plusieurs tâches à exécuter, une solution consiste à utiliser un “pool” de threads. Ce “pool” comprend un nombre limité de threads qui se partiront l’exécution de toutes les tâches.

Le partionnement va donc consister à répartir ces tâches sur chaque thread. Un partionnement efficace repartira équitablement les tâches pour que la charge processeur soit plus ou moins identique pour chaque thread. Dans les faits, la répartition n’est jamais équitable parce qu’il est difficile de prévoir la charge que va engendrer l’exécution d’une tâche.

A l’opposé, un mauvais partionnement peut mener à une charge processeur déséquilibrée qui peut entraîner une charge importante sur quelques threads et une charge faible sur les autres. Un déséquilibre fait baisser l’efficacité d’une exécution parallèle en particulier dans un contexte multi-cœur.

La synchronisation entre threads tend à faire baisser l’efficacité d’une exécution parallèle puisqu’elle augmente l’attente de threads par rapport à d’autres. Plus il y a de synchronisation entre thread et moins efficace sera le partionnement.

Dans le cas où les tâches à exécuter sont équivalentes, le partionnement le plus efficace consiste à affecter exactement le même nombre de tâches à chaque thread. Sans avoir systématiquement ce cas de figure, une bonne implémentation est un compromis entre le moins de synchronisation possible et un partionnement permettent une répartition dynamique pour favoriser la charge processeur équitable entre threads.

Eviter un grand nombre de changements de contexte

Dans le corps d’une boucle, l’appel à un délégué a un coût. Un grand nombre d’appels à un délégué à partir de threads différents peut mener à des changements de contexte fréquents entre threads. Le gain provenant de l’utilisation d’une boucle Parallel.For() ou Parallel.ForEach() peut être perdu dans le cas où ces changements de contexte dégraderaient trop les performances.

D’une façon générale, éviter d’avoir un corps de boucle trop petit permet de limiter des changements de contexte fréquents. Toutefois il faut tester différentes implémentations de façon à assurer que celle qui est choisie est la plus optimale.

Implémentations possibles de boucles parallèles avec Parallel

Contrairement aux apparences, les différentes implémentations de boucles avec Parallel ne sont pas équivalentes. Ainsi:

  • Parallel.For() n’utilise pas “lock”: les accès aux éléments de la liste se font avec un index, il n’y a donc pas besoin de “locks”. Le partionnement est de plus prévisible puisqu’on connait la taille de la liste. Cette implémentation est particulièrement efficace pour répartir la charge processeur équitablement.
  • Parallel.ForEach(): dans le cas où la structure parcourue satisfait IList<T> cette implémentation est aussi efficace que Parallel.For() et n’utilise pas de “lock”. En revanche si la structure satisfait seulement IEnumerable<T>, Parallel.ForEach() utilise des “locks” pour accéder aux éléments de la structure. De plus le partitionnement est moins efficace car le nombre d’éléments de la structure est inconnu.
  • Parallel.Invoke(): cette implémentation est la moins efficace car elle ne permet pas de prévoir un partitionnement optimal.

Parallel.For()

Par exemple:

ParallelLoopResult result = Parallel.For(0, 100, cpt =>  
{  
  // ...
});

Cette implémentation est la plus efficace, elle permet d’exploiter toutes les optimisations possibles:

  • Partionnement efficace: elle permet de partitionner efficacement la charge processeur.
  • Paramétrage dynamique du nombre de threads: elle permet de gérer dynamiquement le nombre de threads pendant l’exécution pour optimiser la répartition de la charge.
  • Gestion de long: une surcharge permet d’utiliser des objets de type long.
  • Boucles imbriquées: il est possible d’implémenter des boucles Parallel.For() dans une autre boucle Parallel.For() sans se préoccuper de nombre de threads utilisés. Une boucle Parallel.For() imbriqué prend en compte le nombre de threads déjà exécuté par une boucle de plus haut niveau.
  • Pas d’utilisation de “lock”: il n’est pas nécessaire d’utiliser un “lock” pour exécuter des itérations parallèlement.
  • Gestion des exceptions

Accès couteux à une liste indexée

Dans la plupart des cas, il faut privilégier cette implémentation. Toutefois elle peut ne pas convenir dans certaines conditions notamment si l’accès indexé à la structure de données parcourue est très couteux. Dans ce cas il vaut mieux parcourir la structure sous forme de IEnumerable<T> plutôt qu’en l’utilisant en structure indexée avec IList<T>.
On peut forcer à utiliser la structure en IEnumerable<T>.

Parallel.ForEach()

Par exemple:

List items = new List{ ... }; 
Parallel.ForEach(items, item =>  
{  
  // ...
});
Toutes les surcharges de Parallel.ForEach() ne sont pas équivalentes

L’exécution de cette boucle est différente suivant le type de l’objet énumérable passé en paramètre:

  • Si l’objet satisfait IList<T>: le fonctionnement est similaire à celui d’une boucle Parallel.For() et l’exécution parallèle des itérations se fait sans utiliser de “lock”. Cette surcharge bénéficie des mêmes optimisations que les boucles Parallel.For() concernant la répartition efficace de la charge.
  • Si l’objet satisfait IEnumerable<T>: l’exécution est moins efficace que le cas précédent puisque le nombre d’itérations n’est pas connu en avance. De plus un “lock” est utilisé pour éviter des appels concurrents aux fonctions de l’interface IEnumerable<T> en particulier si la structure n’est pas “thread-safe”.

Cette implémentation est la plus flexible puisque la plupart des structures de données satisfont IEnumerable<T>. Elle bénéficie de certaines fonctionnalités communes avec Parallel.For():

  • La gestion des exceptions,
  • Paramétrage dynamique du nombre de threads,
  • Partitionnement efficace: même s’il n’est pas aussi précis que pour Parallel.For().

Présence d’un “lock” pour accéder aux éléments de la structure IEnumerable<T>

L’inconvénient majeur de cette implémentation est la présence de “lock” pour accéder aux éléments de la structure IEnumerable<T> (si la structure satisfait IList<T>, Parallel.ForEach() n’utilise pas de “lock”).

Il faut avoir en tête que l’acquisition de “lock” se fait à chaque accès à un élément de la structure parcourue, ensuite un thread exécute une ou plusieurs itérations de la boucle donc plus il y a des accès au corps de la boucle Parallel.ForEach(), plus il y aura des changements de contexte entre threads. Un grand nombre de changements de contexte peut ralentir l’exécution de la boucle.

Dans le cas où on se rends compte du manque d’efficacité de la boucle Parallel.ForEach(), il faut augmenter la taille du code exécuté dans le corps de la boucle pour minimiser les changements de contexte.

Par exemple, si on doit traiter une structure IEnumerable<T> avec:
Action<T> treatment = item => { ... }.

Au lieu d’utiliser la boucle directement:

Parallel.ForEach(items, treatment);

On peut trouver un élément discriminant dans la structure IEnumerable<T> pour organiser les éléments, par exemple, dans une structure comme un Dictionary<TKey, IEnumerable<T>> (les accès en lecture seule d’un dictionnaire sont “thread-safe” s’il n’y a pas d’écritures).

On peut alors utiliser le dictionnaire:

Dictionary<Key, IEnumerable<T>> dictionary = new Dictionary<Key, IEnumerable<T>> { ... }; 
Parallel.ForEach(dictionary.Keys, key =>  
{ 
  foreach (var item in dictionary[key]) 
  { 
    treatment(item); 
  } 
});

Forcer l’utilisation de Parallel.ForEach() avec Partitioner

Dans certains cas, on peut se rendre compte que l’utilisation de Parallel.For() est moins performant que Parallel.ForEach(), on peut utiliser la classe System.Concurrent.Collections.Partitioner pour forcer l’utilisation de Parallel.ForEach() avec une structure satisfaisant IList<T>.

La fonction Partitioner.Create() permet d’obtenir un OrderablePartitioner<Tuple<Int32, Int32>> à partir d’un intervalle from...to.

Si on utilise Parallel.For() de cette façon:

Parallel.For(from, to, i =>  
{ 
  // ...  
});

On peut forcer l’utilisation de Parallel.ForEach() en écrivant:

Parallel.ForEach(Partitioner.Create(from, to), range =>  
{ 
  for (int i = range.Item1; i < range.Item2; i++)  
  { 
    // ...  
  }  
});

Forcer l’utilisation de Parallel.ForEach() avec LinQ

On peut aussi utiliser LinQ pour forcer la surcharge de Parallel.ForEach() avec pour argument une structure IEnumerable<T>:

IList<T> source = ...; 
Parallel.ForEach(source.Select(i => i), item =>  
{  
  // ...  
});

Paralle.Invoke()

Par exemple:

Parallel.Invoke( 
  () => action1(), 
  () => action2(), 
  () => action3() 
);

Cette surcharge est la moins performante des 3. Elle permet d’appeler directement plusieurs délégués. Contrairement aux autres surcharges, il n’y a pas forcément un parcourt d’une structure de données ni de boucles. Les délégués sont exécutés parallèlement suivant le degré de parallélisme possible sur la machine.

Cette implémentation est un équivalent à l’utilisation de Task avec un Task.WaitAll():

var t1 = Task.Factory.StartNew(() => action1()); 
var t2 = Task.Factory.StartNew(() => action2()); 
var t3 = Task.Factory.StartNew(() => action3()); 
Task.WaitAll(t1, t2, t3);

Parallel.Invoke() convient bien s’il n’y a pas beaucoup de délégués. Dans le cas contraire, il faut privilégier l’utilisation de Parallel.For() ou Parallel.ForEach().

Sortie d’une boucle

Sortie prévue en utilisant Stop() ou Break()

Il est possible d’arrêter une boucle Parallel.For() et Parallel.ForEach() en utilisant Stop() ou Break(). Toutefois l’utilisation de ces méthodes doit respecter certaines précautions.

Stop() et Break() peuvent s’utiliser de cette façon:

ParallelLoopResult loopResult = Parallel.For(0, N,  
(int i, ParallelLoopState loop) => 
{ 
  // ... 
  loop.Stop(); 
  // ... 
});

loop.Break() peut s’utiliser de la même façon.

Stop()

Lorsque Stop() est exécuté, la boucle Parallel.For() ou Parallel.ForEach() n’exécute plus de nouvelles itérations. Les itérations commencées sont terminées. La boucle se terminera normalement s’il n’y a pas d’exception.

Le résultat de la boucle ParallelLoopResult sera false.

loop.IsStopped() permet de savoir si loop.Stop() a été exécuté dans une des itérations. L’intérêt de cette méthode est de permettre de stopper une itération longue dans le cas où un arrêt est requis.

Stop() convient bien pour les structure non ordonnées puisque toute itération avant ou après l’itération où Stop() est exécuté, ne sera pas exécutée.

Break()

Lorsque Break() est exécuté, la boucle Parallel.For() ou Parallel.ForEach() tente d’arrêter les itérations après celle où Break() a été exécuté. Les itérations précédent l’itération où Break() est exécuté seront exécutées.

Toutefois il n’y a pas de garantie absolue que les itérations suivant l’itération où Break() a été exécuté, ne soient pas exécutées. Leur exécution sera juste évitée.

loop.LowestBreakIteration() retourne l’itération à partir de la laquelle on a exécuté Break().

Break() convient bien pour les structures ordonnées puisqu’il y a une notion d’itérations précédents et suivants l’itération où Break() a été exécuté.

L’exécution de Stop() et Break() dans la même boucle provoque une exception

Il faut prendre des précautions si on utilise Stop() et Break() dans le même corps d’une boucle Parallel.For() ou Parallel.ForEach(). En effet si on exécute Stop() puis Break(), une exception survient.

On peut résumer certaines propriétés lorsque Stop() et Break() sont utilisés de cette façon:

Instruction exécutée ParallelLoopResult
.IsCompleted
ParallelLoopResult
.LowestBreakIteration
.HasValue
ParallelLoopState
.IsStopped
Pas d’exécution de Stop() ou Break() true (si pas d’exception) false false
Stop() false true true
Break() false true false

Sortie par exception

L’utilisation d’un bloc try...catch dans une boucle Parallel.For() et Parallel.ForEach() peut s’utiliser de cette façon:

var exceptions = new ConcurrentQueue();  
Parallel.For(0, N, i => 
{ 
  try 
  { 
    // ... 
  } 
  catch (Exception e)  
  { 
    exceptions.Enqueue(e);  
  } 
}); 
if (!exceptions.IsEmpty) 
{ 
  throw new AggregateException(exceptions); 
}

Il faut avoir en tête qu’une exception qui survient à l’intérieur de la boucle dégrade les performances. Si une exception survient pour beaucoup d’itérations, l’exécution peut être considérablement ralentie.

CancellationToken

Les boucles Parallel.For() et Parallel.ForEach() supportent l’utilisation de CancellationToken. A chaque nouvelle itération, Parallel.For() et Parallel.ForEach() vérifient si CancellationToken.IsCanceled est vraie, si c’est le cas, une OperationCancelledException est lancée. Il faut donc protéger la boucle dans le cas où on utilise un CancellationToken:

CancellationTokenSource cancellationTokenSource = new CancellationTokenSource(); 
// ... 
var options = new ParallelOptions { CancellationToken = cancellationTokenSource.Token }; 
try 
{ 
  Parallel.For(0, N, options, i => 
  { 
    // ... 
  }); 
} 
catch(OperationCanceledException operationCanceledException) 
{ 
  // Traitement de l'exception 
}

IsExceptional

Dans le cas d’itérations longues, si une exception survient, la sortie de la boucle Parallel.For() ou Parallel.ForEach() peut prendre du temps. Pour éviter des comportements imprévus, on peut utiliser ParallelLoopState.IsExceptional pour vérifier si une exception est survenue dans une autre itération.

Pour résumer…

  • Pour utiliser des boucles Parallel.For() et Parallel.ForEach(), il faut implémenter le code des boucles pour que chaque itération soit indépendante.
  • Le corps des boucles ne doit pas être de trop petite taille pour éviter des changements de contexte trop nombreux lors de l’exécution des itérations. Il faut tester différentes implémentations pour comparer les performances.
  • Parallel.For() est généralement plus performant que Parallel.ForEach() car l’accès à une structure indexée permet de prévoir un partionnement plus optimal des threads lors de l’exécution.
  • Parallel.For() n’utilise pas de “locks” pour accéder aux différents éléments de la structure.
  • Parallel.ForEach() fonctionne comme Parallel.For() pour les structures satisfaisant IList<T>. En revanche, pour les structures satisfaisant seulement IEnumerable<T>, Parallel.ForEach() utilise des “locks” pour accéder aux différents éléments de la structure.
  • Parallel.Invoke() est moins performant que Parallel.For() et Parallel.ForEach(), toutefois la différence peut être minime suivant l’implémentation du corps des boucles. Il convient donc de tester pour comparer les performances.
  • Dans certains cas, on peut forcer l’utilisation d’une structure avec IEnumerable<T> plutôt que IList<T> pour Parallel.ForEach() en utilisant Partionner ou LinQ.
  • L’exécution successive de ParallelLoopState.Stop() et ParallelLoopState.Break() dans le même corps d’une boucle Parallel.For() et Parallel.ForEach() provoque une exception.
  • Lorsque ParallelLoopState.Stop() est exécuté, la boucle évitera d’exécuter toute nouvelle itération. ParallelLoopState.Stop() convient bien pour les structures non indexées.
  • Lorsque ParallelLoopState.Break() est exécuté, la boucle évitera d’exécuter toute nouvelle itération se trouvant après l’itération durant laquelle ParallelLoopState.Break() a été exécutée. ParallelLoopState.Break() convient bien pour les structures indexées.
Références

Leave a Reply