Performance testing of Dictionary - List - Hashtable

Still working with high-volume realtime datafeeds, I'm struggling to understand where the bottleneck in my code is. It's not with the database, it's not with the network - it's somewhere in the code. Now that doesn't help a lot.

So I decided to have a look at the different data structures that could be usable for my needs. Right now I'm using a List to keep track of my orders, and each time I get a new order, I check that list for the given ID.

So I'm starting to wonder, maybe there is a performance issue with the List data structure. So I made a small test with the following code:

static void TestList()

{

var watch = new Stopwatch();

var theList = new List<int>();

watch.Start();

//Fill it

for (int i = 0; i <>

{

theList.Add(i);

}

watch.Stop();

Console.WriteLine("Avg add time for List: {0}", (watch.Elapsed.TotalMilliseconds / noOfIterations));

watch.Reset();

watch.Start();

//Test containsKey

for (int j = 0; j <>

{

theList.Contains(j);

}

watch.Stop();

Console.WriteLine("Avg Contains lookup time for List: {0}", (watch.Elapsed.TotalMilliseconds / noOfIterations));

}

I created similar test code for Dictionary and HashSet. In all of the tests I used a loop where the given key always existed in the data structure. I used Add instead of Insert, because of tests I've seen online show that this is much faster. For example, this one.

First run, I used 1,000 for the noOfIterations variable and ran it three times.

The horizontal scale here is in milliseconds, so things are reasonably fast. A value of 0.2 gives you a possible 200 adds per second. As you probably can see without checking the numbers, dictionary is faster. List is slower for lookup, but HashSet suprises a little with the slow add function. So what happens when we go to 100,000 items?

OK, List is a lot slower for lookup still. Add seems to compare ok though. Let's see how it compares if we remove the lookup-time from the chart: