HashSet Initialisation Speed in C#

Jan 5, 2023 | 2 min | #csharp #performance

Which one is faster?

1var hs = new HashSet<int>(_data);

1var hs = new HashSet<int>();
2foreach(int i in _data) {
3    hs.Add(i);
4}

1var hs = new HashSet<int>(_data.Length);
2foreach (int i in _data) {
3	hs.Add(i);
4}

My first thought was that option 1 is definitely faster - I’m passing entire dataset into HashSet so .NET should be efficient enough to figure that out. Testing it:

Method	Length	Mean	Error	StdDev	Min	Max	Median	Gen0	Gen1	Gen2	Allocated
WithConstructor	1000000	52.07 ms	44.886 ms	2.460 ms	49.47 ms	54.37 ms	52.36 ms	454.5455	454.5455	454.5455	17.74 MB
WithAddNoLength	1000000	53.45 ms	5.679 ms	0.311 ms	53.10 ms	53.70 ms	53.54 ms	900.0000	900.0000	900.0000	41.12 MB
WithAddWithLength	1000000	37.92 ms	15.129 ms	0.829 ms	37.01 ms	38.64 ms	38.10 ms	500.0000	500.0000	500.0000	17.74 MB

which means option #3 is faster! Passing data length into constructor makes sure we’ll have no memory reallocation, and then adding element one by one fills it up quicker.

Benchmark Code

 1#LINQPad optimize+
 2
 3void Main()
 4{
 5	Util.AutoScrollResults = true;
 6	BenchmarkRunner.Run<Enumeration>();
 7}
 8
 9[ShortRunJob]
10[MinColumn, MaxColumn, MeanColumn, MedianColumn]
11[MemoryDiagnoser]
12[MarkdownExporter]
13public class Enumeration
14{
15	[Params(1000000)]
16	public int Length;
17    
18    private int[] _data;
19    private static Random random = new Random();
20
21	[GlobalSetup]
22	public void Setup()
23	{
24        _data = Enumerable.Range(0, Length).Select(i => random.Next()).ToArray();
25	}
26
27
28	[Benchmark]
29	public void WithConstructor()
30	{
31        var hs = new HashSet<int>(_data);
32	}
33
34    [Benchmark]
35    public void WithAddNoLength() {
36        var hs = new HashSet<int>();
37        foreach(int i in _data) {
38            hs.Add(i);
39        }
40    }
41
42    [Benchmark]
43    public void WithAddWithLength() {
44        var hs = new HashSet<int>(_data.Length);
45        foreach (int i in _data) {
46            hs.Add(i);
47        }
48    }
49
50
51}

Have feedback or questions? Feel free to email me.