Optimize Enumerable.SkipLast() for IPartition and IList by timandy · Pull Request #41342 · dotnet/corefx

timandy · 2019-09-26T06:07:58Z

Enumerable.SkipLast() can be cast to Enumerable.Take() when source type is IPartition or IList.

performance test see #40014

Wraith2 · 2019-09-26T07:50:59Z

Can you provide some pre and post performance figures using BenachmarkDotNet? There have been a number of suggestions to change the behaviour of linq query methods which were rejected because they degrade the performance of the common case in favour of an edge case,

timandy · 2019-09-26T08:03:51Z

Can you provide some pre and post performance figures using BenachmarkDotNet? There have been a number of suggestions to change the behaviour of linq query methods which were rejected because they degrade the performance of the common case in favour of an edge case,

@Wraith2 Performance test is in the issue #40014. Should I move the testcase to here?

timandy · 2019-09-26T09:23:59Z

    [MemoryDiagnoser]
    public class SkipLastPerf
    {
        private IEnumerable<int> data;

        [Params(10, 100, 1000)]
        public int COUNT;

        [GlobalSetup]
        public void Setup()
        {
            List<int> tmp = new List<int>(COUNT);
            for (int i = 0; i < COUNT; i++)
            {
                tmp.Add(i);
            }

            data = tmp;
        }

        [Benchmark]
        public int SkipLast()
        {
            return data.SkipLast(5).Sum();
        }

        [Benchmark(Baseline = true)]
        public int SkipLastOld()
        {
            return data.SkipLastOld(5).Sum();
        }
    }

BenchmarkDotNet=v0.11.5, OS=Windows 10.0.17134.915 (1803/April2018Update/Redstone4)
Intel Core i7-8550U CPU 1.80GHz (Kaby Lake R), 1 CPU, 8 logical and 4 physical cores
Frequency=1945313 Hz, Resolution=514.0561 ns, Timer=TSC
.NET Core SDK=3.0.100
  [Host]     : .NET Core 3.0.0 (CoreCLR 4.700.19.46205, CoreFX 4.700.19.46214), 64bit RyuJIT
  DefaultJob : .NET Core 3.0.0 (CoreCLR 4.700.19.46205, CoreFX 4.700.19.46214), 64bit RyuJIT

Method	COUNT	Mean	Error	StdDev	Ratio	Gen 0	Gen 1	Gen 2	Allocated
SkipLast	10	71.08 ns	1.352 ns	1.198 ns	0.32	0.0114	-	-	48 B
SkipLastOld	10	223.76 ns	4.636 ns	4.761 ns	1.00	0.0591	-	-	248 B

SkipLast	100	806.39 ns	6.829 ns	6.053 ns	0.42	0.0114	-	-	48 B
SkipLastOld	100	1,924.12 ns	35.878 ns	31.805 ns	1.00	0.0572	-	-	248 B

SkipLast	1000	8,304.96 ns	88.786 ns	78.707 ns	0.43	-	-	-	48 B
SkipLastOld	1000	19,396.12 ns	138.287 ns	115.476 ns	1.00	0.0305	-	-	248 B

maryamariyan · 2019-09-26T19:36:01Z

Thank you @timandy. The benchmarks test results you provided show improvements. LGTM but also would like to get @stephentoub 's feedback on this.

@adamsitnik would you recommend benchmark tests like these get included in the dotnet benchmark repo?

maryamariyan

LGTM.
cc: @stephentoub

src/System.Linq/src/System/Linq/Skip.SpeedOpt.cs

src/System.Linq/src/System/Linq/Take.cs

src/System.Linq/src/System/Linq/Take.SpeedOpt.cs

stephentoub · 2019-09-27T03:36:35Z

For the benchmarks, the tests shared show the optimized case. Can you share results when the input doesn't hit the optimizations, namely when the input isn't an IList or an IPartition? For example, your setup does this:

        [GlobalSetup]
        public void Setup()
        {
            List<int> tmp = new List<int>(COUNT);
            for (int i = 0; i < COUNT; i++)
            {
                tmp.Add(i);
            }

            data = tmp;
        }

What are the results of your test if you instead do this:

        [GlobalSetup]
        public void Setup()
        {
            data = GetInput(COUNT);
        }

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

?

Thanks.

src/System.Linq/src/System/Linq/Skip.SpeedOpt.cs

timandy · 2019-09-27T05:37:27Z

@stephentoub I test the code with your testcase, The result is

BenchmarkDotNet=v0.11.5, OS=Windows 10.0.17134.915 (1803/April2018Update/Redstone4)
Intel Core i7-8550U CPU 1.80GHz (Kaby Lake R), 1 CPU, 8 logical and 4 physical cores
Frequency=1945313 Hz, Resolution=514.0561 ns, Timer=TSC
.NET Core SDK=3.0.100
  [Host]     : .NET Core 3.0.0 (CoreCLR 4.700.19.46205, CoreFX 4.700.19.46214), 64bit RyuJIT
  DefaultJob : .NET Core 3.0.0 (CoreCLR 4.700.19.46205, CoreFX 4.700.19.46214), 64bit RyuJIT

Method	COUNT	Mean	Error	StdDev	Median	Ratio	RatioSD	Gen 0	Gen 1	Gen 2	Allocated
SkipLast	10	238.4 ns	6.197 ns	16.325 ns	231.7 ns	1.20	0.12	0.0591	-	-	248 B
SkipLastOld	10	212.9 ns	2.897 ns	2.709 ns	213.0 ns	1.00	0.00	0.0591	-	-	248 B

SkipLast	100	1,759.0 ns	28.236 ns	22.045 ns	1,759.6 ns	1.01	0.02	0.0591	-	-	248 B
SkipLastOld	100	1,736.1 ns	33.219 ns	32.626 ns	1,728.5 ns	1.00	0.00	0.0591	-	-	248 B

SkipLast	1000	16,974.7 ns	333.448 ns	356.785 ns	16,836.1 ns	1.05	0.03	0.0305	-	-	248 B
SkipLastOld	1000	16,286.4 ns	195.489 ns	182.860 ns	16,311.9 ns	1.00	0.00	0.0305	-	-	248 B

stephentoub · 2019-09-27T05:41:32Z

test the code with your testcase

Thanks for sharing the results.

Do we have any evidence around the typical type and length of input used with SkipLast? As expected, this demonstrates a nice improvement for the optimized case, but we pay for that with a non-trivial regression (20%) in the case of a short regular enumerable.

This reverts commit 7c7908f

stephentoub · 2019-09-27T11:48:08Z

Other than my question in #41342 (comment), LGTM.

timandy · 2019-09-29T07:53:08Z

@stephentoub I rerun the testcase several times, and wait the programe exit without do anything on my computer. About 5%-6% slower than before optimization.

BenchmarkDotNet=v0.11.5, OS=Windows 10.0.17134.915 (1803/April2018Update/Redstone4)
Intel Core i7-8550U CPU 1.80GHz (Kaby Lake R), 1 CPU, 8 logical and 4 physical cores
Frequency=1945313 Hz, Resolution=514.0561 ns, Timer=TSC
.NET Core SDK=3.0.100
  [Host]     : .NET Core 3.0.0 (CoreCLR 4.700.19.46205, CoreFX 4.700.19.46214), 64bit RyuJIT
  DefaultJob : .NET Core 3.0.0 (CoreCLR 4.700.19.46205, CoreFX 4.700.19.46214), 64bit RyuJIT

Method	COUNT	Mean	Error	StdDev	Ratio	RatioSD	Gen 0	Gen 1	Gen 2	Allocated
SkipLast	10	236.5 ns	2.883 ns	2.555 ns	1.05	0.01	0.0591	-	-	248 B
SkipLastOld	10	224.5 ns	2.305 ns	2.156 ns	1.00	0.00	0.0591	-	-	248 B

SkipLast	100	1,845.4 ns	34.071 ns	40.560 ns	1.01	0.03	0.0591	-	-	248 B
SkipLastOld	100	1,841.8 ns	28.275 ns	26.448 ns	1.00	0.00	0.0591	-	-	248 B

SkipLast	1000	17,342.4 ns	198.178 ns	185.376 ns	1.02	0.02	0.0305	-	-	248 B
SkipLastOld	1000	16,953.2 ns	184.808 ns	172.869 ns	1.00	0.00	0.0305	-	-	248 B

timandy · 2019-10-09T07:17:47Z

@maryamariyan What should I do next?

maryamariyan · 2019-10-09T08:39:30Z

Thanks a lot for the PR @timandy.
Overall the results show the optimized case is faster and that is great. But the issue is with the regressed cases: If the regressed cases for this optimization are also frequently used then merging this PR would be a problem.

In other words, it would be hard to merge the PR if there is no evidence demonstrating that for the "most used cases" we have not made a regression. (The question posed in @stephentoub 's last comment needs to be answered before we can confidently merge the PR).

timandy · 2019-10-09T10:02:32Z

I think it's worthy to use 5% loss of the performance swap 60% performance improvement. And the time of one option for small amount is very very short.

stephentoub · 2019-10-09T11:19:08Z

I think it's worthy to use 5% loss of the performance swap 60% performance improvement. And the time of one option for small amount is very very short.

Waving my hands, if the 5% regression is for a case that's > 12x as common as the 60% improvement, this is a net loss. What evidence do we have about how common these cases are? That's what I'm trying to understand.

safern · 2019-10-22T20:13:30Z

@timandy are you planning on following up on this wrt the question asked above?

stephentoub · 2019-10-23T22:09:22Z

Ok. I just looked at what we do for Enumerable.Skip, Take, and TakeLast, and for all of those we check both of these interfaces. Given that, it seems reasonable to be consistent and complete this one with those two interface as well. I'd like to avoid another PR that does the same in other operators without compelling data about why it's worthwhile. Thanks.

…x#41342) * Optimize Enumerable.SkipLast() for IPartition and IList * Convert to conditional expression * Add parameter name * Revert "Convert to conditional expression" This reverts commit 7c7908fb * Format conditional expression Commit migrated from dotnet/corefx@bdd3397

Dotnet-GitSync-Bot added the area-System.Linq label Sep 26, 2019

timandy added 2 commits September 26, 2019 14:27

Optimize Enumerable.SkipLast() for IPartition and IList

06ae036

Convert to conditional expression

7c7908f

timandy force-pushed the opt-linq branch from df26672 to 7c7908f Compare September 26, 2019 06:27

safern requested a review from maryamariyan September 26, 2019 18:59

maryamariyan approved these changes Sep 26, 2019

View reviewed changes

danmoseley reviewed Sep 26, 2019

View reviewed changes

src/System.Linq/src/System/Linq/Skip.SpeedOpt.cs Outdated Show resolved Hide resolved

Add parameter name

af90403

stephentoub reviewed Sep 27, 2019

View reviewed changes

src/System.Linq/src/System/Linq/Take.cs Outdated Show resolved Hide resolved

stephentoub reviewed Sep 27, 2019

View reviewed changes

src/System.Linq/src/System/Linq/Take.SpeedOpt.cs Outdated Show resolved Hide resolved

stephentoub reviewed Sep 27, 2019

View reviewed changes

src/System.Linq/src/System/Linq/Skip.SpeedOpt.cs Outdated Show resolved Hide resolved

timandy added 2 commits September 27, 2019 13:46

Revert "Convert to conditional expression"

e1f7ff7

This reverts commit 7c7908f

Format conditional expression

af78087

maryamariyan assigned timandy Oct 7, 2019

stephentoub merged commit bdd3397 into dotnet:master Oct 23, 2019

timandy deleted the opt-linq branch November 28, 2019 01:08

karelz added this to the 5.0 milestone Dec 19, 2019

sglienke mentioned this pull request Jul 23, 2020

IEnumerable<T>.SkipLast and TakeLast behave wrong dotnet/runtime#39864

Closed

stephentoub mentioned this pull request Sep 20, 2020

Fix Enumerable.Take/SkipLast on mutable collections dotnet/runtime#42506

Merged

Conversation

timandy commented Sep 26, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Wraith2 commented Sep 26, 2019

Uh oh!

timandy commented Sep 26, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

timandy commented Sep 26, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

maryamariyan commented Sep 26, 2019

Uh oh!

maryamariyan left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

stephentoub commented Sep 27, 2019

Uh oh!

Uh oh!

timandy commented Sep 27, 2019

Uh oh!

stephentoub commented Sep 27, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

stephentoub commented Sep 27, 2019

Uh oh!

timandy commented Sep 29, 2019

Uh oh!

timandy commented Oct 9, 2019

Uh oh!

maryamariyan commented Oct 9, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

timandy commented Oct 9, 2019

Uh oh!

stephentoub commented Oct 9, 2019

Uh oh!

safern commented Oct 22, 2019

Uh oh!

stephentoub commented Oct 23, 2019

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

8 participants

timandy commented Sep 26, 2019 •

edited

Loading

timandy commented Sep 26, 2019 •

edited

Loading

timandy commented Sep 26, 2019 •

edited

Loading

stephentoub commented Sep 27, 2019 •

edited

Loading

maryamariyan commented Oct 9, 2019 •

edited

Loading