Why is OrderedDict() ~10x slower than dict() and list()?

Question

Just run the tests below and noticed that filling an OrderedDict() is roughly an order of magnitude slower than filling a dict() or a list().

Why?

# list()
In [1]: timeit test_list()
1000 loops, best of 3: 298 us per loop

# dict()    
In [3]: timeit test_dict()
1000 loops, best of 3: 269 us per loop

# dict()    
In [3]: timeit test_ord_dict()                                                  
100 loops, best of 3: 1.77 ms per loop

with:

def test_ord_dict():
  a = OrderedDict()
  for el in xrange(1000):
    a[el] = np.random.randint(100)
  return a

def test_dict():
  a = dict()
  for el in xrange(1000):
    a[el] = np.random.randint(100)
  return a

def test_list():
  a = list()
  for el in xrange(1000):
    a.append(np.random.randint(100))
  return a

Answer 1

OrderedDict is implemented in pure Python, so here's the relevant part of the source:

def __setitem__(self, key, value, dict_setitem=dict.__setitem__):
    'od.__setitem__(i, y) <==> od[i]=y'
    # Setting a new item creates a new link at the end of the linked list,
    # and the inherited dictionary is updated with the new key/value pair.
    if key not in self:
        root = self.__root
        last = root[0]
        last[1] = root[0] = self.__map[key] = [last, root, key]
    return dict_setitem(self, key, value)

If the key doesn't exist, you'll be creating a new list and accessing two items from a list, which will slow things down.

Answer 2

Two reasons:

1. An OrderedDict, by definition, has to do more work than a dict.

2. (much more importantly) OrderedDict is written in Python, while dict and list are written in C.