How can I measure the performance of a HashTable in C#?

Question

Hello everyone,

I am playing around with C# collections and I have decided to write a quick test to measure the performance of different collections.

My performance test goes like this:

int numOps= (put number here);
long start, end, numTicks1, numTicks2;
float ratio;

start = DateTime.Now.Ticks;

for(int i = 0; i < numOps; i++)
{
  //add two elements to collection #1
  //remove one element from collection #1
}

end = DateTime.Now.Ticks;

numTicks1 = end - start;


start = DateTime.Now.Ticks;

for(int i = 0; i < numOps; i++)
{
  //add two elements to collection #2
  //remove one element from collection #2
}

end = DateTime.Now.Ticks;

numTicks2 = end - start;

ratio = (float)numTicks2/(float)numTicks1;

Then I compare the ratio value using different Collections and different values for numOps to see how they compare.

The problem is sometimes when I use a small enough number (numOps = 500), the test results between a Hashtable and List are sporadic (in other words it's a coin flip which one is faster). Can anyone explain why this is?

EDIT: Thanks everyone! Stopwatch works like a charm.

Answer 1

try taking a look at StopWatch class instead of using DateTime

this example straight out of MSDN

    Stopwatch stopWatch = new Stopwatch();
    stopWatch.Start();
    Thread.Sleep(10000); //your for loop
    stopWatch.Stop();
    // Get the elapsed time as a TimeSpan value.
    TimeSpan ts = stopWatch.Elapsed;

    // Format and display the TimeSpan value.
    string elapsedTime = String.Format("{0:00}:{1:00}:{2:00}.{3:00}",
        ts.Hours, ts.Minutes, ts.Seconds,
        ts.Milliseconds / 10);
    Console.WriteLine(elapsedTime, "RunTime");

Answer 2

I would start by trying out a higher resolution timer.

There are quite a few questions and answers about timers already on SO.

Here's one answer that has a list of options available to you.

In particular, check out System.Diagnostics.Stopwatch.

Answer 3

The proper way to time things diagnostically is to run the code many times iteratively (so that the total time is many multiples of the resolution of whatever timing mechanism you use) and then divide by the number of iterations to get an accurate time estimate.

Stopwatch returns times that are not quantized by 15 ms, so it's obviously more appropriate for timing events.

Answer 4

I used the following code to test the performance of a Dictionary using three different GetHash implementations:

    class TestGetHash
    {
        class First
        {
            int m_x;
        }
        class Second
        {
            static int s_allocated = 0;
            int m_allocated;
            int m_x;
            public Second()
            {
                m_allocated = ++s_allocated;
            }
            public override int GetHashCode()
            {
                return m_allocated;
            }
        }
        class Third
        {
            int m_x;
            public override int GetHashCode()
            {
                return 0;
            }
        }

        internal static void test()
        {
            testT<First>(100, 1000);
            testT<First>(1000, 100);
            testT<Second>(100, 1000);
            testT<Second>(1000, 100);
            testT<Third>(100, 100);
            testT<Third>(1000, 10);
        }

        static void testT<T>(int objects, int iterations)
            where T : new()
        {
            System.Diagnostics.Stopwatch stopWatch = System.Diagnostics.Stopwatch.StartNew();
            for (int i = 0; i < iterations; ++i)
            {
                Dictionary<T, object> dictionary = new Dictionary<T, object>();
                for (int j = 0; j < objects; ++j)
                {
                    T t = new T();
                    dictionary.Add(t, null);
                }
                for (int k = 0; k < 100; ++k)
                {
                    foreach (T t in dictionary.Keys)
                    {
                        object o = dictionary[t];
                    }
                }
            }
            stopWatch.Stop();
            string stopwatchMessage = string.Format("Stopwatch: {0} type, {1} objects, {2} iterations, {3} msec", typeof(T).Name, objects, iterations, stopWatch.ElapsedMilliseconds);
            System.Console.WriteLine(stopwatchMessage);

            stopWatch = System.Diagnostics.Stopwatch.StartNew();
            for (int i = 0; i < iterations; ++i)
            {
                Dictionary<T, object> dictionary = new Dictionary<T, object>();
                for (int j = 0; j < objects; ++j)
                {
                    T t = new T();
                    dictionary.Add(t, null);
                }
            }
            stopWatch.Stop();
            stopwatchMessage = string.Format("Stopwatch (fill dictionary): {0} type, {1} objects, {2} iterations, {3} msec", typeof(T).Name, objects, iterations, stopWatch.ElapsedMilliseconds);
            System.Console.WriteLine(stopwatchMessage);

            {
                Dictionary<T, object> dictionary = new Dictionary<T, object>();
                for (int j = 0; j < objects; ++j)
                {
                    T t = new T();
                    dictionary.Add(t, null);
                }
                stopWatch = System.Diagnostics.Stopwatch.StartNew();
                for (int i = 0; i < iterations; ++i)
                {
                    for (int k = 0; k < 100; ++k)
                    {
                        foreach (T t in dictionary.Keys)
                        {
                            object o = dictionary[t];
                        }
                    }
                }
                stopWatch.Stop();
                stopwatchMessage = string.Format("Stopwatch (read from dictionary): {0} type, {1} objects, {2} iterations, {3} msec", typeof(T).Name, objects, iterations, stopWatch.ElapsedMilliseconds);
                System.Console.WriteLine(stopwatchMessage);
            }
        }
    }