When dealing with a real-time application, like say a video game, efficiency is key. My last post pointed to some great articles about XNA efficiency, but there just isn’t any substitute for experience. In my latest quandaries with XNA, I’ve been dealing with the C# generic data structures. Here’s what I’ve found:
Hello Mr. Vector, meet Mr. List
If you’re familiar with C++ vectors, then a C# List is where you’d like to go. A list is implemented as a dynamic array, so you may access each element just like you would with an array. That comes in handy since we like to avoid those nasty foreach loops. For the most part, the list implementation is fairly quick. What isn’t quick?
List.Remove(Object objectVariable)
Yeah, my ImagineCup team makes use of this for moving objects in the game. The remove call seems to be the slowest we have, and it makes since. To remove an item from the list, you must check the item against every item in the list or at least until you find a match. Since list’s are unordered beasts, this is, at worst, O(n). Do that a couple of thousand times and see if your XBox lags a bit.
Dictionary: It’s like a really slow hash
A dictionary is a new (at least to me) implementation in C#. They are based on a key, value pair which is where the hashing comes in. Given a key, the dictionary invokes a hash function to find the element you requested. In my case, we used enumerations for the key, and a list for values. This helped us keep organized, find things quickly, and all was well. That is, until we realized how long it takes to actually grab items out of the dictionary. Ordinarily, reaching values given a key will take a hash function O(1) time. That’s really quick! With a dictionary, you still find items in O(1) time, but the overhead to grab that item’s value is massive (perhaps an overstatement). If you iterate through items (like you would using a list) this isn’t the data type for you. For simple classification though, you might get by with it.
While trying to figure out things on my own, and make our game as efficient as possible, I stumbled upon this article at XNA Creators Club: Data Structures. It covers (a little more in depth) how each structure works and it’s relative time complexity in big O notation. It’s a good read if you’re having slow down in your game. You might just be using a structure that’s killing you.