Weird performance results using Dictionary<>

Question

It seems that Dictionary<,> performance is affected by the size of the item being stored (which seems bizarre).

Here's my simple class:

public class MyObject
{
    public Guid Key { get; set; }
}

And two simple tests:

private long _Iterations = 1000000;

[TestMethod]
public void ShouldTestDefaultConstructorPerformance()
{
    for (var i = 0; i < _Iterations; i++)
    {
        var obj = new MyObject() { Key = Guid.NewGuid() };
    }
}

[TestMethod]
public void ShouldTestDefaultGuidDictionaryPerformance()
{
    var dict = new Dictionary<Guid, MyObject>();
    for (var i = 0; i < _Iterations; i++)
    {
        var obj = new MyObject() { Key = Guid.NewGuid() };
        dict.Add(obj.Key, obj);
    }
}

Initially I get the following timings:

ShouldTestDefaultConstructorPerformance    : 00:00:00.580
ShouldTestDefaultGuidDictionaryPerformance : 00:00:01.238

Now, I'll change MyObject class:

public class MyObject
{
    public Guid Key { get; set; }

    private Dictionary<string, string> _Property0 = new Dictionary<string, string>();
    private Dictionary<string, string> _Property1 = new Dictionary<string, string>();
    private Dictionary<string, string> _Property2 = new Dictionary<string, string>();
    private Dictionary<string, string> _Property3 = new Dictionary<string, string>();
    private Dictionary<string, string> _Property4 = new Dictionary<string, string>();
    private Dictionary<string, string> _Property5 = new Dictionary<string, string>();
    private Dictionary<string, string> _Property6 = new Dictionary<string, string>();
    private Dictionary<string, string> _Property7 = new Dictionary<string, string>();
    private Dictionary<string, string> _Property8 = new Dictionary<string, string>();
    private Dictionary<string, string> _Property9 = new Dictionary<string, string>();
}

And run the tests again:

ShouldTestDefaultConstructorPerformance    : 00:00:01.333
ShouldTestDefaultGuidDictionaryPerformance : 00:00:07.556

In the second test, the object construction takes 1.72x longer, but adding to the Dictionary takes 6.11x longer. I expected the tests to take longer, but why does the Dictionary take so much longer to add larger objects?

This tests *creation* of the objects as well as insertion into the dictionary. You haven't isolated one from the other. — dlev, Aug 25 '11 at 14:21
Not exactly a fair comparison since in the second test you're allocating `iterations* — Rudu, Aug 25 '11 at 14:21

score 1 · Answer 1 · answered Aug 25 '11 at 14:30

I think people need to read questions more carefully instead of rushing to post an answer. If you look at his sample code carefully (BOTH tests), the difference between having a MyObject with a Guid and MyObject with a Guid and 10 Dict's is under a second (object construction) for his loop. However the add dictionary accounts for at least 5 more seconds.

score 0 · Answer 2 · answered Aug 25 '11 at 14:24

0

I would think that var obj = new MyObject() { Key = Guid.NewGuid() }; this line actually takes much longer and not Add() of dictionary. Did you make measuring inside methods provided?

answered Aug 25 '11 at 14:24

Tigran

61,654
8
86
123

score 0 · Accepted Answer · answered Aug 25 '11 at 14:27

0

I think my answer would be: use a profiler and work out which bit is actually taking longer.

That'd probably highlight the instantiation. Maybe :)

answered Aug 25 '11 at 14:27

Tim Barrass

4,813
2
29
55

Yep. Ran in through SlimTune, which showed that the ctor was taking the longest amount of time. Lesson of the day: don't always believe the Duration figures shown in the VS IDE! Many thanks. – Vijay Patel Aug 26 '11 at 15:59
I'm going to come back and remind myself of this next time I do exactly the same thing :) – Tim Barrass Aug 31 '11 at 15:07

score -2 · Answer 4 · answered Aug 25 '11 at 14:21

-2

Each object you add to the dictionary is given a special unique identifier to speed up its searching and retrieval in memory. This special unique identifier (called a hash) is computed by analysing the entire content of the object. The larger the object, the slower it will be to compute the hash.

If you are interested in the fine details of how it works, check out this example from a university course: http://www.ccs.neu.edu/home/sbratus/com1101/hash-dict.html

answered Aug 25 '11 at 14:21

Jay

19,649
38
121
184

1

I thought only the Key got hashed (because that's what the Dictionay uses to work out which bucket it uses internally)? – Vijay Patel Aug 25 '11 at 14:27
-1 object is not given an unique identifier for adding to a dictionary. Hash value is not unique. Object 'size' does not affect hash computation speed directly. Do the homework – George Polevoy Aug 25 '11 at 14:31
@Vijay in your case, Key is not contributing to hash value computation. You have to override GetHashCode for this to function correctly. – George Polevoy Aug 25 '11 at 14:34
Since MyObject is a class that isn't true: http://stackoverflow.com/questions/720177/default-implementation-for-object-gethashcode/720282#720282 – Rag Aug 25 '11 at 14:36
@Brian it's ok for writing a green test, not more. Not overriding the GetHashCode function, you are braking the contract of a hash based collection. As performance is in question, it's also worth mentioning that algorithmic time of hash based insert and lookup is broken too – George Polevoy Aug 25 '11 at 14:56
@George I was addressing Jacob, pointing out that it's not true that GetHashCode analyzes the entire content of the object. – Rag Aug 25 '11 at 15:18

Weird performance results using Dictionary<>

4 Answers4