performance of two Dictionary retrievals vs one key retrieval

Question

I have this legacy code where there's often this pattern of a dictionary of string to dictionary of string to some object.

Dictionary<string, Dictionary<string, someobject>>

retrieval of an object is then always based on two times TryGetValue

Dictionary<string, Dictionary<string, Dealer>> dicDealers ...

if (dicDealers.TryGetValue(lab, out dealers))
  dealers.TryGetValue(dealerNumber, out dealer);

Now I was thinking it should be more efficient when the two string keys are combined into a key struct with two string members so the objects get retrieved in one go. So I created a Key struct which overrides GetHashCode and Equals calculating a hash on bots key members.

public struct Key<T>
{
    private T mKey1;
    private T mKey2;

    public Key(T t, T u)
    {
        mKey1 = t;
        mKey2 = u;
    }

    public override bool Equals(object obj)
    {
        if (obj == null) return false;

        Key<T> rhs = (Key<T>)obj;

        return mKey1.Equals(rhs.mKey1) && mKey2.Equals(rhs.mKey2);
    }

    public override int GetHashCode()
    {
        int hash = 17;

        hash = ((hash << 5) - hash) + mKey1.GetHashCode();
        hash = ((hash << 5) - hash) + mKey2.GetHashCode();
        return hash;
    }
}

Now you can do it at once.

Key<string> key = new Key<string>(lab, dealerNumber);

if (dicDealers.TryGetValue(key, out someobject))
{
...
}

I thought it should be faster but it turns out both ways are about as fast. How can that be? Can I do something to make the second technique run faster?

Is there a performance problem? If not, then prioritize readability, it might make sense to encapsulate the Directory in a new class with method to retrieve items, so you don't have to litter the code with TryGetValue calls. — Jesper Fyhr Knudsen, Dec 16 '13 at 11:26
it was also for readability yes but thats not the issue here — Serve Laurijssen, Dec 16 '13 at 11:28
I have noticed that instead of keeping multiple nested dictionaries, using a `new key = key1 + "-" + key2` is easy to maintain. You have to carefully choose your separator. — Akash Kava, Dec 16 '13 at 11:50

score 7 · Accepted Answer · edited May 23 '17 at 12:03

You are trying to improve a method that has amortized O(1) complexity. That's a tall task, you can never get more efficient than O(1), there is no algorithm that is O(1/x).

The only thing you could improve is the Oh. A dictionary's Oh is determined by the cost of GetHashCode() and how well the hash code is distributed. You are again fighting a battle that's very hard to win. String.GetHashCode() is written in hand-optimized code and produces a very good hash.

And you did not in fact make your GetHashCode() more efficient, it costs the same as two GetHashCode() calls in the original version. So yes, you certainly should expect your version to take as much time.

Trying to produce a better version is a long shot. You'd have to have special knowledge of the strings, like knowing that only the 1st character is required for a good hash so you can take a shortcut on calculating the hash on the entire string. That's uncommon and a bit dangerous, a poor hash code distribution is detrimental. Most of all, it is not necessary. The core mistake you made was trying to improve code that didn't require improvement. Only ever consider doing this when a profiler told you that TryGetValue() is the critical code.

I left the part out that it was also for readability. But ok, optimizing O(1) is pretty hard yeah — Serve Laurijssen, Dec 16 '13 at 11:52

performance of two Dictionary retrievals vs one key retrieval

1 Answers1