[C#] Parallel for dotNET 2.0

Cette section est destinée aux scripts partagés par la communauté. Chaque post est destiné à un script. Suivez bien les recommandations.
Avatar de l’utilisateur
artemisart
Messages : 1893
Inscription : 21 Juin 2011 19:51
Localisation : Centre
Contact :

[C#] Parallel for dotNET 2.0

Message par artemisart » 29 Mai 2013 17:48

Vous connaissez la classe Parallel ? Non ?
C'est une classe qui permet de paralléliser des boucles très simplement (for et foreach), et donc de booster assez efficacement certaines tâches. Petit hic... c'est minimum du dotNET 4 ! (Unity, c'est 2 max).
Cette classe est donc un portage assez "basique" en dotNET 2 (avec des perfs parfois supérieures à celles de la classe originale :P ), elle peut bien sûr être utilisée hors de Unity.

Attention : cette classe ne va pas faire des miracles et c'est pas un prétexte pour ne pas optimiser vos algos :twisted: (le mieux est je pense d'optimiser en premier, puis de multithreader si besoin).
Vous ne pouvez pas utiliser l'API d'Unity en dehors du main thread (à part quelques trucs du style Mathf et Vector).
Un minimum de connaissance est requis sur le multithreading (accès concurrent aux objets par exemple), sur les delegates (avec Action et Func), et c'est encore mieux si vous connaissez les lambdas.

- NOM DU SCRIPT : Parallel

- AUTEUR(S): artemisart + code basé sur http://coding-time.blogspot.fr/2008/03/ ... -in-c.html

- DESCRIPTION : .NET 4 Parallel like

- UTILISATION : 4 méthodes (en comptant les surcharges :mrgreen: )

public static void Parallel.Invoke (params Action[] actions)
-> permet d'appeler plusieurs méthodes qui seront dispatchées sur plusieurs threads

public static void Parallel.For (int fromInclusive, int toExclusive, Action<int> action, int chunkSize, int threadCount)
-> exécute une boucle for par "groupes" de [chunkSize] sur [threadCount] threads (commençant à l'index [fromInclusive] et terminant à [toExclusive].

public static void Parallel.For (int fromInclusive, int toExclusive, Action<int> action)
-> exécute une boucle for par "groupes" de 4 sur [Environment.ProcessorCount] threads.

public static void Parallel.ForAutoChunkSize (int fromInclusive, int toExclusive, Action<int> action)
-> exécute une boucle for en la divisant en [Environment.ProcessorCount] groupes (presque) égaux, chaque groupe étant exécuté sur un thread différent.



Je sais pas si c'est très clair :lol: , un exemple :
Nous avons le code suivant, non multithreadé :

Code : Tout sélectionner

for (int i = 0; i < "Hello World !\n".Length; i++)
	Console.Write ("Hello World !\n"[i]);
Le résultat est : "Hello World !" avec un retour à la ligne.

Maintenant, avec un Parallel.For :

Code : Tout sélectionner

Parallel.For (
	0,
	"Hello World !\n".Length,
	(i) => Console.Write ("Hello World !\n"[i])
);
// si vous aimez pas les lambdas :
Parallel.For (
	0,
	"Hello World !\n".Length,
	Write
);
// avec la fonction Write étant :
public static void Write (int index)
{
	Console.Write ("Hello World !\n"[index]);
}
Et le résultat... "Hellrld !o Wo" et oui ! l’exécution ne se fait pas dans l'ordre, car plusieurs threads écrivent en même temps dans la console. C'est le principe du multithreading, il ne faut cependant pas l'oublier.
Action<int> représente donc une méthode qui prend un int en paramètre (l'index, égale à "i" dans une boucle for classique) et ne retourne rien.
chunkSize est le nombre d'items qui seront exécutés en même temps (en gros, le tout est séparé en groupes de taille [chunkSize], et chaque thread exécute des groupes 1 à 1 tant qu'il en reste).
threadCount est le nombre de threads qui seront lancés (ça sert pas à grand chose de monter au dessus de Environment.ProcessorCount).


La méthode Invoke est très simple à utiliser, ex :

Code : Tout sélectionner

Parallel.Invoke (
	() => Console.Write ("Hello "),
	() => Console.Write ("World "),
	() => Console.Write ("!\n")
);
Résultat (variable) : "!\nHello World ".

Toutes ces méthodes sont bloquantes (comme la classe originale), cad qu'elles ne se termineront pas tant avant que tous les threads aient terminés (si vous voulez simplement lancer une méthode asynchrone, regardez du côté de la classe Thread, BeginInvoke, ou ThreadPool.QueueUserWorkItem).


- SCRIPT :

Code : Tout sélectionner

using System;
using System.Collections.Generic;
using System.Threading;

// code : see http://coding-time.blogspot.fr/2008/03/implement-your-own-parallelfor-in-c.html
public static class Parallel
{
	public static void ForAutoChunkSize (int fromInclusive, int toExclusive, Action<int> action)
	{
		For (
			fromInclusive,
			toExclusive,
			action,
			(toExclusive - fromInclusive) / Environment.ProcessorCount + 1,
			Environment.ProcessorCount
			);
	}

	public static void For (int fromInclusive, int toExclusive, Action<int> action)
	{
		For (fromInclusive, toExclusive, action, 4, Environment.ProcessorCount);
	}

	public static void For (int fromInclusive, int toExclusive, Action<int> action, int chunkSize, int threadCount)
	{
		if (chunkSize < 1)
			chunkSize = 1;
		if (threadCount < 1)
			threadCount = 1;

		int index = fromInclusive - chunkSize;
		var locker = new object ();

		Action process = () =>
		{
			int chunkStart;
			while (true)
			{
				chunkStart = 0;
				lock (locker)
					chunkStart = index += chunkSize;
				for (int i = chunkStart; i < chunkStart + chunkSize; i++)
				{
					if (i >= toExclusive)
						return;
					action (i);
				}
			}
		};

		IAsyncResult[] results = new IAsyncResult[threadCount];
		for (int i = 0; i < threadCount; ++i)
			results[i] = process.BeginInvoke (null, null);

		// wait all
		for (int i = 0; i < threadCount; ++i)
			process.EndInvoke (results[i]);
	}

	public static void Invoke (params Action[] actions)
	{
		IAsyncResult[] results = new IAsyncResult[actions.Length];

		for (int i = 0; i < actions.Length; i++)
			results[i] = actions[i].BeginInvoke (null, null);

		for (int i = 0; i < actions.Length; i++)
			actions[i].EndInvoke (results[i]);
	}
}

Avatar de l’utilisateur
Max
Newser
Newser
Messages : 7506
Inscription : 30 Juil 2011 13:57

Re: [C#] Parallel for dotNET 2.0

Message par Max » 29 Mai 2013 18:08

sympa et excellent ;)
Qu'est qui t'as fait partir la dessus ? le fun ou un besoin ?
Pas d'aide par MP, le forum est là pour ça.
En cas de doute sur les bonnes pratiques à adopter sur le forum, consulter la Charte et sa FAQ


Avatar de l’utilisateur
Max
Newser
Newser
Messages : 7506
Inscription : 30 Juil 2011 13:57

Re: [C#] Parallel for dotNET 2.0

Message par Max » 29 Mai 2013 18:12

artemisart a écrit :mais vous en saurez plus bientôt :mrgreen: .
ha ha suspense alors :D
Pas d'aide par MP, le forum est là pour ça.
En cas de doute sur les bonnes pratiques à adopter sur le forum, consulter la Charte et sa FAQ

Avatar de l’utilisateur
artemisart
Messages : 1893
Inscription : 21 Juin 2011 19:51
Localisation : Centre
Contact :

Re: [C#] Parallel for dotNET 2.0

Message par artemisart » 05 Juin 2013 15:46

Un ptit test de perf, juste pour voir :mrgreen: :

Code : Tout sélectionner

custom parallel CPU smooth (chunkSize    4) :   00:00:55.2784224
custom parallel CPU smooth (chunkSize    8) :   00:00:34.7866166
custom parallel CPU smooth (chunkSize   16) :   00:00:33.1803737
custom parallel CPU smooth (chunkSize   32) :   00:00:32.3917460
custom parallel CPU smooth (chunkSize   64) :   00:00:31.2058682
custom parallel CPU smooth (chunkSize  128) :   00:00:31.6156023
custom parallel CPU smooth (chunkSize  256) :   00:00:32.7941422
custom parallel CPU smooth (chunkSize  512) :   00:00:31.8694892
custom parallel CPU smooth (chunkSize 1024) :   00:00:30.6303695
custom parallel CPU smooth (chunkSize 2048) :   00:00:31.0798307
custom parallel CPU smooth (chunkSize 4096) :   00:00:31.2680962
custom parallel CPU smooth (chunkSize 8192) :   00:00:31.8348405
custom parallel CPU smooth (auto chunkSize) :   00:00:39.5953471
dotNET parallel CPU smooth :    00:00:33.3017367
main thread only CPU smooth :   00:01:52.9912234
Le code (les calculs) vient de là : http://www.codeproject.com/Articles/582 ... Flow=Fluid
C'est compilé/exécuté avec Mono (IDE: Xamarin Studio qui est en fait MonoDevelop 4), donc la classe Parallel est peut-être plus performante avec VS (mais de toute façon Unity utilise Mono...).

Le code entier si ça intéresse quelqu'un :

Code : Tout sélectionner

using System;
using System.Diagnostics;
using System.Threading;
using System.Threading.Tasks;
using System.Collections.Generic;

namespace Test
{
	static class MainClass
	{
		public static void Main (string[] args)
		{
			CPUTests ();
			Console.WriteLine ("Press any key to continue.");
			Console.ReadKey ();
		}

		static float[] coefficients;
		public static void CPUTests () // http://www.codeproject.com/Articles/582494/GPGPUplusPerformanceplusTests?PageFlow=Fluid
		{
			coefficients = new float[64];
			for (int i = 0; i < 32; i++)
				coefficients [i] = coefficients [62 - i] = i / 31f;
			Console.WriteLine ("Starting computations... Please be patient.\n");
			CPUSmooth ();
		}

		public static void CPUSmooth ()
		{
			const int mb = 1024 * 1024;
			float[] dataIn = new float[mb];
			float[] dataOut = new float[mb];

			for (int i = 0; i < mb; i++)
				dataIn[i] = i;

			const int loops = 1024; // original : 1024
			Stopwatch timer = new Stopwatch ();

			for (int i = 2; i < 14; i++) // chunk sizes of 1 and 2 are to slow... so we start with 4
			{
				int chunkSize = 1 << i;
				timer.Restart ();
				for (int loop = 0; loop < loops; loop++)
					For (0, mb, index => dataOut[index] = SmoothPoint (dataIn, index), chunkSize, Environment.ProcessorCount);
				timer.Stop ();
				Console.WriteLine ("custom parallel CPU smooth (chunkSize {0,4}) :\t{1}", chunkSize, timer.Elapsed);
			}

			timer.Restart ();
			for (int loop = 0; loop < loops; loop++)
				ForAutoChunkSize (0, mb, index => dataOut[index] = SmoothPoint (dataIn, index));
			timer.Stop ();
			Console.WriteLine ("custom parallel CPU smooth (auto chunkSize) :\t{0}", timer.Elapsed);

			timer.Restart ();
			for (int loop = 0; loop < loops; loop++)
				Parallel.For(0, mb, index => dataOut[index] = SmoothPoint (dataIn, index));
			timer.Stop ();
			Console.WriteLine ("dotNET parallel CPU smooth :\t{0}", timer.Elapsed);

			timer.Restart ();
			for (int loop = 0; loop < loops; loop++)
				for (int i = 0; i < mb; i++)
					dataOut[i] = SmoothPoint (dataIn, i);
			Console.WriteLine ("main thread only CPU smooth :\t{0}", timer.Elapsed);
			timer.Stop ();
		}

		public static float SmoothPoint (float[] data, int index)
		{
			float sum = 0;
			int count = 0;
			for (int coefficientIndex = 0; coefficientIndex < coefficients.Length; coefficientIndex++)
			{
				int sourceIndex = index + coefficientIndex - 32;
				if (sourceIndex >= 0 && sourceIndex < data.Length)
				{
					sum += data[sourceIndex] * coefficients[coefficientIndex];
					count++;
				}
			}
			return sum / count;
		}

		public static void ForAutoChunkSize (int fromInclusive, int toExclusive, Action<int> action)
		{
			For (
				fromInclusive,
				toExclusive,
				action,
				(toExclusive - fromInclusive) / Environment.ProcessorCount + 1,
				Environment.ProcessorCount
				);
		}

		public static void For (int fromInclusive, int toExclusive, Action<int> action, int chunkSize, int threadCount)
		{
			int index = fromInclusive - chunkSize;
			var locker = new object ();

			Action process = () =>
			{
				int chunkStart;
				while (true)
				{
					chunkStart = 0;
					lock (locker)
						chunkStart = index += chunkSize;
					for (int i = chunkStart; i < chunkStart + chunkSize; i++)
					{
						if (i >= toExclusive)
							return;
						action (i);
					}
				}
			};

			IAsyncResult[] results = new IAsyncResult[threadCount];
			for (int i = 0; i < threadCount; ++i)
				results[i] = process.BeginInvoke (null, null);

			// wait all
			for (int i = 0; i < threadCount; ++i)
				process.EndInvoke (results[i]);
		}
	}
}

Avatar de l’utilisateur
cayou66
Codeur
Codeur
Messages : 6451
Inscription : 30 Juin 2011 14:45
Localisation : Montréal

Re: [C#] Parallel for dotNET 2.0

Message par cayou66 » 05 Juin 2013 16:19

Impressionnant... :shock:


Avatar de l’utilisateur
cayou66
Codeur
Codeur
Messages : 6451
Inscription : 30 Juin 2011 14:45
Localisation : Montréal

Re: [C#] Parallel for dotNET 2.0

Message par cayou66 » 05 Juin 2013 16:38

Dans plusieurs projets on a utilisé des systèmes de thread, ce qui marchait plus ou moins bien, ça risque de nous intéresser pour l'avenir l'import de la classe Parallel.

Avatar de l’utilisateur
lenneth78
Messages : 187
Inscription : 05 Jan 2012 16:58

Re: [C#] Parallel for dotNET 2.0

Message par lenneth78 » 11 Juin 2013 19:30

Très intéressent et impressionnant !

Concrètement ça marche comment ?( en résumé ) Et il n'y a pas de problème de sur allocation ? ( très coûteux pour les mobiles )

Avatar de l’utilisateur
artemisart
Messages : 1893
Inscription : 21 Juin 2011 19:51
Localisation : Centre
Contact :

Re: [C#] Parallel for dotNET 2.0

Message par artemisart » 11 Juin 2013 19:53

Concrètement ça va séparer le for en pleins de petits bouts (chunks).
Après, on crée un delegate (process) qui va exécuter tous ces petits bouts, avec la synchronisation nécessaire pour que plusieurs instances de ce delegate puissent fonctionner en même temps.
Ensuite on lance x delegates process, x étant par défaut le nombre de cœur de l'ordi, avec la fonction BeginInvoke permettant d'exécuter la fonction sur le ThreadPool : il n'y a donc pas (ou rarement) d'allocation (couteuse !) de threads puisque le ThreadPool en garde constamment plusieurs actifs.
Et pour finir, on attend la fin de tous le monde avec les EndInvoke !

Répondre

Revenir vers « Scripts »