I implemented the QuickSort-Algorithm 3 times and measured the time for sorting 50 million random numbers:
sequential (took ~14 seconds)
With
Parallel.Invoke()in the same method as the sorting algorithm (took ~12 seconds)With
Parallel.Invoke()in a separate method (took ~7 seconds)
So my question is: Why is Parallel.Invoke() much faster if the call is in a separate method?
On my computer the 3. example was more than twice as fast as the 2.
2. With Parallel.Invoke() in the same method as the sorting algorithm
public class ParallelQuickSort
{
private const int Threshold = 100;
public static void Sort(int[] array)
{
if (array == null || array.Length == 0)
{
new ArgumentException("number array must be at least of length 1");
}
QuickSort(array, 0, array.Length - 1);
}
private static void QuickSort(int[] array, int left, int right)
{
var i = left;
var j = right;
var m = array[(left + right) / 2];
while (i <= j)
{
while (array[i] < m) { i++; }
while (array[j] > m) { j--; }
if (i <= j)
{
var t = array[i]; array[i] = array[j]; array[j] = t;
i++; j--;
}
}
if (j - left > Threshold && right - i > Threshold)
{
Parallel.Invoke(
() => QuickSort(array, left, j),
() => QuickSort(array, i, right)
);
}
else
{
if (j > left) { QuickSort(array, left, j); }
if (i < right) { QuickSort(array, i, right); }
}
}
}
3. With Parallel.Invoke() in a separate method
public class ParallelSeparateMethodQuickSort
{
private const int Threshold = 100;
public static void Sort(int[] array)
{
if (array == null || array.Length == 0)
{
new ArgumentException("number array must be at least of length 1");
}
QuickSort(array, 0, array.Length - 1);
}
private static void QuickSort(int[] array, int left, int right)
{
var i = left;
var j = right;
var m = array[(left + right) / 2];
while (i <= j)
{
while (array[i] < m) { i++; }
while (array[j] > m) { j--; }
if (i <= j)
{
var t = array[i]; array[i] = array[j]; array[j] = t;
i++; j--;
}
}
if (j - left > Threshold && right - i > Threshold)
{
ParallelInvoke(array, left, j, i, right);
}
else
{
if (j > left) { QuickSort(array, left, j); }
if (i < right) { QuickSort(array, i, right); }
}
}
private static void ParallelInvoke(int[] array, int left, int j, int i, int right)
{
Parallel.Invoke(
() => QuickSort(array, left, j),
() => QuickSort(array, i, right)
);
}
}
Full Code
using System;
using System.Threading.Tasks;
using System.Diagnostics;
namespace parallelQuicksort
{
class Program
{
static void Main(string[] args)
{
const int N = 50_000_000;
for (int i = 0; i < 5; i++)
{
var array = GetRandomArray(N);
Measure("Sequential\t", () => SequentialQuickSort.Sort(array));
array = GetRandomArray(N);
Measure("Parallel\t", () => ParallelQuickSort.Sort(array));
array = GetRandomArray(N);
Measure("P. Separate Method", () => ParallelSeparateMethodQuickSort.Sort(array));
}
}
private static int[] GetRandomArray(int length)
{
var random = new Random(4711);
var array = new int[length];
for (int i = 0; i < length; i++)
{
array[i] = random.Next();
}
return array;
}
public static void Measure(string name, Action action)
{
Stopwatch stopwatch = Stopwatch.StartNew();
action();
stopwatch.Stop();
var time = stopwatch.ElapsedMilliseconds;
Console.WriteLine($"{name}: \tElapsed={time}");
}
}
public class SequentialQuickSort
{
public static void Sort(int[] array)
{
if (array == null || array.Length == 0)
{
new ArgumentException("number array must be at least of length 1");
}
QuickSort(array, 0, array.Length - 1);
}
private static void QuickSort(int[] array, int left, int right)
{
var i = left;
var j = right;
var m = array[(left + right) / 2];
while (i <= j)
{
while (array[i] < m) { i++; }
while (array[j] > m) { j--; }
if (i <= j)
{
var t = array[i]; array[i] = array[j]; array[j] = t;
i++; j--;
}
}
if (j > left) { QuickSort(array, left, j); }
if (i < right) { QuickSort(array, i, right); }
}
}
public class ParallelQuickSort
{
private const int Threshold = 100;
public static void Sort(int[] array)
{
if (array == null || array.Length == 0)
{
new ArgumentException("number array must be at least of length 1");
}
QuickSort(array, 0, array.Length - 1);
}
private static void QuickSort(int[] array, int left, int right)
{
var i = left;
var j = right;
var m = array[(left + right) / 2];
while (i <= j)
{
while (array[i] < m) { i++; }
while (array[j] > m) { j--; }
if (i <= j)
{
var t = array[i]; array[i] = array[j]; array[j] = t;
i++; j--;
}
}
if (j - left > Threshold && right - i > Threshold)
{
Parallel.Invoke(
() => QuickSort(array, left, j),
() => QuickSort(array, i, right)
);
}
else
{
if (j > left) { QuickSort(array, left, j); }
if (i < right) { QuickSort(array, i, right); }
}
}
}
public class ParallelSeparateMethodQuickSort
{
private const int Threshold = 100;
public static void Sort(int[] array)
{
if (array == null || array.Length == 0)
{
new ArgumentException("number array must be at least of length 1");
}
QuickSort(array, 0, array.Length - 1);
}
private static void QuickSort(int[] array, int left, int right)
{
var i = left;
var j = right;
var m = array[(left + right) / 2];
while (i <= j)
{
while (array[i] < m) { i++; }
while (array[j] > m) { j--; }
if (i <= j)
{
var t = array[i]; array[i] = array[j]; array[j] = t;
i++; j--;
}
}
if (j - left > Threshold && right - i > Threshold)
{
ParallelInvoke(array, left, j, i, right);
}
else
{
if (j > left) { QuickSort(array, left, j); }
if (i < right) { QuickSort(array, i, right); }
}
}
private static void ParallelInvoke(int[] array, int left, int j, int i, int right)
{
Parallel.Invoke(
() => QuickSort(array, left, j),
() => QuickSort(array, i, right)
);
}
}
}
You find my code here: https://github.com/Lazzaretti/ParallelQuicksort
Output
Sequential : Elapsed=14534
Parallel : Elapsed=11960
P. Separate Method: Elapsed=6353
Sequential : Elapsed=14620
Parallel : Elapsed=11954
P. Separate Method: Elapsed=6647
Sequential : Elapsed=14529
Parallel : Elapsed=11870
P. Separate Method: Elapsed=6389
Sequential : Elapsed=14512
Parallel : Elapsed=11787
P. Separate Method: Elapsed=6590
Sequential : Elapsed=16203
Parallel : Elapsed=11738
P. Separate Method: Elapsed=6674
GetRandomArray(N)for each measurement (thereby getting a new unsorted array each time), and I also flip flopped the order that the methods were called, and I still observed that the P. Separate Method was indeed consistently about 2 seconds faster than the other method. So, I agree with you, this is an unexpected outcome. I'm not seeing anything obvious here that would account for this. – Nate