title: Inefficient .Net fork/join
body: <p>I've implemented a parallel mergesort using Java fork/join pool and .Net Parallel.Invoke, and I observe  drmamatic difference in perofmance between the versions: 5 sec (Java) and 45 sec (.Net) to sort a 2GB file. That's almost order of magnitude difference.</p>
  
  <p>Here's the .Net code:</p>
  
  <pre><code>    public void ParallelSort()
      {
          Start = DateTime.Now.Ticks;
  
          int lo = 0;
          int hi = values.Length - 1;
          int mid = values.Length / 2;
          int maxDepth = Environment.ProcessorCount;
          Sort(lo, mid, hi, maxDepth);
  
          End = DateTime.Now.Ticks;
      }
      private void Sort(int lo, int mid, int hi, int maxDepth)
      {
         if (hi - lo &lt; 16)
              InsertionSort.Sort(values, lo, hi);
          else if (maxDepth &gt; 0)
          {
              Parallel.Invoke(
                  () =&gt; Sort(lo, (mid + lo)/2, mid, maxDepth-1),
                  () =&gt; Sort(mid + 1, (hi + mid)/2, hi, maxDepth-1));
              Merge(lo, mid, hi);
  
          }
          else
          {
              Sort(lo, (mid + lo)/2, mid, 0);
              Sort(mid + 1, (hi + mid)/2, hi, 0);
              Merge(lo, mid, hi);
          }
      }
  </code></pre>
  
  <p>Concurrency Visualizer shows that, as far as I can see, threads mostly spend their time waiting, syncing and GCing (not enough rep to post a picture).</p>
  
  <p>What can be done to achieve comparable speed with Java fork/join implmentation? Or is .Net Parallel engine by design inefficient for aggresive multithreading (multitasking)?</p>
  
  <p>PS: Java code</p>
  
  <pre><code>public class MergeSort extends RecursiveAction
  {
  public void parallelSort()
  {
      int lo = 0;
      int hi = values.length - 1;
      int mid = values.length / 2;
      ForkJoinPool p = new ForkJoinPool();
      MergeSort s = new MergeSort(lo, mid, hi);
      try
      {
          p.invoke(s);
          p.shutdown();
      }
      catch (Exception e)
      {
          e.printStackTrace();
      }
  }
  @Override
  protected void compute()
  {
      if (hi - lo &gt; 16)
      {
          invokeAll(
                  new MergeSort(lo, (mid + lo)/2, mid),
                  new MergeSort(mid + 1, (hi + mid)/2, hi));
  
          merge(lo, mid, hi);
      }
      else
          ElementarySort.insertionSort(values, lo, hi);
  
  }
  }
  </code></pre>
  
  <p>Update 1:
  interesting, a bottom-up implementation shows inverse results: .Net's Parallel.For() shines and Java's ExecutorService.InvokeAll(): 4 sec vs 193 sec to sort a 256Mb file. Dunno, maybe I'm doing something wrong.
  Java code:</p>
  
  <pre><code>public void parallelBottomUpSort() throws Exception
  {
      ExecutorService p = Executors.newFixedThreadPool(8);
  
  
      for (int sz = 1; sz &lt; values.length; sz *= 2)
      {
          int N = (int) Math.ceil((double) values.length / (2 * sz));
          System.out.println(N);
          List&lt;MergeSort&gt; ms = new ArrayList&lt;&gt;(N);
          for (int i = 0; i &lt; N; i++)
          {
              int lo = 2 * sz * i;
              int hi = Math.min(lo + 2 * sz, values.length) - 1;
              int mid = lo + sz - 1;
              ms.add(new MergeSort(values, aux, lo, mid, hi));
          }
  
          p.invokeAll(ms);
      }
      p.shutdown();
  }
  </code></pre>
  
  <p>.Net code:</p>
  
  <pre><code> public void ParallelBottomUpSort()
      {
  
          for (int sz = 1; sz &lt; values.Length; sz *= 2)
              Parallel.For(0, (int) Math.Ceiling((double) values.Length/(2*sz)), i =&gt;
              {
                  int lo = 2 * sz * i;
                  int hi = Math.Min(lo + 2 * sz, values.Length) - 1;
                  int mid = lo + sz - 1;
                  Merge(lo, mid, hi);
              });
  
  
      }   
  </code></pre>
  
  <p>Looks like .Net's parallel engine is generally more stable. Java's concurrent package has its worst and best cases.</p>
  
  <p>Update 2: compilable sources</p>
  
  <pre><code>    class Sort
  {
      private int[] values, aux;
  
       public Sort(int[] values)
      {
          this.values = values;
          this.aux = new int[values.Length];
      }
  
       private unsafe void Merge(int lo, int mid, int hi)
       {
           if (lo == hi)
               return;
  
           if (mid + 1 &lt;= hi &amp;&amp; values[mid] &lt;= values[mid + 1])
               return;
  
           Buffer.BlockCopy(values, sizeof(int) * lo, aux, sizeof(int) * lo, sizeof(int) * (hi - lo + 1));
  
           int i = lo;
           int j = mid + 1;
  
           fixed (int* a = values, b = aux)
           {
               for (int k = lo; k &lt;= hi; k++)
               {
                   if (i &gt; mid)
                       a[k] = b[j++];
                   else if (j &gt; hi)
                       a[k] = b[i++];
                   else if (b[i] &lt; b[j])
                       a[k] = b[i++];
                   else
                       a[k] = b[j++];
               }
           }
       }
  
       public void ParallelBottomUpSort()
       {
           for (int sz = 1; sz &lt; values.Length; sz *= 2)
               Parallel.For(0, (int)Math.Ceiling((double)values.Length / (2 * sz)), i =&gt;
               {
                   int lo = 2 * sz * i;
                   int hi = Math.Min(lo + 2 * sz, values.Length) - 1;
                   int mid = lo + sz - 1;
                   Merge(lo, mid, hi);
               });
  
       }
  
       public void ParallelTopDownSort()
       {
           int lo = 0;
           int hi = values.Length - 1;
           int mid = values.Length / 2;
           int maxDepth = (int)Math.Log(Environment.ProcessorCount, 2);
           ParallelTopDownSort(lo, mid, hi, maxDepth);
  
       }
  
       private void ParallelTopDownSort(int lo, int mid, int hi, int maxDepth)
       {
           if (hi - lo &lt; 16)
               InsertionSort.Sort(values, lo, hi);
           else if (maxDepth &gt; 0)
           {
               Parallel.Invoke(
                   () =&gt; ParallelTopDownSort(lo, (mid + lo) / 2, mid, maxDepth - 1),
                   () =&gt; ParallelTopDownSort(mid + 1, (hi + mid) / 2, hi, maxDepth - 1));
               Merge(lo, mid, hi);
  
           }
           else
           {
               ParallelTopDownSort(lo, (mid + lo) / 2, mid, 0);
               ParallelTopDownSort(mid + 1, (hi + mid) / 2, hi, 0);
               Merge(lo, mid, hi);
           }
       }
  
      static unsafe void Main(string[] args)
      {
          // path to file to be sorted
          String path = args[0];
  
          Console.WriteLine("Reading file");
          int[] values;
  
          // Loading file
          var loadStart = DateTime.Now.Ticks;
          long intCount = (new FileInfo(path)).Length / 4;
          values = new int[intCount];
          MemoryMappedFile mmf = MemoryMappedFile.CreateFromFile(path);
          MemoryMappedViewAccessor mma = mmf.CreateViewAccessor();
          byte* ptr = (byte*) 0;
          mma.SafeMemoryMappedViewHandle.AcquirePointer(ref ptr);
          Marshal.Copy(new IntPtr(ptr), values, 0, (int) intCount);
          var loadEnd = DateTime.Now.Ticks;
          Console.WriteLine("Loaded in " + (loadEnd - loadStart) / (10000) + " ms");
  
          // Sorting
          Console.WriteLine("Sorting " + values.Length + " ints");
          Sort ms = new Sort(values);
          var start = DateTime.Now.Ticks;
          ms.ParallelBottomUpSort();
          var end = DateTime.Now.Ticks;
          Console.WriteLine("Done sorting");
          Console.WriteLine((end - start) / (1000 * 10000));
      }
  
  
  }
  </code></pre>