Nexus

Based on a Vladimir Bodurov blog post on IDictionary options – performance test – SortedList vs. SortedDictionary vs. Dictionary vs. Hashtable, it seems to indicate that SortedDictionary is slower during inserts as compared to Dictionary but faster during searching.

However during the course of my development in ASP.NET 3.5, there have been several occasions which seems to contradict this behaviour, perhaps it is because he is using WinForms and i’m using ASP.NET. So i took his code, did some modification for it to run several rounds and in IIS and went off from there (The source code can be found at the bottom of the page)

The test procedure is exactly the same as what he did, except since its only 2 i did 2 sets of 20, First doing SortedDictionary then Dictionary (Test result 1 to 20) and the second set doing Dictionary then SortedDictionary (Test result 21 to 40).

The averages of both set do seem to indicate negligible differences in the execution sequence.

The results are extremely interesting. Dictionary outperforms SortedDictionary on all counts! Memory usage, insertion time and search time are all much lower for Dictionary compared to SortedDictionary!

Not really sure why this is so, but if i remember correctly Dictionary uses hashes, so my best guess is it is easier to search for a hash as compared to string comparison..

Time Taken for Search

Time Taken for Insert

Memory Usage for Insert

The generated raw results from the web application

Source Code (.aspx.cs)

using System;
using System.Collections.Generic;
using System.Linq;
using System.Web;
using System.Web.UI;
using System.Web.UI.WebControls;
using System.Diagnostics;
using System.Data;

public partial class test_cittka : System.Web.UI.Page
{
protected void Page_Load(object sender, EventArgs e)
{
DataTable tbl = new DataTable();
tbl.Columns.Add(”Memory_SortedDictionary”);
tbl.Columns.Add(”Memory_Dictionary”);
tbl.Columns.Add(”Insert_SortedDictionary”);
tbl.Columns.Add(”Insert_Dictionary”);
tbl.Columns.Add(”Search_SortedDictionary”);
tbl.Columns.Add(”Search_Dictionary”);

for (int i = 0; i < 20; i++)
{
DataRow row = tbl.NewRow();
sortedDictionary = new SortedDictionary<string, string>();
dictionary = new Dictionary<string, string>();
Insert_Test(”SortedDictionary”, sortedDictionary, row, 0, 2);
Insert_Test(”Dictionary”, dictionary, row, 1,3);
Search_Test(”SortedDictionary”, sortedDictionary, row,4);
Search_Test(”Dictionary”, dictionary,row,5);
tbl.Rows.Add(row);
}
GridView gv = new GridView();
gv.DataSource = tbl;
gv.DataBind();
Page.Form.Controls.Add(gv);
}
private readonly int searchIndex = 88888;
private readonly int numberRepetition = 500000;
private SortedDictionary<string, string> sortedDictionary = new SortedDictionary<string, string>();
private Dictionary<string, string> dictionary = new Dictionary<string, string>();

private void Insert_Test(string name, IDictionary<string, string> dict, DataRow row, int idxMemory, int idxInsert)
{
Response.Write(String.Format(”<br>——–Insert {0}——–”, name));
string[] letters = { “A”, “B”, “C”, “D”, “E”, “F”, “G”, “H”, “I”, “J” };
long memoryStart = System.GC.GetTotalMemory(true);
Stopwatch watch = new Stopwatch();
watch.Start();
Random rand = new Random();
for (int i = 0; i < numberRepetition; i++)
{
string key = GetRandomLetter(letters, rand, i) + “_key” + i;
string value = “value” + i;

dict.Add(key, value);
}
long memoryEnd = System.GC.GetTotalMemory(true);
watch.Stop();
Response.Write(String.Format(”<br>Memory Allocated by {0} is: {1}bytes”,
name, memoryEnd – memoryStart));
PrintResults(watch);
row[idxMemory] = (memoryEnd – memoryStart).ToString();
row[idxInsert] = watch.ElapsedTicks.ToString();
}
private void Search_Test(string name, IDictionary<string, string> dict, DataRow row, int idx)
{
Stopwatch watch = new Stopwatch();
Response.Write(String.Format(”<br>——–Search {0}——–”, name));
watch.Start();
Response.Write(String.Format(”<br>Found:{0}”, dict["A_key" + searchIndex]));
watch.Stop();
PrintResults(watch);
row[idx] = watch.ElapsedTicks.ToString();
}
private void PrintResults(Stopwatch watch)
{
Response.Write(String.Format(”<br>Elapsed: {0}”, watch.Elapsed));
Response.Write(String.Format(”<br>In milliseconds: {0}”, watch.ElapsedMilliseconds));
Response.Write(String.Format(”<br>In timer ticks: {0}”, watch.ElapsedTicks));
}
private string GetRandomLetter(string[] letters, Random rand, int i)
{
if (i == searchIndex)
{
return “A”;
}
return letters[rand.Next(0, 10)];
}
}

This entry was posted on Thursday, April 16th, 2009 at 12:17 am and is filed under ASP.NET, Performance and. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.