classification
Title: dict viewkeys intersection slow for large dicts
Type: performance Stage: patch review
Components: Library (Lib) Versions: Python 3.6
process
Status: open Resolution:
Dependencies: Superseder:
Assigned To: rhettinger Nosy List: David Su2, Mali Akmanalp, fgregg, rhettinger
Priority: normal Keywords: patch

Created on 2016-07-19 17:51 by David Su2, last changed 2018-06-15 02:41 by fgregg.

Files
File name Uploaded Description Edit
dict_view_intersection.patch David Su2, 2016-08-01 06:34 review
dictview_intersection_test.py David Su2, 2016-08-01 06:36
performance_test.sh David Su2, 2016-08-01 06:36
Pull Requests
URL Status Linked Edit
PR 7696 open fgregg, 2018-06-14 18:46
Messages (10)
msg270836 - (view) Author: David Su (David Su2) * Date: 2016-07-19 17:51
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);
...
    tmp = PyObject_CallMethod(result, "intersection_update", "(O)", other);
...

Similar logic can be found in the Python 3 code as well.


For large dicts (~10 000 000 keys), it takes a significant amount of time to copy the keys into a new set, and also wastes a lot of memory. This issue is amplified when the intersection operation is performed many times.

This implementation uses O(len(self)) time and space, while it is expected to use O(min(len(self), len(other)) time and space.


Solution 1: Manually copy the keys of the dict into a set, and perform all intersection operations on that set. However, still wastes lots of memory. 

Solution 2 (Recommended): Port the intersection logic from the set class to the dict view class.
msg270905 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2016-07-21 03:30
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 than the containers that refers to the data).

Also, the use case of having very large dicts with repeated intersection operations isn't common enough to warrant any significant code expansion (your solution two).   

I don't understand your "solution one".  PySet_New(self) does copy references to the keys from the dict to a set and the intersection_update() does perform operations on that set.

Lastly, since there was no clear example given, there isn't an opportunity to look at it to see if the code would have been better designed to simply use sets for the set operations and keep the dict around to the key to value transformations (in other words, the current toolset may already afford some way to accomplish the goal).
msg270906 - (view) Author: David Su (David Su2) * Date: 2016-07-21 04:28
Here are some tests that I ran:


Using current naive viewkeys intersection:

$ python -m timeit -n 100 -s "d = dict.fromkeys(xrange(10000000), 0)" "d.viewkeys() & {0}"
100 loops, best of 3: 447 msec per loop

Nearly half a second per iteration is unacceptably slow.



Solution 1 from my previous comment:

$ python -m timeit -n 100 -s "d = dict.fromkeys(xrange(10000000), 0); s = set(d)" "s & {0}"
100 loops, best of 3: 0.391 usec per loop

This solution caches the keys of the dict in a set, then performs all intersections on that set. 
The initial creation of the set is slow, and it wastes a lot of memory, but each iteration is much faster.



The workaround that I ended up using:

$ python -m timeit -n 100 -s "d = dict.fromkeys(xrange(10000000), 0)" "{item for item in {0} if item in d}"
100 loops, best of 3: 0.629 usec per loop

This solution just looks up each value in the set to see if it is also in the dict using a set comprehension.
This avoids wasting time and space on creating a set. For my use case, memory was a bigger issue as my dictionary can approach tens of GBs in size, and almost doubling the memory consumption from creating a cache set was unacceptable. 

Of course, in the set comprehension, the smaller of the dict/set should be iterated over to satisfy the O(min(len(d), len(s))) condition as specified in https://wiki.python.org/moin/TimeComplexity.
A implementation would look something like this:

def efficient_intersection(smaller_dict_or_set, bigger_dict_or_set):
    if len(bigger_dict_or_set) < len(smaller_dict_or_set):
        bigger_dict_or_set, smaller_dict_or_set = smaller_dict_or_set, bigger_dict_or_set
    
    return {item for item in smaller_dict_or_set if item in bigger_dict_or_set}




In conclusion, porting over the set intersection logic to viewkeys would be the ideal solution. It avoids wasting memory like in the set cache solution, and I am sure the C implementation will be much faster than my workaround of manually performing an intersection using set comprehensions.

My view is that dict.viewkeys() & set(...) should be as performant as the syntax suggests.
msg271035 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2016-07-22 21:23
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.
msg271095 - (view) Author: David Su (David Su2) * Date: 2016-07-23 18:05
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 generate all subsequences (Note: subsequence, not substring) of that string length (len(n) - k), call that subsequence t, where k is a tunable parameter. Then, I create a dict mapping the subsequences t to the original string s.

This process creates a very large dict from a relatively small corpus. For example, my corpus of ~500k strings blew up to a dict of ~10M keys, with k=3.

Then, for a query string q, you generate all subsequences of (len(q) - k), and perform an intersection with the keys of the dict. Then, the values of the dict corresponding to the key intersection will be possible misspelling of the query string q.

In pseudo-python:

def get_subseq(s: str, k: int):
    returns all subsequences of s of length len(s) - k

def build_dict(corpus: List[str], k: int):
    d = defaultdict(list)

    for orig_str in corpus:
        for subseq in get_subseq(orig_str, k):
            d[subseq].append(orig_str)

    return d

def query(d: dict, q: str, k:int):
    q_subseq = set(get_subseq(q, k))
    intersection = d.viewkeys() & q_subseq # this is slow when len(d) is large
    return [orig_str for k in intersection for orig_str in d[k]]
    

By exposing an intersection interface, a certain degree of performance is expected by the user. It took me a considerable amount of debugging to realize that the dict.viewkeys() intersection was the performance bottleneck. I finally decided to dig into the CPython source code before discovering the root cause of the issue. While I am familiar with C and found the issue relatively quickly, for those that aren't, it should not be necessary to dig into the source code for a mainstream programming language like Python.


I am currently looking at how to potentially fix this in the CPython repository. I may submit a patch in the near future if I find a good solution.
msg271770 - (view) Author: David Su (David Su2) * Date: 2016-08-01 06:34
Attached is a patch that I had been working on. Could you please review and provide me with some feedback? Thanks!
msg274563 - (view) Author: David Su (David Su2) * Date: 2016-09-06 16:25
ping
msg319469 - (view) Author: Forest (fgregg) * Date: 2018-06-13 14:50
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 of multisets. I started with the collections.Counter object, but the current intersection method is too slow. As Counter is a subclass of dict, I thought that I could significantly speed it up by taking advantage of keys intersections.

I've been able to verify that if key intersection was roughly similar in speed to set intersection, than that would be very helpful. However, the   current speed of key intersection does not make that practicable. I can, of course, cast the keys to sets before intersecting, but as David points out that casting is what is taking significant time.




slow dictionary intersection for becoming larger dicts is becoming a problem for me
msg319488 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2018-06-13 23:54
> 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.
msg319575 - (view) Author: Forest (fgregg) * Date: 2018-06-15 02:41
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 review. Please let me know if there's anything else I can do.

Thanks,

Forest
History
Date User Action Args
2018-06-15 02:41:28fgreggsetmessages: + msg319575
2018-06-14 18:46:55fgreggsetstage: patch review
pull_requests: + pull_request7311
2018-06-13 23:54:16rhettingersetmessages: + msg319488
2018-06-13 21:13:16Mali Akmanalpsetnosy: + Mali Akmanalp
2018-06-13 14:50:45fgreggsetnosy: + fgregg
messages: + msg319469
2016-09-06 21:19:49rhettingersetassignee: rhettinger
2016-09-06 16:25:10David Su2setmessages: + msg274563
2016-08-01 06:36:18David Su2setfiles: + performance_test.sh
2016-08-01 06:36:06David Su2setfiles: + dictview_intersection_test.py
2016-08-01 06:34:07David Su2setfiles: + dict_view_intersection.patch
keywords: + patch
messages: + msg271770
2016-07-23 18:05:29David Su2setmessages: + msg271095
2016-07-22 21:23:54rhettingersetmessages: + msg271035
2016-07-21 04:28:37David Su2setmessages: + msg270906
2016-07-21 03:30:38rhettingersetmessages: + msg270905
versions: - Python 2.7, Python 3.2, Python 3.3, Python 3.4, Python 3.5
2016-07-20 20:14:12David Su2setnosy: + rhettinger
2016-07-19 17:51:47David Su2create