[issue27575] dict viewkeys intersection slow for large dicts

Serhiy Storchaka added the comment: This changed behavior. See issue38210. See also issue38202 for other regression. -- status: closed -> open ___ Python tracker ___

[issue27575] dict viewkeys intersection slow for large dicts

Change by Serhiy Storchaka : -- status: open -> closed ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: https:

[issue27575] dict viewkeys intersection slow for large dicts

Change by Serhiy Storchaka : -- versions: +Python 3.9 -Python 3.6 ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscri

[issue27575] dict viewkeys intersection slow for large dicts

Serhiy Storchaka added the comment: I am puzzled why we still call set.intersection_update with empty set? -- nosy: +serhiy.storchaka ___ Python tracker ___ __

[issue27575] dict viewkeys intersection slow for large dicts

Raymond Hettinger added the comment: Thanks David and Forest. -- resolution: -> fixed stage: patch review -> resolved status: open -> closed ___ Python tracker ___ __

[issue27575] dict viewkeys intersection slow for large dicts

Raymond Hettinger added the comment: New changeset 998cf1f03a61de8a0cd3811faa97973d4022bc55 by Raymond Hettinger (Forest Gregg) in branch 'master': bpo-27575: port set intersection logic into dictview intersection (GH-7696) https://github.com/python/cpython/commit/998cf1f03a61de8a0cd3811faa97

[issue27575] dict viewkeys intersection slow for large dicts

Forest added the comment: Hi Raymond, I've created a PR here: https://github.com/python/cpython/pull/7696, and I've verified that there are tests for all the code paths. I reached out to Daniel Hsu and he has given his blessing to help push this forward. I think this is ready for your re

[issue27575] dict viewkeys intersection slow for large dicts

Change by Forest : -- pull_requests: +7311 stage: -> patch review ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscr

[issue27575] dict viewkeys intersection slow for large dicts

Raymond Hettinger added the comment: > Is there anything helpful I can do to help close this issue? > Maybe convert it into a github PR? Yes, that would be nice. Also, please verify that the test cases cover all the code paths. -- ___ Python trac

[issue27575] dict viewkeys intersection slow for large dicts

Change by Mali Akmanalp : -- nosy: +Mali Akmanalp ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: https://mai

[issue27575] dict viewkeys intersection slow for large dicts

Forest added the comment: Is there anything helpful I can do to help close this issue? Maybe convert it into a github PR? Since Raymond asked for cases where this issue is a problem, I'll add the case that brought me here. I have an application where I need to do thousands of intersections

[issue27575] dict viewkeys intersection slow for large dicts

Changes by Raymond Hettinger : -- assignee: -> rhettinger ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http

[issue27575] dict viewkeys intersection slow for large dicts

David Su added the comment: ping -- ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mai

[issue27575] dict viewkeys intersection slow for large dicts

Changes by David Su : Added file: http://bugs.python.org/file43961/performance_test.sh ___ Python tracker ___ ___ Python-bugs-list mailing lis

[issue27575] dict viewkeys intersection slow for large dicts

Changes by David Su : Added file: http://bugs.python.org/file43960/dictview_intersection_test.py ___ Python tracker ___ ___ Python-bugs-list m

[issue27575] dict viewkeys intersection slow for large dicts

David Su added the comment: Attached is a patch that I had been working on. Could you please review and provide me with some feedback? Thanks! -- keywords: +patch Added file: http://bugs.python.org/file43959/dict_view_intersection.patch ___ Python tr

[issue27575] dict viewkeys intersection slow for large dicts

David Su added the comment: I am trying to implement the following algorithm: http://blog.faroo.com/2012/06/07/improved-edit-distance-based-spelling-correction/ This algorithm is used for fast nearest neighbor queries for spell correction. Given a corpus of strings, for each string s, I gener

[issue27575] dict viewkeys intersection slow for large dicts

Raymond Hettinger added the comment: Do you encounter an actual real-world use case or is this just a theoretical issue? ISTM, the performance is already good enough for most practical applications. -- ___ Python tracker

[issue27575] dict viewkeys intersection slow for large dicts

David Su added the comment: Here are some tests that I ran: Using current naive viewkeys intersection: $ python -m timeit -n 100 -s "d = dict.fromkeys(xrange(1000), 0)" "d.viewkeys() & {0}" 100 loops, best of 3: 447 msec per loop Nearly half a second per iteration is unacceptably slow.

[issue27575] dict viewkeys intersection slow for large dicts

Raymond Hettinger added the comment: FWIW, sets and dicts convert back and forth very efficiently (the hash values are reused and the collection is presized with just a single memory allocation). Also, the sets and dicts have shared pointers to the underlying data (which is often much bigger

[issue27575] dict viewkeys intersection slow for large dicts

Changes by David Su : -- nosy: +rhettinger ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.

[issue27575] dict viewkeys intersection slow for large dicts

New submission from David Su: In dictobject.c, the function dictviews_and performs a very expensive set creation operation on the keys of the self dict object: >From Python 2.7: ... static PyObject* dictviews_and(PyObject* self, PyObject *other) { PyObject *result = PySet_New(self); ...