NotificationsYou must be signed in to change notification settings
Fork5.1k
Star16.6k

Use Iterator<T>.TryGetFirst in Enumerable.Any()#99218

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.

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

Already on GitHub?Sign in to your account

Jump to bottom

Merged

stephentoub merged 1 commit intodotnet:mainfromstephentoub:anyiterator

Mar 4, 2024

Merged

Use Iterator<T>.TryGetFirst in Enumerable.Any()#99218

stephentoub merged 1 commit intodotnet:mainfromstephentoub:anyiterator

Mar 4, 2024

Conversation

Copy link

Member

stephentoub commentedMar 4, 2024

Enumerable.Any() currently uses TryGetNonEnumeratedCount, comparing the result to 0, and TryGetNonEnumeratedCount usesIterator<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 everyIterator<T> providing aTryGetFirst; itsfound result can be used as the result ofAny. This PR inlines TryGetNonEnumeratedCount into Any and then updates its use ofIterator<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

usingBenchmarkDotNet.Attributes;usingBenchmarkDotNet.Running;BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);[MemoryDiagnoser(false)][HideColumns("Job","Error","StdDev","Median","RatioSD")]publicpartialclassTests{privateIEnumerable<int>_data;[Params(0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19)]publicintSource{get;set;}[GlobalSetup]publicvoidSetup(){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=>newint[]{i}),8=>data.Distinct(),9=>data.Concat(data),            _=>thrownewNotSupportedException()};}[Benchmark]publicboolAny()=>_data.Any();privatestaticIEnumerable<int>Iterations(intcount){for(inti=0;i<count;i++)yieldreturni;}}

Use Iterator<T>.TryGetFirst in Enumerable.Any()

bc123ba

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 added area-System.Linq tenet-performancePerformance related issue labels

Mar 4, 2024

stephentoub added this to the9.0.0 milestone

Mar 4, 2024

Copy link

ghost commentedMar 4, 2024

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

Issue Details

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

usingBenchmarkDotNet.Attributes;usingBenchmarkDotNet.Running;BenchmarkSwitcher.FromAssembly(typeof(Tests).Assembly).Run(args);[MemoryDiagnoser(false)][HideColumns("Job","Error","StdDev","Median","RatioSD")]publicpartialclassTests{privateIEnumerable<int>_data;[Params(0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19)]publicintSource{get;set;}[GlobalSetup]publicvoidSetup(){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=>newint[]{i}),8=>data.Distinct(),9=>data.Concat(data),            _=>thrownewNotSupportedException()};}[Benchmark]publicboolAny()=>_data.Any();privatestaticIEnumerable<int>Iterations(intcount){for(inti=0;i<count;i++)yieldreturni;}}