High performance LINQ implementation with minimal heap allocations. Supports enumerables, async enumerables, arrays and Span
NetFabric.Hyperlinq
contains alternative implementations of many operations found in the System.Linq
namespace:
Span<>
, ReadOnlySpan<>
, Memory<>
and ReadOnlyMemory<>
.This implementation favors performance in detriment of assembly binary size (lots of overloads).
NetFabric.Hyperlinq
can enumerate faster the results of a query than System.Linq
by performing all of the following:
Current
property and the MoveNext()
method are non-virtual.GetEnumerator()
or GetAsyncEnumerator()
does not implement IDisposable
. This allows the foreach
that enumerates the result to be inlinable.ArraySegment<>
, Span<>
, ReadOnlySpan<>
, Memory<>
, ReadOnlyMemory<>
, or implements IReadOnlyList<>
.Range()
and Repeat()
return enumerables that implement IReadOnlyCollection<>
and ICollection<>
. Return()
and Select()
return enumerables that implement IReadOnlyList<>
and IList<>
.Distinct()
, ToArray()
and ToList()
.Sum()
and SelectVector()
.Where().Count()
.EqualityComparer<>.Default
devirtualization whenever possible.The performance is equivalent when the enumerator is a reference-type. This happens when the enumerable is generated using yield
or when it's cast to one of the BCL enumerable interfaces (IEnumerable
, IEnumerable<>
, IReadOnlyCollection<>
, ICollection<>
, IReadOnlyList<>
, IList<>
, or IAsyncEnumerable<>
). In the case of operation composition, this only affects the first operation. The subsequent operations will have value-type enumerators.
NetFabric.Hyperlinq
allocates as much as possible on the stack. Enumerables and enumerators are defined as value-types. Generics constraints are used for the operation parameters so that the value-types are not boxed.
It only allocates on the heap for the following cases:
ICollection<>.CopyTo()
, ICollection<>.Contains()
, or IList<>.IndexOf()
will box enumerables that are value-types.ToArray()
and ToList()
allocate their results on the heap. You can use the ToArray()
overload that take an buffer pool as parameter so that its result is not managed by the garbage collector.The results of the benchmarks comparing multiple LINQ libraries can be found in the LinqBenchmarks repository.
The results of the benchmarks included in this repository can be found in the Benchmarks folder.
The names of the benchmarks are structured as follow:
System.Linq
namespace (includes System.Linq.Async, System.Interactive, and System.Interactive.Async)Span<>
Memory<>
IEnumerable<>
IReadOnlyCollection<>
and ICollection<>
IReadOnlyList<>
and IList<>
but is not an arrayIAsyncEnumerable<>
for
loop is used to call the indexerforeach
loop is used to call the enumeratorNetFabric.Hyperlinq
NuGet package to your project.NetFabric.Hyperlinq.Analyzer
NuGet package to your project. It's a Roslyn analyzer that suggests performance improvements on your enumeration source code. No dependencies are added to your assemblies.using NetFabric.Hyperlinq
directive to all source code files where you want to use NetFabric.Hyperlinq
. It can coexist with System.Linq
and System.Linq.Async
directives:using System;
using System.Linq;
using NetFabric.Hyperlinq; // add this directive
AsValueEnumerable()
to make any collection usable with NetFabric.Hyperlinq
. This includes arrays, Memory<>
, ReadOnlyMemory<>
, Span<>
, ReadOnlySpan<>
, BCL collections, and any other implementation of IEnumerable<>
. Use AsAsyncValueEnumerable()
for any implementation of IAsyncEnumerable<>
.public static void Example(IReadOnlyList<int> list)
{
var result = list
.AsValueEnumerable()
.Where(item => item > 2)
.Select(item => item * 2);
foreach(var value in result)
Console.WriteLine(value);
}
Netfabric.Hyperlinq
contains special versions of AsValueEnumerable()
for better performance with all collections in the System.Collections.Immutable
namespace. Projects targetting .NET Framework, netcoreapp2.1
or netstandard2.0
, require the addition of the NetFabric.Hyperlinq.Immutable
NuGet package dependency.
Most enumerables returned by NetFabric.Hyperlinq
are compatible with System.Linq
. The exception is enumerables for Span<>
or ReadOnlySpan<>
.
This allows the use of System.Linq
operators on NetFabric.Hyperlinq
enumerables. OrderByDescending()
is not yet available in Netfabric.Hyperlinq
but can still be used without requiring any conversion:
public static void Example(IReadOnlyList<int> list)
{
var result = list
.AsValueEnumerable()
.Where(item => item > 2)
.OrderByDescending(item => item) // is not yet available in Netfabric.Hyperlinq
.AsValueEnumerable()
.Select(item => item * 2);
foreach(var value in result)
Console.WriteLine(value);
}
To add NetFabric.Hyperlinq
operations after a System.Linq
operation, simply add one more AsValueEnumerable()
or AsAsyncValueEnumerable()
.
Calling a lambda expression for each item of the collection is very expensive. NetFabric.Hyperlinq
supports an alternative that is not as practical but that has much better performance.
struct
that implements IFunction<>
. Here's two examples of how to implement:readonly struct MultiplyBy2
: IFunction<int, int>
{
public int Invoke(int element)
=> element * 2;
}
readonly struct LessThan
: IFunction<int, bool>
{
readonly int value;
public LessThan(int value)
=> this.value = value;
public bool Invoke(int element)
=> element < value;
}
public static void Example(IReadOnlyList<int> list)
{
var result = list
.AsValueEnumerable()
.Where(new LessThan(10))
.Select<int, MultiplyBy2>();
foreach(var value in result)
Console.WriteLine(value);
}
The instances are allocated on the stack and the methods calls are non-virtual.
In NetFabric.Hyperlinq
, the generation operations like Empty()
, Range()
, Repeat()
and Return()
are static methods implemented in the static class ValueEnumerable
. To use them, instead of the System.Linq
equivalents, simply use ValueEnumerable
instead of Enumerable
.
public static void Example(int count)
{
var source = ValueEnumerable
.Range(0, count)
.Select(item => item * 2);
foreach(var value in source)
Console.WriteLine(value);
}
NetFabric.Hyperlinq
operations can be composed just like with System.Linq
. The difference is on how each one optimizes the internals to reduce the number of enumerators required to iterate the values.
Both System.Linq
and NetFabric.Hyperlinq
optimize the code in the following example so that only one enumerator is used to perform both the Where()
and the Select()
:
var result = source.AsValueEnumerable()
.Where(item => item > 2)
.Select(item => item * 2);
NetFabric.Hyperlinq
includes many more composition optimizations. In the following code, only one enumerator is used:
var result = array.AsValueEnumerable()
.Skip(1)
.Take(10)
.Where(item => item > 2)
.Select(item => item * 2)
.First();
In System.Linq
, the aggregation operations like First()
, Single()
and ElementAt()
, throw an exception when the source has no items. Often, empty collections are a valid scenario and exception handling is very slow. System.Linq
has alternative methods like FirstOrDefault()
, SingleOrDefault()
and ElementAtOrDefault()
, that return the default
value instead of throwing. This is still an issue when the items are of a value-type, where there's no way to distinguish between an empty collection and a valid item.
In NetFabric.Hyperlinq
, aggregation operations return an Option<>
type. This is similar in behavior to the Nullable<>
but it can contain reference types.
Here's a small example using First()
:
var result = source.AsValueEnumerable().First();
if (result.IsSome)
Console.WriteLine(result.Value);
It also provides a deconstructor so, you can convert it to a tuple:
var (isSome, value) = source.AsValueEnumerable().First();
if (isSome)
Console.WriteLine(value);
If you prefer a more functional approach, you can use Match()
to specify the value returned when the collection has values and when it's empty. Here's how to use it to define the previous behavior of First()
and FirstOrDefault()
:
var first = source.AsValueEnumerable()
.First()
.Match(
item => item,
() => throw new InvalidOperationException("Sequence contains no elements"));
var firstOrDefault = source.AsValueEnumerable()
.First()
.Match(
item => item,
() => default);
Console.WriteLine(first);
Console.WriteLine(firstOrDefault);
Match()
can also be used to define actions:
source.AsValueEnumerable()
.First()
.Match(
item => Console.WriteLine(item),
() => { });
The NetFabric.Hyperlinq
operations can be applied to Option<>
, including Where()
, Select()
and SelectMany()
. These return another Option<>
with the predicate/selector applied to the value, if it exists.
source.AsValueEnumerable()
.First()
.Where(item => item > 2)
.Match(
item => Console.WriteLine(item),
() => { });
Buffer pools allow the use of heap memory without adding pressure to the garbage collector. It pre-allocates a chunk of memory and "rents" it as required. The garbage collector will add this memory to the Large Object Heap (LOH).
ToArray()
is frequently used to cache values for a brief period and the use of buffer pools may be useful.
Netfabric.Hyperlinq
adds an overload that takes a ArrayPool<>
as a parameter:
void Method()
{
using var buffer = source.AsValueEnumerable()
.ToArray(ArrayPool<int>.Shared);
var memory = buffer.Memory;
// use memory here
}
It returns an instance of a IMemoryOwner<>
. The using
statement guarantees that it is disposed and the buffer automatically returned to the pool.
NetFabric.Hyperlinq
uses SIMD implicitly to improve performance of some operations. Many times this can only be done explicitly because it can only be used on a limited number of types and operations on them.
In NetFabric.Hyperlinq
, alternative methods that use SIMD, have the word Vector
at the end of its name. You'll also find that the operations that require an expression, now require two.
var result = list
.AsValueEnumerable()
.SelectVector(item = item * 2, item = item * 2)
.ToArray();
SIMD improves performance by performing the same operations simultaneously on multiple items. The operation can only be performed if this number is met. This means that the remaining number of items has to be processed without SIMD. The first expression is applied on a System.Numerics.Vector<>
, while the second one is applied on an item.
These methods also support the use of value delegates. In this case, the struct
containing the expressions must implement two IFunction<,>
:
readonly struct MultiplyBy2
: IFunction<Vector<int>, Vector<int>>
, IFunction<int, int>
{
public Vector<int> Invoke(Vector<int> element)
=> element * 2;
public int Invoke(int element)
=> element * 2;
}
public static void Example(List<int> list)
{
var result = list
.AsValueEnumerable()
.SelectVector<int, MultiplyBy2>()
.ToArray();
foreach(var value in result)
Console.WriteLine(value);
}
Please note that the operation SelectVector()
does not return an enumerable. It returns the context required for subsequent operations like ToArray()
, ToList()
, and Sum()
.
Up until now I haven't found a way to improve the performance of Select()
by using SIMD. The returned context allows the use of composition, exposing only the operations that can gain with the use of SIMD.
Articles explaining implementation:
Count()
Sum()
AsEnumerable()
AsValueEnumerable()
ToArray()
ToList()
ToDictionary(Func<TSource, TKey>)
ToDictionary(Func<TSource, TKey>, IEqualityComparer<TKey>)
ToDictionary(Func<TSource, TKey>, Func<TSource, TElement>)
ToDictionary(Func<TSource, TKey>, Func<TSource, TElement>, IEqualityComparer<TKey>)
ElementAt()
First()
Single()
Where(Func<TSource, bool>)
Where(Func<TSource, int, bool>)
Create(Func<TEnumerator>)
Empty()
Range(int, int)
Repeat(TSource, int)
Return(TSource)
Select(Func<TSource, TResult>)
Select(Func<TSource, int, TResult>)
SelectMany(IValueEnumerable<TSource>)
Take(int)
Skip(int)
All(Func<TSource, bool>)
All(Func<TSource, int, bool>)
Any()
Any(Func<TSource, bool>)
Any(Func<TSource, int, bool>)
Contains(TSource)
Contains(TSource, IEqualityComparer<TSource>)
Distinct(TSource)
Distinct(TSource, IEqualityComparer<TSource>)
The following open-source projects are used to build and test this project:
This project is licensed under the MIT license. See the LICENSE file for more info.