2
\$\begingroup\$

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...

\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks a lot for answer! It was really helpful in giving me a decent understanding appropriate uses of Dictionaries. Seems like I'm going back to the good ol' arrays. My procedural generation system sets all the initial data at the beginning of the game (data will not be affected in any way during the course of the game, except for the addition of new vertices on a mesh) and meshes need to be compared in "batches" against random values given by the user (for example a range from mesh 25 to mesh 35) based on distance thresholds using a set of arrays seems like the way to go. \$\endgroup\$ – MadLed Jan 24 at 10:21
  • \$\begingroup\$ And I don't need to modify the capacity of the collection, since from the start the capacity is way bigger to accommodate possible changes in the amount of vertices/triangles but the order of meshes and their vertices/triangles will always be the same. Nonetheless the idea to keep a set of Dictionaries in case I need to access an specific mesh based on instance ID is actually pretty useful! Thanks a lot for your help. \$\endgroup\$ – MadLed Jan 24 at 10:21
  • \$\begingroup\$ If you're comparing them using distances, a spatial partition data structure might be useful here. These are structures that answer the question "what content is in/near this area/point?" efficiently. \$\endgroup\$ – DMGregory Jan 24 at 13:08
  • \$\begingroup\$ Thanks, I'll look into that! I believe I had checked out Octrees for spatial division in the past but I settled into a simple solution using a big collider to detect the primitive colliders attached to each gameobject/mesh (even tho it might not be the most performance-friendly solution) because it was really easy to implement \$\endgroup\$ – MadLed Jan 24 at 13:47
  • \$\begingroup\$ In that case, you're already taking advantage of the spatial partitioning data structures that the physics engine uses to accelerate its queries, so you might not need to roll your own. \$\endgroup\$ – DMGregory Jan 24 at 14:09
0
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.