title: Time optimization of parallel long-running tasks
body: <h2>Intro</h2>
  
  <p>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. </p>
  
  <p>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</p>
  
  <h2>Problem</h2>
  
  <p>Given a non-async action, where you can know the "size" (ie, complexity) of the action in advance:</p>
  
  <pre><code>public interface IAction
  {
      int Size { get; }
      void Execute();
  }
  </code></pre>
  
  <p>And given there are 3 variants of this action:</p>
  
  <pre><code>public class LongAction : IAction
  {
      public int Size =&gt; 10000;
      public void Execute()
      {
          Thread.Sleep(10000);
      }
  }
  
  public class MediumAction : IAction
  {
  
      public int Size =&gt; 1000;
      public void Execute()
      {
          Thread.Sleep(1000);
      }
  }
  
  public class ShortAction : IAction
  {
      public int Size =&gt; 100;
      public void Execute()
      {
          Thread.Sleep(100);
      }
  }
  </code></pre>
  
  <p>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?</p>
  
  <p>Naively, you could just throw the entire lot at a <code>Parallel.ForEach</code>, 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.</p>
  
  <p>To further illustrate the problem, if we take a super-simplified example</p>
  
  <ul>
  <li>1 task of size 10</li>
  <li>5 tasks of size 2</li>
  <li>10 tasks of size 1</li>
  </ul>
  
  <p>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):</p>
  
  <p><a href="https://i.stack.imgur.com/YJoeu.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/YJoeu.png" alt="enter image description here"></a></p>
  
  <p>Clearly the first one completes earlier than the second.</p>
  
  <h2>Minimal Complete &amp; Verifiable Code</h2>
  
  <p>Entire test code if anyone fancies a bash (try to make it faster than my naive implementation below):</p>
  
  <pre><code>class Program
  {
      static void Main(string[] args)
      {
          MainAsync().GetAwaiter().GetResult();
          Console.ReadLine();
      }
  
      static async Task MainAsync()
      {
          var list = new List&lt;IAction&gt;();
          for (var i = 0; i &lt; 200; i++) list.Add(new LongAction());
          for (var i = 0; i &lt; 200; i++) list.Add(new MediumAction());
          for (var i = 0; i &lt; 200; i++) list.Add(new ShortAction());
  
  
          var swSync = Stopwatch.StartNew();
          Parallel.ForEach(list, new ParallelOptions { MaxDegreeOfParallelism = 20 }, action =&gt;
          {
              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 =&gt; 10000;
      public void Execute()
      {
          Thread.Sleep(10000);
      }
  }
  
  public class MediumAction : IAction
  {
  
      public int Size =&gt; 1000;
      public void Execute()
      {
          Thread.Sleep(1000);
      }
  }
  
  public class ShortAction : IAction
  {
      public int Size =&gt; 100;
      public void Execute()
      {
          Thread.Sleep(100);
      }
  }
  </code></pre>