LINQ 内部结构:速度优化
LINQ 优雅的外观背后隐藏着一个精心设计的核心，其设计不仅仅是为了简单。 本文深入探讨 LINQ 的技术复杂性，重点关注提高其执行效率的“速度优化”。 这些优化也有很多缺点。
LINQ
LINQ 是“语言集成查询”的缩写。 它的名字来自于直接用 C# 编写查询的能力：
var query =
from person in people
where person.Age > 20
select person.Name;优点是所有查询组件都可以在编译时由编译器验证，而不是让应用程序在运行时失败。 还支持自动完成。
SharpLab 是一个很好的工具，可以查看编译器对代码的实际操作。 您可以看到查询实际上已转换为与以下内容等效的内容：
var query =
Enumerable.Select(Enumerable.Where(people, person => person.Age > 20), person => person.Name);Enumerable 是在 System.Linq 命名空间中声明的静态类。 这意味着它的所有方法都是静态的，包括此查询中使用的 Select() 和Where() 方法。
注意：Enumerable 是一个包含数百个方法的庞大类。 这实际上是使用partial 关键字的一个很好的例子。 这允许类被分成多个文件。 请随时在
https://github.com/dotnet/dotnet/tree/main/src/runtime/src/libraries/System.Linq/src/System/Linq 检查源代码
Enumerable 中的所有方法实际上都被声明为 IEnumerable<T> 的扩展方法。 这意味着查询可以重写如下：
var query = people
.Where(person => person.Age > 20)
.Select(person => person.Name);这样更容易理解。 people 是一个实现 IEnumerable<Person> 的集合，然后Where() 应用谓词函数并返回实现 IEnumerable<T> 的对象的实例，然后 Select() 应用选择器函数并返回实现 IEnumerable<T> 的另一个对象的实例 IEnumerable<字符串>。 这意味着查询将保留对 Select() 返回的 IEnumerable<string> 的引用。
这里重要的是 Enumerable 类中声明的方法支持 LINQ。 LINQ 的性能是由这些方法的性能定义的。 在本文中，我将尝试解释 LINQ 中用于提高其性能的许多技巧。
IQueryable<T>
LINQ 实际上提供了另一种查询机制，该机制由 IQueryable<T> 接口支持，该接口也在 System.Linq 命名空间中定义。 在这种情况下，查询被委托给提供者，该提供者在运行时将查询转换为表达式树，然后生成可由其他引擎解释的查询。
您可能会发现多个“LINQ to SQL”提供程序将查询转换为可由数据库执行的 SQL 查询。 您还可能会找到其他提供程序，例如 LinqToExcel、LinqToTwitter、LinqToCsv、LINQ-to-BigQuery、
LINQ-to-GameObject-for-Unity、ElasticLINQ、GpuLinq 等等。 它们可以在非常不同的引擎中执行相同的查询。
使用提供程序时，查询在其他地方执行，性能取决于许多因素。 因此，这种类型的查询执行超出了本文的讨论范围。
隐式枚举器崩溃
LINQ 操作是可组合的，这意味着一个操作的输出可以是另一个操作的输入。 我们已经在上面看到 Select() 可以在Where()之后使用。
在没有任何优化的情况下，Where() 和 Select() 的实现类似于以下内容：
public static IEnumerable<TSource> Where<TSource>(
this IEnumerable<TSource> source,
Func<TSource, bool> predicate)
{
foreach(var item in source)
{
if(predicate(item))
yield return item;
}
}
public static IEnumerable<TResult> Select<TSource, TResult>(
this IEnumerable<TSource> source,
Func<TSource, TResult> selector)
{
foreach(var item in source)
{
yield return selector(item);
}
} 每个操作都会返回一个可枚举值。 这意味着要遍历其组合结果，必须创建每个枚举器的实例，必须从枚举器“拉”每个项目，该枚举器从另一个枚举器“拉”该项目，后者从源“拉” 枚举器。 操作组合是使用 LINQ 的一大优势，但也是最大的性能问题之一。 幸运的是，在某些情况下可以避免这种情况。
在Where()之后使用Select()是一种非常常见的使用模式。 为了提高性能，Where() 返回的枚举具有 Select() 的重载，该重载返回一个采用谓词和选择器作为参数的枚举。 这相当于执行以下命令：
public static IEnumerable<TResult> WhereSelect<TSource, TResult>(
this IEnumerable<TSource> source,
Func<TSource, bool> predicate,
Func<TSource, TResult> selector)
{
foreach(var item in source)
{
if(predicate(item))
yield return selector(item);
}
}它在一个 foreach 循环中同时应用谓词和选择器。 这意味着减少了一层枚举器来“拉动”项目，从而获得更好的性能。
注意：查看我的另一篇文章“高效数据处理：利用 C# 的 foreach 循环”以了解 foreach 的工作原理。
如果您碰巧连续有两个Where() 或两个Select() 操作，也会发生同样的情况。 这相当于执行以下命令之一：
public static IEnumerable<TSource> Where<TSource>(
this IEnumerable<TSource> source,
Func<TSource, bool> predicate1,
Func<TSource, bool> predicate2)
=> source.Where(item => predicate1(item) && predicate2(item));
public static IEnumerable<TResult> Select<TSource, TMiddle, TResult>(
this IEnumerable<TSource> source,
Func<TSource, TMiddle> selector1,
Func<TMiddle, TResult> selector2)
=> source.Select(item => selector2(selector1(item)));所有这些枚举器优化都是隐式发生的。 您无需更改代码中的任何内容即可使它们发生。
显式枚举器崩溃
在某些情况下，您必须显式使用某个重载，以便折叠枚举器。 First()、FirstOrDefault()、Single()、SingleOrDefault()、Last()、LastOrDefault()、Any() 和 Count() 等操作就是这种情况。 所有这些操作都有一个以谓词作为参数的重载。 它与使用相同谓词在无参数扩展之前使用Where() 具有完全相同的结果。 这意味着， source.Where(predicate).Count() 的结果与 source.Count(predicate) 相同，但第二个可能具有更好的性能。
以下是 Count() 操作的可能实现（无需其他优化）：
public static int Count<TSource>(
this IEnumerable<TSource> source
{
var count = 0;
using(var enumerator = source.GetEnumerator())
{
checked
{
while(enumerator.MoveNext())
count++;
}
}
return count;
}
public static int Count<TSource>(
this IEnumerable<TSource> source,
Func<TSource, bool> predicate)
{
var count = 0;
foreach(var item in source)
{
checked
{
if(predicate(item))
count++;
}
}
return count;
})第二个重载使用一个 foreach 来进行过滤和求和。 这可以避免使用枚举器来执行谓词。
请注意，隐式折叠对于这些重载不起作用。
源类型
所有 LINQ 方法都是 IEnumerable<T> 的扩展方法。 正如我在之前的几篇文章中已经解释过的，就遍历集合时的性能而言，IEnumerable<T> 是最糟糕的情况。 有多种集合类型可以提供更好的性能。
LINQ 库假定源集合可能已转换为不同的类型。 例如，List<T> 可以转换为 IEnumerable<T>。 例如，通过这样做，就不可能显式调用 Count 属性来查找它包含的项目数。
例如，要查找集合是否为空，我们应该使用 Any() 操作。 没有优化的情况下，其实现如下：
public static bool Any<TSource>(this IEnumerable<TSource> source)
{
using(var enumerator = source.GetEnumerator())
{
return enumerator.MoveNext();
}
}它必须创建枚举器的实例，然后调用 MoveNext() 方法。 如果该方法返回 true，则意味着它至少包含一项。
许多集合（例如 List<T>）在内部存储项目数。 对于数组和跨度，通常可以使用 Length 属性来检索，或者在其他情况下使用 Count 属性来检索。 这些集合通常实现提供 Count 属性的接口 IReadOnlyCollection<T> 和 ICollection<T>。 调用这些属性应该比使用枚举器更快。
注意：没有任何 LINQ 操作检查 IReadOnlyCollection<T> 和 IReadOnlyList<T> 类型。 正如我在之前的文章中所解释的，实现这些接口的集合还必须分别实现 ICollection<T> 和 IList<T>，以便 LINQ 可以优化它们的遍历。
如果检查 Any() 的实现，您会发现它调用内部方法 TryGetNonEnumeratedCount() 来查找集合是否提供 Count 属性。 然后，此方法检查源集合是否为 null，以及它是否实现 ICollection()、IIListProvider<T> 或 ICollection。 如果该方法返回 true，则 Any() 使用 Count 属性，否则使用枚举器。 这一切都是在运行时完成的，消耗CPU时间。
注意：Iterator<T>、IIListProvider<T> 和 IPartition<T> 是内部接口，只有内部枚举可以实现，因此只有这些可以利用这些优化。
此初始化时间在 Any() 等操作中或当集合中的项目很少时最为明显。 对于包含大量项目的集合，这种初始化时间是非常值得的，因为在每个项目上节省少量时间将为完全遍历集合节省大量时间。
这些优化带来了很多问题。 首先，并非所有方法都具有这些优化，并且具有这些优化的方法不一致且没有记录。 您必须检查每个操作及其组合的源代码。
值类型枚举器
对于源是 List<T> 的情况，Where() 使用自定义WhereListIterator<T>。 这个“迭代器”保证 List<T> 提供的值类型枚举器不被装箱。
注意：查看我的另一篇文章“C# 中值类型与引用类型枚举器的性能”，了解为什么值类型枚举器很重要。
另一方面，.NET 提供的所有集合确实都有值类型枚举器，但 LINQ 不会优化它们，因为此解决方案不是通用的，它仅适用于 List<T>。
此外，LINQ 不提供任何值类型枚举器，因为所有返回可枚举值的操作都返回 IEnumerable<T>，而不是显式枚举器类型。
通用数学
在 .NET 中实现数学运算一直是一个挑战，因为数学运算符无法在接口中定义。 这导致 LINQ 必须为 .NET 提供的每种数字类型提供 Sum() 和 Average() 的特定实现。
不幸的是，.NET 8 微弱地尝试使用这个新功能。 它仅在内部使用它，并且仍然提供数字类型的所有重载。 这意味着第三方数字类型仍然无法有效地使用 Sum() 和 Average() 方法。
注意：查看我的另一篇文章“.NET 中的通用数学”，了解如何针对您自己的数字类型进行优化。
SIMD
.NET 8 中的 LINQ 最终使用了 SIMD。 不幸的是，它的使用场景非常有限：
Sum() 但仅当项目类型为 int 或 long 时。
Average() 但仅当项目类型为 int 时。
不幸的是，只有这些场景才能保证处理 NaN 和 Infinite 时的向后兼容性。
注意：查看我的另一篇文章“.NET 中的单指令、多数据 (SIMD)”，了解什么是 SIMD 以及如何在自己的代码中使用它。
结论
IEnumerable<T> 提供的抽象使 LINQ 成为一个出色的库，以便可以轻松实现和维护数据处理。 同时，它也是 .NET 应用程序性能不足的最大原因。
.NET 性能的提高主要归功于 JIT 编译器的改进。 该框架还通过新的 API 进行了改进。 然而，这些不能用于保持 LINQ 100% 向后兼容。 很多内部优化与最新进展不一致。
