Array vs Dictionary lookup in C#
We were taught about data structures that the Dictionary has O(1) lookup and the linear search in an unsorted array is O(n). So based on this we can assume that when we need frequent access by a key we should use the Dictionary, right?
Well, not quite always. Even though Microsoft suggests in this article to use the Dictionary in that case.
Disclaimer: you should profile your code on a target architecture when making any assumptions. And micro-optimizations could have absolutely zero effect on the overall performance of your game or app. I just want you to show that Dictionary lookup can be slower than Array lookup under some conditions.
I ran the test using:
BenchmarkDotNet=v0.13.1, OS=Windows 10.0.19042.1288 (20H2/October2020Update)
IntelCore i7-8750H CPU 2.20GHz (Coffee Lake), 1 CPU, 12 logical and 6 physical cores
[Host] : .NET Framework 4.8 (4.8.4420.0), X86 LegacyJIT
And here are the results I got:
Array Linear Search vs Dictionary<int, int>
| Method | Size | Mean | Error | StdDev | Allocated |
|------------------------ |----- |----------:|---------:|---------:|----------:|
| ArrayLookupLinearSearch | 5 | 55.29 ns | 1.118 ns | 0.991 ns | - |
| DictionaryLookup | 5 | 202.42 ns | 1.412 ns | 1.321 ns | - |
| ArrayLookupLinearSearch | 10 | 92.36 ns | 0.520 ns | 0.435 ns | - |
| DictionaryLookup | 10 | 202.53 ns | 1.274 ns | 1.192 ns | - |
| ArrayLookupLinearSearch | 15 | 131.67 ns | 1.017 ns | 0.902 ns | - |
| DictionaryLookup | 15 | 201.87 ns | 0.979 ns | 0.818 ns | - |
| ArrayLookupLinearSearch | 20 | 184.05 ns | 2.216 ns | 2.073 ns | - |
| DictionaryLookup | 20 | 202.13 ns | 0.803 ns | 0.671 ns | - |
| ArrayLookupLinearSearch | 25 | 213.62 ns | 3.777 ns | 5.170 ns | - |
| DictionaryLookup | 25 | 204.99 ns | 3.821 ns | 3.190 ns | - |
| ArrayLookupLinearSearch | 30 | 259.69 ns | 3.448 ns | 3.225 ns | - |
| DictionaryLookup | 30 | 203.51 ns | 2.189 ns | 1.941 ns | - |
| ArrayLookupLinearSearch | 40 | 367.43 ns | 3.651 ns | 3.049 ns | - |
| DictionaryLookup | 40 | 202.52 ns | 1.059 ns | 0.939 ns | - |
| ArrayLookupLinearSearch | 50 | 466.88 ns | 4.029 ns | 3.364 ns | - |
| DictionaryLookup | 50 | 202.90 ns | 1.781 ns | 1.666 ns | - |The linear search is 4 times faster for a small collection of 5 elements but becomes slower at around 25 elements on my machine. Also keep in mind that the hash function for the int key is very simple, so it is mostly a Dictionary overhead. However, this example can be further exaggerated. If you are using a collection mostly for read operations on a hot path and very rare write operations (e.g. creating at the start of a level or a game session and not changing after), then you can keep your Array or List sorted, that allows to use binary search for lookup which, as we know, has O(log n) complexity.
Sorted Array Binary Search vs Dictionary<int, int>
| Method | Size | Mean | Error | StdDev | Allocated |
|------------------------ |-------|---------:|--------:|--------:|----------:|
| ArrayLookupBinarySearch | 5 | 82.1 ns | 0.41 ns | 0.34 ns | - |
| DictionaryLookup | 5 | 202.4 ns | 1.41 ns | 1.32 ns | - |
| ArrayLookupBinarySearch | 10 | 124.8 ns | 1.28 ns | 1.20 ns | - |
| DictionaryLookup | 10 | 202.5 ns | 1.27 ns | 1.19 ns | - |
| ArrayLookupBinarySearch | 15 | 118.3 ns | 0.89 ns | 0.83 ns | - |
| DictionaryLookup | 15 | 201.8 ns | 0.97 ns | 0.81 ns | - |
| ArrayLookupBinarySearch | 20 | 139.3 ns | 0.42 ns | 0.35 ns | - |
| DictionaryLookup | 20 | 202.1 ns | 0.80 ns | 0.67 ns | - |
| ArrayLookupBinarySearch | 25 | 159.9 ns | 3.20 ns | 3.15 ns | - |
| DictionaryLookup | 25 | 204.9 ns | 3.82 ns | 3.19 ns | - |
| ArrayLookupBinarySearch | 30 | 133.4 ns | 1.29 ns | 1.20 ns | - |
| DictionaryLookup | 30 | 203.5 ns | 2.18 ns | 1.94 ns | - |
| ArrayLookupBinarySearch | 40 | 145.6 ns | 1.25 ns | 0.97 ns | - |
| DictionaryLookup | 40 | 202.5 ns | 1.05 ns | 0.93 ns | - |
| ArrayLookupBinarySearch | 50 | 172.4 ns | 1.12 ns | 1.05 ns | - |
| DictionaryLookup | 50 | 202.9 ns | 1.78 ns | 1.66 ns | - |
| ArrayLookupBinarySearch | 100 | 253.3 ns | 5.03 ns | 4.94 ns | - |
| DictionaryLookup | 100 | 202.9 ns | 2.50 ns | 2.34 ns | - |
| ArrayLookupBinarySearch | 500 | 317.5 ns | 5.14 ns | 4.81 ns | - |
| DictionaryLookup | 500 | 202.6 ns | 2.44 ns | 2.16 ns | - |
| ArrayLookupBinarySearch | 1000 | 382.9 ns | 5.54 ns | 5.69 ns | - |
| DictionaryLookup | 1000 | 204.1 ns | 1.57 ns | 1.39 ns | - |
| ArrayLookupBinarySearch | 10000 | 470.0 ns | 2.42 ns | 2.02 ns | - |
| DictionaryLookup | 10000 | 202.4 ns | 1.35 ns | 1.12 ns | - |
Here you can see that the size of a collection can be increased even further: the binary search at 50 elements is still ~15% faster than Dictionary lookup.
Feel free to check it yourself.
Conclusion
Based on my observations and experience in game scripting, in most cases, dictionaries are used for really small collections, so these results can be helpful to squeeze a little bit more performance, but obviously, it would be noticeable only on a hot path. For bigger collections, you definitely should not use the linear search. Better to research some more advanced techniques if the Dictionary is not suitable for you.
Takeaways
- Always profile your code
- For a small collection, it is possible to use Array or List<T> instead of Dictionary<TKey, TValue>
- If it is possible and viable to keep the collection sorted, then you can use the binary search and use it with an even bigger collection
- Have I said profile your code already? Just do it before any optimization attempt. Without profiling, you can’t guarantee whether your changes result in better performance, as well as are these changes 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:
Have you tried testing values other than ints? I imagine that walking a list of larger items would be more expensive. It seems like it would be cost of hashcode generation versus cost of walking the keys. I’m not sure what wins out.
Yeah, for strings of length 10 Dictionary beats string[] at 15 elements. Seems like calculating string hash is faster than comparing 2 strings even when we consider dictionary overhead.
| Method | Size | Mean
| Array | 5 | 91.81 ns
| Dict_ | 5 | 242.19 ns
| Array | 10 | 338.12 ns
| Dict_ | 10 | 421.51 ns
| Array | 15 | 1,087.65 ns
| Dict_ | 15 | 687.37 ns
| Array | 25 | 3,156.60 ns
| Dict_ | 25 | 1,112.10 ns
| Array | 50 | 9,324.54 ns
| Dict_ | 50 | 2,489.67 ns