Skip to content

Conversation

@stephentoub
Copy link
Member

@stephentoub stephentoub commented Mar 6, 2024

Use a custom enumerator for Grouping.GetEnumerator. Today it's just implemented with an iterator, but while simple:

  • The resulting class is generic on TKey even thought it doesn't need to be (possibly resulting in extra generic instantiations).
  • The generated type is larger than it needs to be, with a field for _current, even though at this point the array is observably immutable and we don't need separate storage for the current item.
  • There's more overhead in MoveNext than is necessary, because we only need to track the current index and not also a separate state.
Method Toolchain ItemsPerGroup Mean Ratio Allocated Alloc Ratio
Sum \main\corerun.exe 1 167.5 ns 1.00 448 B 1.00
Sum \pr\corerun.exe 1 137.3 ns 0.82 368 B 0.82
Sum \main\corerun.exe 2 195.4 ns 1.00 448 B 1.00
Sum \pr\corerun.exe 2 155.0 ns 0.79 368 B 0.82
Sum \main\corerun.exe 3 225.3 ns 1.00 448 B 1.00
Sum \pr\corerun.exe 3 171.9 ns 0.76 368 B 0.82
Sum \main\corerun.exe 4 260.1 ns 1.00 448 B 1.00
Sum \pr\corerun.exe 4 190.7 ns 0.73 368 B 0.82
Sum \main\corerun.exe 5 291.3 ns 1.00 448 B 1.00
Sum \pr\corerun.exe 5 208.2 ns 0.71 368 B 0.82
Sum \main\corerun.exe 6 331.1 ns 1.00 448 B 1.00
Sum \pr\corerun.exe 6 225.6 ns 0.68 368 B 0.82
Sum \main\corerun.exe 7 367.2 ns 1.00 448 B 1.00
Sum \pr\corerun.exe 7 246.7 ns 0.67 368 B 0.82
Sum \main\corerun.exe 8 388.1 ns 1.00 448 B 1.00
Sum \pr\corerun.exe 8 265.5 ns 0.68 368 B 0.82
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[MemoryDiagnoser(false)]
[HideColumns("Job", "Error", "StdDev", "Median", "RatioSD")]
public class Tests
{
    private ILookup<int, string> _stringsByLength;

    [Params(1, 2, 3, 4, 5, 6, 7, 8)]
    public int ItemsPerGroup { get; set; }

    [GlobalSetup]
    public void Setup()
    {
        const int NumGroups = 10;

        var list = new List<string>();
        for (int i = 0; i < NumGroups; i++)
        {
            for (int item = 0; item < ItemsPerGroup; item++)
            {
                list.Add(new string((char)('a' + item), i + 1));
            }
        }

        _stringsByLength = list.ToLookup(s => s.Length);
    }

    [Benchmark]
    public int Sum()
    {
        int sum = 0;
        foreach (IGrouping<int, string> group in _stringsByLength)
        {
            foreach (string item in group)
            {
                sum += item.Length;
            }
        }
        return sum;
    }
}

Use a custom enumerator for Grouping.GetEnumerator. Today it's just implemented with an iterator, but while simple:
- The resulting class is generic on TKey even thought it doesn't need to be (possibly resulting in extra generic instantiations), and the implementation.
- The generated type is larger than it needs to be, with a field for _current, even though at this point the array is observably immutable and we don't need separate storage for the current item.
- There's more overhead in MoveNext than is necessary, because we only need to track the current index and not also a separate state.
@ghost
Copy link

ghost commented Mar 6, 2024

Tagging subscribers to this area: @dotnet/area-system-linq
See info in area-owners.md if you want to be subscribed.

Issue Details

Use a custom enumerator for Grouping.GetEnumerator. Today it's just implemented with an iterator, but while simple:

  • The resulting class is generic on TKey even thought it doesn't need to be (possibly resulting in extra generic instantiations), and the implementation.
  • The generated type is larger than it needs to be, with a field for _current, even though at this point the array is observably immutable and we don't need separate storage for the current item.
  • There's more overhead in MoveNext than is necessary, because we only need to track the current index and not also a separate state.
Method Toolchain ItemsPerGroup Mean Ratio Allocated Alloc Ratio
Sum \main\corerun.exe 1 167.5 ns 1.00 448 B 1.00
Sum \pr\corerun.exe 1 137.3 ns 0.82 368 B 0.82
Sum \main\corerun.exe 2 195.4 ns 1.00 448 B 1.00
Sum \pr\corerun.exe 2 155.0 ns 0.79 368 B 0.82
Sum \main\corerun.exe 3 225.3 ns 1.00 448 B 1.00
Sum \pr\corerun.exe 3 171.9 ns 0.76 368 B 0.82
Sum \main\corerun.exe 4 260.1 ns 1.00 448 B 1.00
Sum \pr\corerun.exe 4 190.7 ns 0.73 368 B 0.82
Sum \main\corerun.exe 5 291.3 ns 1.00 448 B 1.00
Sum \pr\corerun.exe 5 208.2 ns 0.71 368 B 0.82
Sum \main\corerun.exe 6 331.1 ns 1.00 448 B 1.00
Sum \pr\corerun.exe 6 225.6 ns 0.68 368 B 0.82
Sum \main\corerun.exe 7 367.2 ns 1.00 448 B 1.00
Sum \pr\corerun.exe 7 246.7 ns 0.67 368 B 0.82
Sum \main\corerun.exe 8 388.1 ns 1.00 448 B 1.00
Sum \pr\corerun.exe 8 265.5 ns 0.68 368 B 0.82
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);

[MemoryDiagnoser(false)]
[HideColumns("Job", "Error", "StdDev", "Median", "RatioSD")]
public class Tests
{
    private ILookup<int, string> _stringsByLength;

    [Params(1, 2, 3, 4, 5, 6, 7, 8)]
    public int ItemsPerGroup { get; set; }

    [GlobalSetup]
    public void Setup()
    {
        const int NumGroups = 10;

        var list = new List<string>();
        for (int i = 0; i < NumGroups; i++)
        {
            for (int item = 0; item < ItemsPerGroup; item++)
            {
                list.Add(new string((char)('a' + item), i + 1));
            }
        }

        _stringsByLength = list.ToLookup(s => s.Length);
    }

    [Benchmark]
    public int Sum()
    {
        int sum = 0;
        foreach (IGrouping<int, string> group in _stringsByLength)
        {
            foreach (string item in group)
            {
                sum += item.Length;
            }
        }
        return sum;
    }
}
Author: stephentoub
Assignees: -
Labels:

area-System.Linq, tenet-performance

Milestone: -

@ghost ghost assigned stephentoub Mar 6, 2024
@stephentoub stephentoub merged commit 3c17fe0 into dotnet:main Mar 8, 2024
@stephentoub stephentoub deleted the groupingenumerator branch March 8, 2024 13:40
@github-actions github-actions bot locked and limited conversation to collaborators Apr 9, 2024
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.

Labels

area-System.Linq tenet-performance Performance related issue

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants