Skip to content

Improve Enumerable.Skip and Enumerable.Take performance #112401

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
stephentoub merged 3 commits into from
Feb 13, 2025
Merged

Improve Enumerable.Skip and Enumerable.Take performance #112401

stephentoub merged 3 commits into from
Feb 13, 2025

Conversation

@miyaji255
Copy link
Contributor

@miyaji255 miyaji255 commented Feb 11, 2025

Summary

CopyTo is now used in ToArray and ToList after Skip and Take when source is List<T> or T[].

Benchmark

BenchmarkDotNet=v0.13.5, OS=Windows 11 (10.0.26100.3037)
12th Gen Intel Core i7-12700F, 1 CPU, 20 logical and 12 physical cores
.NET SDK=8.0.300
  [Host]     : .NET 8.0.5 (8.0.524.21615), X64 RyuJIT AVX2
  DefaultJob : .NET 8.0.5 (8.0.524.21615), X64 RyuJIT AVX2


|         Method |      Mean |     Error |    StdDev |   Gen0 |   Gen1 | Allocated |
|--------------- |----------:|----------:|----------:|-------:|-------:|----------:|
|    SkipAndTake | 533.98 ns | 10.388 ns | 10.203 ns | 0.1335 |      - |   1.71 KB |
| SkipAndTake_PR | 118.56 ns |  1.430 ns |  1.194 ns | 0.1340 | 0.0007 |   1.71 KB |
|       GetRange |  77.37 ns |  0.815 ns |  0.723 ns | 0.1267 | 0.0007 |   1.62 KB |

[MemoryDiagnoser]
public class Benchmark
{
    private readonly List<string> _list = Enumerable.Range(0, 1000).Select(i => i.ToString()).ToList();

    [Benchmark]
    public List<string> SkipAndTake() =>
        _list.Skip(200).Take(200).ToList();

    [Benchmark]
    public List<string> SkipAndTake_PR() =>
        _list.Skip_PR(200).Take_PR(200).ToList();

    [Benchmark]
    public List<string> GetRange() =>
        _list.GetRange(200, 200);
}

@ghost ghost added the area-System.Linq label Feb 11, 2025
@dotnet-policy-service dotnet-policy-service bot added the community-contribution Indicates that the PR has been added by a community member label Feb 11, 2025
@dotnet-policy-service
Copy link
Contributor

dotnet-policy-service bot commented Feb 11, 2025

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

@eiriktsarpalis
Copy link
Member

eiriktsarpalis commented Feb 11, 2025

What does the performance look like for IList sources that are neither List<T> or T[]?

@EgorBo
Copy link
Member

EgorBo commented Feb 11, 2025

@EgorBot -amd -arm

using System.Collections.Immutable;
using BenchmarkDotNet.Attributes;

[MemoryDiagnoser]
public class Benchmark
{
    private readonly IList<string> _list = Enumerable.Range(0, 1000)
        .Select(i => i.ToString()).ToImmutableArray();

    [Benchmark]
    public List<string> SkipAndTake() =>
        _list.Skip(200).Take(200).ToList();
}

@EgorBot EgorBot mentioned this pull request Feb 11, 2025
Open
@EgorBo
Copy link
Member

EgorBo commented Feb 11, 2025 •
edited
Loading

I think with help of PGO, these casts are cheap (at least, in monomorphic microbenchmarks). Presumably the overhead is more visible on smaller inputs and when the input is diverse (so PGO can't help).

@eiriktsarpalis
Copy link
Member

eiriktsarpalis commented Feb 11, 2025

Presumably the overhead is more visible on smaller inputs and when the input is diverse (so PGO can't help).

Perhaps using one benchmark class to run three against three different input types could help here?

@miyaji255
Copy link
Contributor Author

miyaji255 commented Feb 11, 2025

Even with small inputs there was not much degradation in performance

|                            Method | SkipCount | TakeCount |         Mean |      Error |     StdDev |       Median |   Gen0 |   Gen1 | Allocated |
|---------------------------------- |---------- |---------- |-------------:|-----------:|-----------:|-------------:|-------:|-------:|----------:|
|    ReadOnlyCollection_SkipAndTake |         2 |         5 |     57.05 ns |   0.479 ns |   0.400 ns |     57.08 ns | 0.0147 |      - |     192 B |
| ReadOnlyCollection_SkipAndTake_PR |         2 |         5 |     59.40 ns |   1.232 ns |   1.954 ns |     58.57 ns | 0.0147 |      - |     192 B |
|                  List_SkipAndTake |         2 |         5 |     48.11 ns |   0.229 ns |   0.179 ns |     48.12 ns | 0.0147 |      - |     192 B |
|               List_SkipAndTake_PR |         2 |         5 |     50.09 ns |   0.496 ns |   0.440 ns |     49.96 ns | 0.0147 |      - |     192 B |
|                     List_GetRange |         2 |         5 |     11.45 ns |   0.150 ns |   0.133 ns |     11.46 ns | 0.0073 |      - |      96 B |
|    ReadOnlyCollection_SkipAndTake |        20 |        50 |    225.20 ns |   1.150 ns |   1.020 ns |    225.09 ns | 0.0422 |      - |     552 B |
| ReadOnlyCollection_SkipAndTake_PR |        20 |        50 |    227.43 ns |   1.754 ns |   1.465 ns |    227.10 ns | 0.0422 |      - |     552 B |
|                  List_SkipAndTake |        20 |        50 |    169.29 ns |   1.191 ns |   1.055 ns |    169.08 ns | 0.0422 |      - |     552 B |
|               List_SkipAndTake_PR |        20 |        50 |     66.71 ns |   0.316 ns |   0.264 ns |     66.72 ns | 0.0422 |      - |     552 B |
|                     List_GetRange |        20 |        50 |     27.52 ns |   0.203 ns |   0.180 ns |     27.49 ns | 0.0349 | 0.0001 |     456 B |
|    ReadOnlyCollection_SkipAndTake |       200 |       500 |  1,948.57 ns |  12.762 ns |  11.313 ns |  1,946.40 ns | 0.3166 | 0.0038 |    4152 B |
| ReadOnlyCollection_SkipAndTake_PR |       200 |       500 |  1,894.11 ns |  10.677 ns |   9.987 ns |  1,891.91 ns | 0.3166 | 0.0038 |    4152 B |
|                  List_SkipAndTake |       200 |       500 |  1,360.73 ns |  11.972 ns |  10.612 ns |  1,362.17 ns | 0.3166 | 0.0038 |    4152 B |
|               List_SkipAndTake_PR |       200 |       500 |    218.02 ns |   4.362 ns |   6.919 ns |    215.36 ns | 0.3176 | 0.0045 |    4152 B |
|                     List_GetRange |       200 |       500 |    172.92 ns |   1.922 ns |   1.704 ns |    172.49 ns | 0.3102 | 0.0045 |    4056 B |
|    ReadOnlyCollection_SkipAndTake |      2000 |      5000 | 19,448.66 ns |  92.606 ns |  82.093 ns | 19,464.56 ns | 3.0518 | 0.3357 |   40152 B |
| ReadOnlyCollection_SkipAndTake_PR |      2000 |      5000 | 18,834.30 ns |  82.067 ns |  72.750 ns | 18,842.62 ns | 3.0518 | 0.3357 |   40152 B |
|                  List_SkipAndTake |      2000 |      5000 | 12,860.73 ns |  57.382 ns |  50.868 ns | 12,869.06 ns | 3.0670 | 0.3357 |   40152 B |
|               List_SkipAndTake_PR |      2000 |      5000 |  1,977.67 ns |  20.074 ns |  16.762 ns |  1,978.10 ns | 3.0670 | 0.3395 |   40152 B |
|                     List_GetRange |      2000 |      5000 |  1,957.41 ns |  13.694 ns |  12.139 ns |  1,955.80 ns | 3.0556 | 0.3395 |   40056 B |

[MemoryDiagnoser]
public class Benchmark
{
    [Params(2, 20, 200, 2000)]
    public int SkipCount { get; set; }

    [Params(5, 50, 500, 5000)]
    public int TakeCount { get; set; }

    private readonly List<string> _list = Enumerable.Range(0, 10000).Select(i => i.ToString()).ToList();
    private readonly ReadOnlyCollection<string> _readOnlyCollection = Enumerable.Range(0, 10000).Select(i => i.ToString()).ToList().AsReadOnly();

    [Benchmark]
    public List<string> ReadOnlyCollection_SkipAndTake() =>
        _readOnlyCollection.Skip(SkipCount).Take(TakeCount).ToList();

    [Benchmark]
    public List<string> ReadOnlyCollection_SkipAndTake_PR() =>
        _readOnlyCollection.Skip_PR(SkipCount).Take_PR(TakeCount).ToList();

    [Benchmark]
    public List<string> List_SkipAndTake() =>
        _list.Skip(SkipCount).Take(TakeCount).ToList();

    [Benchmark]
    public List<string> List_SkipAndTake_PR() =>
        _list.Skip_PR(SkipCount).Take_PR(TakeCount).ToList();

    [Benchmark]
    public List<string> List_GetRange() =>
        _list.GetRange(SkipCount, TakeCount);
}

neon-sunset
neon-sunset reviewed Feb 11, 2025
View reviewed changes
This was referenced Feb 11, 2025
Open
Closed
Open
Open
Open
Closed
Open
Closed
Closed
stephentoub
stephentoub approved these changes Feb 13, 2025
View reviewed changes
Copy link
Member

@stephentoub stephentoub left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks

@stephentoub stephentoub merged commit 45caaf8 into dotnet:main Feb 13, 2025
85 of 87 checks passed
@miyaji255 miyaji255 deleted the improve-performance-of-skip-take branch February 13, 2025 18:45
@github-actions github-actions bot locked and limited conversation to collaborators Mar 16, 2025
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.

Reviewers

@stephentoub stephentoub stephentoub approved these changes

@eiriktsarpalis eiriktsarpalis eiriktsarpalis approved these changes

+1 more reviewer

@neon-sunset neon-sunset neon-sunset left review comments

Reviewers whose approvals may not affect merge requirements

Assignees

No one assigned

Labels

area-System.Linq community-contribution Indicates that the PR has been added by a community member

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

5 participants

@miyaji255 @eiriktsarpalis @EgorBo @stephentoub @neon-sunset