LINQ is powerful tool for collection (or enumeration) operating. You use functional-like syntax for filtering, grouping, transforming data. All LINQ methods work with common interface IEnumerable<T> and usually methods do not check real type of collection, or data type. Sometimes, if you know the type of collection or generic type, you can optimize code for better performance (like in Any vs Count).

This article will show, how you can speed up grouping by specific key - byte.

Let's look at LINQ GroupBy method implementation. It creates a Lookup - kind of hash-table with multiple values for one key. Like standard hash-table it operates with "buckets" (Lookup<TKey, TElement>.Grouping type). For every element from source collection it finds group by computing hash and comparing with key.

public class Lookup<TKey, TElement> : IEnumerable<IGrouping<TKey, TElement>>, IEnumerable, ILookup<TKey, TElement>
{
    private Lookup<TKey, TElement>.Grouping[] groupings;

    //...
    internal Lookup<TKey, TElement>.Grouping GetGrouping(TKey key, bool create)
    {   
        int hashCode = this.InternalGetHashCode(key);
        for (Lookup<TKey, TElement>.Grouping grouping = this.groupings[hashCode % this.groupings.Length]; grouping != null; grouping = grouping.hashNext)
        {
            if (grouping.hashCode == hashCode && this.comparer.Equals(grouping.key, key))
                return grouping;
        }
    
        //...        
    }
    //...        
}

Here is one possibility for optimization with type byte. byte has only 256 different values, so grouping by byte value gives us only 256 different keys. We can replace "buckets" with one array of 256 elements - one per possible value of byte type.

internal sealed class ByteLookup<TElement> : ILookup<byte, TElement>
{
    private readonly Grouping[] groupings = new Grouping[byte.MaxValue + 1];
    
    //...        
    
    private Grouping GetGrouping(byte key)
    {
        return groupings[key] ?? (groupings[key] = new Grouping(key));
    }
}

Source code.

This gives us the following benefits:

• Hash is equal to value - no collision
• Simple key comparison

Benchmark

Full listing of benchmark tests:

[GroupBenchmarksBy(BenchmarkLogicalGroupRule.ByCategory)]
public class GroupByByteBenchmark
{
    [Params(10, 100, 1000, 10000)]
    public int count;

    private byte[] randomData;
    private byte[] zeroData;

    [GlobalSetup]
    public void Setup()
    {
        randomData = new byte[count];
        zeroData = new byte[count];
        new Random(42).NextBytes(randomData);
    }

    [Benchmark(Baseline = true)]
    [BenchmarkCategory("Random")]
    public IEnumerator<IGrouping<byte, byte>> GroupBy()
    {
        return randomData.GroupBy(o => o).GetEnumerator();
    }


    [Benchmark]
    [BenchmarkCategory("Random")]
    public IEnumerator<IGrouping<byte, byte>> GroupByByte()
    {
        return randomData.GroupByByte(o => o).GetEnumerator();
    }

    [Benchmark(Baseline = true)]
    [BenchmarkCategory("Zero")]
    public IEnumerator<IGrouping<byte, byte>> ZeroGroupBy()
    {
        return zeroData.GroupBy(o => o).GetEnumerator();
    }

    [Benchmark]
    [BenchmarkCategory("Zero")]
    public IEnumerator<IGrouping<byte, byte>> ZeroGroupByByte()
    {
        return zeroData.GroupByByte(o => o).GetEnumerator();
    }
}

And results:

BenchmarkDotNet=v0.11.5, OS=Windows 10.0.18362
Intel Core i7-2670QM CPU 2.20GHz (Sandy Bridge), 1 CPU, 8 logical and 4 physical cores
.NET Core SDK=2.2.106
  [Host]     : .NET Core 2.2.4 (CoreCLR 4.6.27521.02, CoreFX 4.6.27521.01), 64bit RyuJIT
  DefaultJob : .NET Core 2.2.4 (CoreCLR 4.6.27521.02, CoreFX 4.6.27521.01), 64bit RyuJIT

For random data and array of zero values we get dome performance improvements up to 2 times. Also this optimization can be used for grouping by enum value with underlying byte type.

Links

• Performance LINQ
• BenchmarkDotNet