Why is python dict creation from list of tuples 3x slower than from kwargs

dict(**kwargs) passes in a ready-made dictionary, so Python can just copy an already existing internal structure.

A list of tuples, on the other hand, requires iteration, validation, hashing and slotting the results into a fresh, empty table. That's not nearly as fast.

A Python dictionary is implemented as a hash table, and is grown dynamically as keys are added over time; they start small and as the need arises a new, larger hash table is constructed, data (keys, values and hashes) are copied across. That’s all invisible from Python code but resizing takes time. But when you use dict(**kwargs) (or dict(other_dict) CPython (the default Python implementation you used to test with) can take a shortcut: start with a hash table that’s big enough immediately. You can’t do that same trick with a sequence of tuples, because you can’t know up front if there won’t be duplicate keys in the sequence.

For more details, see the C source code of the dict type, specifically dict_update_common implementation (which is called from dict_init()); this calls either PyDict_MergeFromSeq2() for the sequence-of-tuples case, or calls PyDict_Merge() when keyword arguments are passed in.

The PyDict_MergeFromSeq2() function iterates over the sequence, tests each result to make sure there are two elements, then essentially calls .__setitem__(key, value) on the dictionary. This may need to resize the dictionary at some point!

The PyDict_Merge() function (via dict_merge()) specifically detects if a regular dictionary was passed in, then executes a fast path that resizes the internal structures once, and then copies across the hashes and structure from the original dictionary directly using insertdict() calls (follow the override == 1 path, as override has been set to 1 when the target dictionary is empty, which is always the case for dict(**kwargs)). Just resizing once and using internal data directly is a lot faster, far less work needs to be done!

All of this is an implementation detail specific to CPython. Other Python implementations such as Jython, IronPython and PyPy can make their own decisions on how the internals of the dict type work, and will show different performance differences for the same operations.

Short answer (TL;DR)

This is because in the first test the CPython implementation of dict will create a new dict from the list, but the second only copies the dictionary. Copying takes less time than parsing the list.

Additional info

Consider this code:

import dis
dis.dis("dict([('foo', 1), ('bar', 'bar'), ('baz', 100)])", depth=10)
print("------------")
dis.dis("dict({'foo': 1, 'bar': 'bar', 'baz': 100})", depth=10)

Where

The dis module supports the analysis of CPython bytecode by disassembling it.

Which lets us see the bytecode operations performed. Output shows

  1           0 LOAD_NAME                0 (dict)
              2 LOAD_CONST               0 (('foo', 1))
              4 LOAD_CONST               1 (('bar', 'bar'))
              6 LOAD_CONST               2 (('baz', 100))
              8 BUILD_LIST               3
             10 CALL_FUNCTION            1
             12 RETURN_VALUE
------------
  1           0 LOAD_NAME                0 (dict)
              2 LOAD_CONST               0 (1)
              4 LOAD_CONST               1 ('bar')
              6 LOAD_CONST               2 (100)
              8 LOAD_CONST               3 (('foo', 'bar', 'baz'))
             10 BUILD_CONST_KEY_MAP      3
             12 CALL_FUNCTION            1
             14 RETURN_VALUE

From the output you can see:

1. Both calls need to load the dict name that is going to be called.
2. After that, the first method loads a list to memory (BUILD_LIST) whereas the second builds a dictionary (BUILD_CONST_KEY_MAP) (see here)
3. For that reason, when the dict function is called (the CALL_FUNCTION step (see here)), it takes much shorter in the second case, because the dictionary has been already created so it simply makes a copy instead of having to iterate over the list to create a hash table.

Note: with the bytecode you can't conclusively decide that CALL_FUNCTION does that, since its implementation is written in C and only by reading it you can actually know that (see Martijn Pieters' answer for an accurate explanation on how this part works). However, it helps see how the dictionary object is already created outside dict() (step-wise, not syntactically-wise in the example), while as for the list, this is not the case.

Edit

To be clear, when you say

There are a couple of ways to construct a dictionary in python

It is true that by doing:

dkwargs = {'foo': 1, 'bar': 'bar', 'baz': 100}

You are creating a dictionary, in the sense that the interpreter transforms an expression into a dictionary object stored in memory, and makes the variable dkwargs point to it. However, by doing: dict(**kwargs) or if you prefer dict(kwargs), you are not really creating a dictionary, but just copying an already existing object (and it's important to emphasise copying):

>>> dict(dkwargs) is dkwargs
False

dict(kwargs) forces Python to create a new object; however, that does not mean it has to re-build the object. In fact, that operation is useless because in practice they are equal objects (though not the same object).

>>> id(dkwargs)
2787648914560
>>> new_dict = dict(dkwargs)
>>> id(new_dict)
2787652299584
>>> new_dict == dkwargs
True
>>> id(dkwargs) is id(new_dict)
False

Where id:

Return the “identity” of an object. This is an integer which is guaranteed to be unique and constant for this object during its lifetime [...]

CPython implementation detail: This is the address of the object in memory.

Unless, of course, you want to specifically duplicate the object in order to modify one so edits are not linked to the other reference.

dkwargs is already a dictionary so you basically make a copy of it. That is why it is so much faster.