How can I improve performance when looping and comparing values on dictionaries?

Question

On my quest to creating 0 garbage when procedurally generating points I've stumbled upon a performance issue when comparing values to another values stored inside Dictionaries.

Initially I used lists and arrays but I recently revisited the code in order to avoid any garbage generation. Also I decided to use Dictionaries instead of Arrays/Lists because it seems useful to access a certain Key in a Dictionary.

I use Dictionaries in the following way:

• Each key is a mesh in my game
• Each value is an array of vertices or triangles
• Every array contains hundreds of vertices or triangles

Dictionary<int, Vector3[]> exampleVerticesDictionary;  
Dictionary<int, int[]> exampleTrianglesDictionary;  

My procedural system does the following:

1. Takes an initial random value (int or float).  
2. Loops through all the items in the arrays of the 1st Dictionary.  
3. If the value matches any value on any of the arrays, continue on the next loop.*  
4. Loops through all the items in the arrays of the 2nd Dictionary.  
5. If the initial value matches again, continue on next loop.  
6. Loops through all the items in the arrays of the 3rd Dictionary.  
7. If the initial value matches again, create a 3D point.  

I access and compare items in Dictionaries in the following way:

if (exampleVerticesDictionary[key][index] == 1)

---

The problem: It causes noticeable performance spikes. The profiler indicates it's caused by the numerous calls (tens of thousands) to these methods:

  Dictionary.get_Item()
      GenericEqualityComparer.Equals()
          Int32.Equals()
      GenericEqualityComparer.Equals()
          Int32.GetHashCode() 

The questions:

• Why does the performance drop so much when using Dictionaries to make those comparisons?
• Am I just better off using Arrays of Arrays instead of Dictionaries of Arrays?
• Should I be using other way of accessing and comparing items in Dictionaries?

---

Thanks in advance! Coding is not my strong suit and I'm kinda lost with this issue...

Answer 1

Dictionaries are great when you want random access to one element (that's identified by a non-integer key, or by integer keys that are sparsely distributed) without iterating over all/most of the elements in the collection.

Internally, they hash your key, and use that hash result to guide a probe/search of a (generally very small) portion of the collection. That means you're paying hashing and comparison costs for each individual lookup, but it's still cheaper per lookup than searching the whole collection with something like exhaustive iteration or binary search. In particular, in a well balanced dictionary application, the cost of the lookup doesn't grow with the size of the collection, unlike search methods.

But if you're planning to iterate over all values in the collection anyway, then this is just wasteful. You haven't cut down on the number of entries in the collection you're visiting - in fact you've increased your workload by visiting some entries multiple times in the event of collisions.

You could instead store your items in a list and iterate over all of them sequentially without any of those extra hashing and comparison steps for every probe in every lookup, and with no redundant probes.

So you're using the wrong structure for this particular application. It's fine to also keep a dictionary for fast random lookup, in addition to a list for fast exhaustive iteration, using the appropriate tool for whichever operation you need to perform at the time.

(Although I do note your keys are integers: if those keys are dense - say, you have an entry for most integers from 42 to 105 - then you might as well store the collection in a list anyway, which also gives you random access to numeric indices as long as they're in a contiguous range, and does so without the hashing/probing. You might just need to scale/shift the range into valid indices for the list.)

Something to keep in mind is that modern processors and their cache hierarchies absolutely love walking linearly through an array or list. They can reliably predict the next action, pre-fetch the data they need, and plow through at full speed without waiting on memory latency or rewinding mis-predicted branches. All of that can grind to a halt when they hit a dictionary lookup, which by its nature looks to the processor like a random leap, losing much of the acceleration of prediction & caching. So a naive iteration can often be faster if it lets the hardware do what it's good at and chew contiguous data in predictable patterns, and finding ways to make your access patterns more linear like this will frequently yield benefits.

---

That costly random leap can still be worthwhile if it saves you a long search though! So that suggests a different way you could use dictionaries productively here: instead of using many dictionary lookups to search through all your meshes, use one dictionary lookup instead of searching all your meshes.

Here you'd key our new dictionary on the value you're searching for. That way you can use it to pre-cache the answers to the question "does value X match any value in any of my meshes?", and return the result in one single lookup instead of iterating every mesh to find a match.

Each time you change your set of meshes, or change the contents of one of the meshes, you update this cache. This will be a speedup if your frequency of updates is less than your frequency of queries - accelerating the action you do often, and the cost of a little extra book-keeping for the action you do less often.

Answer 2

Have you guys thought about using multi-threaded LINQ for reading the dictionary faster? Something like

exampleDictionary.AsParallel()
.ForAll(kv => 
{ 
    // do something with kv.Key or kv.Value
    // if custom object, kv.YourProp
});

Hopefully this can be used! Good luck!