C# Generic Dictionary retrieval performance benchmarks

C# Dictionary select performance benchmarks

These benchmarks are testing a Dictionary <int,string> and a  Dictionary<IUserKey, string>

In theory retrieval on a Hash Table (which is the data container inside each dictionary) should be constant regardless of number of items in the Hash Table.

The reason being is that accessing a hash table is a random access of an array element  which of the key is generated by a Hashing algorithm.

1-      Dictionary.GetItem(key)

2-      f(Key) à indexValue: random access index of value. F is the hash algorithm.

3-      Dictionary.hashtable[indexValue]

However, The problem is that the hash algorithm is not generating a unique index all the time, when it doesn’t it a collision event!

Collisions are the culprit of decrease in hash table item retrievals (long story short)

In these set of tests I am examining the different items added to dictionary an int an object and a Object with specified HashCode algorithm.

DictionaryPerfTest10Mil1Mil means that Test was ran over a dictionary filled with 10 million items and it was queried 1 million times

Int dictionary-  

  private static void IntDictPerf(int fillSize, int selectionSize)

        {

            Random random = new Random();

            Dictionary<int, string> dictHash = new Dictionary<int, string>(fillSize);

            try

            {

                for (int i = 0; i < fillSize; i++)

                {

                    dictHash.Add(i, "value" + i.ToString());

                }

            }

            catch (Exception )

            {

                System.Diagnostics.Debug.WriteLine("Collision occured");

            }

            Stopwatch stopWatch = new Stopwatch();

            stopWatch.Start();

            for (int i = 0; i < selectionSize; i++)

            {

                int index = random.Next(fillSize);

                var x = dictHash[index];

            }

            stopWatch.Stop();

            TimeSpan ts = stopWatch.Elapsed;

            string elapsedTime = String.Format("{0:00}:{1:00}:{2:00}.{3:00}",

                ts.Hours, ts.Minutes, ts.Seconds, ts.Milliseconds / 10);

            System.Diagnostics.Debug.WriteLine(elapsedTime, "RunTime");

        }

Result:

Under 200K items fetch time is almost constant above 300K to 500K it doubles and above 500K it triples.

1^st Run:

IntDictionaryPerfTest10Mil1Mil - RunTime: 00:00:00.27

IntDictionaryPerfTest1Mil1Mil - RunTime: 00:00:00.20

IntDictionaryPerfTest500K1Mil - RunTime: 00:00:00.15

IntDictionaryPerfTest300K1Mil - RunTime: 00:00:00.11

IntDictionaryPerfTest200K1Mil - RunTime: 00:00:00.06

IntDictionaryPerfTest100K1Mil - RunTime: 00:00:00.06

IntDictionaryPerfTest10K1Mil - RunTime: 00:00:00.05

IntDictionaryPerfTest1K1Mil - RunTime: 00:00:00.04

2^nd Run:

IntDictionaryPerfTest10Mil1Mil - RunTime: 00:00:00.27

IntDictionaryPerfTest500K1Mil - RunTime: 00:00:00.15

IntDictionaryPerfTest300K1Mil - RunTime: 00:00:00.09

IntDictionaryPerfTest100K1Mil - RunTime: 00:00:00.05

IntDictionaryPerfTest10K1Mil - RunTime: 00:00:00.05

IntDictionaryPerfTest1K1Mil - RunTime: 00:00:00.04

3^rd Run:

IntDictionaryPerfTest10Mil1Mil - RunTime: 00:00:00.27

IntDictionaryPerfTest1Mil1Mil - RunTime: 00:00:00.21

IntDictionaryPerfTest500K1Mil - RunTime: 00:00:00.16

IntDictionaryPerfTest100K1Mil - RunTime: 00:00:00.05

IntDictionaryPerfTest10K1Mil - RunTime: 00:00:00.05

4^th Run:

DictionaryPerfTest10Mil1Mil - RunTime: 00:00:00.27

DictionaryPerfTest1Mil1Mil - RunTime: 00:00:00.20

DictionaryPerfTest100K1Mil - RunTime: 00:00:00.05

DictionaryPerfTest10K1Mil - RunTime: 00:00:00.05

5^th Run:

DictionaryPerfTest10Mil1Mil - RunTime: 00:00:00.27

DictionaryPerfTest100K1Mil - RunTime: 00:00:00.05

DictionaryPerfTest1Mil1Mil - RunTime: 00:00:00.21

DictionaryPerfTest10K1Mil - RunTime: 00:00:00.05

6^th Run:

DictionaryPerfTest10Mil1Mil - RunTime: 00:00:00.27

DictionaryPerfTest1Mil1Mil - RunTime: 00:00:00.21

DictionaryPerfTest100K1Mil - RunTime: 00:00:00.05

DictionaryPerfTest10K1Mil - RunTime: 00:00:00.05

DictionaryPerfTest1K1Mil - RunTime: 00:00:00.04

User Key struct - Default hashcode (GetHashCode())

public interface IUserKey

    {

        int ID { get; set; }

    }

    public struct UserKey : IUserKey

    {

        public int ID

        {

            get;

            set;

        }

       // public override int GetHashCode()

        //{

        //    return this.ID.GetHashCode();

        //}

    }

private static void UserKeyDictPerf(int fillSize, int selectionSize)

        {

            Random random = new Random();

            Dictionary<IUserKey, string> dictHash = new Dictionary<IUserKey, string>(fillSize);

            try

            {

                for (int i = 0; i < fillSize; i++)

                {

                    IUserKey usr = new UserKey() { ID=i };

                    dictHash.Add(usr, "value" + i.ToString());

                }

            }

            catch (Exception )

            {

                System.Diagnostics.Debug.WriteLine("Collision occured");

            }

            Stopwatch stopWatch = new Stopwatch();

            stopWatch.Start();

            for (int i = 0; i < selectionSize; i++)

            {

                //int index = random.Next(fillSize);

                IUserKey usr = new UserKey() { ID = random.Next(fillSize) };

                var x = dictHash[usr];

            }

            stopWatch.Stop();

            TimeSpan ts = stopWatch.Elapsed;

            string elapsedTime = String.Format("{0:00}:{1:00}:{2:00}.{3:00}",

                ts.Hours, ts.Minutes, ts.Seconds, ts.Milliseconds / 10);

            System.Diagnostics.Debug.WriteLine(elapsedTime, "RunTime");

        }

DictionaryPerfTest10Mil1Mil - RunTime: 00:00:00.80

DictionaryPerfTest1Mil1Mil - RunTime: 00:00:00.47

DictionaryPerfTest100K1Mil - RunTime: 00:00:00.29

DictionaryPerfTest10K1Mil - RunTime: 00:00:00.16

DictionaryPerfTest1K1Mil - RunTime: 00:00:00.14

User Key struct - Overriden hash code

Same as the above test with the exception  of defining the HashCode method

    public struct UserKey : IUserKey

    {

        public int ID

        {

            get;

            set;

        }

        public override int GetHashCode()

        {

            return this.ID.GetHashCode();

        }

    }

DictionaryPerfTest10Mil1Mil - RunTime: 00:00:00.78

DictionaryPerfTest1Mil1Mil - RunTime: 00:00:00.48

DictionaryPerfTest100K1Mil - RunTime: 00:00:00.30

DictionaryPerfTest10K1Mil - RunTime: 00:00:00.17

DictionaryPerfTest1K1Mil - RunTime: 00:00:00.15

User Lo Key struct –

UserLoKeyDictionaryPerfTest10Mil1Mil - RunTime: 00:00:00.79

UserLoKeyDictionaryPerfTest1Mil1Mil - RunTime: 00:00:00.48

UserLoKeyDictionaryPerfTest100K1Mil - RunTime: 00:00:00.28

UserLoKeyDictionaryPerfTest10K1Mil - RunTime: 00:00:00.16

UserLoKeyDictionaryPerfTest1K1Mil - RunTime: 00:00:00.15