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.
1st 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
2nd 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
3rd 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
4th 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
5th 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
6th 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
