Lost in Linq source code - Part 2
Coffee brewing
In a part 1 We focused on basics and implemented Select and Where enumerators with extensions methods. This approach allowed us to filter and manipulate type of elements in arrays, but when We look into Linq source code, there are classes like ArrayWhereIterator<TSource>, ListWhereIterator<TSource> and IEnumerableWhereIterator<TSource>. Each of them works as a road where a Where<TSource> method works like a grade-sepearted junction. Previously We used public static T[] ToArray<TEnumerator, T>(this InternalWhere<TEnumerator, T> enumerator) and private static InternalWhere<TEnumerable, TIn> StructWhere<TIn, TEnumerable>(this TEnumerable source, Func<TIn, bool> filter), where We partially utilize this approach, as We support arrays only right now.
But We should notice anothe thing in our implementation. Let’s imagine We want to make a coffee (output). To do this We need water, and a grinded coffee (our input).
Here we Can take two approaches:
- Boil water and filter it out through coffee to make solution (e.g coffee dripper, french press), or
- Prepare grinded coffee and water in one machine or tool without separating (e.g moka pot, espresso machine)
Note to coffee purists, I know about the fact that moka pots, coffe machines (and so on) processes, can be separated to different stages.
During first approach out water after boiling (Enumerator<T>) is poured through coffee grounds (Select), but also we have to filter it out (Where), until we receive our coffee.
In a second approach We’re boiling water and filtering nearly at the same time. It means We pour room’s temperature water and during boiling stage is being filtered through coffee grounds.
You should know what does it mean right now - We want to combineWhereandSelectto be more efficient.
Our brewing machine
To implement our brewing machine IStructEnumerator We have to do modifications to our previous code. I mean, to make a array-specific implementations of enumerators, precisely.
Right now, our StructEnumerator<T> supports an arrays only, but name suggest more generic implementation. So, let’s change it into ArrayStructEnumerator<T>.
Next, We need to write a Where-like structs for arrays exclusively.
First, let’s focus on Where:
public struct InternalWhereArray<TIn> : IStructEnumerator<TIn>
{
internal ArrayStructEnumerator<TIn> _source;
internal readonly Func<TIn, bool> _filter;
public InternalWhereArray(ArrayStructEnumerator<TIn> source, Func<TIn, bool> filter)
{
_source = source;
_filter = filter;
}
public void Dispose()
{
_source.Dispose();
}
public bool Next(ref TIn current)
{
TIn? fromSource = default(TIn);
while(_source.Next(ref fromSource))
{
if (_filter(fromSource))
{
current = fromSource;
return true;
}
}
return false;
}
public bool GetCountToLeftEnumerate(out int count)
{
bool val = _source.GetCountToLeftEnumerate(out int enumeratorCount);
count = enumeratorCount;
return val;
}
public bool GetUnderlying(ref ReadOnlySpan<TIn> span)
{
span = default;
return false;
}
public bool TryCopy(ref Span<TIn> destination, int offset) => false;
}
The major difference between our generic implementation lies here:
public struct InternalWhereArray<TIn> : IStructEnumerator<TIn>
{
internal ArrayStructEnumerator<TIn> _source;
internal readonly Func<TIn, bool> _filter;
public InternalWhereArray(ArrayStructEnumerator<TIn> source, Func<TIn, bool> filter)
{
_source = source;
_filter = filter;
}
The reason behind internal is to access them within same assembly to create another struct with Where and Select combined. On the other hand, constructor accepts only concrete implementation of ArrayStructEnumerator, extending this path for arrays exclusively. The rest is left intact, as in generic InternalWhere.
If We want to create a struct combining projection and filtering, We should iterate directly on an array skipping creation of unnecessary enumerators. I’ve observed this shortcut here, when I was browsing ZLinq..
But to make it true, we have to come back to ArrayStructEnumerator<T> and expose an array for internal access.
public struct ArrayStructEnumerator<T> : IStructEnumerator<T>
{
internal readonly T[] _array;
private int _index;
private readonly int _count;
public ArrayStructEnumerator(T[] array)
{
_array = array ?? throw new ArgumentNullException(nameof(array));
_count = array.Length;
_index = -1;
}
Now We can make solid assumptions here:
- Our shortcut must iterate on array directly
- Must create a new instance of objects
- Must filter original data
- Must accept two
Func- one for filtering, second for projection
It’s time to move foward into implementation:
public struct InternalWhereSelectArray<TIn, TOut> : IStructEnumerator<TOut>
{
private readonly TIn[] _source;
private int _index;
private readonly int _count;
private readonly Func<TIn, bool> _filter;
private readonly Func<TIn, TOut> _selector;
public InternalWhereSelectArray(TIn[] source, Func<TIn, bool> filter, Func<TIn, TOut> selector)
{
_source = source;
_filter = filter;
_selector = selector;
_index = -1;
_count = source.Length;
}
Next, our InternalWhereSelectArray should do filter and projection in the same method. During enumeration when We move to next element We don’t want to transform object and then filter it.
That’s because We must perform transformation on every sigle element, rather than this - filter and then transform.
It is going to skip some elements without performing transformations on all of them.
public bool Next(ref TOut current)
{
TIn source = default(TIn);
while(_index < _count - 1)
{
_index++;
source = _source[_index];
if (_filter(source))
{
current = _selector(source);
return true;
}
}
return false;
}
Dispose and GetCountToLeftEnumerate will look exactly the same as a ArrayStructSelector<T>, because our struct fulfills an exact functionality here.
public bool GetCountToLeftEnumerate(out int count)
{
if (_index < 0)
{
count = _count;
return true;
}
if(_index >= _count)
{
count = 0;
return false;
}
count = _count - _index - 1;
return true;
}
public void Dispose()
{
_index = -1;
}
Remains can be implemented, but It’s unnecessary, unless requirement occur.
public bool GetUnderlying(ref ReadOnlySpan<TOut> span)
{
span = default;
return false;
}
public bool TryCopy(ref Span<TOut> destination, int offset)
{
return false;
}
Our whole struct should look like this:
public struct InternalWhereSelectArray<TIn, TOut> : IStructEnumerator<TOut>
{
private readonly TIn[] _source;
private int _index;
private readonly int _count;
private readonly Func<TIn, bool> _filter;
private readonly Func<TIn, TOut> _selector;
public InternalWhereSelectArray(TIn[] source, Func<TIn, bool> filter, Func<TIn, TOut> selector)
{
_source = source;
_filter = filter;
_selector = selector;
_index = -1;
_count = source.Length;
}
public void Dispose()
{
_index = -1;
}
public bool Next(ref TOut current)
{
TIn source = default(TIn);
while(_index < _count - 1)
{
_index++;
source = _source[_index];
if (_filter(source))
{
current = _selector(source);
return true;
}
}
return false;
}
public bool GetCountToLeftEnumerate(out int count)
{
if (_index < 0)
{
count = _count;
return true;
}
if(_index >= _count)
{
count = 0;
return false;
}
count = _count - _index - 1;
return true;
}
public bool GetUnderlying(ref ReadOnlySpan<TOut> span)
{
span = default;
return false;
}
public bool TryCopy(ref Span<TOut> destination, int offset)
{
return false;
}
}
And generic version should look equivalent to concrete one, but without an array:
public struct InternalWhereSelect<TEnumerator, TIn, TOut> : IStructEnumerator<TOut>
where TEnumerator : IStructEnumerator<TIn>
{
internal TEnumerator _source;
internal readonly Func<TIn, bool> _filter;
internal readonly Func<TIn, TOut> _selector;
public InternalWhereSelect(ref TEnumerator source, Func<TIn, bool> filter, Func<TIn, TOut> selector)
{
_source = source;
_filter = filter;
_selector = selector;
}
public void Dispose()
{
_source.Dispose();
}
public bool Next(ref TOut current)
{
TIn source = default(TIn);
while(_source.Next(ref source))
{
if (_filter(source))
{
current = _selector(source);
return true;
}
}
return false;
}
public bool GetCountToLeftEnumerate(out int count)
{
bool val = _source.GetCountToLeftEnumerate(out int enumeratorCount);
count = enumeratorCount;
return val;
}
public bool GetUnderlying(ref ReadOnlySpan<TOut> span)
{
span = default;
return false;
}
public bool TryCopy(ref Span<TOut> destination, int offset)
{
return false;
}
}
Lastly, We should adjust and implement extension methods to match our shortcuts, and/or use our array-like path.
public static class WhereStruct
{
public static InternalWhereArray<TIn> StructWhere<TIn>(this TIn[] arr,
Func<TIn, bool> filter)
{
return new InternalWhereArray<TIn>(new ArrayStructEnumerator<TIn>(arr), filter);
}
public static InternalWhere<IStructEnumerator<TIn>, TIn> StructWhere<TIn>(this IStructEnumerator<TIn> source, Func<TIn, bool> filter)
{
return new InternalWhere<IStructEnumerator<TIn>, TIn>(source, filter);
}
}
public static class SelectStruct
{
public static IStructEnumerator<TOut> StructSelect<TIn, TOut>(this TIn[] array, Func<TIn, TOut> selector)
{
return new ArrayStructEnumerator<TIn>(array).InternalStructSelectArray(selector);
}
public static InternalWhereSelectArray<TIn, TOut> StructSelect<TIn, TOut>(
this InternalWhereArray<TIn> source, Func<TIn, TOut> selector) =>
new(source._source._array, source._filter, selector);
private static IStructEnumerator<TOut> InternalStructSelectArray<TEnumerator, TIn, TOut>(
this TEnumerator source, Func<TIn, TOut> selector)
where TEnumerator : IStructEnumerator<TIn> => new InternalSelect<TEnumerator, TIn, TOut>(source, selector);
}
And extension method to get an result array
public static TOut[] ToArray<TIn, TOut>(this InternalWhereSelectArray<TIn, TOut> enumerator)
{
TOut[] result = null;
var arr = new ArrayBuilder<TOut>();
TOut? current = default;
int idx = 0;
while (enumerator.Next(ref current))
{
arr.Add(current);
}
result = arr.ToArray();
arr.Clear();
return result;
}
Benchmarks
It’s time to compare our code with others
Benchmark class:
[MemoryDiagnoser]
[ThreadingDiagnoser]
public class SelectWhereVsWhereSelectBenchmark
{
public IEnumerable<Example[]> Data()
{
//yield return Generator.Generate(5_000);
//yield return Generator.Generate(10_000);
//yield return Generator.Generate(50_000);
yield return Generator.Generate(500_000);
}
[Benchmark]
[ArgumentsSource(nameof(Data))]
public void LinqSelectWhere(Example[] input) =>
input.Select(x => new NewExample()
{
HalvedInt = x.ExampleNumber / 2,
NewStringProp = x.ExampleString
})
.Where(x => x.NewStringProp[0] == 'c' || x.NewStringProp[1] == '2')
.ToArray()
.Consume(new Consumer());
[Benchmark]
[ArgumentsSource(nameof(Data))]
public void LinqWhereSelect(Example[] input) =>
input.Where(x => x.ExampleString[0] == 'c' || x.ExampleString[1] == '2')
.Select(x => new NewExample()
{
HalvedInt = x.ExampleNumber / 2,
NewStringProp = x.ExampleString
})
.ToArray()
.Consume(new Consumer());
[Benchmark]
[ArgumentsSource(nameof(Data))]
public void ParallelLinqSelectWhere(Example[] input) =>
input.AsParallel()
.Select(x => new NewExample()
{
HalvedInt = x.ExampleNumber / 2,
NewStringProp = x.ExampleString
})
.Where(x => x.NewStringProp[0] == 'c' || x.NewStringProp[1] == '2')
.ToArray().Consume(new Consumer());
[Benchmark]
[ArgumentsSource(nameof(Data))]
public void ParallelLinqWhereSelect(Example[] input) =>
input
.AsParallel()
.Where(x => x.ExampleString[0] == 'c' || x.ExampleString[1] == '2')
.Select(x => new NewExample()
{
HalvedInt = x.ExampleNumber / 2,
NewStringProp = x.ExampleString
})
.ToArray().Consume(new Consumer());
[Benchmark]
[ArgumentsSource(nameof(Data))]
public void NonAllocWhereSelect_WithoutShortcut(Example[] input)
{
new InternalSelect<InternalWhere<ArrayStructEnumerator<Example>, Example>, Example, NewExample>(
new InternalWhere<ArrayStructEnumerator<Example>, Example>(new ArrayStructEnumerator<Example>(input),
x => x.ExampleString[0] == 'c' || x.ExampleString[1] == '2'), x => new NewExample())
.ToArray()
.Consume(new Consumer());
}
[Benchmark]
[ArgumentsSource(nameof(Data))]
public void NonAllocSelectWhere(Example[] input)
{
input
.StructSelect(x => new NewExample()
{
HalvedInt = x.ExampleNumber / 2,
NewStringProp = x.ExampleString
})
.StructWhere(x => x.NewStringProp[0] == 'c' || x.NewStringProp[1] == '2')
.ToArray().Consume(new Consumer());
}
[Benchmark]
[ArgumentsSource(nameof(Data))]
public void NonAllocWhereSelect(Example[] input)
{
input.StructWhere(x => x.ExampleString[0] == 'c' || x.ExampleString[1] == '2')
.StructSelect(x => new NewExample()
{
HalvedInt = x.ExampleNumber / 2,
NewStringProp = x.ExampleString
})
.ToArray().Consume(new Consumer());
}
[Benchmark]
[ArgumentsSource(nameof(Data))]
public void ZLinqSelectWhere(Example[] input)
{
input.AsValueEnumerable()
.Select(x => new NewExample()
{
HalvedInt = x.ExampleNumber / 2,
NewStringProp = x.ExampleString
})
.Where(x => x.NewStringProp[0] == 'c' || x.NewStringProp[1] == '2')
.ToArray().Consume(new Consumer());
}
[Benchmark]
[ArgumentsSource(nameof(Data))]
public void ZLinqWhereSelect(Example[] input)
{
input.AsValueEnumerable()
.Where(x => x.ExampleString[0] == 'c' || x.ExampleString[1] == '2')
.Select(x => new NewExample()
{
HalvedInt = x.ExampleNumber / 2,
NewStringProp = x.ExampleString
}).ToArray().Consume(new Consumer());
}
}
Results
| Method | input | Mean | Error | StdDev | Gen0 | Completed Work Items | Lock Contentions | Gen1 | Gen2 | Allocated |
|------------------------------------ |---------------- |----------:|----------:|----------:|----------:|---------------------:|-----------------:|---------:|--------:|----------:|
| LinqSelectWhere | Example[500000] | 13.196 ms | 0.2588 ms | 0.3542 ms | 968.7500 | - | - | 312.5000 | 31.2500 | 15.72 MB |
| LinqWhereSelect | Example[500000] | 4.358 ms | 0.0543 ms | 0.0482 ms | 125.0000 | - | - | 117.1875 | 15.6250 | 2.31 MB |
| ParallelLinqSelectWhere | Example[500000] | 10.243 ms | 0.1123 ms | 0.1051 ms | 1062.5000 | 15.0000 | - | 453.1250 | 31.2500 | 16.74 MB |
| ParallelLinqWhereSelect | Example[500000] | 3.700 ms | 0.0397 ms | 0.0332 ms | 210.9375 | 15.0000 | - | 207.0313 | 27.3438 | 3.32 MB |
| NonAllocWhereSelect_WithoutShortcut | Example[500000] | 6.276 ms | 0.1193 ms | 0.1373 ms | 179.6875 | - | - | 171.8750 | 70.3125 | 5.66 MB |
| NonAllocSelectWhere | Example[500000] | 17.650 ms | 0.3435 ms | 0.3675 ms | 1000.0000 | - | - | 343.7500 | 62.5000 | 19.07 MB |
| NonAllocWhereSelect | Example[500000] | 4.650 ms | 0.0780 ms | 0.0692 ms | 125.0000 | - | - | 117.1875 | 15.6250 | 2.3 MB |
| ZLinqSelectWhere | Example[500000] | 15.374 ms | 0.2831 ms | 0.2648 ms | 968.7500 | - | - | 312.5000 | 31.2500 | 15.72 MB |
| ZLinqWhereSelect | Example[500000] | 4.512 ms | 0.0486 ms | 0.0431 ms | 125.0000 | - | - | 117.1875 | 15.6250 | 2.31 MB |