C#: Dictionary vs List — Benchmark Testing

NOTE: These tests are done on Windows 7 64bit, 12gig ram, Intel i5-2500K @ 3.30GHz

I’ve been working on a spaceship type game (New game in progress) in C#/XNA and ran into a little question new coders normally want to know. Should we use Dictionary or List for our elements of data? It depends on what you are planning on doing with your data.

Our base coding will be the following:

class ShipData
{
    public string name;
    public int value;
    public ShipData(string name, int value)
    {
        this.name = name;
        this.value = value;
    }
}
class Program
{
    static void Main(string[] args)
    {
        List list = new List();
        Dictionary dictionary = new Dictionary();
        list.Add(new ShipData("Corvette", 1));
        list.Add(new ShipData("Frigate", 2));
        list.Add(new ShipData("Destroyer", 3));
        list.Add(new ShipData("Cruiser", 4));
        list.Add(new ShipData("Battlecruiser", 5));
        list.Add(new ShipData("Battleship", 6));</code>
 
        <code>dictionary.Add("Corvette",1);
        dictionary.Add("Frigate",2);
        dictionary.Add("Destroyer",3);
        dictionary.Add("Cruiser",4);
        dictionary.Add("Battlecruiser",5);
        dictionary.Add("Battleship",6);
 
        int value;
        const int benchmarkRuns = 10000000;
        var s1 = Stopwatch.StartNew();
        for (int i = 0; i < benchmarkRuns; i++)
        {
            //MY BENCHMARK CODING HERE
        }
        s1.Stop();
    }
}

The gist is that there is a name and a value, (value being the cost of the ship). Obviously, you could get more crazy then this, but this is a very simple example. Dictionary does not require this as it holds a Key and Value already (Value can also be your own structure/class, but in this case, again not needed!).

Let’s dive right into benchmarking, first off, we’ll test running through the elements of data in a dictionary or list, grabbing the value of each element, and doing some simple calculations on it. Please note, for benchmarking purposes, we actually add the coding in a loop and run it 10000000 times (const int benchmarkRuns = 10000000;) to get the result. This will give us a base percentage on how long it takes and how much faster it is for all these tests.

Looping through all elements

Let us start with looping through all the elements and doing a small calculation on the value.

METHOD 1 – For loop, list:

 for (int j = 0; j < list.Count; i++)
value = (list[j].value * 200) / 15;

METHOD 2 – Foreach loop, list:

 foreach (var result in list)
value = (result.value * 200) / 15;

METHOD 3 – For loop, dictionary:

 var result = dictionary.ToList();
for (int j = 0; j < result.Count; j++)
value = (result[j].Value * 200) / 15;

METHOD 4 – Foreach loop, dictionary:

 foreach (var result in dictionary)
value = (result.Value * 200) / 15;

METHOD 1 – Completion Time: 514ms (FASTEST)
METHOD 2 – Completion Time: 785ms (+52.7%)
METHOD 3 – Completion Time: 1876ms (+364.9%)
METHOD 4 – Completion Time: 1591ms (+309.5%)

As you can see here, method 1 is the fastest, which is a List run through a for loop. For loops are always faster then Foreach loops, hence why method 2 is a bit slower. Dictionaries are not made for constant running through all elements inside the dictionary. The problem with two is you need to first convert it to a list, then run through the values. Because of the conversion to list required to run it through a basic for loop, the time ends up being slower then running it through a simple foreach loop. In short, Lists are far better to use when running through the whole list without lookups. This makes it good for data that you know you are running through constantly. In my game, the game objects being updated and drawn should use lists, because you know you need to update all of them every frame.

There are some cases where you will want dictionaries though, so don’t let this first test fool you just yet.

————–

Finding one element

Let’s say we want to find X item in a dictionary or list, what is the best option here?

METHOD 1 – for loop, list:

for (int j = 0; j < list.Count; j++)
{
if (list[j].name == "Battlecruiser")
{
value = list[j].value;
break;
}
}

METHOD 2 – foreach loop, dictionary:

 foreach (var pair in dictionary)
if (pair.Key == "Battlecruiser") { value = pair.Value; break; }

METHOD 3 – ContainsKey, dictionary:

 if (dictionary.ContainsKey("Battlecruiser"))
value = dictionary["Battlecruiser"];

METHOD 4 – TryGetValue, dictionary

 dictionary.TryGetValue("Battlecruiser", out value);

METHOD 1 – Completion Time: 530ms (+53.1%)
METHOD 2 – Completion Time: 1419ms (+410.1%)
METHOD 3 – Completion Time: 663ms (+91.6%)
METHOD 4 – Completion Time: 346ms (FASTEST)

The best option here is to use the dictionary with TryGetValue. Method 3 is double the amount of slowness, or around, because you are doing TWO checks for “Battlecruiser”, first to get a true/false if it exists, then searching again for the value and adding it. TryGetValue will handle this for you, and return true/false if it is successful, so it’s good to add it in its own method with the value and bool return value.

A simple for loop is also okay, it’s not the fastest, but it’s still relatively fast. I didn’t include the ‘foreach’ method, as it was obviously slower, as like before when looping through all the elements.

Adding and removing seemed to be the same, time wise, around 5 seconds for 1million adds/removes. The only suggestion I have when doing something important where optimizing code is vital is storing any removed data to a second pool list/dictionary. What I mean is that instead of always creating a new object only create it when it is needed. So if you call list.Remove(ObjectToRemoveHere); you should also call listpool.Add(ObjectToRemoveHere). Before creating a new object, in your create method, check to see if there are any elements that are free first (in listpool) and use those first. If none are found, then you can directly create a new element. That’s a short summary of that though, it’s a bit more interesting when you get into the coding of that, but that’s a different topic all together.

————–

Optimizing, and Big Lists/Dictionaries performance

A couple more things to speed up the dictionary class and make it accel even more. You should typically shorten the key value instead of using long strings, what you could so is define it like so:

Dictionary dictionary = new Dictionary();

And then add data like so:

 dictionary.Add("Cor", new ShipData("Corvette", 1));
dictionary.Add("Fri", new ShipData("Corvette", 1));

…etc. So you would have a shortname, and the fullname of the object. The shortname would be used specifically for search reasons. In terms of speed, This reduces the Completion time to about 248ms, which is again, another 39.5% percent faster then using longer strings as the key when doing a TryGetValue() check. If you are strictly looking for time, then use a integer rather then a string, so you could then do:

 dictionary.Add(1111, new ShipData("Corvette", 1));
dictionary.Add(2222, new ShipData("Corvette", 1));

…etc. Again, this shortens another 23.2% off the TryGetValue() checking time, or 72% off METHOD 4 when using long strings for a total of 201ms to run. Amazing!

Does this little trick by adding a shortname work with lists? Nope! Consider this:

 class ShipData
{
public string name;
public int value;
public string shortname;
 
public ShipData(string shortname, string name, int value)
{
this.shortname = shortname;
this.name = name;
this.value = value;
}
}

And then adding the data:

 list.Add(new ShipData("Corv", "Corvette", 1));
list.Add(new ShipData("Fri", "Frigate", 2));
list.Add(new ShipData("Dest", "Destroyer", 3));

…etc

And your search query would then become:

 for (int j = 0; j < list.Count; j++)
{
if (list[j].shortname == "Bat")
{
value = list[j].value;
break;
}
}

This does not improve your time, it actually increased it a small amount, from METHOD1′s 541ms, to 592ms (+9%).

However, when using integers, the time does decrease to around 398ms (+35%), which is about double the time of a dictionary, but still very fast… For little lists! What about larger amounts of data you say?

For this example I reduced the benchmark runs to 1000000, and added 10k worth of elements in the list and dictionary. Using the fastest methods, which is either Dictionary dictionary = new Dictionary(); or ShipData with an extra ID column to search (rather then a string) The benchmark is as follows:

List – Grabbing last element: 70715ms
Dictionary – Grabbing last element: 19ms

No contest! Dictionary times destroy the lists times when searching elements. The issue is with lists, the farther it has to check in the list, the worse times you get. So if an element is in the beginning of the list, you’ll get very fast times, maybe faster then dictionary, but it will progress to become very slow within a small amount of time. With dictionaries, it doesn’t seem to matter if the data you want is from the beginning or the end in the dictionary elements, the speed is consistent, and very fast.

What about the same things, but looping through all the elements rather then grabbing only one element?

List – 79140ms
Dictionary – 198120ms

About a 250% difference when looping through all the elements. So it looks like lists defeat dictionaries when looping through all elements once again!

So as your lists or dictionaries get bigger, so will the spread between lookups vs running through all elements. Dictionaries are primary used for fast lookup in a group of elements for one specific element, and lists are better are running through all elements and doing something with each element.

A good example, let’s say in the game I am working on, would be storing the weapon base designs in a dictionary, as you will typically have to lookup elements rather constantly rather than looping through all the weapons. So typically ‘shops’ will have the IDs of the items they sell, and you lookup those to display what’s needed, and look them up when they add them to the ship for the weapon stats.

Once the weapon is on the ship (A turret), since you need to constantly update and animate the weapon/turret, it is better to use a list. You aren’t often doing single element lookups in this case, you typically update all weapons/turrets on the ship, so lists would work faster here.

If you have anything to comment, let me know! This is really based on someone new to C#, so there might be other things to add to this!

Hope this helps!

Edit: Sorry, some of the coding lost it’s format, I’ll have to fix that another time!

No related posts.