.NET 9: Array vs Dictionary lookup performance in C#
One of the most viewed posts in my blog is Array vs Dictionary lookup in C#. The focus was on .NET Framework 4.8, while there have been a plethora of performance improvements in every .NET release: .NET 6, .NET 7, .NET 8. So today I want to check whether the previous results hold true. We will compare the linear search in an array, the binary search in a sorted array, and a dictionary lookup. The reasoning behind these approaches can be found in the previous post.
Tests performed on the following configuration:
BenchmarkDotNet v0.13.12, Windows 11 (10.0.22631.3737/23H2/2023Update/SunValley3)
13th Gen Intel Core i7-13700KF, 1 CPU, 24 logical and 16 physical cores
.NET SDK 9.0.100-preview.5.24307.3
[Host] : .NET 9.0.0 (9.0.24.30607), X64 RyuJIT AVX2
.NET 8.0 : .NET 8.0.0 (8.0.23.53103), X64 RyuJIT AVX2
.NET 9.0 : .NET 9.0.0 (9.0.24.30607), X64 RyuJIT AVX2
.NET Framework 4.8 : .NET Framework 4.8.1 (4.8.9241.0), X64 RyuJIT VectorSize=256
Dictionary<int, int> lookup in .NET 9 vs older .NET versions
Let’s look at the dictionary lookup improvements. The test code is available here. I have just added the RuntimeMoniker attribute to compare different versions:
[MemoryDiagnoser]
[SimpleJob(RuntimeMoniker.Net48)]
[SimpleJob(RuntimeMoniker.Net80)]
[SimpleJob(RuntimeMoniker.Net90)]
public class LookupBenchmarks
{
...
}
I ran the benchmarks on collections of sizes: 5, 10, 15, 20, 25, 30, 40, and 50. Here are the results only for 5 and 50 to keep the table small, since the results are the same for all sizes as expected for a dictionary lookup, which is an O(1) operation:
| Method | Runtime | Size | Mean | Error | StdDev | Allocated |
|------------------------ |------------------- |----- |---------:|---------:|---------:|----------:|
| DictionaryLookup | .NET Framework 4.8 | 5 | 37.34 ns | 0.124 ns | 0.116 ns | - |
| DictionaryLookup | .NET 8.0 | 5 | 18.29 ns | 0.053 ns | 0.047 ns | - |
| DictionaryLookup | .NET 9.0 | 5 | 17.76 ns | 0.096 ns | 0.090 ns | - |
| DictionaryLookup | .NET Framework 4.8 | 50 | 37.37 ns | 0.133 ns | 0.125 ns | - |
| DictionaryLookup | .NET 8.0 | 50 | 18.51 ns | 0.037 ns | 0.034 ns | - |
| DictionaryLookup | .NET 9.0 | 50 | 17.97 ns | 0.067 ns | 0.062 ns | - |
The dictionary lookup is 2 times faster compared to 4.8.
Here is the source code and you can check why the new version is so much faster .NET 9 vs 4.8.
Linear search in .NET 9 vs older .NET versions
Let’s look at the linear search which is an O(n) operation:
| Method | Runtime | Size | Mean | Error | StdDev | Allocated |
|------------------------ |------------------- |----- |---------:|---------:|---------:|----------:|
| ArrayLookupLinearSearch | .NET Framework 4.8 | 5 | 13.70 ns | 0.074 ns | 0.070 ns | - |
| ArrayLookupLinearSearch | .NET 8.0 | 5 | 13.26 ns | 0.055 ns | 0.049 ns | - |
| ArrayLookupLinearSearch | .NET 9.0 | 5 | 11.39 ns | 0.055 ns | 0.051 ns | - |
| ArrayLookupLinearSearch | .NET Framework 4.8 | 10 | 20.67 ns | 0.314 ns | 0.294 ns | - |
| ArrayLookupLinearSearch | .NET 8.0 | 10 | 24.39 ns | 0.083 ns | 0.078 ns | - |
| ArrayLookupLinearSearch | .NET 9.0 | 10 | 17.81 ns | 0.142 ns | 0.133 ns | - |
| ArrayLookupLinearSearch | .NET Framework 4.8 | 15 | 24.55 ns | 0.085 ns | 0.079 ns | - |
| ArrayLookupLinearSearch | .NET 8.0 | 15 | 31.65 ns | 0.168 ns | 0.157 ns | - |
| ArrayLookupLinearSearch | .NET 9.0 | 15 | 23.15 ns | 0.224 ns | 0.209 ns | - |
| ArrayLookupLinearSearch | .NET Framework 4.8 | 20 | 30.81 ns | 0.255 ns | 0.239 ns | - |
| ArrayLookupLinearSearch | .NET 8.0 | 20 | 40.51 ns | 0.133 ns | 0.118 ns | - |
| ArrayLookupLinearSearch | .NET 9.0 | 20 | 29.79 ns | 0.284 ns | 0.265 ns | - |
| ArrayLookupLinearSearch | .NET Framework 4.8 | 25 | 35.44 ns | 0.288 ns | 0.270 ns | - |
| ArrayLookupLinearSearch | .NET 8.0 | 25 | 48.20 ns | 0.603 ns | 0.564 ns | - |
| ArrayLookupLinearSearch | .NET 9.0 | 25 | 34.93 ns | 0.500 ns | 0.467 ns | - |
| ArrayLookupLinearSearch | .NET Framework 4.8 | 30 | 40.72 ns | 0.523 ns | 0.489 ns | - |
| ArrayLookupLinearSearch | .NET 8.0 | 30 | 54.98 ns | 0.311 ns | 0.291 ns | - |
| ArrayLookupLinearSearch | .NET 9.0 | 30 | 39.42 ns | 0.363 ns | 0.340 ns | - |
| ArrayLookupLinearSearch | .NET Framework 4.8 | 40 | 52.07 ns | 0.286 ns | 0.239 ns | - |
| ArrayLookupLinearSearch | .NET 8.0 | 40 | 70.08 ns | 0.533 ns | 0.498 ns | - |
| ArrayLookupLinearSearch | .NET 9.0 | 40 | 52.16 ns | 0.399 ns | 0.373 ns | - |
| ArrayLookupLinearSearch | .NET Framework 4.8 | 50 | 64.72 ns | 0.583 ns | 0.517 ns | - |
| ArrayLookupLinearSearch | .NET 8.0 | 50 | 86.82 ns | 0.565 ns | 0.529 ns | - |
| ArrayLookupLinearSearch | .NET 9.0 | 50 | 63.15 ns | 0.375 ns | 0.351 ns | - |
Surprisingly .NET 8 is slower than 4.8, but .NET 9 improves it and is on par with the old version.
Binary search in .NET 9 vs older .NET versions
And the binary search results which is an O(log n) operation:
| Method | Runtime | Size | Mean | Error | StdDev | Allocated |
|------------------------ |------------------- |----- |---------:|---------:|---------:|----------:|
| ArrayLookupBinarySearch | .NET Framework 4.8 | 5 | 17.12 ns | 0.036 ns | 0.032 ns | - |
| ArrayLookupBinarySearch | .NET 8.0 | 5 | 17.63 ns | 0.081 ns | 0.076 ns | - |
| ArrayLookupBinarySearch | .NET 9.0 | 5 | 13.16 ns | 0.059 ns | 0.053 ns | - |
| ArrayLookupBinarySearch | .NET Framework 4.8 | 10 | 23.79 ns | 0.078 ns | 0.069 ns | - |
| ArrayLookupBinarySearch | .NET 8.0 | 10 | 23.70 ns | 0.057 ns | 0.051 ns | - |
| ArrayLookupBinarySearch | .NET 9.0 | 10 | 18.96 ns | 0.044 ns | 0.041 ns | - |
| ArrayLookupBinarySearch | .NET Framework 4.8 | 15 | 22.19 ns | 0.113 ns | 0.106 ns | - |
| ArrayLookupBinarySearch | .NET 8.0 | 15 | 22.36 ns | 0.072 ns | 0.064 ns | - |
| ArrayLookupBinarySearch | .NET 9.0 | 15 | 18.59 ns | 0.034 ns | 0.028 ns | - |
| ArrayLookupBinarySearch | .NET Framework 4.8 | 20 | 26.85 ns | 0.146 ns | 0.136 ns | - |
| ArrayLookupBinarySearch | .NET 8.0 | 20 | 26.89 ns | 0.086 ns | 0.080 ns | - |
| ArrayLookupBinarySearch | .NET 9.0 | 20 | 22.72 ns | 0.070 ns | 0.065 ns | - |
| ArrayLookupBinarySearch | .NET Framework 4.8 | 25 | 29.58 ns | 0.088 ns | 0.082 ns | - |
| ArrayLookupBinarySearch | .NET 8.0 | 25 | 29.46 ns | 0.167 ns | 0.156 ns | - |
| ArrayLookupBinarySearch | .NET 9.0 | 25 | 24.21 ns | 0.015 ns | 0.012 ns | - |
| ArrayLookupBinarySearch | .NET Framework 4.8 | 30 | 25.15 ns | 0.050 ns | 0.044 ns | - |
| ArrayLookupBinarySearch | .NET 8.0 | 30 | 25.71 ns | 0.065 ns | 0.061 ns | - |
| ArrayLookupBinarySearch | .NET 9.0 | 30 | 21.50 ns | 0.086 ns | 0.080 ns | - |
| ArrayLookupBinarySearch | .NET Framework 4.8 | 40 | 27.33 ns | 0.226 ns | 0.211 ns | - |
| ArrayLookupBinarySearch | .NET 8.0 | 40 | 27.46 ns | 0.252 ns | 0.236 ns | - |
| ArrayLookupBinarySearch | .NET 9.0 | 40 | 23.07 ns | 0.034 ns | 0.028 ns | - |
| ArrayLookupBinarySearch | .NET Framework 4.8 | 50 | 31.54 ns | 0.236 ns | 0.209 ns | - |
| ArrayLookupBinarySearch | .NET 8.0 | 50 | 32.64 ns | 0.221 ns | 0.206 ns | - |
| ArrayLookupBinarySearch | .NET 9.0 | 50 | 27.47 ns | 0.043 ns | 0.041 ns | - |
Now .NET 8 is on par with 4.8, while .NET 9 shows slightly better performance.
Array Linear Search vs Sorted Array Binary Search vs Dictionary<int, int>
This time we will compare all 3 approaches in one go.
Let’s first look at .NET 9:
| Method | Runtime | Size | Mean | Error | StdDev | Allocated |
|------------------------ |------------------- |----- |---------:|---------:|---------:|----------:|
| ArrayLookupLinearSearch | .NET 9.0 | 5 | 11.39 ns | 0.055 ns | 0.051 ns | - |
| ArrayLookupBinarySearch | .NET 9.0 | 5 | 13.16 ns | 0.059 ns | 0.053 ns | - |
| DictionaryLookup | .NET 9.0 | 5 | 17.76 ns | 0.096 ns | 0.090 ns | - |
| ArrayLookupLinearSearch | .NET 9.0 | 10 | 17.81 ns | 0.142 ns | 0.133 ns | - |
| ArrayLookupBinarySearch | .NET 9.0 | 10 | 18.96 ns | 0.044 ns | 0.041 ns | - |
| DictionaryLookup | .NET 9.0 | 10 | 17.98 ns | 0.071 ns | 0.066 ns | - |
| ArrayLookupLinearSearch | .NET 9.0 | 15 | 23.15 ns | 0.224 ns | 0.209 ns | - |
| ArrayLookupBinarySearch | .NET 9.0 | 15 | 18.59 ns | 0.034 ns | 0.028 ns | - |
| DictionaryLookup | .NET 9.0 | 15 | 17.97 ns | 0.063 ns | 0.056 ns | - |
| ArrayLookupLinearSearch | .NET 9.0 | 20 | 29.79 ns | 0.284 ns | 0.265 ns | - |
| ArrayLookupBinarySearch | .NET 9.0 | 20 | 22.72 ns | 0.070 ns | 0.065 ns | - |
| DictionaryLookup | .NET 9.0 | 20 | 17.98 ns | 0.079 ns | 0.074 ns | - |
| ArrayLookupLinearSearch | .NET 9.0 | 25 | 34.93 ns | 0.500 ns | 0.467 ns | - |
| ArrayLookupBinarySearch | .NET 9.0 | 25 | 24.21 ns | 0.015 ns | 0.012 ns | - |
| DictionaryLookup | .NET 9.0 | 25 | 17.97 ns | 0.074 ns | 0.065 ns | - |
| ArrayLookupLinearSearch | .NET 9.0 | 30 | 39.42 ns | 0.363 ns | 0.340 ns | - |
| ArrayLookupBinarySearch | .NET 9.0 | 30 | 21.50 ns | 0.086 ns | 0.080 ns | - |
| DictionaryLookup | .NET 9.0 | 30 | 17.99 ns | 0.060 ns | 0.053 ns | - |
So the last time the dictionary caught up with the linear search at a collection size of 25. Now, due to dictionary improvements, it achieves the same performance at just 10 elements. The binary search stays on par with the dictionary for collections of up to 15 elements.
And the complete table with results
| Method | Runtime | Size | Mean | Error | StdDev | Allocated |
|------------------------ |------------------- |----- |---------:|---------:|---------:|----------:|
| ArrayLookupLinearSearch | .NET Framework 4.8 | 5 | 13.70 ns | 0.074 ns | 0.070 ns | - |
| ArrayLookupBinarySearch | .NET Framework 4.8 | 5 | 17.12 ns | 0.036 ns | 0.032 ns | - |
| DictionaryLookup | .NET Framework 4.8 | 5 | 37.34 ns | 0.124 ns | 0.116 ns | - |
| ArrayLookupLinearSearch | .NET 8.0 | 5 | 13.26 ns | 0.055 ns | 0.049 ns | - |
| ArrayLookupBinarySearch | .NET 8.0 | 5 | 17.63 ns | 0.081 ns | 0.076 ns | - |
| DictionaryLookup | .NET 8.0 | 5 | 18.29 ns | 0.053 ns | 0.047 ns | - |
| ArrayLookupLinearSearch | .NET 9.0 | 5 | 11.39 ns | 0.055 ns | 0.051 ns | - |
| ArrayLookupBinarySearch | .NET 9.0 | 5 | 13.16 ns | 0.059 ns | 0.053 ns | - |
| DictionaryLookup | .NET 9.0 | 5 | 17.76 ns | 0.096 ns | 0.090 ns | - |
| ArrayLookupLinearSearch | .NET Framework 4.8 | 10 | 20.67 ns | 0.314 ns | 0.294 ns | - |
| ArrayLookupBinarySearch | .NET Framework 4.8 | 10 | 23.79 ns | 0.078 ns | 0.069 ns | - |
| DictionaryLookup | .NET Framework 4.8 | 10 | 37.41 ns | 0.128 ns | 0.113 ns | - |
| ArrayLookupLinearSearch | .NET 8.0 | 10 | 24.39 ns | 0.083 ns | 0.078 ns | - |
| ArrayLookupBinarySearch | .NET 8.0 | 10 | 23.70 ns | 0.057 ns | 0.051 ns | - |
| DictionaryLookup | .NET 8.0 | 10 | 18.53 ns | 0.020 ns | 0.017 ns | - |
| ArrayLookupLinearSearch | .NET 9.0 | 10 | 17.81 ns | 0.142 ns | 0.133 ns | - |
| ArrayLookupBinarySearch | .NET 9.0 | 10 | 18.96 ns | 0.044 ns | 0.041 ns | - |
| DictionaryLookup | .NET 9.0 | 10 | 17.98 ns | 0.071 ns | 0.066 ns | - |
| ArrayLookupLinearSearch | .NET Framework 4.8 | 15 | 24.55 ns | 0.085 ns | 0.079 ns | - |
| ArrayLookupBinarySearch | .NET Framework 4.8 | 15 | 22.19 ns | 0.113 ns | 0.106 ns | - |
| DictionaryLookup | .NET Framework 4.8 | 15 | 37.44 ns | 0.067 ns | 0.062 ns | - |
| ArrayLookupLinearSearch | .NET 8.0 | 15 | 31.65 ns | 0.168 ns | 0.157 ns | - |
| ArrayLookupBinarySearch | .NET 8.0 | 15 | 22.36 ns | 0.072 ns | 0.064 ns | - |
| DictionaryLookup | .NET 8.0 | 15 | 18.52 ns | 0.013 ns | 0.010 ns | - |
| ArrayLookupLinearSearch | .NET 9.0 | 15 | 23.15 ns | 0.224 ns | 0.209 ns | - |
| ArrayLookupBinarySearch | .NET 9.0 | 15 | 18.59 ns | 0.034 ns | 0.028 ns | - |
| DictionaryLookup | .NET 9.0 | 15 | 17.97 ns | 0.063 ns | 0.056 ns | - |
| ArrayLookupLinearSearch | .NET Framework 4.8 | 20 | 30.81 ns | 0.255 ns | 0.239 ns | - |
| ArrayLookupBinarySearch | .NET Framework 4.8 | 20 | 26.85 ns | 0.146 ns | 0.136 ns | - |
| DictionaryLookup | .NET Framework 4.8 | 20 | 37.47 ns | 0.155 ns | 0.145 ns | - |
| ArrayLookupLinearSearch | .NET 8.0 | 20 | 40.51 ns | 0.133 ns | 0.118 ns | - |
| ArrayLookupBinarySearch | .NET 8.0 | 20 | 26.89 ns | 0.086 ns | 0.080 ns | - |
| DictionaryLookup | .NET 8.0 | 20 | 18.50 ns | 0.026 ns | 0.024 ns | - |
| ArrayLookupLinearSearch | .NET 9.0 | 20 | 29.79 ns | 0.284 ns | 0.265 ns | - |
| ArrayLookupBinarySearch | .NET 9.0 | 20 | 22.72 ns | 0.070 ns | 0.065 ns | - |
| DictionaryLookup | .NET 9.0 | 20 | 17.98 ns | 0.079 ns | 0.074 ns | - |
| ArrayLookupLinearSearch | .NET Framework 4.8 | 25 | 35.44 ns | 0.288 ns | 0.270 ns | - |
| ArrayLookupBinarySearch | .NET Framework 4.8 | 25 | 29.58 ns | 0.088 ns | 0.082 ns | - |
| DictionaryLookup | .NET Framework 4.8 | 25 | 37.37 ns | 0.106 ns | 0.094 ns | - |
| ArrayLookupLinearSearch | .NET 8.0 | 25 | 48.20 ns | 0.603 ns | 0.564 ns | - |
| ArrayLookupBinarySearch | .NET 8.0 | 25 | 29.46 ns | 0.167 ns | 0.156 ns | - |
| DictionaryLookup | .NET 8.0 | 25 | 18.54 ns | 0.029 ns | 0.027 ns | - |
| ArrayLookupLinearSearch | .NET 9.0 | 25 | 34.93 ns | 0.500 ns | 0.467 ns | - |
| ArrayLookupBinarySearch | .NET 9.0 | 25 | 24.21 ns | 0.015 ns | 0.012 ns | - |
| DictionaryLookup | .NET 9.0 | 25 | 17.97 ns | 0.074 ns | 0.065 ns | - |
| ArrayLookupLinearSearch | .NET Framework 4.8 | 30 | 40.72 ns | 0.523 ns | 0.489 ns | - |
| ArrayLookupBinarySearch | .NET Framework 4.8 | 30 | 25.15 ns | 0.050 ns | 0.044 ns | - |
| DictionaryLookup | .NET Framework 4.8 | 30 | 37.33 ns | 0.080 ns | 0.071 ns | - |
| ArrayLookupLinearSearch | .NET 8.0 | 30 | 54.98 ns | 0.311 ns | 0.291 ns | - |
| ArrayLookupBinarySearch | .NET 8.0 | 30 | 25.71 ns | 0.065 ns | 0.061 ns | - |
| DictionaryLookup | .NET 8.0 | 30 | 18.54 ns | 0.043 ns | 0.040 ns | - |
| ArrayLookupLinearSearch | .NET 9.0 | 30 | 39.42 ns | 0.363 ns | 0.340 ns | - |
| ArrayLookupBinarySearch | .NET 9.0 | 30 | 21.50 ns | 0.086 ns | 0.080 ns | - |
| DictionaryLookup | .NET 9.0 | 30 | 17.99 ns | 0.060 ns | 0.053 ns | - |
| ArrayLookupLinearSearch | .NET Framework 4.8 | 40 | 52.07 ns | 0.286 ns | 0.239 ns | - |
| ArrayLookupBinarySearch | .NET Framework 4.8 | 40 | 27.33 ns | 0.226 ns | 0.211 ns | - |
| DictionaryLookup | .NET Framework 4.8 | 40 | 37.45 ns | 0.200 ns | 0.187 ns | - |
| ArrayLookupLinearSearch | .NET 8.0 | 40 | 70.08 ns | 0.533 ns | 0.498 ns | - |
| ArrayLookupBinarySearch | .NET 8.0 | 40 | 27.46 ns | 0.252 ns | 0.236 ns | - |
| DictionaryLookup | .NET 8.0 | 40 | 18.48 ns | 0.015 ns | 0.014 ns | - |
| ArrayLookupLinearSearch | .NET 9.0 | 40 | 52.16 ns | 0.399 ns | 0.373 ns | - |
| ArrayLookupBinarySearch | .NET 9.0 | 40 | 23.07 ns | 0.034 ns | 0.028 ns | - |
| DictionaryLookup | .NET 9.0 | 40 | 17.95 ns | 0.047 ns | 0.039 ns | - |
| ArrayLookupLinearSearch | .NET Framework 4.8 | 50 | 64.72 ns | 0.583 ns | 0.517 ns | - |
| ArrayLookupBinarySearch | .NET Framework 4.8 | 50 | 31.54 ns | 0.236 ns | 0.209 ns | - |
| DictionaryLookup | .NET Framework 4.8 | 50 | 37.37 ns | 0.133 ns | 0.125 ns | - |
| ArrayLookupLinearSearch | .NET 8.0 | 50 | 86.82 ns | 0.565 ns | 0.529 ns | - |
| ArrayLookupBinarySearch | .NET 8.0 | 50 | 32.64 ns | 0.221 ns | 0.206 ns | - |
| DictionaryLookup | .NET 8.0 | 50 | 18.51 ns | 0.037 ns | 0.034 ns | - |
| ArrayLookupLinearSearch | .NET 9.0 | 50 | 63.15 ns | 0.375 ns | 0.351 ns | - |
| ArrayLookupBinarySearch | .NET 9.0 | 50 | 27.47 ns | 0.043 ns | 0.041 ns | - |
| DictionaryLookup | .NET 9.0 | 50 | 17.97 ns | 0.067 ns | 0.062 ns | - |
Conclusion
Well, the conclusion remains the same as in the previous post. Based on my observations and experience in game scripting, dictionaries are often used for very small collections on the client. These benchmarks show that we can squeeze a little more performance out of the code by using an array, but it would be noticeable only on a very hot path. Now with .NET 9, even small collections of 10 elements are faster as a dictionary than an array if you perform many lookups based on a property or key. To be fair, at this point, in 99.9% of cases, you should just use a dictionary when you need access by a key.
Takeaways
- Always profile your code.
- For a tiny collection of 5 or fewer elements, it is possible to use Array or List<T> instead of Dictionary<TKey, TValue> to get a little performance benefit.
- If it’s viable to keep the collection sorted, you can use binary search with a slightly larger array.
- Have I mentioned profiling your code already? Always do it before any optimization attempt. Without profiling, you can’t guarantee whether your changes result in better performance or if these changes are even needed in the first place.
Alexey Merzlikin
Experienced game developer and tech lead with a passion for writing educational content about game development and programming. I have over 10 years of industry experience focused on performance optimization, clean code practices, and robust game architecture. I share regular posts on my Telegram channel about applying software engineering best practices to build high-quality games. My goal is to help other game developers level up their skills.
You might also consider subscribing to receive updates about new blog posts via email:
Leave a Reply