Question Performance: go through a dictionary vs find an element in a list?

I know those two are not comparable, but hear me out before answering that.

So, first of all, context. I have a dictionary of things (let's call them abilities) with their id and their data. But some of those may be active, and I need to perform some calculations only on the active ones. So my issue is that I need to perform two operations on some data. I need to go through all the elements to do some stuff, but I also need to search for a specific item (basically to remove it from the list under certain conditions). So I have two options here.

Option 1: Use a second dictionary
So, I could have another dictionary:

Code (CSharp):

1. Dictionary<string, Ability> AllAbilities;
2. Dictionary<string, Ability> ActiveAbilities;

And then I would need to go through all elements of that said dictionary, which is not really performant.
But I would also need to add and remove certain elements, which is really fast with a dictionary if I know the key (I'm assuming I will always know the key in this case)

Option 2: Use a list
The second option is to just use a list of keys to keep track of the active abilities:

Code (CSharp):

1. Dictionary<string, Ability> AllAbilities;
2. List<string> ActiveAbilityIDs;

So in this case, going through all the elements is easier and faster.
But the downside of this solution is that finding a specific key to remove it from the dictionary is slower.

End thoughts
In my personal case, I am probably going to go with option 2, because I believe I will need to iterate through the entire active abilities more times than I will need to remove an item. But I wanted to ask in case anyone had tested this and has a more reasoned decision.

Thanks!

 

Can't you just have a list of Abilities?

 

Or store both in the List using a tuple:

Code (csharp):

1. List<(string, Ability)> ActiveAbilityIDs;

https://learn.microsoft.com/en-us/dotnet/csharp/language-reference/builtin-types/value-tuples

 

I would have just stuck the active property on the Ability itself unless there's some reason I can't (like the Ability is a flyweight used across multiple entities and putting the bool on the Ability would make it active for all entities and I for whatever reason don't want to duplicate the ability).

As for performance... how many abilities are we talking about? The performance difference of iterating a List vs Dictionary is so negligible for small collections. I wouldn't be picking one or the other based on that... I'd be picking between them based on if I need a Dictionary or a List. One is for looking up entries by keys, the other is an ordered collection. As you even say in your first sentence, they're not really comparable. And that's sort of the whole thing. They're not really comparable.

If you can't put a property on the Ability, and all you need is a collection of active abilities... that sounds like List to me.

You say:

Why do you need to find a key to remove it from the List?

Is there more to your design outside of Lists and Dictionary's that we don't know about that ties your hands behind your back about having to rely on keys for everything?

 

Sometimes, where the "find" in a list isn't fast enough, it can be helpful to create a custom collection class that stores values both in a dictionary and in a list, and you can get values by either index or key. It doubles the memory usage but it combines the benefits of both collection types.

That's your third solution.

 

I am really just agreeing with everyone else in this post, that you can probably just use an array for small sized collections when dictionary syntax doesn't work well for all of your use cases. However, I wanted to demonstrate some numbers.

Looking at your example code, I ended up modifying it into something more like this. I like to start with code that I know compiles in Unity and works the way I expect.

Code (CSharp):

1. public abstract class Ability : ScriptableObject
2. {
3.     public abstract void Activate();
4. }

Code (CSharp):

1. [CreateAssetMenu(menuName = "Abilities/Punch", fileName = "PunchAbility", order = 2023)]
2. public class Punch : Ability
3. {
4.     public override void Activate()
5.     {
6.         // Get it? Punch. Throw. Eh?
7.         throw new NotImplementedException();
8.     }
9. }

I'm not a big Tuple user, so I basically created my own Tuple here. Normally I would make this struct explicitly readonly, but then Unity doesn't know how to serialize it by calling the appropriate constructor.

Code (CSharp):

1. [Serializable]
2. public struct AbilityMapping
3. {
4.     public string ID => _id;
5.     [SerializeField] private string _id;
6.  
7.     public Ability Ability => _ability;
8.     [SerializeField] private Ability _ability;
9.  
10.     public AbilityMapping(string id, Ability ability)
11.     {
12.         if(string.IsNullOrEmpty(id))
13.             throw new ArgumentNullException(nameof(id));
14.  
15.         if(ability == null)
16.             throw new ArgumentNullException(nameof(ability));
17.  
18.         _id = id;
19.         _ability = ability;
20.     }
21. }

And then, you can serialize your abilities, mapped to certain key strings, like so:

Code (CSharp):

1. public AbilityMapping[] AbilityMap;

And it looks like this in the inspector:


So, having established that, I created this benchmark for BenchmarkDotNet.

Code (CSharp):

1. namespace Benchmarks
2. {
3.     public class DictionaryVsList
4.     {
5.         [ParamsSource(nameof(Sizes))]
6.         public int Size;
7.         public int[] Sizes { get; } = new int[]
8.         {
9.             4,
10.             8,
11.             16,
12.             32,
13.             64,
14.             128,
15.             256,
16.             512,
17.             1024,
18.             2048,
19.             4096,
20.             8192,
21.             16384,
22.             // Large Object Heap Territory
23.         };
24.  
25.         private Dictionary<string, Ability> AbilityDictionary;
26.         private AbilityMapping[] AbilityMap;
27.  
28.         private string[] RandomIDs;
29.         private int Index;
30.         private Random Random;
31.         private int RandomSeed = 8675309;
32.  
33.  
34.         [GlobalSetup(Target = "DictionaryFind")]
35.         public void DictionarySetup()
36.         {
37.             AbilityDictionary = new Dictionary<string, Ability>(Size);
38.             for(int i = 0; i < Size; i++)
39.             {
40.                 AbilityDictionary[i.ToString()] = new Punch();
41.             }
42.             GenerateRandomIDs();
43.         }
44.  
45.         [GlobalSetup(Target = "ArrayFind")]
46.         public void ArraySetup()
47.         {
48.             AbilityMap = new AbilityMapping[Size];
49.             for(int i = 0; i < Size; i++)
50.             {
51.                 AbilityMap[i] = new AbilityMapping(i.ToString(), new Punch());
52.             }
53.             GenerateRandomIDs();
54.         }
55.  
56.         private void GenerateRandomIDs()
57.         {
58.             Random = new Random(RandomSeed);
59.             RandomIDs = new string[Size];
60.             for(int i = 0; i < Size; i++)
61.             {
62.                 RandomIDs[i] = i.ToString();
63.             }
64.             for(int i = 0; i < Size; i++)
65.             {
66.                 int randomIndex = Random.Next(Size);
67.                 string swap = RandomIDs[i];
68.                 RandomIDs[i] = RandomIDs[randomIndex];
69.                 RandomIDs[randomIndex] = swap;
70.             }
71.         }
72.  
73.  
74.         [Benchmark]
75.         public Ability DictionaryFind()
76.         {
77.             string randomID = RandomIDs[Index];
78.             ++Index;
79.             if(Index == Size)
80.                 Index = 0;
81.  
82.             if(AbilityDictionary.TryGetValue(randomID, out Ability ability))
83.                 return ability;
84.             return null;
85.         }
86.  
87.         [Benchmark]
88.         public Ability ArrayFind()
89.         {
90.             string randomID = RandomIDs[Index];
91.             ++Index;
92.             if(Index == Size)
93.                 Index = 0;
94.  
95.             foreach(AbilityMapping mapping in AbilityMap)
96.             {
97.                 if(mapping.ID == randomID)
98.                     return mapping.Ability;
99.             }
100.             return null;
101.         }
102.  
103.  
104.         public abstract class Ability
105.         {
106.             public abstract void Activate();
107.         }
108.  
109.  
110.         public class Punch : Ability
111.         {
112.             public override void Activate()
113.             {
114.                 throw new NotImplementedException();
115.             }
116.         }
117.  
118.         [Serializable]
119.         public struct AbilityMapping
120.         {
121.             public string ID => _id;
122.             private string _id;
123.  
124.             public Ability Ability => _ability;
125.             private Ability _ability;
126.  
127.             public AbilityMapping(string id, Ability ability)
128.             {
129.                 if(string.IsNullOrEmpty(id))
130.                     throw new ArgumentNullException(nameof(id));
131.  
132.                 if(ability == null)
133.                     throw new ArgumentNullException(nameof(ability));
134.  
135.                 _id = id;
136.                 _ability = ability;
137.             }
138.         }
139.     }
140. }

And here are the results:

Code (CSharp):

1. string Summary = @"
2. BenchmarkDotNet v0.13.6, Windows 10 (10.0.19045.3208/22H2/2022Update)
3. Intel Core i7-6700HQ CPU 2.60GHz (Skylake), 1 CPU, 8 logical and 4 physical cores
4. .NET SDK 7.0.306
5.  [Host]     : .NET 6.0.20 (6.0.2023.32017), X64 RyuJIT AVX2
6.  DefaultJob : .NET 6.0.20 (6.0.2023.32017), X64 RyuJIT AVX2
7.  
8. |         Method |  Size |          Mean |         Error |        StdDev |        Median |
9. |--------------- |------ |--------------:|--------------:|--------------:|--------------:|
10. | DictionaryFind |     4 |     20.815 ns |     0.6731 ns |     1.8540 ns |     20.580 ns |
11. |      ArrayFind |     4 |      8.065 ns |     0.2530 ns |     0.7095 ns |      7.822 ns |
12. | DictionaryFind |     8 |     19.808 ns |     0.4886 ns |     1.3782 ns |     19.594 ns |
13. |      ArrayFind |     8 |     15.855 ns |     0.4956 ns |     1.3897 ns |     16.011 ns |
14. | DictionaryFind |    16 |     21.250 ns |     0.1561 ns |     0.1219 ns |     21.221 ns |
15. |      ArrayFind |    16 |     25.717 ns |     0.6154 ns |     1.7658 ns |     25.828 ns |
16. | DictionaryFind |    32 |     22.285 ns |     0.8531 ns |     2.3064 ns |     21.706 ns |
17. |      ArrayFind |    32 |     57.003 ns |     1.2242 ns |     3.1380 ns |     57.352 ns |
18. | DictionaryFind |    64 |     24.638 ns |     0.5826 ns |     0.8720 ns |     24.671 ns |
19. |      ArrayFind |    64 |    125.365 ns |     2.5849 ns |     5.5087 ns |    125.234 ns |
20. | DictionaryFind |   128 |     24.902 ns |     0.7089 ns |     1.9760 ns |     24.477 ns |
21. |      ArrayFind |   128 |    201.070 ns |     3.4830 ns |     6.6267 ns |    199.864 ns |
22. | DictionaryFind |   256 |     27.977 ns |     0.7175 ns |     2.0354 ns |     27.814 ns |
23. |      ArrayFind |   256 |    365.521 ns |     7.3880 ns |    13.5094 ns |    364.162 ns |
24. | DictionaryFind |   512 |     30.253 ns |     0.6875 ns |     1.7870 ns |     29.809 ns |
25. |      ArrayFind |   512 |    833.799 ns |    13.5265 ns |    22.9691 ns |    830.685 ns |
26. | DictionaryFind |  1024 |     34.237 ns |     0.7716 ns |     2.0993 ns |     33.887 ns |
27. |      ArrayFind |  1024 |  1,909.245 ns |    47.1224 ns |   131.3585 ns |  1,873.256 ns |
28. | DictionaryFind |  2048 |     51.169 ns |     0.8057 ns |     0.6291 ns |     51.121 ns |
29. |      ArrayFind |  2048 |  2,878.870 ns |    57.5982 ns |   154.7337 ns |  2,869.356 ns |
30. | DictionaryFind |  4096 |     56.531 ns |     3.0639 ns |     8.7415 ns |     52.884 ns |
31. |      ArrayFind |  4096 |  6,877.113 ns |   235.5934 ns |   648.8925 ns |  6,684.001 ns |
32. | DictionaryFind |  8192 |     62.142 ns |     2.4857 ns |     6.9292 ns |     59.879 ns |
33. |      ArrayFind |  8192 | 15,290.297 ns |   323.4290 ns |   912.2372 ns | 14,977.000 ns |
34. | DictionaryFind | 16384 |     81.942 ns |     5.2839 ns |    15.3294 ns |     82.216 ns |
35. |      ArrayFind | 16384 | 27,110.029 ns | 1,219.1895 ns | 3,498.0833 ns | 26,325.769 ns |
36. ";

Now, you may be thinking after looking at those results that dictionary lookup is clearly faster. However, what I want to point out is that even in the worst case, with thousands of abilities in an array, the worst case is still measured in microseconds. Look at the array results without considering the three worst cases, when you only have say 1000 abilities. Then, the results are pretty similar to any kind of human perception. So, presuming you don't need to do these lookups a very high number of times per frame, it will cost you some number of microseconds, or even nanoseconds to perform. The true difference only really begins when you have hundreds or thousands of abilities to search. A microsecond is 1/1000 of a millisecond. At 60fps you have around 16ms to work with. So, you shouldn't notice much of a difference in performance. If you are developing performance sensitive code in a hot path it could make sense to stick with the dictionary for lookups, and use other collections of active and inactive keys, or even just two dictionaries, one active, one inactive, and check them both. But, if it's not that performance critical, it may just be better to do what is most readable, logical, and easy to work with.

 

What is this ghastly slow code I am seeing?! If you want performance, you should of course use

Span<T>

Code (CSharp):

1. public sealed class Abilities
2. {
3.     private readonly ReadOnlyMemory<Ability> all;
4.     public Abilities(params Ability[] all) => this.all = new ReadOnlyMemory<Ability>(all);
5.     public ReadOnlySpan<Ability> All => all.Span;
6.     public Ability this[AbilityId id] => all.Span[(int)id];
7. }

Jokes aside, the choice here doesn't matter at all in terms of performance - both are plenty fast for a handful of abilities.

In this situation you should focus your optimization efforts on making the public API of the class as simple as possible to use, as well as on the readability of the code. If you need to access a value by it's id, I think using a dictionary makes a lot of sense.