Memory optimization for set.issubset

[SimpleArt]

BPO	46705
Nosy	@rhettinger, @serhiy-storchaka, @SimpleArt
PRs	bpo-46705: Memory optimization for set.issubset #31267
Files	instrument_issubset.py: Instrument the baseline and proposed issubset() method instrument_issubset.py: Added Serhiy's difference variant

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/rhettinger'
closed_at = None
created_at = <Date 2022-02-10.01:24:46.738>
labels = ['interpreter-core', '3.11', 'performance']
title = 'Memory optimization for set.issubset'
updated_at = <Date 2022-02-13.20:01:30.345>
user = 'https://github.com/SimpleArt'

bugs.python.org fields:

activity = <Date 2022-02-13.20:01:30.345>
actor = 'serhiy.storchaka'
assignee = 'rhettinger'
closed = False
closed_date = None
closer = None
components = ['Interpreter Core']
creation = <Date 2022-02-10.01:24:46.738>
creator = 'panda1200'
dependencies = []
files = ['50615', '50620']
hgrepos = []
issue_num = 46705
keywords = ['patch']
message_count = 8.0
messages = ['412966', '412977', '412978', '412982', '413030', '413037', '413074', '413194']
nosy_count = 3.0
nosy_names = ['rhettinger', 'serhiy.storchaka', 'panda1200']
pr_nums = ['31267']
priority = 'normal'
resolution = None
stage = 'patch review'
status = 'open'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue46705'
versions = ['Python 3.11']

[SimpleArt]

I noticed that the set.issubset cpython implementation casts its iterable argument to a set. In some cases, casting the whole iterable to a set is unnecessary (see https://bugs.python.org/issue18032). Although the latter suggestion is to perform early termination, my suggestion is to use the intersection instead.

    # PyAnySet_Check coming from the cpython source code.
    def issubset(self, other):
        # Intersection suggestion:
        if not PyAnySet_Check(other):
            return len(self.intersection(other)) == len(self)
        # Usual implementation for sets.
        else:
            return ...

The main advantage that this implementation has is its memory performance, using only O(min(len(self), len(other))) memory, since it never stores elements it does not need.

I'm assuming that set construction costs O(n) set.__contains__ calls. This implementation uses len(other) calls to self.__contains__ and tmp.__contains__, where tmp = set(other). The current implementation uses len(self) + len(other) calls to tmp.__contains__.

Thus, I suspect the current implementation only has a chance at running noticeably faster when len(self) << len(other), where it performs fewer calls to set.__contains__. This is, however, also where the proposed implementation has significantly superior memory performance.

[rhettinger]

We care more about the running speed than the memory usage. Since sets only store pointers to data, they are typically smaller than the data they refer to.

I've attached some instrumentation code for running experiments to verify the workload under various scenarios.

[rhettinger]

I've run a few more experiments and this looks like a net win more often than not. Go ahead and submit a PR so we can evaluate it further.