classification
Title: Optimization for set/frozenset.issubset()
Type: performance Stage: patch review
Components: Interpreter Core Versions: Python 3.5
process
Status: closed Resolution: rejected
Dependencies: Superseder:
Assigned To: rhettinger Nosy List: bru, dhaffner, ezio.melotti, hhm, josh.r, pconnell, rhettinger, serhiy.storchaka, vstinner
Priority: normal Keywords: easy, patch

Created on 2013-05-22 11:58 by hhm, last changed 2015-05-28 03:12 by rhettinger. This issue is now closed.

Files
File name Uploaded Description Edit
issubset_improvement.patch dhaffner, 2013-11-19 19:19 review
0001-Improve-set.issubset-performance-on-iterables.patch bru, 2014-11-27 13:38 Patch that improves set.issubset() perf. on iterables review
set_issubset_bitarray.patch serhiy.storchaka, 2015-05-27 13:00 review
Messages (11)
msg189806 - (view) Author: hhm (hhm) Date: 2013-05-22 11:58
It says here (http://docs.python.org/2/library/stdtypes.html#set-types-set-frozenset) that some of the set methods take iterables as a parameter.

Usually, the expected behavior is for a iterator consumer to consume only as much data as it needs. For example, for the code `any(itertools.repeat(True))`, the code will complete speedily, in contrast to when all() is used instead of any(), in which case the code will go forever.

A least some of the set methods have semantics such that they can consume only some of the input; for example, "issubset" only needs to make sure that all of the items in the set are in the iterable, and once this is the case, it can return "True".

However in such a case, the methods will *still* go forever.

The docs should specify that this is the case, to disambiguate the semantics.

(Tested on Python 3.2.3 and 2.7.3).
msg190133 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2013-05-27 07:59
We don't normally document implementation details or the presences or absence of internal optimizations.  This gives us freedom to change the implementation and it allows freedom for other implementations (such as Jython, IronPython, and PyPy) to make their own choices.  Often those implementations start out with the simplest correct approach and then become increasingly optimized over time. 

I'm leaving this one open as a possible CPythhon performance enhancement, adding early-out behavior to issubset() when the argument is a non-set, non-dict iterable:

    def issubset(self, iterable):
        n = len(self)
        seen = set() 
        for x in iterable:
            if x not in seen and x in self:
                seen.add(x)
                n -= 1
                if not n:
                    return True             # early-out
        return False
msg203416 - (view) Author: Dustin Haffner (dhaffner) * Date: 2013-11-19 19:19
I've made an attempt at patching set_issubset() to match the Python from Raymond's message. I've rearranged the set_issubset function so that it checks for a set/frozenset, dict, or iterable in that order. In the iterable case it will create a temporary set and add elements to it as it consumes them from the iterable, returning early when possible.

This is my first patch, please let me know how I may improve it!
msg221338 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2014-06-23 03:24
The patch looks good.  I'll go over it in more detail shortly.
msg221382 - (view) Author: Josh Rosenberg (josh.r) * (Python triager) Date: 2014-06-23 23:07
Patch needs some work. See comments on patch.
msg231760 - (view) Author: Bruno Cauet (bru) * Date: 2014-11-27 13:38
Here is an updated patch based on Dustin's work with Josh's comments. I also added a test which takes forever on an unpatched python interpreter.

Since it's a performance issue, I've benchmarked the results. They don't change for the most part (argument is a set or a dict) but they're way better for iterables.
For every type of argument I test 1 case where "set.issubset" returns True and 1 case where it returns False.


(a) simple argument (results unchanged)

$ ./python -m timeit -s "s1 = set(range(1000)); s2 = set(range(1000))" "s1.issubset(s2)"
Unpatched: 10000 loops, best of 3: 63.7 usec per loop
Patched:   10000 loops, best of 3: 63.5 usec per loop

$ ./python -m timeit -s "s1 = set(range(1000)); s2 = set(range(1, 1000))" "s1.issubset(s2)"
Unpatched: 1000000 loops, best of 3: 0.248 usec per loop
Patched:   1000000 loops, best of 3: 0.25 usec per loop

$ ./python -m timeit -s "s1 = set(range(1000)); s2 = dict(enumerate(range(1000)))" "s1.issubset(s2)"
Unpatched: 10000 loops, best of 3: 107 usec per loop
Patched: 10000 loops, best of 3: 108 usec per loop

$ ./python -m timeit -s "s1 = set(range(1000)); s2 = dict(enumerate(range(1, 1000)))" "s1.issubset(s2)"
Unpatched: 10000 loops, best of 3: 43.5 usec per loop
Patched:   10000 loops, best of 3: 42.6 usec per loop


(b) iterable argument (speed improvement)

1) no improvements/slight degradation when everything must be consumed

$ ./python -m timeit -s "s1 = set(range(1000))" "s1.issubset(range(1000))"
Unpatched: 1000 loops, best of 3: 263 usec per loop
Patched:   1000 loops, best of 3: 263 usec per loop

$ ./python -m timeit -s "s1 = set(range(1000))" "s1.issubset(range(1, 1000))"
Unpatched: 10000 loops, best of 3: 201 usec per loop
Patched:   1000 loops, best of 3: 259 usec per loop

$ ./python -m timeit -s "s1 = set(range(100))" "s1.issubset(range(1, 1000))"
Unpatched: 1000 loops, best of 3: 198 usec per loop
Patched:   1000 loops, best of 3: 218 usec per loop

2) tremendous improvements when it can return early

$ ./python -m timeit -s "s1 = set(range(100))" "s1.issubset(range(1000))"
Unpatched: 1000 loops, best of 3: 209 usec per loop
Patched:   100000 loops, best of 3: 12.1 usec per loop

$ ./python -m timeit -s "s1 = set('a'); s2 = ['a'] + ['b'] * 10000" "s1.issubset(s2)"
Unpatched: 1000 loops, best of 3: 368 usec per loop
Patched:   1000000 loops, best of 3: 0.934 usec per loop

$ ./python -m timeit -s "s1 = set('a'); from itertools import repeat" "s1.issubset(repeat('a'))"
Unpatched: NEVER FINISHES
Patched:   1000000 loops, best of 3: 1.33 usec per loop
msg244155 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2015-05-27 10:44
In C implementation no need to create set object seen. More efficient way is to use bit array.

Here is a patch that uses this approach.

./python -m timeit -s "s1 = set(range(1000))" "s1.issubset(range(1000))"
Unpatched  : 10000 loops, best of 3: 115 usec per loop
bru's patch: 10000 loops, best of 3: 114 usec per loop
My patch   : 10000 loops, best of 3: 92.6 usec per loop

./python -m timeit -s "s1 = set(range(1000))" "s1.issubset(range(1, 1000))"
Unpatched  : 10000 loops, best of 3: 73.4 usec per loop
bru's patch: 10000 loops, best of 3: 114 usec per loop
My patch   : 10000 loops, best of 3: 93 usec per loop

./python -m timeit -s "s1 = set(range(100))" "s1.issubset(range(1, 1000))"
Unpatched  : 10000 loops, best of 3: 73.6 usec per loop
bru's patch: 10000 loops, best of 3: 89 usec per loop
My patch   : 10000 loops, best of 3: 62.4 usec per loop

./python -m timeit -s "s1 = set(range(100))" "s1.issubset(range(1000))"
Unpatched  : 10000 loops, best of 3: 75.5 usec per loop
bru's patch: 100000 loops, best of 3: 8.77 usec per loop
My patch   : 100000 loops, best of 3: 5.34 usec per loop

./python -m timeit -s "s1 = set('a'); s2 = ['a'] + ['b'] * 10000" "s1.issubset(s2)"
Unpatched  : 1000 loops, best of 3: 326 usec per loop
bru's patch: 1000000 loops, best of 3: 0.394 usec per loop
My patch   : 1000000 loops, best of 3: 0.409 usec per loop

./python -m timeit -s "s1 = set('a'); from itertools import repeat" "s1.issubset(repeat('a'))"
Unpatched  : NEVER FINISHES
bru's patch: 1000000 loops, best of 3: 0.794 usec per loop
My patch   : 1000000 loops, best of 3: 0.725 usec per loop
msg244158 - (view) Author: Bruno Cauet (bru) * Date: 2015-05-27 12:38
Serhiy, that sounds good but I think that you have forgotten to attach the mentioned patch.
msg244163 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2015-05-27 13:00
Oh, sorry. Here is it.
msg244246 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2015-05-28 03:01
Personally I don't sure that this optimization is worth to apply. Its cost is high and optimized case is not common. This is rather an experiment, how large can be maximal effect of the optimization.
msg244250 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2015-05-28 03:12
> Personally I don't sure that this optimization is worth to apply.

I concur.  Closing as "not worth it"  :-)
History
Date User Action Args
2015-05-28 03:12:00rhettingersetstatus: open -> closed
resolution: rejected
messages: + msg244250
2015-05-28 03:01:45serhiy.storchakasetmessages: + msg244246
2015-05-27 13:00:14serhiy.storchakasetfiles: + set_issubset_bitarray.patch

messages: + msg244163
2015-05-27 12:38:52brusetmessages: + msg244158
2015-05-27 10:44:58serhiy.storchakasetnosy: + serhiy.storchaka
messages: + msg244155
2014-11-27 13:38:47brusetfiles: + 0001-Improve-set.issubset-performance-on-iterables.patch
nosy: + vstinner, bru
messages: + msg231760

2014-06-23 23:07:34josh.rsetnosy: + josh.r
messages: + msg221382
2014-06-23 04:26:07rhettingersettitle: set methods should specify whether they consume iterators "lazily" -> Optimization for set/frozenset.issubset()
2014-06-23 03:24:09rhettingersetversions: + Python 3.5, - Python 3.4
nosy: - docs@python

messages: + msg221338

stage: needs patch -> patch review
2013-11-19 19:19:32dhaffnersetfiles: + issubset_improvement.patch

nosy: + dhaffner
messages: + msg203416

keywords: + patch
2013-05-27 07:59:28rhettingersettype: behavior -> performance
messages: + msg190133
components: + Interpreter Core, - Documentation
versions: - Python 2.7, Python 3.3
2013-05-27 07:03:14rhettingersetassignee: docs@python -> rhettinger

nosy: + rhettinger
2013-05-26 13:45:02ezio.melottisetkeywords: + easy
nosy: + ezio.melotti
stage: needs patch

versions: + Python 3.3, Python 3.4, - Python 3.2
2013-05-25 09:09:12pconnellsetnosy: + pconnell
2013-05-22 11:58:43hhmcreate