| 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) *  |
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) * |
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) * |
Date: 2010-05-10 18:07 |
| The answer is almost certainly "no". |
|
|
| msg105452 - (view) |
Author: Alexander Belopolsky (belopolsky) * |
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) * |
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) * |
Date: 2010-05-11 09:31 |
| See also issue 8685. |
|
|
| msg122954 - (view) |
Author: Raymond Hettinger (rhettinger) * |
Date: 2010-11-30 23:24 |
| Deferring to 3.3. |
|
|
| msg122957 - (view) |
Author: Raymond Hettinger (rhettinger) * |
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) * |
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) * |
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) * |
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) * |
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 .2.patch && make -j3 >/dev/null 2>/dev/null sto applicando .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) * |
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) * |
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 (.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) * |
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) * |
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 (.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) * |
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) * |
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) * |
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 |
|
|