Consider the following code:

$ cat x.py
from collections import OrderedDict
class X:
    def items(self):
        print('items')
        return []
    def keys(self):
        print('keys')
        return []

print(dict(X()))
print(OrderedDict(X()))

When I run it under python 3.4, I get

$ python3.4 x.py
keys
{}
keys
OrderedDict()

but under python 3.5, I get

$ python3.5 x.py
keys
{}
items
OrderedDict()


Under 3.4 both dict and OrderedDict constructors call the keys() method of the underlying object (and then call __getitem__ repeatedly if keys() returns a non-empty list), but in 3.5 OrderedDict behavior changed and it calls the values() method instead.

This does need to be fixed.  

FWIW, here is the relevant docstring from MutableMapping:
        ''' D.update([E, ]**F) -> None.  Update D from mapping/iterable E and F.
            If E present and has a .keys() method, does:     for k in E: D[k] = E[k]
            If E present and lacks .keys() method, does:     for (k, v) in E: D[k] = v
            In either case, this is followed by: for k, v in F.items(): D[k] = v
        '''

Submit a patch to fix this. Hope it helps.

I think this case (fast path for exact dict) is not needed at all. Exact dict is not ordered, and OrderedDict created from exact dict has nondetermined order (unless a dict has size 0 or 1).

I didn't think about order. I just thought using concrete API may be faster. But after your comment, I tested the performance and it seems PyDict_Items makes it much slower (it does more work, eg, make tuples). So I agree it is not needed at all.

I write a new version restoring the fast path for dict. It now uses PyDict_Next and seems to be much faster than the path using keys.

[cpython]$ ./python -m timeit -s 'from collections import OrderedDict; d = {"a":1,"c":2,"b":3,"d":4}' 'OrderedDict(d)'
1000000 loops, best of 3: 0.639 usec per loop
[cpython]$ ./python -m timeit -s 'from collections import OrderedDict; d = {"a":1,"c":2,"b":3,"d":4}' 'OrderedDict(d)'
1000000 loops, best of 3: 0.372 usec per loop

After totally studying OrderedDict, I get a better understanding of what Serhiy means. So although we can get a better performance for dict, it's not needed at all. Remove the v3 patch.

New changeset 70758c12e888 by Eric Snow in branch 'default':
Issue #27576: Fix call order in OrderedDict.__init__().
https://hg.python.org/cpython/rev/70758c12e888

Thanks for pointing this out, Alexander.