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 combine Where and Select to be more efficient.
Our brewing machine
To carry implementation of our brewing machine, We have to use code from previous part. Do you remember array-specific implementations of enumerators?
Right now, our StructEnumerator<T> supports an arrays only, with ArrayStructEnumerator<T> implementation.
First, let’s focus on fields of our enumerator:
internal readonly T[] Array;
internal int Index;
internal readonly int Count;
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..
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 forward into implementation:
//generic
public ref struct InternalWhereSelect<TEnumerator, TIn, TOut> : IStructEnumerator<TOut>
where TEnumerator : struct, IStructEnumerator<TIn>, allows ref struct
{
private TEnumerator _source;
private readonly Func<TIn, TOut> _selector;
private readonly Func<TOut, bool> _filter;
public InternalWhereSelect(TEnumerator source, Func<TIn, TOut> selector, Func<TOut, bool> filter)
{
_source = source;
_selector = selector;
_filter = filter;
}
public void Dispose()
{
_source.Dispose();
}
Next, our InternalWhereSelect 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 single 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 (_source.Next(ref source))
{
TOut selected = _selector(source);
if (_filter(selected))
{
current = selected;
return true;
}
}
return false;
}
GetCountToLeftEnumerate, GetUnderlying and TryCopy will not return any results this time.
public bool GetCountToLeftEnumerate(out int count)
{
Unsafe.SkipInit(out count);
return false;
}
public bool GetUnderlying(ref ReadOnlySpan<TOut> span)
{
return false;
}
public bool TryCopy(ref Span<TOut> destination, int offset)
{
return false;
}
Our whole struct should look like this:
//generic
public ref struct InternalWhereSelect<TEnumerator, TIn, TOut> : IStructEnumerator<TOut>
where TEnumerator : struct, IStructEnumerator<TIn>, allows ref struct
{
private TEnumerator _source;
private readonly Func<TIn, TOut> _selector;
private readonly Func<TOut, bool> _filter;
public InternalWhereSelect(TEnumerator source, Func<TIn, TOut> selector, Func<TOut, bool> filter)
{
_source = source;
_selector = selector;
_filter = filter;
}
public void Dispose()
{
_source.Dispose();
}
public bool Next(ref TOut current)
{
TIn source = default(TIn);
while (_source.Next(ref source))
{
TOut selected = _selector(source);
if (_filter(selected))
{
current = selected;
return true;
}
}
return false;
}
public bool GetCountToLeftEnumerate(out int count)
{
Unsafe.SkipInit(out count);
return false;
}
public bool GetUnderlying(ref ReadOnlySpan<TOut> span)
{
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 path.
public static class WhereStruct
{
public static StructEnumerable<InternalWhereArray<T>, T> StructWhere<T>(
this T[] array,
Func<T, bool> filter)
{
return new(new InternalWhereArray<T>(new ArrayStructEnumerator<T>(array), filter));
}
public static StructEnumerable<InternalWhere<TEnumerator, T>, T> StructWhere<TEnumerator, T>(
this StructEnumerable<TEnumerator, T> source,
Func<T, bool> filter) where TEnumerator : struct, IStructEnumerator<T>, allows ref struct
{
return new(new InternalWhere<TEnumerator, T>(source.Enumerator, filter));
}
public static StructEnumerable<InternalWhereSelect<TEnumerator, TIn, TOut>, TOut> StructWhere<
TEnumerator, TIn, TOut>(
this StructEnumerable<InternalSelect<TEnumerator, TIn, TOut>, TOut> source,
Func<TOut, bool> filter)
where TEnumerator : struct, IStructEnumerator<TIn>, allows ref struct
{
return new(new InternalWhereSelect<TEnumerator, TIn, TOut>(source.Enumerator._source, source.Enumerator.Selector, filter));
}
}
And extension method to get an result array
public static TOut[] ToArray<TEnumerator, TIn, TOut>(
this StructEnumerable<InternalWhereSelect<TEnumerator, TIn, TOut>, TOut> enumerable)
where TEnumerator : struct, IStructEnumerator<TIn>, allows ref struct
{
return enumerable.Enumerator.FromArrayBuilder<InternalWhereSelect<TEnumerator, TIn, TOut>, TOut>();
}
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 |