An unexpected difference between dict and OrderedDict

[abalkin]

BPO	27576
Nosy	@rhettinger, @abalkin, @ericsnowcurrently, @serhiy-storchaka, @zhangyangyu, @Vgr255, @alakyadav
Files	odict_update.patch odict_update_v2.patch

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/ericsnowcurrently'
closed_at = <Date 2016-09-09.19:07:14.833>
created_at = <Date 2016-07-19.21:01:30.614>
labels = ['type-bug', 'library']
title = 'An unexpected difference between dict and OrderedDict'
updated_at = <Date 2016-09-09.19:07:14.832>
user = 'https://github.com/abalkin'

bugs.python.org fields:

activity = <Date 2016-09-09.19:07:14.832>
actor = 'eric.snow'
assignee = 'eric.snow'
closed = True
closed_date = <Date 2016-09-09.19:07:14.833>
closer = 'eric.snow'
components = ['Library (Lib)']
creation = <Date 2016-07-19.21:01:30.614>
creator = 'belopolsky'
dependencies = []
files = ['43876', '43879']
hgrepos = []
issue_num = 27576
keywords = ['patch', '3.5regression']
message_count = 9.0
messages = ['270842', '270851', '271247', '271256', '271276', '271427', '271694', '275393', '275394']
nosy_count = 8.0
nosy_names = ['rhettinger', 'belopolsky', 'python-dev', 'eric.snow', 'serhiy.storchaka', 'xiang.zhang', 'abarry', 'alakyadav']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'behavior'
url = 'https://bugs.python.org/issue27576'
versions = ['Python 3.5']

[abalkin]

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.

[rhettinger]

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
'''

[zhangyangyu]

Submit a patch to fix this. Hope it helps.

[serhiy-storchaka]

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).

[zhangyangyu]

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.

[zhangyangyu]

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

[zhangyangyu]

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.

[python-dev]

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

[ericsnowcurrently]

Thanks for pointing this out, Alexander.