Optimisation du temps des tâches parallèles de longue durée

Pour commencer, je dirais que le problème est le suivant:

Vous avez une liste d'entiers et un nombre limité d'étés. Vous voulez un algorithme qui additionne les nombres entiers dans les étés afin que la valeur maximale des étés soit le minimum possible.

Par exemple:

while (taskManager.HasTasks())
{
    task = taskManager.GetLongestTask();
    thread = threadManager.GetFreeThread(); // blocks if no thread available
    thread.Run(task);
}

Comme vous le pouvez voir le facteur de délimitation est la tâche la plus longue. Les plus courts sont facilement servis en parallèle ou en moins de temps. C'est similaire à Knapsack, mais à la fin se résume à un très simple "premier" ordre des tâches.

Le pseudo code (avec mes classes inventées ) serait:

list = 1, 4, 10, 2, 3, 4
summers = 3

summer(1): 10
summer(2): 4 + 4
summer(3): 3 + 2 + 1

Ceci est juste du pseudo-code, pas parallèle / asynchrone et des blocs. J'espère que vous pourrez en tirer quelque chose d'utile.

Eh bien, cela dépend. Sur mon matériel, votre exemple artificiel (modifié pour que le sommeil soit 1000,100 et 10 ms car je n'ai pas toute la journée) est ~ 30% plus rapide (~ 15s vs ~ 22s) si je change simplement la boucle pour exécuter toutes les tâches longues d'abord:

Parallel.ForEach(list.OrderByDescending(l=>l.Size), action => ...

Mais bien sûr, cela dépend entièrement de la charge de ces tâches. Si deux tâches différentes utilisent fortement la même ressource (par exemple, une base de données partagée), il peut y avoir des gains très limités à exécuter ces deux tâches en parallèle car elles finiront par se verrouiller l'une l'autre pendant des périodes à un certain niveau.

Je suggérerais que vous ayez besoin d'une analyse plus approfondie, puis de regrouper les tâches en fonction de leur capacité à être parallèles en fonction de ce qu'elles font réellement, et d'essayer de vous assurer d'en exécuter autant des threads parallèles avec autant de tâches «compatibles» que possible ... Et bien sûr, si une tâche particulière semble toujours prendre autant de temps que toutes les autres assemblées, assurez-vous que l'on commence en premier ....

Très difficile de donner de meilleurs conseils avec les détails donnés ici.

Le tri par taille de tâche dans l'ordre décroissant, puis l'utilisation de TaskFactory pour exécuter chacune dans une tâche différente a réduit considérablement le temps d'exécution. Le niveau de parallélisme est resté 20. Les résultats ont été: 114 676 ms contre 193 713 ms dans votre échantillon d'origine. (~ 40% d'amélioration)

EDIT: Dans votre exemple spécifique, la liste est de toute façon triée dès le départ, mais Parallel.ForEach ne conserve pas l'ordre d'entrée.

static async Task MainAsync()
{
    var list = new List<IAction>();
    for (var i = 0; i < 200; i++) list.Add(new LongAction());
    for (var i = 0; i < 200; i++) list.Add(new MediumAction());
    for (var i = 0; i < 200; i++) list.Add(new ShortAction());

    Console.WriteLine("Sorting...");
    list.Sort((x, y) => y.Size.CompareTo(x.Size));
    int totalTasks = 0;

    int degreeOfParallelism = 20;
    var swSync = Stopwatch.StartNew();
    using (SemaphoreSlim semaphore = new SemaphoreSlim(degreeOfParallelism))
    {
        foreach (IAction action in list)
        {
            semaphore.Wait();
            Task.Factory.StartNew(() =>
            {
                try
                {
                    Console.WriteLine($"{DateTime.Now:HH:mm:ss}: Starting action {action.GetType().Name} on thread {Thread.CurrentThread.ManagedThreadId}");
                    var sw = Stopwatch.StartNew();
                    action.Execute();
                    sw.Stop();
                    Console.WriteLine($"{DateTime.Now:HH:mm:ss}: Finished action {action.GetType().Name} in {sw.ElapsedMilliseconds}ms on thread {Thread.CurrentThread.ManagedThreadId}");
                }
                finally
                {
                    totalTasks++;
                    semaphore.Release();
                }
            });
        }

        // Wait for remaining tasks....
        while (semaphore.CurrentCount < 20)
        { }

        swSync.Stop();
        Console.WriteLine($"Done in {swSync.ElapsedMilliseconds}ms");
        Console.WriteLine("Performed total tasks: " + totalTasks);
    }
}

Une solution relativement rapide et sale consiste à utiliser un partitionneur d'équilibrage de charge au-dessus d'une liste d'actions triée par taille décroissante

var sorted = list.OrderByDescending(a => a.Size);
var partitioner=Partitioner.Create(sorted,EnumerablePartitionerOptions.NoBuffering);

En utilisant seulement ces deux lignes, les performances s'améliorent d'environ 30%, tout comme les autres réponses.

PLINQ partitionne les données et utilise une tâche distincte pour traiter une partition entière à la fois . Lorsque la taille d'entrée est connue, comme c'est le cas avec les tableaux et listes dérivés d'IList, l'entrée est partitionnée en morceaux de taille égale et envoyée à chaque tâche de travail.

Lorsque la taille n'est pas connue, comme C'est le cas avec les méthodes d'itération, les requêtes LINQ, etc. PLINQ utilise le partitionnement par blocs. Un morceau de données est récupéré à la fois et transmis aux tâches de travail.

Une autre option, que j'avais oubliée, est l ' équilibrage de charge sur le partitionnement de chunck supérieur. Cela applique le partitionnement de blocs à l'aide de petits morceaux aux tableaux et à l'entrée dérivée d'IList. L'équilibrage de charge Partitioner.Create renvoient des instances de OrderablePartitioner, de sorte que l'ordre des éléments IAction est préservé

La même chose peut être obtenue avec un IEnumerable source en spécifiant l'option EnumerablePartitionerOptions.NoBuffering :

var sorted = list.OrderByDescending(a => a.Size).ToArray();
var partitioner=Partitioner.Create(sorted, loadBalance:true);

Parallel.ForEach(partitioner, options, action =>...);

Cela créera un OrderablePartitioner qui utilise le codage par blocs