NotificationsYou must be signed in to change notification settings
Fork5.2k
Star17.2k

Improve`.Distinct().ToList()` and`.Union(e).ToList()`#95224

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

eiriktsarpalis merged 1 commit intodotnet:mainfromWindows10CE:distinct-tolist-improvements

Nov 27, 2023

Merged

Improve`.Distinct().ToList()` and`.Union(e).ToList()`#95224

eiriktsarpalis merged 1 commit intodotnet:mainfromWindows10CE:distinct-tolist-improvements

Nov 27, 2023

Conversation

Copy link

Contributor

Windows10CE commentedNov 25, 2023

Enumerable.HashSetToList fills the result list by copying from the set to the list itself, but this can be done faster (and more simply) by using theList<T>(IEnumerable<T>) constructor to callHashSet<T>.CopyTo(T[]).

publicclassBench{[Params(10,1000,1_000_000)]publicintCount{get;set;}privateint[]_arr;[GlobalSetup]publicvoidInit(){_arr=newint[Count];newRandom(3).NextBytes(MemoryMarshal.AsBytes(_arr.AsSpan()));}[Benchmark]publicList<int>DistinctToList(){return_arr.Distinct().ToList();}}

BenchmarkDotNet v0.13.10, Arch LinuxAMD Ryzen 9 5900X, 1 CPU, 24 logical and 12 physical cores.NET SDK 8.0.100  [Host]     : .NET 8.0.0 (8.0.23.53103), X64 RyuJIT AVX2  Job-KQNFCO : .NET 8.0.1 (42.42.42.42424), X64 RyuJIT AVX2  Job-BSODDZ : .NET 8.0.0 (8.0.23.53103), X64 RyuJIT AVX2Runtime=.NET 8.0

Method	Job	Toolchain	Count	Mean	Error	StdDev	Ratio	RatioSD
DistinctToList	Job-KQNFCO	CoreRun	10	119.9 ns	2.42 ns	2.49 ns	0.86	0.02
DistinctToList	Job-BSODDZ	net8.0	10	138.2 ns	1.33 ns	1.11 ns	1.00	0.00

DistinctToList	Job-KQNFCO	CoreRun	1000	6,280.2 ns	60.54 ns	56.63 ns	0.80	0.01
DistinctToList	Job-BSODDZ	net8.0	1000	7,831.8 ns	47.20 ns	44.15 ns	1.00	0.00

DistinctToList	Job-KQNFCO	CoreRun	1000000	17,175,312.7 ns	341,877.48 ns	406,980.82 ns	0.94	0.02
DistinctToList	Job-BSODDZ	net8.0	1000000	18,496,042.9 ns	123,385.89 ns	96,331.59 ns	1.00	0.00

Replace Enumerable.HashSetToList with List constructor

3934503

ghost added community-contribution

Indicates that the PR has been added by a community member

area-System.Linq labels

Nov 25, 2023

Copy link

ghost commentedNov 25, 2023

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

Issue Details

publicclassBench{[Params(10,1000,1_000_000)]publicintCount{get;set;}privateint[]_arr;[GlobalSetup]publicvoidInit(){_arr=newint[Count];newRandom(3).NextBytes(MemoryMarshal.AsBytes(_arr.AsSpan()));}[Benchmark]publicList<int>DistinctToList(){return_arr.Distinct().ToList();}}

BenchmarkDotNet v0.13.10, Arch LinuxAMD Ryzen 9 5900X, 1 CPU, 24 logical and 12 physical cores.NET SDK 8.0.100  [Host]     : .NET 8.0.0 (8.0.23.53103), X64 RyuJIT AVX2  Job-KQNFCO : .NET 8.0.1 (42.42.42.42424), X64 RyuJIT AVX2  Job-BSODDZ : .NET 8.0.0 (8.0.23.53103), X64 RyuJIT AVX2Runtime=.NET 8.0

Method	Job	Toolchain	Count	Mean	Error	StdDev	Ratio	RatioSD
DistinctToList	Job-KQNFCO	CoreRun	10	119.9 ns	2.42 ns	2.49 ns	0.86	0.02
DistinctToList	Job-BSODDZ	net8.0	10	138.2 ns	1.33 ns	1.11 ns	1.00	0.00

DistinctToList	Job-KQNFCO	CoreRun	1000	6,280.2 ns	60.54 ns	56.63 ns	0.80	0.01
DistinctToList	Job-BSODDZ	net8.0	1000	7,831.8 ns	47.20 ns	44.15 ns	1.00	0.00

DistinctToList	Job-KQNFCO	CoreRun	1000000	17,175,312.7 ns	341,877.48 ns	406,980.82 ns	0.94	0.02
DistinctToList	Job-BSODDZ	net8.0	1000000	18,496,042.9 ns	123,385.89 ns	96,331.59 ns	1.00	0.00

Author:	Windows10CE
Assignees:	-
Labels:	`area-System.Linq`,`community-contribution`
Milestone:	-

Copy link

ContributorAuthor

Windows10CE commentedNov 25, 2023

@dotnet-policy-service agree

build-analysisbot mentioned this pull request

Nov 25, 2023

ComInterfaceGenerator.Unit.Tests crashes on net9.0-linux-Debug-x64-Mono_release-Ubuntu.2204.Amd64.Open#92070

Open

Copy link

Member

huoyaoyuan commentedNov 26, 2023

Can you compare with latest main branch too, and include memory diagnoser?HashSet has a struct enumerator and I'd expect it to be faster with directforeach.

Copy link

ContributorAuthor

Windows10CE commentedNov 26, 2023•
edited
Loading

Can you compare with latest main branch too, and include memory diagnoser?HashSet has a struct enumerator and I'd expect it to be faster with directforeach.

Ah, yes, thank you for saying this, it is indeed less of an improvement than that first bench shows, most of the improvements gained here were also gained with#86796 (when I had checked earlier, I hadthought this PR was included in net8, which was why I just benched against that, but looking again it was not).

Here are the new results:

Method	Job	Toolchain	Count	Mean	Error	StdDev	Ratio	RatioSD	Gen0	Gen1	Gen2	Allocated	Alloc Ratio
DistinctToList	Job-HVDLNJ	.NET 8.0	10	132.3 ns	1.97 ns	1.85 ns	1.00	0.00	0.0291	-	-	488 B	1.00
DistinctToList	Job-GVVNDQ	main	10	118.9 ns	0.36 ns	0.28 ns	0.90	0.01	0.0291	-	-	488 B	1.00
DistinctToList	Job-NUYUKR	#95224	10	112.1 ns	1.75 ns	1.64 ns	0.85	0.02	0.0291	-	-	488 B	1.00

DistinctToList	Job-HVDLNJ	.NET 8.0	1000	8,013.0 ns	151.11 ns	155.18 ns	1.00	0.00	1.2970	0.0763	-	21920 B	1.00
DistinctToList	Job-GVVNDQ	main	1000	6,902.9 ns	136.73 ns	162.76 ns	0.86	0.03	1.3046	0.0763	-	21920 B	1.00
DistinctToList	Job-NUYUKR	#95224	1000	6,623.9 ns	98.54 ns	92.17 ns	0.83	0.02	1.3046	0.0763	-	21920 B	1.00

DistinctToList	Job-HVDLNJ	.NET 8.0	1000000	19,286,187.6 ns	314,736.06 ns	262,818.86 ns	1.00	0.00	406.2500	406.2500	406.2500	22603123 B	1.00
DistinctToList	Job-GVVNDQ	main	1000000	17,551,160.4 ns	133,451.94 ns	111,438.41 ns	0.91	0.02	406.2500	406.2500	406.2500	22603123 B	1.00
DistinctToList	Job-NUYUKR	#95224	1000000	17,392,611.3 ns	108,270.07 ns	101,275.89 ns	0.90	0.01	343.7500	343.7500	343.7500	22603082 B	1.00