我执行了 3 次 QuickSort-Algorithm 并测量了对 5000 万个随机数进行排序的时间:
顺序(大约需要 14 秒)
使用
Parallel.Invoke()
作为排序算法的相同方法(耗时约 12 秒)使用
Parallel.Invoke()
在单独的方法中(耗时约 7 秒)
所以我的问题是:如果在单独的方法中调用,为什么 Parallel.Invoke()
会快得多?
在我的电脑上,示例 3. 的速度是示例 2 的两倍多。
2。使用 Parallel.Invoke()
作为排序算法的相同方法
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。在单独的方法
中使用Parallel.Invoke()
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)
);
}
}
完整代码
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)
);
}
}
}
您可以在这里找到我的代码:https://github.com/Lazzaretti/ParallelQuicksort
输出
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
最佳答案
解决了对评论中提到的已排序数组进行排序的问题后,您的问题仍然重现。
我认为原因是您传递给 Parallel.Invoke
的 lambda 捕获的内容和方式。
第一种情况(当 Parallel.Invoke
位于 QuickSort
方法中时):
Parallel.Invoke(
() => QuickSort(array, left, j),
() => QuickSort(array, i, right)
);
您捕获了 5 个变量,所有这些变量都用于整个 QuickSort
方法。所有这些变量都成为编译器生成类的字段。这意味着整个 QuickSort
方法现在适用于对象字段而不是局部变量。如果你反编译那个方法,你会看到类似这样的东西:
var cDisplayClass20 = new SomeCompilerGeneratedClass();
cDisplayClass20.array = array;
cDisplayClass20.left = left;
cDisplayClass20.right = right;
cDisplayClass20.i = cDisplayClass20.left;
cDisplayClass20.j = cDisplayClass20.right;
int num1 = cDisplayClass20.array[(cDisplayClass20.left + cDisplayClass20.right) / 2];
while (cDisplayClass20.i <= cDisplayClass20.j) // field access
{
while (cDisplayClass20.array[cDisplayClass20.i] < num1) // field access
cDisplayClass20.i++;
while (cDisplayClass20.array[cDisplayClass20.j] > num1) // and again
cDisplayClass20.j--;
if (cDisplayClass20.i <= cDisplayClass20.j) // again field access
{
// they are everywhere
int num2 = cDisplayClass20.array[cDisplayClass20.i];
cDisplayClass20.array[cDisplayClass20.i] = cDisplayClass20.array[cDisplayClass20.j];
cDisplayClass20.array[cDisplayClass20.j] = num2;
cDisplayClass20.i++;
cDisplayClass20.j--;
}
}
这证实了上面的观点。
但是,如果您将 Parallel.Invoke
移动到单独的方法中,情况就不再是这样了。仍然捕获了 5 个变量,但这并不影响整个 QuickSort
方法,因为捕获现在发生在单独的 ParallelInvoke
方法中,因此是本地化的。 QuickSort
仍然适用于局部变量,而不适用于编译器生成类的字段。如果你用单独的方法反编译版本,它看起来就像你写的一样:
int index1 = left;
int index2 = right;
int num1 = array[(left + right) / 2];
while (index1 <= index2) // local variables
{
while (array[index1] < num1) // num1 is local variable
++index1;
while (array[index2] > num1)
--index2;
if (index1 <= index2) // local variables again
{
int num2 = array[index1];
array[index1] = array[index2];
array[index2] = num2;
++index1;
--index2;
}
}
...
现在,我假设访问对象字段(通常在堆上)比访问局部变量(通常在堆栈上\在 CPU 寄存器中)要慢一些,因此具有单独方法的版本更快。 Eric Lippert 还在评论中指出:
The jitter will likely do a worse job with the fields than it will with the locals because it will not enregister them as aggressively.
您可以像这样修改您的第一个版本来确认以上内容:
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) {
// copy all variables you pass to lambda
// so that their capture does not affect the whole method
var tmpArray = array;
var tmpLeft = left;
var tmpJ = j;
var tmpI = i;
var tmpRight = right;
Parallel.Invoke(
() => QuickSort(tmpArray, tmpLeft, tmpJ),
() => QuickSort(tmpArray, tmpI, tmpRight)
);
}
else {
if (j > left) {
QuickSort(array, left, j);
}
if (i < right) {
QuickSort(array, i, right);
}
}
}
}
然后两种方法的执行时间将相同。
正如@Eugene 在评论和他的回答中提到的那样 - 除了字段与局部变量访问之外,可能还有其他事情会减慢速度 - 例如上述编译器生成的类的构造和(可能)垃圾收集。然而,这些都是同源根的结果——以不同方式在闭包中捕获局部变量。
关于c# - 如果在单独的方法中调用,为什么 Parallel.Invoke 会快得多?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49818054/