8

在应用程序分析期间，我发现检查模式匹配的功能非常慢。它是使用 LINQ 编写的。用循环简单地替换这个 LINQ 表达式会产生很大的不同。它是什么？LINQ 真的是一件坏事并且工作如此缓慢还是我误解了什么？

private static bool PatternMatch1(byte[] buffer, int position, string pattern)
{
    int i = 0;

    foreach (char c in pattern)
    {
        if (buffer[position + i++] != c)
        {
            return false;
        }
    }

    return true;
}

带有 LINQ 的版本 2（由 Resharper 建议）

private static bool PatternMatch2(byte[] buffer, int position, string pattern)
{
    int i = 0;
    return pattern.All(c => buffer[position + i++] == c);
}

带有 LINQ 的版本 3

private static bool PatternMatch3(byte[] buffer, int position, string pattern)
{
    return !pattern.Where((t, i) => buffer[position + i] != t).Any();
}

版本 4 使用 lambda

private static bool PatternMatch4(byte[] buffer, int position, string pattern, Func<char, byte, bool> predicate)
{
    int i = 0;

    foreach (char c in pattern)
    {
        if (predicate(c, buffer[position + i++]))
        {
            return false;
        }
    }

    return true;
}

这是大缓冲区的用法

const int SIZE = 1024 * 1024 * 50;

byte[] buffer = new byte[SIZE];

for (int i = 0; i < SIZE - 3; ++i)
{
    if (PatternMatch1(buffer, i, "xxx"))
    {
        Console.WriteLine(i);
    }
}

调用PatternMatch2orPatternMatch3非常慢。大约需要 8 秒PatternMatch3， 大约需要 4 秒PatternMatch2，而调用PatternMatch1大约需要 0.6。据我了解，它是相同的代码，我看不出有什么区别。有任何想法吗？

4

4 回答 4

7

Mark Byers 和 Marco Mp 对额外通话开销的看法是正确的。但是，这里还有另一个原因：由于闭包导致的许多对象分配。

编译器在每次迭代时创建一个新对象，存储 的当前值buffer，position并且i谓词可以使用该对象。这是PatternMatch2显示此内容的 dotTrace 快照。<>c_DisplayClass1是编译器生成的类。

（请注意，数字很大，因为我正在使用跟踪分析，这会增加开销。但是，每次调用的开销相同，因此总体百分比是正确的）。

在此处输入图像描述

于 2012-10-10T13:14:09.477 回答
6

不同之处在于 LINQ 版本有额外的函数调用。在 LINQ 内部，您的 lambda 函数在循环中被调用。

虽然JIT 编译器可能会优化额外的调用，但不能保证它会增加一点开销。在大多数情况下，额外的开销无关紧要，但是由于您的函数非常简单并且被调用的次数非常多，因此即使是很小的开销也会很快加起来。以我的经验，LINQ 代码通常比等效循环慢一点。这就是您经常为更高级的语法付出的性能代价。for

在这种情况下，我建议坚持使用显式循环。

在优化这部分代码时，您可能还需要考虑更有效的搜索算法。您的算法是最坏情况 O(n*m) 但存在更好的算法。

于 2012-10-10T12:54:41.097 回答
6

好吧，让我们以 Where 运算符为例。

它的实现几乎（*）像：

public IEnumerable<T> Where(this IEnumerable<T> input, Func<T, bool> fn)
{
    foreach(T i in input) 
        if (fn(i))
            yield return i;
}

这意味着，对于 IEnumerable 上的每个循环，都会创建一个迭代器对象 - 请注意，您有 SIZE - n 个这些分配，因为您执行了许多 LINQ 查询。

然后对于您拥有的模式中的每个字符：

  1. 对枚举器的函数调用
  2. 对谓词的函数调用

第二个是对委托的调用，其成本大约是典型虚拟调用的两倍（在第一个版本中，除了数组去索引之外，您没有额外的调用。

如果您真的想要粗暴的性能，您可能希望获得尽可能“旧式”的代码。在这种情况下，我什至会用一个普通的 for 替换方法 1 中的 foreach （至少如果它不能用于优化，它会使其更具可读性，因为您无论如何都在跟踪索引）。

在这种情况下，它也更具可读性，它表明 Resharper 的建议有时是值得商榷的。

(*) 我说几乎是因为它使用代理方法来检查输入可枚举是否为空，并在枚举集合之前抛出异常——这是一个小细节，不会使我之前写的内容无效，在这里突出显示为了完整性。

于 2012-10-10T13:06:53.930 回答
1

LINQ 应用于集合时的主要目标是其简单性。如果你想要性能，你应该完全避免使用 LINQ。同样要枚举一个数组，您只需增加一个索引变量，而 LINQ 需要设置一个完整的枚举器对象。

于 2012-10-10T12:56:27.423 回答