Benchmark of Collection Searching (TryGetValue method) in terms of Execution Time (Mean)
BenchmarkDotNet v0.13.12, Windows 11 (10.0.22631.3007/23H2/2023Update/SunValley3)
AMD Ryzen 7 5800H with Radeon Graphics, 1 CPU, 16 logical and 8 physical cores
.NET SDK 8.0.101
[Host] : .NET 8.0.1 (8.0.123.58001), X64 RyuJIT AVX2
ShortRun : .NET 8.0.1 (8.0.123.58001), X64 RyuJIT AVX2
Job=ShortRun IterationCount=3 LaunchCount=1
WarmupCount=3
Comparison: Mean
| Method | Big O | Length | Existed | Int32 | String | StructInts | ClassInts | RecordStructInts | RecordClassInts | StructStrings | ClassStrings | RecordStructStrings | RecordClassStrings |
| FrozenSet |
O(1) |
1000 |
False |
2.017 ns |
6.279 ns |
20.44 ns |
7.170 ns |
2.770 ns |
8.372 ns |
55.73 ns |
26.46 ns |
22.32 ns |
29.70 ns |
| FrozenDictionary |
O(1) |
1000 |
False |
2.030 ns |
4.421 ns |
19.79 ns |
3.893 ns |
2.496 ns |
5.194 ns |
56.43 ns |
23.98 ns |
22.38 ns |
26.36 ns |
| Dictionary |
O(1) |
1000 |
False |
3.391 ns |
7.095 ns |
19.37 ns |
5.800 ns |
2.594 ns |
7.600 ns |
51.74 ns |
26.80 ns |
22.39 ns |
28.87 ns |
| ReadOnlyDictionary |
O(1) |
1000 |
False |
3.455 ns |
9.358 ns |
33.32 ns |
8.227 ns |
4.541 ns |
10.164 ns |
64.18 ns |
27.73 ns |
24.38 ns |
30.32 ns |
| HashSet |
O(1) |
1000 |
False |
3.481 ns |
7.151 ns |
22.08 ns |
6.058 ns |
4.426 ns |
7.548 ns |
57.58 ns |
26.76 ns |
24.29 ns |
28.78 ns |
| ImmutableDictionary |
O(1) |
1000 |
False |
7.248 ns |
16.466 ns |
26.32 ns |
11.503 ns |
7.737 ns |
12.672 ns |
62.28 ns |
30.47 ns |
25.24 ns |
33.59 ns |
| ImmutableHashSet |
O(1) |
1000 |
False |
7.340 ns |
15.515 ns |
27.27 ns |
10.564 ns |
7.797 ns |
12.355 ns |
60.33 ns |
30.72 ns |
25.47 ns |
33.02 ns |
| SortedSet |
O(log(N)) |
1000 |
False |
11.367 ns |
303.085 ns |
12.72 ns |
42.620 ns |
12.721 ns |
42.326 ns |
295.38 ns |
321.25 ns |
297.21 ns |
325.54 ns |
| List (Sorted + BinarySearch) |
O(log(N)) |
1000 |
False |
14.998 ns |
353.234 ns |
19.01 ns |
36.647 ns |
19.119 ns |
35.829 ns |
312.10 ns |
323.10 ns |
307.28 ns |
334.64 ns |
| Array (Sorted + BinarySearch) |
O(log(N)) |
1000 |
False |
15.383 ns |
311.216 ns |
19.36 ns |
37.925 ns |
18.860 ns |
38.351 ns |
299.34 ns |
336.69 ns |
292.68 ns |
340.86 ns |
| ImmutableArray (Sorted + BinarySearch) |
O(log(N)) |
1000 |
False |
15.764 ns |
321.109 ns |
19.09 ns |
39.116 ns |
19.021 ns |
37.963 ns |
293.73 ns |
337.24 ns |
311.06 ns |
332.00 ns |
| SortedList |
O(log(N)) |
1000 |
False |
16.714 ns |
319.730 ns |
23.61 ns |
48.149 ns |
23.539 ns |
45.018 ns |
310.73 ns |
335.78 ns |
311.69 ns |
350.56 ns |
| SortedDictionary |
O(log(N)) |
1000 |
False |
19.917 ns |
358.193 ns |
27.48 ns |
60.603 ns |
24.387 ns |
60.654 ns |
325.09 ns |
362.20 ns |
329.71 ns |
356.53 ns |
| ImmutableSortedDictionary |
O(log(N)) |
1000 |
False |
23.368 ns |
323.934 ns |
36.37 ns |
52.262 ns |
36.601 ns |
51.219 ns |
351.23 ns |
338.19 ns |
310.22 ns |
338.98 ns |
| ImmutableSortedSet |
O(log(N)) |
1000 |
False |
24.754 ns |
336.183 ns |
36.35 ns |
48.278 ns |
37.911 ns |
48.499 ns |
310.70 ns |
362.93 ns |
309.88 ns |
339.99 ns |
| ImmutableList (Sorted + BinarySearch) |
O(log(N)) |
1000 |
False |
28.555 ns |
357.601 ns |
36.04 ns |
79.511 ns |
32.269 ns |
77.948 ns |
343.91 ns |
380.81 ns |
310.73 ns |
363.58 ns |
| Array |
O(N) |
1000 |
False |
41.027 ns |
4,006.808 ns |
12,541.77 ns |
1,736.114 ns |
502.378 ns |
2,684.823 ns |
108,295.13 ns |
4,278.42 ns |
3,002.75 ns |
4,876.45 ns |
| ReadOnlyCollection |
O(N) |
1000 |
False |
42.841 ns |
3,005.547 ns |
12,254.54 ns |
773.975 ns |
513.425 ns |
1,975.733 ns |
118,003.93 ns |
806.45 ns |
2,721.37 ns |
4,492.43 ns |
| List |
O(N) |
1000 |
False |
42.976 ns |
4,002.468 ns |
12,764.38 ns |
1,508.505 ns |
491.131 ns |
2,788.096 ns |
112,553.83 ns |
4,405.76 ns |
2,432.59 ns |
4,918.19 ns |
| ImmutableArray |
O(N) |
1000 |
False |
68.369 ns |
3,938.770 ns |
12,889.71 ns |
1,504.838 ns |
505.744 ns |
2,686.475 ns |
111,003.80 ns |
4,104.14 ns |
2,706.27 ns |
4,864.75 ns |
| Method | Big O | Length | Existed | Int32 | String | StructInts | ClassInts | RecordStructInts | RecordClassInts | StructStrings | ClassStrings | RecordStructStrings | RecordClassStrings |
| FrozenDictionary |
O(1) |
1000 |
True |
2.095 ns |
4.857 ns |
34.89 ns |
7.734 ns |
3.898 ns |
9.072 ns |
278.40 ns |
27.86 ns |
23.84 ns |
29.57 ns |
| FrozenSet |
O(1) |
1000 |
True |
2.394 ns |
10.957 ns |
45.59 ns |
13.617 ns |
4.049 ns |
15.024 ns |
277.42 ns |
33.70 ns |
24.57 ns |
35.91 ns |
| HashSet |
O(1) |
1000 |
True |
2.853 ns |
9.021 ns |
36.13 ns |
9.552 ns |
3.997 ns |
11.522 ns |
271.28 ns |
30.82 ns |
25.17 ns |
32.48 ns |
| Dictionary |
O(1) |
1000 |
True |
4.085 ns |
8.973 ns |
35.81 ns |
9.370 ns |
3.575 ns |
10.990 ns |
269.36 ns |
30.29 ns |
24.77 ns |
32.05 ns |
| ReadOnlyDictionary |
O(1) |
1000 |
True |
4.432 ns |
11.229 ns |
39.45 ns |
12.288 ns |
5.672 ns |
14.022 ns |
267.79 ns |
33.20 ns |
27.13 ns |
34.84 ns |
| ImmutableDictionary |
O(1) |
1000 |
True |
6.307 ns |
20.911 ns |
40.20 ns |
17.573 ns |
7.762 ns |
18.683 ns |
286.65 ns |
35.85 ns |
26.29 ns |
38.15 ns |
| ImmutableHashSet |
O(1) |
1000 |
True |
6.315 ns |
19.697 ns |
39.89 ns |
15.310 ns |
7.407 ns |
17.343 ns |
279.63 ns |
34.40 ns |
26.31 ns |
37.07 ns |
| SortedSet |
O(log(N)) |
1000 |
True |
12.824 ns |
289.570 ns |
18.54 ns |
39.951 ns |
18.607 ns |
41.549 ns |
246.11 ns |
271.12 ns |
244.64 ns |
288.70 ns |
| ImmutableArray (Sorted + BinarySearch) |
O(log(N)) |
1000 |
True |
13.101 ns |
265.289 ns |
20.32 ns |
38.523 ns |
20.234 ns |
38.337 ns |
225.38 ns |
287.29 ns |
223.43 ns |
283.93 ns |
| Array (Sorted + BinarySearch) |
O(log(N)) |
1000 |
True |
13.181 ns |
264.543 ns |
20.34 ns |
39.157 ns |
20.193 ns |
38.776 ns |
222.51 ns |
284.16 ns |
230.00 ns |
265.16 ns |
| SortedList |
O(log(N)) |
1000 |
True |
13.182 ns |
270.004 ns |
26.04 ns |
43.552 ns |
26.215 ns |
42.708 ns |
237.37 ns |
266.62 ns |
237.11 ns |
260.66 ns |
| List (Sorted + BinarySearch) |
O(log(N)) |
1000 |
True |
13.594 ns |
264.359 ns |
20.60 ns |
36.386 ns |
20.436 ns |
36.092 ns |
247.74 ns |
279.69 ns |
220.86 ns |
278.72 ns |
| ImmutableSortedDictionary |
O(log(N)) |
1000 |
True |
18.594 ns |
237.537 ns |
26.37 ns |
42.528 ns |
28.917 ns |
41.881 ns |
243.21 ns |
260.24 ns |
249.12 ns |
266.12 ns |
| ImmutableSortedSet |
O(log(N)) |
1000 |
True |
18.637 ns |
245.379 ns |
29.35 ns |
39.679 ns |
30.016 ns |
39.638 ns |
239.16 ns |
259.80 ns |
238.64 ns |
259.17 ns |
| SortedDictionary |
O(log(N)) |
1000 |
True |
19.448 ns |
281.324 ns |
27.64 ns |
59.154 ns |
25.049 ns |
58.112 ns |
258.40 ns |
323.84 ns |
265.08 ns |
292.27 ns |
| ImmutableList (Sorted + BinarySearch) |
O(log(N)) |
1000 |
True |
27.142 ns |
268.966 ns |
31.13 ns |
68.583 ns |
31.714 ns |
68.878 ns |
249.16 ns |
289.97 ns |
244.42 ns |
294.36 ns |
| Array |
O(N) |
1000 |
True |
28.672 ns |
1,831.162 ns |
6,261.18 ns |
841.566 ns |
253.309 ns |
1,312.305 ns |
52,177.49 ns |
2,075.47 ns |
1,293.04 ns |
2,295.45 ns |
| List |
O(N) |
1000 |
True |
29.101 ns |
1,826.351 ns |
6,091.29 ns |
726.899 ns |
253.244 ns |
1,293.321 ns |
55,667.07 ns |
1,956.09 ns |
1,409.63 ns |
2,321.20 ns |
| ImmutableArray |
O(N) |
1000 |
True |
30.060 ns |
1,789.514 ns |
6,350.76 ns |
852.207 ns |
252.977 ns |
1,315.318 ns |
53,316.98 ns |
1,983.68 ns |
1,326.56 ns |
2,408.86 ns |
| ReadOnlyCollection |
O(N) |
1000 |
True |
32.001 ns |
1,435.280 ns |
6,179.42 ns |
265.686 ns |
254.999 ns |
955.457 ns |
53,090.26 ns |
326.04 ns |
1,418.92 ns |
2,153.06 ns |