KEMBAR78
Use Iterator<T>.TryGetFirst in Enumerable.Any() by stephentoub · Pull Request #99218 · dotnet/runtime · GitHub
Skip to content

Conversation

@stephentoub
Copy link
Member

Enumerable.Any() currently uses TryGetNonEnumeratedCount, comparing the result to 0, and TryGetNonEnumeratedCount uses Iterator<T>.GetCount(onlyIfCheap: true). But this leaves out iterators for which it's not cheap to compute the count; for these, however, we can now benefit from every Iterator<T> providing a TryGetFirst; its found result can be used as the result of Any. This PR inlines TryGetNonEnumeratedCount into Any and then updates its use of Iterator<T> to first use GetCount and then fall back to using TryGetFirst if GetCount is unsuccessful.

Method Toolchain Source Mean Ratio Allocated Alloc Ratio
Any \main\corerun.exe 0 3.346 ns 1.00 - NA
Any \pr\corerun.exe 0 3.277 ns 0.98 - NA
Any \main\corerun.exe 1 2.625 ns 1.00 - NA
Any \pr\corerun.exe 1 2.315 ns 0.88 - NA
Any \main\corerun.exe 2 16.728 ns 1.00 56 B 1.00
Any \pr\corerun.exe 2 4.154 ns 0.25 - 0.00
Any \main\corerun.exe 3 13.110 ns 1.00 - NA
Any \pr\corerun.exe 3 12.690 ns 0.97 - NA
Any \main\corerun.exe 4 14.299 ns 1.00 - NA
Any \pr\corerun.exe 4 12.912 ns 0.90 - NA
Any \main\corerun.exe 5 3.741 ns 1.00 - NA
Any \pr\corerun.exe 5 3.643 ns 0.97 - NA
Any \main\corerun.exe 6 11.118 ns 1.00 - NA
Any \pr\corerun.exe 6 8.741 ns 0.79 - NA
Any \main\corerun.exe 7 47.425 ns 1.00 160 B 1.00
Any \pr\corerun.exe 7 48.630 ns 1.03 160 B 1.00
Any \main\corerun.exe 8 66.663 ns 1.00 328 B 1.00
Any \pr\corerun.exe 8 9.842 ns 0.15 - 0.00
Any \main\corerun.exe 9 12.304 ns 1.00 - NA
Any \pr\corerun.exe 9 17.323 ns 1.40 - NA
Any \main\corerun.exe 10 12.027 ns 1.00 40 B 1.00
Any \pr\corerun.exe 10 10.224 ns 0.84 40 B 1.00
Any \main\corerun.exe 11 26.032 ns 1.00 96 B 1.00
Any \pr\corerun.exe 11 14.288 ns 0.55 40 B 0.42
Any \main\corerun.exe 12 30.752 ns 1.00 104 B 1.00
Any \pr\corerun.exe 12 15.216 ns 0.49 40 B 0.38
Any \main\corerun.exe 13 581.665 ns 1.00 520 B 1.00
Any \pr\corerun.exe 13 195.656 ns 0.34 40 B 0.08
Any \main\corerun.exe 14 1,405.573 ns 1.00 1576 B 1.00
Any \pr\corerun.exe 14 285.060 ns 0.20 40 B 0.03
Any \main\corerun.exe 15 54.888 ns 1.00 96 B 1.00
Any \pr\corerun.exe 15 47.273 ns 0.86 40 B 0.42
Any \main\corerun.exe 16 361.296 ns 1.00 512 B 1.00
Any \pr\corerun.exe 16 173.690 ns 0.48 40 B 0.08
Any \main\corerun.exe 17 46.332 ns 1.00 168 B 1.00
Any \pr\corerun.exe 17 46.564 ns 1.01 168 B 1.00
Any \main\corerun.exe 18 65.017 ns 1.00 336 B 1.00
Any \pr\corerun.exe 18 14.699 ns 0.23 40 B 0.12
Any \main\corerun.exe 19 37.565 ns 1.00 96 B 1.00
Any \pr\corerun.exe 19 23.274 ns 0.62 40 B 0.42
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

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

[MemoryDiagnoser(false)]
[HideColumns("Job", "Error", "StdDev", "Median", "RatioSD")]
public partial class Tests
{
    private IEnumerable<int> _data;

    [Params(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19)]
    public int Source { get; set; }

    [GlobalSetup]
    public void Setup()
    {
        IEnumerable<int> data = Source >= 10 ? Iterations(100) : Enumerable.Range(0, 100).ToArray();
        _data = (Source % 10) switch
        {
            0 => data,
            1 => data.Select(i => i),
            2 => data.Where(i => i % 2 == 0).Select(i => i),
            3 => data.Order(),
            4 => data.OrderBy(i => i).Select(i => i),
            5 => data.Skip(20).Take(10),
            6 => data.Reverse(),
            7 => data.SelectMany(i => new int[] { i }),
            8 => data.Distinct(),
            9 => data.Concat(data),
            _ => throw new NotSupportedException()
        };
    }

    [Benchmark]
    public bool Any() => _data.Any();

    private static IEnumerable<int> Iterations(int count)
    {
        for (int i = 0; i < count; i++) yield return i;
    }
}

Enumerable.Any() currently uses TryGetNonEnumeratedCount, comparing the result to 0, and TryGetNonEnumeratedCount uses `Iterator<T>.GetCount(onlyIfCheap: true)`. But this leaves out iterators for which it's not cheap to compute the count; for these, however, we can now benefit from every `Iterator<T>` providing a `TryGetFirst`; its `found` result can be used as the result of `Any`.  This PR inlines TryGetNonEnumeratedCount into Any and then updates its use of `Iterator<T>` to first use GetCount and then fall back to using TryGetFirst if GetCount is unsuccessful.
@stephentoub stephentoub added area-System.Linq tenet-performance Performance related issue labels Mar 4, 2024
@stephentoub stephentoub added this to the 9.0.0 milestone Mar 4, 2024
@ghost
Copy link

ghost commented Mar 4, 2024

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

Issue Details

Enumerable.Any() currently uses TryGetNonEnumeratedCount, comparing the result to 0, and TryGetNonEnumeratedCount uses Iterator<T>.GetCount(onlyIfCheap: true). But this leaves out iterators for which it's not cheap to compute the count; for these, however, we can now benefit from every Iterator<T> providing a TryGetFirst; its found result can be used as the result of Any. This PR inlines TryGetNonEnumeratedCount into Any and then updates its use of Iterator<T> to first use GetCount and then fall back to using TryGetFirst if GetCount is unsuccessful.

Method Toolchain Source Mean Ratio Allocated Alloc Ratio
Any \main\corerun.exe 0 3.346 ns 1.00 - NA
Any \pr\corerun.exe 0 3.277 ns 0.98 - NA
Any \main\corerun.exe 1 2.625 ns 1.00 - NA
Any \pr\corerun.exe 1 2.315 ns 0.88 - NA
Any \main\corerun.exe 2 16.728 ns 1.00 56 B 1.00
Any \pr\corerun.exe 2 4.154 ns 0.25 - 0.00
Any \main\corerun.exe 3 13.110 ns 1.00 - NA
Any \pr\corerun.exe 3 12.690 ns 0.97 - NA
Any \main\corerun.exe 4 14.299 ns 1.00 - NA
Any \pr\corerun.exe 4 12.912 ns 0.90 - NA
Any \main\corerun.exe 5 3.741 ns 1.00 - NA
Any \pr\corerun.exe 5 3.643 ns 0.97 - NA
Any \main\corerun.exe 6 11.118 ns 1.00 - NA
Any \pr\corerun.exe 6 8.741 ns 0.79 - NA
Any \main\corerun.exe 7 47.425 ns 1.00 160 B 1.00
Any \pr\corerun.exe 7 48.630 ns 1.03 160 B 1.00
Any \main\corerun.exe 8 66.663 ns 1.00 328 B 1.00
Any \pr\corerun.exe 8 9.842 ns 0.15 - 0.00
Any \main\corerun.exe 9 12.304 ns 1.00 - NA
Any \pr\corerun.exe 9 17.323 ns 1.40 - NA
Any \main\corerun.exe 10 12.027 ns 1.00 40 B 1.00
Any \pr\corerun.exe 10 10.224 ns 0.84 40 B 1.00
Any \main\corerun.exe 11 26.032 ns 1.00 96 B 1.00
Any \pr\corerun.exe 11 14.288 ns 0.55 40 B 0.42
Any \main\corerun.exe 12 30.752 ns 1.00 104 B 1.00
Any \pr\corerun.exe 12 15.216 ns 0.49 40 B 0.38
Any \main\corerun.exe 13 581.665 ns 1.00 520 B 1.00
Any \pr\corerun.exe 13 195.656 ns 0.34 40 B 0.08
Any \main\corerun.exe 14 1,405.573 ns 1.00 1576 B 1.00
Any \pr\corerun.exe 14 285.060 ns 0.20 40 B 0.03
Any \main\corerun.exe 15 54.888 ns 1.00 96 B 1.00
Any \pr\corerun.exe 15 47.273 ns 0.86 40 B 0.42
Any \main\corerun.exe 16 361.296 ns 1.00 512 B 1.00
Any \pr\corerun.exe 16 173.690 ns 0.48 40 B 0.08
Any \main\corerun.exe 17 46.332 ns 1.00 168 B 1.00
Any \pr\corerun.exe 17 46.564 ns 1.01 168 B 1.00
Any \main\corerun.exe 18 65.017 ns 1.00 336 B 1.00
Any \pr\corerun.exe 18 14.699 ns 0.23 40 B 0.12
Any \main\corerun.exe 19 37.565 ns 1.00 96 B 1.00
Any \pr\corerun.exe 19 23.274 ns 0.62 40 B 0.42
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

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

[MemoryDiagnoser(false)]
[HideColumns("Job", "Error", "StdDev", "Median", "RatioSD")]
public partial class Tests
{
    private IEnumerable<int> _data;

    [Params(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19)]
    public int Source { get; set; }

    [GlobalSetup]
    public void Setup()
    {
        IEnumerable<int> data = Source >= 10 ? Iterations(100) : Enumerable.Range(0, 100).ToArray();
        _data = (Source % 10) switch
        {
            0 => data,
            1 => data.Select(i => i),
            2 => data.Where(i => i % 2 == 0).Select(i => i),
            3 => data.Order(),
            4 => data.OrderBy(i => i).Select(i => i),
            5 => data.Skip(20).Take(10),
            6 => data.Reverse(),
            7 => data.SelectMany(i => new int[] { i }),
            8 => data.Distinct(),
            9 => data.Concat(data),
            _ => throw new NotSupportedException()
        };
    }

    [Benchmark]
    public bool Any() => _data.Any();

    private static IEnumerable<int> Iterations(int count)
    {
        for (int i = 0; i < count; i++) yield return i;
    }
}
Author: stephentoub
Assignees: -
Labels:

area-System.Linq, tenet-performance

Milestone: 9.0.0

@ghost ghost assigned stephentoub Mar 4, 2024
@stephentoub stephentoub merged commit 0d74d1d into dotnet:main Mar 4, 2024
@stephentoub stephentoub deleted the anyiterator branch March 4, 2024 15:45
@github-actions github-actions bot locked and limited conversation to collaborators Apr 4, 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.

2 participants