classification
Title: a -= b should be fast if a is a small set and b is a large set
Type: resource usage Stage: resolved
Components: Interpreter Core Versions: Python 3.8
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: rhettinger Nosy List: abacabadabacaba, belopolsky, cheryl.sabella, eric.smith, ezio.melotti, maker, mark.dickinson, r.david.murray, rhettinger, serhiy.storchaka, stutzbach
Priority: low Keywords: patch

Created on 2010-04-16 17:19 by abacabadabacaba, last changed 2019-08-29 16:03 by rhettinger. This issue is now closed.

Files
File name Uploaded Description Edit
issue8425.diff belopolsky, 2010-05-10 17:44
issue8425a.diff belopolsky, 2010-05-10 18:13
issue8425-with-tests.diff belopolsky, 2010-05-10 18:27 Patch against py3k revision 81048
issue8425.patch maker, 2012-09-23 15:59 review
issue8425.1.patch maker, 2012-09-24 09:24 review
issue8425.2.patch maker, 2012-09-25 08:22 review
issue8425.3.patch maker, 2012-09-25 19:27 review
bench.py maker, 2012-09-25 19:29
Pull Requests
URL Status Linked Edit
PR 15590 merged rhettinger, 2019-08-29 09:02
Messages (27)
msg103343 - (view) Author: Evgeny Kapun (abacabadabacaba) Date: 2010-04-16 17:19
>>> small_set = set(range(2000))
>>> large_set = set(range(20000000))
>>> large_set -= small_set # Fast
>>> small_set -= large_set # Slow, should be fast
>>> small_set = small_set - large_set # Fast
msg103552 - (view) Author: Ezio Melotti (ezio.melotti) * (Python committer) Date: 2010-04-19 04:20
Raymond, have you forgotten to attach the patch or have you just set the stage to 'patch review' by mistake?
msg105450 - (view) Author: Alexander Belopolsky (belopolsky) * (Python committer) Date: 2010-05-10 17:44
The problem is apparently due to the fact that small_set -= large_set
iterates over the large set removing entries from small_set while more
efficient small_set - large_set builds a new set iterating over a
small_set and adding items that are not in the large set.  Since
lookups are O(1), it is more efficient to iterate over a small set
while looking up a large set than the other way around.  I am
attaching a minimalist patch which gives up in-place update for s1 -=
s2 if len(s1) < len(s2) and effectively replaces it with s1 = s1 - s2.
 The code can be further optimized by replicating set_difference logic
in set_isub instead of relying on fall back behavior, but the big
question here  with whether it is acceptable to give up preserving set
identity in in-place subtract to gain performance.
msg105451 - (view) Author: R. David Murray (r.david.murray) * (Python committer) Date: 2010-05-10 18:07
The answer is almost certainly "no".
msg105452 - (view) Author: Alexander Belopolsky (belopolsky) * (Python committer) Date: 2010-05-10 18:13
On the second thought, it is possible to preserve set identity and avoid iteration over a large set.   See issue8425a.diff attached.

It looks like the unit tests don't check identity preservation.  I will submit additional tests shortly.
msg105455 - (view) Author: Alexander Belopolsky (belopolsky) * (Python committer) Date: 2010-05-10 18:51
Note that issue8425a.diff leaves small_set.difference_update(large_dict) unoptimized:

$ ./python.exe -m timeit -s "s = {1}; l = dict.fromkeys(range(1000));" "s.difference_update(l)"
1000 loops, best of 3: 842 usec per loop
$ ./python.exe -m timeit -s "s = {1}; l = dict.fromkeys(range(1000));" "s.difference(l)"
100000 loops, best of 3: 13.2 usec per loop

It would be easy to add an extra type check, but I noticed that small_set.difference_update(large_dict.viewkeys()) is not optimized either:

$ ./python.exe -m timeit -s "s = {1}; l = dict.fromkeys(range(1000));" "s.difference(l.viewkeys())"
1000 loops, best of 3: 842 usec per loop

It would be nice if there was a uniform C-API that would allow to uniformly check that an object supports O(1) lookup and invoke such lookup efficiently.  I don't think such C-API exists at the moment.

I would like to hear what others have to say before adding optimizations  to the patch that go beyond the scope of this issue.
msg105492 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2010-05-11 09:31
See also issue 8685.
msg122954 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2010-11-30 23:24
Deferring to 3.3.
msg122957 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2010-11-30 23:48
Any new logic should make maximum use of existing tools:

def __isub__(self, other)
    if len(other) > len(self)*8:
        other = self & other
    . . .
    # rest of isub unchanged
msg171049 - (view) Author: Michele Orrù (maker) * Date: 2012-09-23 15:59
Something like this would also need unit tests?

$ ./python.exe -m timeit -s "s= set(range(2000)); l = set(range(20000000)); s=s-l"
10000000 loops, best of 3: 0.0622 usec per loop
[48787 refs]
$ ./python.exe -m timeit -s "s= set(range(2000)); l = set(range(20000000)); s-=l"
10000000 loops, best of 3: 0.0591 usec per loop
[48787 refs]
msg171106 - (view) Author: Michele Orrù (maker) * Date: 2012-09-24 09:24
Reviewed with Ezio.
msg171117 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2012-09-24 11:28
> $ ./python.exe -m timeit -s "s= set(range(2000)); l = set(range(20000000)); s=s-l"

You are measure empty loop.
msg171153 - (view) Author: Michele Orrù (maker) * Date: 2012-09-24 15:06
woops, sry. Re-posting the benchmark, with three tests: the first one proposed (@abacabadabacaba) with very large sets; another one with smaller sets.

$ ./python.exe -m timeit  -n 100 -s "s= set(range(2000)); l = set(range(20000000))"   "s-=l"
100 loops, best of 3: 9.71 usec per loop
[48787 refs]

$ ./python.exe -m timeit  -n 100 -s "s= set(range(1)); l = set(range(20))"   "s-=l"
100 loops, best of 3: 0.366 usec per loop


$ hg co -C
$ make -j3

----[!PATCHED]--------------------------------------------------
$ ./python.exe -m timeit  -n 100 -s "s= set(range(2000)); l = set(range(20000000))"   "s-=l"
100 loops, best of 3: 665 msec per loop
[48787 refs]

$ ./python.exe -m timeit  -n 100 -s "s= set(range(1)); l = set(range(20))"   "s-=l"
100 loops, best of 3: 0.849 usec per loop
[48787 refs]
msg171159 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2012-09-24 16:23
> $ ./python.exe -m timeit  -n 100 -s "s= set(range(2000)); l = set(range(20000000))"   "s-=l"

s is empty set after first loop. Try this:

$ ./python.exe -m timeit  -n 100 -s "s= set(range(2000)); l = set(range(2000,2000+20000000))"   "s-=l"
msg171160 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2012-09-24 16:38
Michele, in any case you patch is not preserve set identity.
msg171162 - (view) Author: Michele Orrù (maker) * Date: 2012-09-24 17:02
What do you mean by "does not preserve set identity"? Because I see: 

$ ./python.exe
Python 3.3.0rc2+ (default:178f9042af81+, Sep 24 2012, 18:54:31) 
[GCC 4.2.1 Compatible Apple Clang 2.1 (tags/Apple/clang-163.7.1)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> a = set(range(1))
[65967 refs]
>>> b = set(range(20))
[65989 refs]
>>> id(a)
4540421032
[65992 refs]
>>> a -= b
[65991 refs]
>>> id(a)
4540421032
msg171164 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2012-09-24 17:33
Sorry, I was wrong.

I think that the proposed changes should be applied in set_difference_update_internal() directly.
msg171232 - (view) Author: Michele Orrù (maker) * Date: 2012-09-25 08:22
Updated.

tumbolandia:cpython maker$ hg import --no-commit -f issue8425.2.patch && make -j3 >/dev/null 2>/dev/null
sto applicando issue8425.2.patch
tumbolandia:cpython maker$ ./python.exe bench.py starting...
setting up tests...
testing...
big_timer_no_intersection 0.0005461599998852762
big_timer_subtraction 382.0618862710003
small_timer 0.0034195990001535392
big_timer 603.5105132449999
std_timer_subtraction 0.0006865100003778934
big_timer_reversed 292.44042680999974
std_timer 8.092500047496287e-05
[44705 refs]
tumbolandia:cpython maker$ hg co -C && make -j3 >/dev/null 2>/dev/null1 files updated, 0 files merged, 0 files removed, 0 files unresolved
tumbolandia:cpython maker$ ./python.exe bench.py 
starting...
setting up tests...
testing...
big_timer_subtraction 611.292889542
big_timer 465.68463925800006
small_timer 0.002618359999360109
big_timer_reversed 256.5112134430001
std_timer 0.00011092699969594833
big_timer_no_intersection 0.0005648139995173551
std_timer_subtraction 2.8619999284273945e-05
[44705 refs]
msg171306 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2012-09-25 19:03
I added a few comments in Rietveld.

Did you run benchmarks in debug mode?

In order for results to be convenient to compare please sort it by name.
msg171307 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2012-09-25 19:04
s/it/them/
msg171312 - (view) Author: Michele Orrù (maker) * Date: 2012-09-25 19:27
> I'm not sure of the usefulness of this comment.
removing, then.

> "else" redundant here.

> Instead of using a local variable "intersected", you can simply add "else
> Py_INCREF(other)" here and then decref "other" unconditionally. It will be
> shorter and perhaps a little clearer, but a bit slower.

I find my first patch more readable and efficient, but if these comments are conformant to pep7.. 
Attaching updated patch (issue8425.3.patch)


> Did you run benchmarks in debug mode?
Yes, but bench.py is available, fell free to run it with whatever configuration; my example was done with a --with-pydebug and clang compiler. 

> In order for results to be convenient to compare please sort it by name.
Done.
msg171322 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2012-09-25 23:06
Please don't apply this until I've signed-off on it.
msg171375 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2012-09-27 14:16
> I find my first patch more readable and efficient, but if these comments
> are conformant to pep7.. Attaching updated patch (issue8425.3.patch)

It was only a suggestion. Both forms are good enougth.

> Yes, but bench.py is available, fell free to run it with whatever
> configuration; my example was done with a --with-pydebug and clang
> compiler.

Yes, I ran it in release mode (gcc, 32-bit Linux) and confirm your results.

In general except minor whitespace defects last patch LGTM.
msg193784 - (view) Author: Michele Orrù (maker) * Date: 2013-07-27 13:57
ping.
msg193807 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2013-07-28 04:10
There's no rush on this.  I have other work I want to do on set objects before applying further optimizations, so I want to hold off on it for a bit.
msg342713 - (view) Author: Cheryl Sabella (cheryl.sabella) * (Python committer) Date: 2019-05-17 12:44
@maker, would you be interested in converting your patch to a Github pull request?  Thanks!
msg350795 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2019-08-29 16:03
New changeset 88ea166dadb8aeb34541a0a464662dea222629e5 by Raymond Hettinger in branch 'master':
bpo-8425: Fast path for set inplace difference when the second set is large (GH-15590)
https://github.com/python/cpython/commit/88ea166dadb8aeb34541a0a464662dea222629e5
History
Date User Action Args
2019-08-29 16:03:37rhettingersetstatus: open -> closed
resolution: fixed
stage: patch review -> resolved
2019-08-29 16:03:04rhettingersetmessages: + msg350795
2019-08-29 09:02:36rhettingersetpull_requests: + pull_request15266
2019-05-17 12:44:34cheryl.sabellasetnosy: + cheryl.sabella

messages: + msg342713
versions: + Python 3.8, - Python 3.4
2013-07-28 04:10:08rhettingersetmessages: + msg193807
2013-07-27 13:57:29makersetmessages: + msg193784
2012-10-14 18:07:54terry.reedysetstage: needs patch -> patch review
2012-09-27 14:16:18serhiy.storchakasetmessages: + msg171375
2012-09-25 23:06:47rhettingersetmessages: + msg171322
2012-09-25 19:29:24makersetfiles: + bench.py
2012-09-25 19:29:04makersetfiles: - bench.py
2012-09-25 19:27:16makersetfiles: + issue8425.3.patch

messages: + msg171312
2012-09-25 19:04:55serhiy.storchakasetmessages: + msg171307
2012-09-25 19:03:07serhiy.storchakasetmessages: + msg171306
2012-09-25 08:23:09makersetfiles: + bench.py
2012-09-25 08:22:38makersetfiles: + issue8425.2.patch

messages: + msg171232
2012-09-24 17:33:10serhiy.storchakasetmessages: + msg171164
2012-09-24 17:02:38makersetmessages: + msg171162
2012-09-24 16:39:03serhiy.storchakasetkeywords: - easy
2012-09-24 16:38:37serhiy.storchakasetmessages: + msg171160
2012-09-24 16:23:39serhiy.storchakasetmessages: + msg171159
2012-09-24 15:06:34makersetmessages: + msg171153
2012-09-24 11:28:14serhiy.storchakasetnosy: + serhiy.storchaka
messages: + msg171117
2012-09-24 09:24:22makersetfiles: + issue8425.1.patch

messages: + msg171106
2012-09-23 15:59:36makersetfiles: + issue8425.patch

messages: + msg171049
2012-09-18 21:48:05vstinnersetversions: + Python 3.4, - Python 3.3
2012-09-18 12:30:44makersetnosy: + maker
2010-11-30 23:48:30rhettingersetmessages: + msg122957
stage: patch review -> needs patch
2010-11-30 23:24:48rhettingersetpriority: normal -> low

messages: + msg122954
versions: + Python 3.3, - Python 2.7, Python 3.2
2010-09-01 21:30:18stutzbachsetnosy: + stutzbach
2010-05-11 09:31:01mark.dickinsonsetnosy: + mark.dickinson
messages: + msg105492
2010-05-10 18:51:22belopolskysetmessages: + msg105455
2010-05-10 18:27:55belopolskysetfiles: + issue8425-with-tests.diff
2010-05-10 18:13:06belopolskysetfiles: + issue8425a.diff

messages: + msg105452
2010-05-10 18:07:41r.david.murraysetnosy: + r.david.murray
messages: + msg105451
2010-05-10 17:46:28belopolskysetstage: needs patch -> patch review
2010-05-10 17:44:36belopolskysetfiles: + issue8425.diff
keywords: + patch
messages: + msg105450
2010-05-09 19:15:23belopolskysetnosy: + belopolsky
2010-04-19 05:14:13rhettingersetstage: test needed -> needs patch
2010-04-19 04:20:04ezio.melottisetpriority: normal

nosy: + ezio.melotti
messages: + msg103552

stage: patch review -> test needed
2010-04-18 05:45:09rhettingersetkeywords: + easy
stage: patch review
versions: + Python 2.7, Python 3.2, - Python 3.3
2010-04-16 21:45:39eric.smithsetnosy: + eric.smith
2010-04-16 19:07:45rhettingersetassignee: rhettinger

nosy: + rhettinger
versions: + Python 3.3, - Python 3.1
2010-04-16 17:19:41abacabadabacabacreate