Home > ASP.NET, Performance > Performance of Generics SortedDictionary and Dictionary

Performance of Generics SortedDictionary and Dictionary

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 Search

Time Taken for Insert

Time Taken for Insert

Memory Usage for Insert

Memory Usage for Insert

The generated raw results from the web application

Test Memory Insert (Time taken in Ticks) Search (Time taken in Ticks)
SortedDictionary Dictionary SortedDictionary Dictionary SortedDictionary Dictionary
1 53919472 53376100 48921833 13100780 488 132
2 53919484 53376100 47371977 12744252 647 72
3 53919468 53376088 47386173 12994452 209 69
4 53919340 53376124 47428627 15464752 239 71
5 53919484 53376112 47508765 13040552 211 68
6 53919644 53376100 48597956 13617493 216 71
7 53919484 53376100 49073226 13166390 404 71
8 53919484 53376100 48807615 13104169 229 69
9 53919484 53376088 48633159 12904931 278 89
10 53919484 53376088 49147736 13043290 243 72
11 53919484 53376100 48755009 12901049 221 68
12 53919484 53376100 48720694 12851970 216 65
13 53919484 53376088 48968614 13938456 278 76
14 53919484 53376124 47349876 13072479 232 69
15 53917592 53376112 47436475 13217946 374 263
16 53919496 53376100 47271521 12936580 279 85
17 53919484 53376088 49116031 14775245 228 64
18 53919496 53376076 47675434 13543449 258 79
19 53919496 53376088 47454095 13330955 219 62
20 53919484 53376100 49053229 12932112 236 73
Average (Set 1) 53919390.6 53376098.8 48233902.25 13334065.1 285.25 84.4
21 53919496 53376052 35231348 9248780 245 108
22 53919544 53376064 35237264 8211268 183 312
23 53919544 53376052 35354053 8161178 170 82
24 53919516 53376040 35166182 8433640 248 117
25 53919984 53376000 35340838 8559027 161 92
26 53919532 53376064 35446193 8515937 190 87
27 53919532 53376040 35425444 8307412 301 89
28 53919484 53376124 35207419 8468252 173 88
29 53919532 53376064 35275126 8100160 326 193
30 53919532 53376064 35484239 8119661 188 86
31 53919532 53376064 35604412 8484580 180 82
32 53919532 53376052 35550023 8283421 247 108
33 53919532 53376076 35213423 8398157 187 85
34 53919484 53376136 35264521 8527381 183 89
35 53919484 53376136 35383377 8723896 179 84
36 53919484 53376100 35232178 8567521 162 83
37 53919544 53376064 35054454 8132677 174 80
38 53919532 53376052 35188672 8193882 184 86
39 53919496 53376136 35265145 8709565 179 103
40 53919532 53376064 35123234 8095966 199 87
Average (Set 2) 53919542.4 53376072.2 35302377.25 8412118.05 202.95 107.05
Average 53919466.5 53376085.5 41768139.75 10873091.58 244.1 95.725

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)];
}
}

Advertisements
Categories: ASP.NET, Performance
  1. April 17, 2009 at 3:51 am

    There might be one problem with your test. You always process SortedDictionary before Dictionary. If you read the description of my tests I have tried those in different order and what is more important each was performed separately. When you start performing operations on the SortedDictionary you initiate actions of the virtual machine related to large memory allocation and then when you reach the Dictionary the hard work is already done. I would encourage trying the same experiment in different order. But it is true that my test was with .NET 2.0 so it may have changed in 3.5.

  2. cittka
    April 17, 2009 at 3:57 am

    Hi Vald,

    Perhaps i was not clear in my posting, i’ve actually did 2 sets of testing.

    The first set of 20 tests, initializes SortedDictionary and then initializes Dictionary.
    The next set of 20 tests, initializes Dictionary and then SortedDictionary.

    Actually in my case, the large memory allocations are done each time they are run (because i instantiate new instances of each object)

  3. Vlad
    April 20, 2009 at 4:51 pm

    Yes true I missed that. I will rerun my tests on 3.5 when I get some time later this week.

  4. Chen Noam
    June 11, 2013 at 1:16 pm

    Hi,

    I think that it’s better not to involve this test with DataTable, since it can change your testing results.
    We’ve changed our ASP.Net 3.5 application to use Dictionary (from List), which made it run faster in about 15% and than we’ve tested the SortedDictionary that helped us with another 15%.

    Sorry, I think that the SortedDictionary is faster than Dictionary.

    Best regards,
    Chen

    • June 11, 2013 at 11:14 pm

      Whether or not sorteddictionary is faster than dictionary depends on the use case.

      I can list out cases where one is faster than the other and also easily list out cases where the opposite is true

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: