Introduction
Note 1: This is an edited version of a full Jupyter Notebook which you can use to follow along with the calculations.
Note 2: All the timings are for CPython 3.9.7 on Intel MacBook Pro (16-inch, 2019)
There are several ways to look up a value in a dictionary in Python.
dictionary = {'known': 'value'}The most obvious way is straight indexing:
key = 'known'
value = dictionary[key]But what if we don’t know if the dictionary contains the key, and we’d like to get a default value if it isn’t?
key = 'unknown'
value = dictionary[key] # will cause an errorSo, we could do this
if key in dictionary:
value = dictionary[key]
else:
value = 'default'But dictionaries also have a .get() method which does basically the same thing. It will return default if the dictionary doesn’t contain the key. If default is not supplied, dictionary.get(key) returns None.
dictionary.get('known', 'default')
'value'dictionary.get('unknown', 'default')
'default'dictionary.get('unknown') is None
TrueI have spotted a pattern where people start using .get() all the time, instead of ever indexing. I think this might be because they feel it’s “safer” – it will never raise an exception. But once you start getting into that habit you forget about using in to check if a key is in a dictionary and you start to do things like this:
def get_if_value_is_none(dictionary, key):
value = dictionary.get(key)
# assuming None wasn't in the dictionary to begin with
if value is not None: # effectively check if key was in dictionary
return value
# expensive operation to perform if key was not in dictionaryNote The code above will only work as designed if the dictionary doesn’t actually contain a None. You might also check using if value, but this is even worse as it will also fail if the actual value you’re looking for is another falsey value (like [] or 0), see for example this video where a pytest slowdown was caused by this exact problem. I’ve linked to the time where that code is on the screen.
I commented on that video about using the in pattern instead and Anthony replied “using in is a common performance mistake — it forces you to use two lookups to retrieve the value rather than just one”
This is pretty clear if you compare the code – you’re doing all the hashing and lookup just once with .get() but with the in check you might need to do it twice:
def in_then_index(dictionary, key):
if key in dictionary: # first lookup
return dictionary[key] # second possible lookup
# expensive operation to perform if key was not in dictionaryEven though the original version with the get and the check for None is really the thing I don’t like, I’ll also do a version with get only.
def only_get(dictionary, key):
return dictionary.get(key)Basic benchmarking
So, I did a quick benchmark. Remember
dictionary = {'known': 'value'}%%timeit
get_if_value_is_none(dictionary, "known")
140 ns ± 1.3 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)%%timeit
get_if_value_is_none(dictionary, "unknown")
130 ns ± 1.99 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)%%timeit
only_get(dictionary, "known")
109 ns ± 5.8 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)%%timeit
only_get(dictionary, "unknown")
108 ns ± 4.62 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)%%timeit
in_then_index(dictionary, "known")
102 ns ± 2.01 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)%%timeit
in_then_index(dictionary, "unknown")
83.2 ns ± 0.845 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)I mentioned in the video comments that my benchmarks didn’t show get to be faster. Anthony doubted the validity of my benchmaks:
I suspect your benchmarking is incorrect. also for caches the hot case is going to be hits (you tend to optimize for success rather than failure). I also suspect you’re not considering fill size or collision rate in your benchmark. there is a third approach which is even faster via
try: ... except KeyError: ...which I usually choose
I think he’s talking about this as a pattern
def try_index_except(dictionary, key):
try:
return dictionary[key]
except KeyError:
pass # or return default%%timeit
try_index_except(dictionary, "known")
91.3 ns ± 1.12 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)%%timeit
try_index_except(dictionary, "unknown")
265 ns ± 7.53 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)It’s worth remembering that there is some overhead associated with calling a function in the first place, even if you just return
def function_call(dictionary, key):
return%%timeit
function_call(dictionary, "known")
69.3 ns ± 0.68 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)Basic benchmark plotted
Let’s see what that looks like on a chart, where we can view the trade-offs of a known key vs an unknown key with the function call overhead
We see that just doing key in dictionary (at the 0 chance part of in_then_index) is not that much slower than calling a function and returning. Let’s see what the timings look like with that function call overhead subtracted. I’d also like to insulate these results from differences on machines, so I’m going to normalise by that function call overhead.
From these simple results it seems like we can make the following preliminary observations:
getcombined with the is None check is never faster thaninfollowed by indexing, even when you do bothinand indexing.- A straight return dictionary.get(value) is a bit better but still slower than in and indexing most of the time
- The cost of raising an exception is so high that you’ve got to be very sure that the key is almost always (more than 90%) in the dictionary, but if you are it is the fastest to try to index and then handle the exception if the key is not found.
I will admit that testing this on a dictionary containing only one key is not the best benchmark. There probably aren’t key collisions here and we’re not checking for fill rate.
Also, Python has a special case fast path for dictionaries which have only string keys (see here), so we expect string dictionaries to be faster than heterogenous ones, and both of those to be faster if the keys are built-in objects than if they are custom objects. See also this stackoverflow question about slow lookups for custom objects.
Non-string dictionary keys
So, let’s try some other kinds of keys We know Python uses a super fast method for hashing ints – they just hash to themselves, so we expect this to be pretty quick too.
Lastly, let’s try to create a new hashable class. To make a class hashable, you need to implement __hash__ and __eq__
class CustomHashable:
def __init__(self, v):
self.v = v
def __hash__(self):
return hash(self.v)
def __eq__(self, other):
return self.v == other.v
def __repr__(self):
return f"CustomHashable({self.v!r})"known = CustomHashable('known')
unknown = CustomHashable('unknown')
df_cust = bench(
dictionary={known: 1},
lookups=((known, 1), (unknown, 0)),
)
So we have found a place where get is better, even with that value check! We’re clearly paying the cost of calculating that hash twice in the in_then_index method.
What about defaultdict?
Since I posted this, a few people have asked me to look at collections.defaultdict. I was totally blown away by the results. For string keys, defaultdict with just normal indexing is the clear winner.
For the case with a custom class, there’s something weird going on:
I’ve re-run this benchmark a couple of times and tried to understand why this is happening, but in this particular case it seems when using a defaultdict, it is somehow faster to do the access in a try block than just normally index. If you’re thinking (like I did at first) that somehow the data for try_index_except and only_index just got swopped, remember for the defaultdict we’re never raising an exception.
Effect of dictionary size
I tried to build dictionaries up to 30 million items in length with unique random strings of 20 character length.
At least for string keys, none of the calls seem to be affected by the size of the dictionary in a way that changes the ordering of the times. Might become an issue at even larger sizes, but I don’t often have 30 million-key dictionaries in my Python code.
Deeper dive
Let’s get a bit more sophisticated about the dictionary and the keys. We’ll build a list of values to look up in a dictionary which has a given fraction of values that are in the dictionary. Note that we’re using strings here. There may be differences in timings due to key collision chances.
def setup(dict_size, lookups, chance_of_dict_hit, string_length):
dictionary = {random_string(string_length): 1 for _ in range(dict_size)}
knowns = list(dictionary)
n_known = int(lookups*chance_of_dict_hit)
n_unknown = lookups - n_known
lookup_list = random.choices(knowns, k=n_known)
lookup_list += [random_string(string_length) for _ in range(n_unknown)]
random.shuffle(lookup_list)
return dictionary, lookup_listI’ve played around with most of the parameters here, and mostly the results later on are dependent of the chance of a dictionary hit.
Time all the things
I then went on a mission to time all the parts of the process which might be pertinent. You should check the notebook for the actual code. The basic setup is always the same – run through the lookup items and do some kind of operation. I’m doing more than one lookup in each function call to reduce the overhead of a function call on the timing.
You can imagine that if the dictionary always contains the key, the in + index method will be at its slowest due to the double lookup. Let’s see how the chance of a hit affects timing.
We see that in this more realistic test, the results are qualitatively the same. get is never the best option and in followed by indexing is the best for almost all cases, except when we are very sure that the key will be in the index (again it starts winning aroung 90%). I haven’t done it but I’d expect defaultdict to continue being better than all comers here.
What is going on here?
We are also now ready to understand why this is the case. The first thing to understand is that Python handles dictionaries with string indexes through dedicated code. Another thing to understand is that it takes quite a bit of time for Python to look up the name of .get in the dictionary’s namespace.
In the following plot, get_name_lookup is the time to do get = dictionary.get, while get_cached does get = dictionary.get outside the lookup loop and uses value = get(key) inside the loop. This name lookup effect explains part of the reason why in is faster. I’ve also added the time it takes to do key in dictionary as in_only. This shows that the name lookup is approximately the same as looking up a value in a dictionary, which is expected since object names are stored in dictionaries. Lastly, I’ve added the time it takes to call hash(key).
A fascinating observation here is that it takes less time to do key in dictionary than it does to do hash(key). How can this be? The answer is that the string dictionary code calls hash on the C side. You can clearly see the effect of doing this hashing twice – the graph moves up and to the right, but the cost is much less than you’d imagine because key in dictionary and dictionary[key] both have dedicated bytecodes, so the Python interpreter doesn’t pay the price of calling a Python function twice. This unpacks most of the mystery here.
My final conclusions in the larger case are unchanged from the toy case:
- If you have control over the construction of your dictionaries and you’re thinking there’s a good chance that missing values will need to be handled, use defaultdict.
- If you are using string or int keys, it’s always faster to do
infollowed by indexing than to do.get()followed by checking if the default was returned. - The only exception to this rule is if you are almost certain that the key will be in the dictionary, in which case, indexing and handling the exception is (marginally) faster.
.get()is better if you are using custom objects which don’t benefit from the fast paths in Python for hashing and lookup. The performance is similar enough for string types that I’d recommend using get() when you actually want to use the value later in the code.
I couldn’t find any size of dictionary with string keys where .get() was the fastest option.
So, .get() is perfectly fine for saving code when doing value = dictionary.get(key, default) . Just don’t get in the habit of using it everywhere – it’s not saving you any time.
Leave a Reply