Intro
I am working with a complex external library, where I am attempting to execute it's functionality on a large list of items. The library does not expose a good async interface, so I'm stuck with some quite old-fashioned code.
My aim is to optimize the time it takes to complete a batch of processing, and to demonstrate the problem without having to include the actual 3rd party library I have created an approximation of the problem below
Problem
Given a non-async action, where you can know the "size" (ie, complexity) of the action in advance:
public interface IAction
{
int Size { get; }
void Execute();
}
And given there are 3 variants of this action:
public class LongAction : IAction
{
public int Size => 10000;
public void Execute()
{
Thread.Sleep(10000);
}
}
public class MediumAction : IAction
{
public int Size => 1000;
public void Execute()
{
Thread.Sleep(1000);
}
}
public class ShortAction : IAction
{
public int Size => 100;
public void Execute()
{
Thread.Sleep(100);
}
}
How could you optimize a long list of these actions, so that when run in some sort of parallel fashion, the entire batch completes as fast as possible?
Naively, you could just throw the entire lot at a Parallel.ForEach, with a reasonably high Parallelism and that certainly works - but there must be a way to optimally schedule them so some of the biggest are started first.
To further illustrate the problem, if we take a super-simplified example
- 1 task of size 10
- 5 tasks of size 2
- 10 tasks of size 1
And 2 available threads. I could come up with 2 (of many) ways to schedule these tasks (The black bar being dead time - nothing to schedule):
Clearly the first one completes earlier than the second.
Minimal Complete & Verifiable Code
Entire test code if anyone fancies a bash (try to make it faster than my naive implementation below):
class Program
{
static void Main(string[] args)
{
MainAsync().GetAwaiter().GetResult();
Console.ReadLine();
}
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());
var swSync = Stopwatch.StartNew();
Parallel.ForEach(list, new ParallelOptions { MaxDegreeOfParallelism = 20 }, action =>
{
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}");
});
swSync.Stop();
Console.WriteLine($"Done in {swSync.ElapsedMilliseconds}ms");
}
}
public interface IAction
{
int Size { get; }
void Execute();
}
public class LongAction : IAction
{
public int Size => 10000;
public void Execute()
{
Thread.Sleep(10000);
}
}
public class MediumAction : IAction
{
public int Size => 1000;
public void Execute()
{
Thread.Sleep(1000);
}
}
public class ShortAction : IAction
{
public int Size => 100;
public void Execute()
{
Thread.Sleep(100);
}
}