classification
Title: An unexpected difference between dict and OrderedDict
Type: behavior Stage: resolved
Components: Library (Lib) Versions: Python 3.5
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: eric.snow Nosy List: abarry, alakyadav, belopolsky, eric.snow, python-dev, rhettinger, serhiy.storchaka, xiang.zhang
Priority: normal Keywords: 3.5regression, patch

Created on 2016-07-19 21:01 by belopolsky, last changed 2016-09-09 19:07 by eric.snow. This issue is now closed.

Files
File name Uploaded Description Edit
odict_update.patch xiang.zhang, 2016-07-25 09:37
odict_update_v2.patch xiang.zhang, 2016-07-25 14:21 review
Messages (9)
msg270842 - (view) Author: Alexander Belopolsky (belopolsky) * (Python committer) Date: 2016-07-19 21:01
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.
msg270851 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2016-07-19 23:13
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
        '''
msg271247 - (view) Author: Xiang Zhang (xiang.zhang) * (Python committer) Date: 2016-07-25 09:37
Submit a patch to fix this. Hope it helps.
msg271256 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2016-07-25 12:22
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).
msg271276 - (view) Author: Xiang Zhang (xiang.zhang) * (Python committer) Date: 2016-07-25 14:21
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.
msg271427 - (view) Author: Xiang Zhang (xiang.zhang) * (Python committer) Date: 2016-07-27 03:08
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
msg271694 - (view) Author: Xiang Zhang (xiang.zhang) * (Python committer) Date: 2016-07-30 15:07
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.
msg275393 - (view) Author: Roundup Robot (python-dev) (Python triager) Date: 2016-09-09 19:04
New changeset 70758c12e888 by Eric Snow in branch 'default':
Issue #27576: Fix call order in OrderedDict.__init__().
https://hg.python.org/cpython/rev/70758c12e888
msg275394 - (view) Author: Eric Snow (eric.snow) * (Python committer) Date: 2016-09-09 19:06
Thanks for pointing this out, Alexander.
History
Date User Action Args
2016-09-09 19:07:14eric.snowsetstatus: open -> closed
resolution: fixed
stage: needs patch -> resolved
2016-09-09 19:06:20eric.snowsetmessages: + msg275394
2016-09-09 19:04:34python-devsetnosy: + python-dev
messages: + msg275393
2016-07-30 15:07:39xiang.zhangsetmessages: + msg271694
2016-07-30 15:06:00xiang.zhangsetfiles: - odict_update_v3.patch
2016-07-27 03:08:07xiang.zhangsetfiles: + odict_update_v3.patch

messages: + msg271427
2016-07-25 14:21:57xiang.zhangsetfiles: + odict_update_v2.patch

messages: + msg271276
2016-07-25 12:22:29serhiy.storchakasetnosy: + serhiy.storchaka
messages: + msg271256
2016-07-25 09:37:50xiang.zhangsetfiles: + odict_update.patch

nosy: + xiang.zhang
messages: + msg271247

keywords: + patch
2016-07-20 19:25:55alakyadavsetnosy: + alakyadav
2016-07-19 23:15:18abarrysetnosy: + eric.snow, abarry
assignee: eric.snow
components: + Library (Lib)
keywords: + 3.5regression, - 3.4regression
stage: needs patch
2016-07-19 23:13:18rhettingersetnosy: + rhettinger
messages: + msg270851
2016-07-19 21:01:30belopolskycreate