在并行for循环中测试2个数组是否相等

Question

我目前有一个for循环来比较2个数组并确定它们是否相等.

public override bool Equals(object obj)
{
    RushHourPathLengthNode otherNode = (RushHourPathLengthNode)obj;

    // Compare their carCoords and return false as soon as we find a difference
    for (int i = 0, l = carCoords.Length; i < l; ++i)
        if (carCoords[i].x != otherNode.carCoords[i].x || carCoords[i].y != otherNode.carCoords[i].y)
            return false;
    return true;
}

这很好用,但它是我的程序中最慢的部分之一.这样我的测试用例大约需要7秒钟来计算.

虽然我可能运行50K任务,但我的i7 860 CPU(4核,8个线程)的CPU使用率约为50%.

我的想法是使用并行for循环来最大化CPU使用率并使其更快.这就是我提出的.

public override bool Equals(object obj)
    {
        RushHourPathLengthNode otherNode = (RushHourPathLengthNode)obj;
        bool result = true;

        Parallel.For(0, carCoords.Length, (i, loopState) =>{
            if (!result)
                loopState.Stop();

            if (carCoords[i].x != otherNode.carCoords[i].x || carCoords[i].y != otherNode.carCoords[i].y)
                result = false;
        });

        return result;
    }

对我来说,看起来它会尝试并行运行,并且一旦因为loopState.Stop而找到差异就会停止工作.这样CPU的使用率是90%+但是我的测试用例大约需要35秒来计算,我不明白为什么.

我的实施有问题还是我的整个方法都错了？

编辑: carCoords.Length将是介于2和+ -100之间的值.听起来这个价值太低,不足以证明这一点并行.

Answer 1

首先，如果您的 for 循环仅执行几百次迭代，则不必费心对其进行并行化。对于您在每次迭代中所做的工作，您需要数千次迭代才能使其有价值。

假设您有很多迭代，那么速度大幅减慢的主要原因是您在每次迭代中只做了很少的工作。在调度任务、调用方法体等方面存在大量开销，并且这些开销在总体执行时间中占主导地位。

Partinioner.Create您可以通过使用（来自命名空间）将范围划分为段来解决此问题System.Collections.Concurrent。这为您提供了包含每个范围的开始和结束索引的元组序列。然后，您可以让每个任务在一个范围内迭代，这样效率会更高。

其次，由于局部变量是在闭包对象中捕获的，因此有时在方法体内使用变量的本地副本会更快。

这就是我们得到的：

    Parallel.ForEach(Partitioner.Create(0, carCoords.Length), (r, loopState) => {
        var c1 = carCoords;
        var c2 = otherNode.carCoords;
        int end = r.Item2;
        for (int i = r.Item1; i < end; ++i) {
            if (loopState.IsStopped)
                return;
            if (c1[i].x != c2[i].x || c1[i].y != c2[i].y) {
                loopState.Stop();
                return;
            }
        }
    });

我不确定是否值得检查IsStopped每次迭代。拥有更多分区（使用重载Partitioner.Create）并将检查放在 for 循环之前可能会更有效。