并行Linq查询优化

16

最近我一直在使用无副作用的方法来重构代码,以便使用并行 Linq 加速程序运行。但是在这个过程中,我多次发现惰性计算会使事情变得更糟,而不是更好,因此我想知道是否有任何工具可以帮助优化并行 Linq 查询。

我之所以问这个问题,是因为最近我通过修改某些方法并在特定的关键位置添加了 AsParallel,从而重构了一些并行代码。运行时间从 2 分钟降至 45 秒,但是从性能监视器中明显可以看出,CPU 上的所有核心都没有被充分利用。经过几次尝试后,我强制执行了其中一些查询,使用 ToArray,运行时间进一步缩短到 16 秒。虽然减少了代码的运行时间,但这也让人感到有些不安,因为不清楚在哪些代码中需要使用 ToArray 强制执行查询。等到最后一刻才等待查询执行并不是最佳策略,但也不清楚在代码的哪些地方需要强制执行一些子查询以利用所有 CPU 核心。

目前我不知道如何正确使用 ToArray 或其他强制执行 Linq 计算的方法,以实现最大的 CPU 利用率。那么,是否有任何通用的准则和工具来优化并行 Linq 查询呢?

以下是伪代码示例:

var firstQuery = someDictionary.SelectMany(FirstTransformation);
var secondQuery = firstQuery.Select(SecondTransformation);
var thirdQuery = secondQuery.Select(ThirdTransformation).Where(SomeConditionCheck);
var finalQuery = thirdQuery.Select(FinalTransformation).Where(x => x != null);
FirstTransformationSecondTransformationThirdTransformation都是CPU密集型操作,复杂度大致相当于几个3x3的矩阵乘法和一些 if 判断。 SomeConditionCheck基本上是一个null检查。 FinalTransformation是代码中最费CPU的部分,因为它将执行一堆线-平面交点检测,并检查这些交点是否被包含在多边形内,然后提取距离某一点最近的交点。
我不知道我在哪里添加AsParallel竟然能如此显著地减少代码运行时间。现在我已经达到了运行时间的局部最小值,但我不知道原因。这只是我无意中发现的愚蠢的运气。如果你想知道,在第一行和最后一行添加AsParallel即可。在其他任何位置添加AsParallel都会增加运行时间,有时甚至会增加20秒。第一行还有一个隐藏的 ToArray

2
与非并行查询相同,对于AsParallel也是如此。在评估查询之前,什么都不会发生。您必须遍历或以其他方式执行查询。 - Anthony Pegram
3
请提供一些样例代码,这样我们可以从概括的解释中想象出更具体的内容,并用具体的代码提供答案。 - George Mamaladze
1
这听起来像是您意外地对一个序列进行了两次迭代。否则,使用.ToArray()将没有真正的好处。 - Johannes Rudolph
3
在开始通过试错进行优化之前,请使用分析器进行分析。 - Daniel Mann
1
@davidk01,你可能正在触发缓存重置。这里有一个例子:src.Select(f1).Select(f2).ToList()与src.Select(f1).ToList().Select(f2).ToList()。在第一种情况下,LINQ会同时应用f1和f2,而在第二种情况下则是逐步进行。f1和f2可能会访问完全不同的内存部分,并不断导致缓存重置。 - Valera Kolupaev
显示剩余5条评论
2个回答

18

这里有几件事情:

  1. PLINQ 比未知长度的 IEnumerable 更高效地并行化集合。如果你有一个数组,它会将数组长度除以 CPU 核心数,并平均分配任务。但是,如果你有一个长度未知的 IEnumerable,它会进行一种奇怪的指数级 ramp-up 类型的操作,其中任务将处理 1、2、4、8 等元素,直到达到 IEnumerable 的末尾。
  2. 通过将所有查询并行化,你将工作分解成小块。如果你在 N 个元素上有 M 个并行查询,则最终会得到 M*N 个任务。与仅并行化最后一个查询相比,这会有更多的线程开销,此时你将只得到 N 个任务。
  3. 当每个任务处理时间大致相同时,PLINQ 表现最佳。这样它就可以将它们均匀地分配在核心之间。通过并行化每个性能行为不同的查询,你将得到 M*N 个任务,这些任务需要花费不同的时间,因此 PLINQ 无法最优地安排它们(因为它无法预先知道每个任务可能需要花费多长时间)。

因此,总体指导原则是:尽可能在开始之前确保你有一个数组,并仅在评估之前对最后一个查询使用 AsParallel。因此,类似以下的内容应该可以很好地工作:

var firstQuery = someDictionary.SelectMany().ToArray().Select(FirstTransformation);
var secondQuery = firstQuery.Select(SecondTransformation);
var thirdQuery = secondQuery.Select(ThirdTransformation).AsParallel().Where(SomeConditionCheck).ToArray();
var finalQuery = thirdQuery.Select(FinalTransformation).AsParallel().Where(x => x != null);

7
没有看到实际的代码,很难确定。但是作为一般准则,应该避免在复杂的数字计算中使用P / LINQ,因为委托和IEnumerable开销太大。使用线程获得的速度很可能被LINQ提供的方便抽象所吞噬。
这里有一些代码,它计算了两个整数列表的总和,进行了一些int到float的比较,然后计算了它的cos。这是基本的东西,可以使用LINQ的.Zip运算符很好地完成...或者用for循环的老方法来完成。
更新1:使用Haswell 8核机器上的更新ParallelLinq
- Linq 0,95秒 - Linq Parallel 0,19秒 - Optimized 0,45秒 - Optimized Parallel 0,08秒
时间差别接近3倍,原因是IEnumerable的惰性和方法调用开销(我使用了Release模式x32 Windows 7,.NET 4双核)。我尝试在LINQ版本中使用AsParallel,但实际上速度变慢了(2.3秒)。如果你是数据驱动的,你应该使用Parallel.For结构来获得良好的可伸缩性。IEnumerable本身不适合并行化,因为:
- 在枚举到结束之前,你不知道有多少工作要做。 - 你不能急切地分块,因为你不知道IEnumerable将返回下一个元素有多快(可能是Web服务调用或数组索引访问)。
下面是一个代码示例来说明这一点。如果你想更多地优化裸机性能,你需要先摆脱成本太高的抽象。与非内联的MoveNext()和Current方法调用相比,数组访问要便宜得多。
    class Program
    {
        static void Main(string[] args)
        {
            var A = new List<int>(Enumerable.Range(0, 10*1000*1000));
            var B = new List<int>(Enumerable.Range(0, 10*1000*1000));

            double[] Actual = UseLinq(A, B);
            double[] pActual = UseLinqParallel(A, B);

            var other = Optimized(A, B);
            var pother = OptimizedParallel(A, B);
        }

        private static double[] UseLinq(List<int> A, List<int> B)
        {
            var sw = Stopwatch.StartNew();
            var Merged = A.Zip(B, (a, b) => a + b);
            var Converted = A.Select(a => (float)a);

            var Result = Merged.Zip(Converted, (m, c) => Math.Cos((double)m / ((double)c + 1)));

            double[] Actual = Result.ToArray();
            sw.Stop();

            Console.WriteLine("Linq {0:F2}s", sw.Elapsed.TotalSeconds);
            return Actual;
        }

    private static double[] UseLinqParallel(List<int> A, List<int> B)
    {
        var sw = Stopwatch.StartNew();
        var x = A.AsParallel();
        var y = B.AsParallel();

        var Merged = x.Zip(y, (a, b) => a + b);
        var Converted = x.Select(a => (float)a);

        var Result = Merged.Zip(Converted, (m, c) => Math.Cos((double)m / ((double)c + 1)));

        double[] Actual = Result.ToArray();
        sw.Stop();

        Console.WriteLine("Linq Parallel {0:F2}s", sw.Elapsed.TotalSeconds);
        return Actual;
    }        

        private static double[] OptimizedParallel(List<int> A, List<int> B)
        {
            double[] result = new double[A.Count];
            var sw = Stopwatch.StartNew();
            Parallel.For(0, A.Count, (i) =>
            {
                var sum = A[i] + B[i];
                result[i] = Math.Cos((double)sum / ((double)((float)A[i]) + 1));
            });
            sw.Stop();

            Console.WriteLine("Optimized Parallel {0:F2}s", sw.Elapsed.TotalSeconds);
            return result;
        }

        private static double[] Optimized(List<int> A, List<int> B)
        {
            double[] result = new double[A.Count];
            var sw = Stopwatch.StartNew();
            for(int i=0;i<A.Count;i++)
            {
                var sum = A[i] + B[i];
                result[i] = Math.Cos((double)sum / ((double)((float)A[i]) + 1));
            }
            sw.Stop();

            Console.WriteLine("Optimized {0:F2}s", sw.Elapsed.TotalSeconds);
            return result;
        }
    }
}

您在此处启动并行LINQ操作的时间有点晚了,无法充分利用PLINQ。如果您在UseLinqParallel中创建两个变量(var x = A.AsParallel(); y = B.AsParallel();) 并在它们上进行操作,而不是在A和B上进行操作,则应该看到大幅度的性能提升(在我的情况下为3-4倍)。同时,结果对象的最后一个AsParallel()可以省略。 - Jakob Möllås
我已经使用您的更改重新测量了一遍。现在,并行LINQ比单线程LINQ更快,但仍然不是很快。 - Alois Kraus
奇怪,我得到了: Linq 0.81秒 Linq并行 0.25秒 优化的 0.42秒 优化的并行 0.15秒使用 var x = A.AsParallel(); var y = B.AsParallel(); var merged = x.Zip(y, (a, b) => a + b); var converted = x.Select(a => (float)a); var result = merged.Zip(converted, (m, c) => Math.Cos((double)m / ((double)c + 1))); var actual = result.ToArray(); - Jakob Möllås
啊,你应该在 MergedConverted 上移除 ToArray() - Jakob Möllås

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接