Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Optimize set.issuperset() for non-set argument #90877

Closed
serhiy-storchaka opened this issue Feb 11, 2022 · 3 comments
Closed

Optimize set.issuperset() for non-set argument #90877

serhiy-storchaka opened this issue Feb 11, 2022 · 3 comments
Assignees
@rhettinger
Labels
3.11 only security fixes interpreter-core (Objects, Python, Grammar, and Parser dirs) performance Performance or resource usage

Comments

@serhiy-storchaka
Copy link
Member

BPO 46721
Nosy @rhettinger, @serhiy-storchaka
PRs
  • bpo-46721: Optimize set.issuperset() for non-set arguments #31280
    		•

    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 = <Date 2022-04-06.17:05:20.544>
created_at = <Date 2022-02-11.15:15:23.893>
labels = ['interpreter-core', '3.11', 'performance']
title = 'Optimize set.issuperset() for non-set argument'
updated_at = <Date 2022-04-06.17:05:20.543>
user = 'https://github.com/serhiy-storchaka'

    bugs.python.org fields:

    activity = <Date 2022-04-06.17:05:20.543>
actor = 'serhiy.storchaka'
assignee = 'rhettinger'
closed = True
closed_date = <Date 2022-04-06.17:05:20.544>
closer = 'serhiy.storchaka'
components = ['Interpreter Core']
creation = <Date 2022-02-11.15:15:23.893>
creator = 'serhiy.storchaka'
dependencies = []
files = []
hgrepos = []
issue_num = 46721
keywords = ['patch']
message_count = 3.0
messages = ['413075', '413076', '416887']
nosy_count = 2.0
nosy_names = ['rhettinger', 'serhiy.storchaka']
pr_nums = ['31280']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue46721'
versions = ['Python 3.11']
    @serhiy-storchaka
    Copy link
    Member Author

    If the argument of set.issuperset() is not a set, it is first converted to a set. It is equivalent to the following code:

        if not isinstance(other, (set, frozenset)):
        other = set(other)
    # The following is equivalent to:
    # return set.issubset(other, self)
    for x in other:
        if x not in self
            return False
    return True

    Two drawbacks of this algorithm:

    1. It creates a new set, which takes O(len(other)) time and consumes O(len(set(other))) memory.
    2. It needs to iterate other to the end, even if the result is known earlier.

    The proposed PR straightforward the code. The C code is now larger, but it no longer need additional memory, performs less operations and can stop earlier.

    @serhiy-storchaka serhiy-storchaka added 3.11 only security fixes interpreter-core (Objects, Python, Grammar, and Parser dirs) performance Performance or resource usage labels Feb 11, 2022
    @serhiy-storchaka
    Copy link
    Member Author

    The new code is similar to the code of set.isdisjoint(), so we can share the code if generalize it.

    @serhiy-storchaka
    Copy link
    Member Author

    New changeset a69a4a9 by Serhiy Storchaka in branch 'main':
    bpo-46721: Optimize set.issuperset() for non-set arguments (GH-31280)
    a69a4a9

    @ezio-melotti ezio-melotti transferred this issue from another repository Apr 10, 2022
    Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
    Assignees

    @rhettinger rhettinger

    Labels
    3.11 only security fixes interpreter-core (Objects, Python, Grammar, and Parser dirs) performance Performance or resource usage
    Projects
    None yet
    Milestone
    No milestone
    Development

    No branches or pull requests
    2 participants
    @rhettinger @serhiy-storchaka