Performance

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)
Intel
Core 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 hash function for 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.

Here is the test code

Feel free to check it yourself.


Conclusion

Based on my observations and experience in game scripting, in most cases dictionaries are used for a 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 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 a better performance, as well as are these changes even needed in the first place.


Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: