Why is it faster to check if dictionary contains the key, rather than catch the exception in case it doesn't?

C#PerformanceDictionary

C# Problem Overview


Imagine the code:

public class obj
{
    // elided
}

public static Dictionary<string, obj> dict = new Dictionary<string, obj>();

Method 1

public static obj FromDict1(string name)
{
    if (dict.ContainsKey(name))
    {
        return dict[name];
    }
    return null;
}

Method 2

public static obj FromDict2(string name)
{
    try
    {
        return dict[name];
    }
    catch (KeyNotFoundException)
    {
        return null;
    }
}

I was curious if there is a difference in performance of these 2 functions, because the first one SHOULD be SLOWER than second one - given that it needs to check twice if the dictionary contains a value, while second function does need to access the dictionary only once but WOW, it's actually opposite:

Loop for 1 000 000 values (with 100 000 existing and 900 000 non existing):

> first function: 306 milliseconds > > second function: 20483 milliseconds

Why is that?

EDIT: As you can notice in comments below this question, the performance of second function is actually slightly better than first one in case there are 0 non existing keys. But once there is at least 1 or more non existing keys, the performance of second one decrease rapidly.

C# Solutions


Solution 1 - C#

On the one hand, throwing exceptions is inherently expensive, because the stack has to be unwound etc.
On the other hand, accessing a value in a dictionary by its key is cheap, because it's a fast, O(1) operation.

BTW: The correct way to do this is to use TryGetValue

obj item;
if(!dict.TryGetValue(name, out item))
    return null;
return item;

This accesses the dictionary only once instead of twice.
If you really want to just return null if the key doesn't exist, the above code can be simplified further:

obj item;
dict.TryGetValue(name, out item);
return item;

This works, because TryGetValue sets item to null if no key with name exists.

Solution 2 - C#

Dictionaries are specifically designed to do super fast key lookups. They are implemented as hashtables and the more entries the faster they are relative to other methods. Using the exception engine is only supposed to be done when your method has failed to do what you designed it to do because it is a large set of object that give you a lot of functionality for handling errors. I built an entire library class once with everything surrounded by try catch blocks once and was appalled to see the debug output which contained a seperate line for every single one of over 600 exceptions!

Attributions

All content for this solution is sourced from the original question on Stackoverflow.

The content on this page is licensed under the Attribution-ShareAlike 4.0 International (CC BY-SA 4.0) license.

Content TypeOriginal AuthorOriginal Content on Stackoverflow
QuestionPetrView Question on Stackoverflow
Solution 1 - C#Daniel HilgarthView Answer on Stackoverflow
Solution 2 - C#Ed HermansonView Answer on Stackoverflow