[issue8425] a -= b should be fast if a is a small set and b is a large set

Change by Raymond Hettinger : -- resolution: -> fixed stage: patch review -> resolved status: open -> closed ___ Python tracker ___

[issue8425] a -= b should be fast if a is a small set and b is a large set

Raymond Hettinger added the comment: 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/88ea166dadb8aeb34541a0a464662de

[issue8425] a -= b should be fast if a is a small set and b is a large set

Change by Raymond Hettinger : -- pull_requests: +15266 pull_request: https://github.com/python/cpython/pull/15590 ___ Python tracker ___

[issue8425] a -= b should be fast if a is a small set and b is a large set

Cheryl Sabella added the comment: @maker, would you be interested in converting your patch to a Github pull request? Thanks! -- nosy: +cheryl.sabella versions: +Python 3.8 -Python 3.4 ___ Python tracker ___

[issue8425] a -= b should be fast if a is a small set and b is a large set

Raymond Hettinger added the comment: 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. -- ___ Python tracker _

[issue8425] a -= b should be fast if a is a small set and b is a large set

Michele Orrù added the comment: ping. -- ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/

[issue8425] a -= b should be fast if a is a small set and b is a large set

Changes by Terry J. Reedy : -- stage: needs patch -> patch review ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe:

[issue8425] a -= b should be fast if a is a small set and b is a large set

Serhiy Storchaka added the comment: > 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

[issue8425] a -= b should be fast if a is a small set and b is a large set

Raymond Hettinger added the comment: Please don't apply this until I've signed-off on it. -- ___ Python tracker ___ ___ Python-bugs-lis

[issue8425] a -= b should be fast if a is a small set and b is a large set

Changes by Michele Orrù : Added file: http://bugs.python.org/file27306/bench.py ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubs

[issue8425] a -= b should be fast if a is a small set and b is a large set

Changes by Michele Orrù : Removed file: http://bugs.python.org/file27293/bench.py ___ Python tracker ___ ___ Python-bugs-list mailing list Unsu

[issue8425] a -= b should be fast if a is a small set and b is a large set

Michele Orrù added the comment: > 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 perha

[issue8425] a -= b should be fast if a is a small set and b is a large set

Michele Orrù added the comment: > 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 perha

[issue8425] a -= b should be fast if a is a small set and b is a large set

Serhiy Storchaka added the comment: s/it/them/ -- ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.py

[issue8425] a -= b should be fast if a is a small set and b is a large set

Serhiy Storchaka added the comment: 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. -- ___ Python tracker

[issue8425] a -= b should be fast if a is a small set and b is a large set

Michele Orrù added the comment: 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_intersectio

[issue8425] a -= b should be fast if a is a small set and b is a large set

Changes by Michele Orrù : Added file: http://bugs.python.org/file27293/bench.py ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubs

[issue8425] a -= b should be fast if a is a small set and b is a large set

Serhiy Storchaka added the comment: Sorry, I was wrong. I think that the proposed changes should be applied in set_difference_update_internal() directly. -- ___ Python tracker _

[issue8425] a -= b should be fast if a is a small set and b is a large set

Michele Orrù added the comment: 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

[issue8425] a -= b should be fast if a is a small set and b is a large set

Changes by Serhiy Storchaka : -- keywords: -easy ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.py

[issue8425] a -= b should be fast if a is a small set and b is a large set

Serhiy Storchaka added the comment: Michele, in any case you patch is not preserve set identity. -- ___ Python tracker ___ ___ Python-b

[issue8425] a -= b should be fast if a is a small set and b is a large set

Serhiy Storchaka added the comment: > $ ./python.exe -m timeit -n 100 -s "s= set(range(2000)); l = > set(range(2000))" "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+2000))" "s-=l" -- _

[issue8425] a -= b should be fast if a is a small set and b is a large set

Michele Orrù added the comment: 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(2000))" "s-=l" 100 loops, best of

[issue8425] a -= b should be fast if a is a small set and b is a large set

Serhiy Storchaka added the comment: > $ ./python.exe -m timeit -s "s= set(range(2000)); l = set(range(2000)); > s=s-l" You are measure empty loop. -- nosy: +storchaka ___ Python tracker ___

[issue8425] a -= b should be fast if a is a small set and b is a large set

Michele Orrù added the comment: Reviewed with Ezio. -- Added file: http://bugs.python.org/file27272/issue8425.1.patch ___ Python tracker ___ __

[issue8425] a -= b should be fast if a is a small set and b is a large set

Michele Orrù added the comment: Something like this would also need unit tests? $ ./python.exe -m timeit -s "s= set(range(2000)); l = set(range(2000)); s=s-l" 1000 loops, best of 3: 0.0622 usec per loop [48787 refs] $ ./python.exe -m timeit -s "s= set(range(2000)); l = set(range(200

[issue8425] a -= b should be fast if a is a small set and b is a large set

Changes by STINNER Victor : -- versions: +Python 3.4 -Python 3.3 ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe:

[issue8425] a -= b should be fast if a is a small set and b is a large set

Changes by Michele Orrù : -- nosy: +maker ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org

[issue8425] a -= b should be fast if a is a small set and b is a large set

Raymond Hettinger added the comment: 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 -- stage: patch review -> needs patch __

[issue8425] a -= b should be fast if a is a small set and b is a large set

Raymond Hettinger added the comment: Deferring to 3.3. -- priority: normal -> low versions: +Python 3.3 -Python 2.7, Python 3.2 ___ Python tracker ___ ___

[issue8425] a -= b should be fast if a is a small set and b is a large set

Changes by Daniel Stutzbach : -- nosy: +stutzbach ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.py

[issue8425] a -= b should be fast if a is a small set and b is a large set

Mark Dickinson added the comment: See also issue 8685. -- nosy: +mark.dickinson ___ Python tracker ___ ___ Python-bugs-list mailing li

[issue8425] a -= b should be fast if a is a small set and b is a large set

Alexander Belopolsky added the comment: 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

[issue8425] a -= b should be fast if a is a small set and b is a large set

Changes by Alexander Belopolsky : Added file: http://bugs.python.org/file17284/issue8425-tests.diff ___ Python tracker ___ ___ Python-bugs-list

[issue8425] a -= b should be fast if a is a small set and b is a large set

Alexander Belopolsky added the comment: 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. -- Add

[issue8425] a -= b should be fast if a is a small set and b is a large set

R. David Murray added the comment: The answer is almost certainly "no". -- nosy: +r.david.murray ___ Python tracker ___ ___ Python-bug

[issue8425] a -= b should be fast if a is a small set and b is a large set

Changes by Alexander Belopolsky : -- stage: needs patch -> patch review ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubs

[issue8425] a -= b should be fast if a is a small set and b is a large set

Alexander Belopolsky added the comment: 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 la

[issue8425] a -= b should be fast if a is a small set and b is a large set

Changes by Alexander Belopolsky : -- nosy: +belopolsky ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http://ma

[issue8425] a -= b should be fast if a is a small set and b is a large set

Changes by Raymond Hettinger : -- stage: unit test needed -> needs patch ___ Python tracker ___ ___ Python-bugs-list mailing list Unsub

[issue8425] a -= b should be fast if a is a small set and b is a large set

Ezio Melotti added the comment: Raymond, have you forgotten to attach the patch or have you just set the stage to 'patch review' by mistake? -- nosy: +ezio.melotti priority: -> normal stage: patch review -> unit test needed ___ Python tracker

[issue8425] a -= b should be fast if a is a small set and b is a large set

Changes by Raymond Hettinger : -- keywords: +easy stage: -> patch review versions: +Python 2.7, Python 3.2 -Python 3.3 ___ Python tracker ___

[issue8425] a -= b should be fast if a is a small set and b is a large set

Changes by Eric Smith : -- nosy: +eric.smith ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.

[issue8425] a -= b should be fast if a is a small set and b is a large set

Changes by Raymond Hettinger : -- assignee: -> rhettinger nosy: +rhettinger versions: +Python 3.3 -Python 3.1 ___ Python tracker ___ _

[issue8425] a -= b should be fast if a is a small set and b is a large set

New submission from Eugene Kapun : >>> small_set = set(range(2000)) >>> large_set = set(range(2000)) >>> large_set -= small_set # Fast >>> small_set -= large_set # Slow, should be fast >>> small_set = small_set - large_set # Fast -- components: Interpreter Core messages: 103343 nosy: