LINQ查询很慢

Question

在应用程序分析期间,我发现模式匹配的函数检查非常慢.它是使用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);
    }
}

呼叫PatternMatch2或PatternMatch3非常慢.它需要大约8秒钟PatternMatch3,大约需要4秒钟PatternMatch2,而呼叫PatternMatch1大约需要0.6 秒.据我所知,它是相同的代码,我认为没有区别.有任何想法吗？

Answer 1

Mark Byers和Marco Mp对于额外的呼叫开销是正确的.但是,这里还有另一个原因:由于关闭,许多对象分配.

编译器在每次迭代创建一个新对象,存储的当前值buffer,position以及i谓词可以使用.这是一个PatternMatch2显示这个的dotTrace快照.<>c_DisplayClass1是编译器生成的类.

(请注意,这些数字很大,因为我正在使用跟踪性能分析,这会增加开销.但是,每次调用的开销相同,因此总体百分比是正确的).

Answer 2

区别在于LINQ版本具有额外的函数调用.在LINQ内部,你的lambda函数在循环中被调用.

虽然额外的调用可能会被JIT编译器优化掉,但它无法保证,并且可以增加很小的开销.在大多数情况下,额外的开销并不重要,但由于您的功能非常简单并且被称为极其多次,即使很小的开销也可以快速累加.根据我的经验,LINQ代码通常比等效for循环慢一点.这是您经常为更高级语法支付的性能价格.

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

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

Answer 3

好吧,让我们采取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. 对谓词的函数调用

第二个是对代表的调用,其成本大约是典型虚拟调用的调用成本的两倍(在第一个版本中,除了数组deindexing之外,您没有额外的调用.

如果你真的想要粗暴的表现,你可能想要获得尽可能"老式​​"的代码.在这种情况下,我甚至会用方法1替换方法1中的foreach(至少如果它不用于优化,它会使它更具可读性,因为无论如何你都要跟踪索引).

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

(*)我说几乎是因为它使用代理方法来检查输入枚举是否为null并且在枚举集合之前抛出异常 - 这是一个小细节,它不会使我之前写的内容无效,在此处突出显示为了完整.