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 some set operations in dictkeys object #82794

Closed
methane opened this issue Oct 28, 2019 · 7 comments
Closed

Optimize some set operations in dictkeys object #82794

methane opened this issue Oct 28, 2019 · 7 comments
Labels
3.9 only security fixes interpreter-core (Objects, Python, Grammar, and Parser dirs) performance Performance or resource usage

Comments

@methane
Copy link
Member

methane commented Oct 28, 2019

BPO 38613
Nosy @rhettinger, @methane, @serhiy-storchaka
PRs
  • bpo-38613: Optimize set operations of dict keys. #16961
    		•

    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 = None
closed_at = <Date 2019-11-07.15:59:26.668>
created_at = <Date 2019-10-28.11:55:45.109>
labels = ['interpreter-core', '3.9', 'performance']
title = 'Optimize some set operations in dictkeys object'
updated_at = <Date 2019-11-07.15:59:26.667>
user = 'https://github.com/methane'

    bugs.python.org fields:

    activity = <Date 2019-11-07.15:59:26.667>
actor = 'methane'
assignee = 'none'
closed = True
closed_date = <Date 2019-11-07.15:59:26.668>
closer = 'methane'
components = ['Interpreter Core']
creation = <Date 2019-10-28.11:55:45.109>
creator = 'methane'
dependencies = []
files = []
hgrepos = []
issue_num = 38613
keywords = ['patch']
message_count = 7.0
messages = ['355536', '355541', '355618', '355619', '355662', '355695', '356195']
nosy_count = 3.0
nosy_names = ['rhettinger', 'methane', 'serhiy.storchaka']
pr_nums = ['16961']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue38613'
versions = ['Python 3.9']
    @methane
    Copy link
    Member Author

    methane commented Oct 28, 2019

    -, |, and ^ of dictkeys are implemented as:

    PyObject *result = PySet_New(self);
// Call set.difference_update, set.update, set.symmetric_difference_update with other.

    PySet_New(iterable) has optimized step for iterable is dict.
    But since iterable is dictkeys, PyIter_Next() is called for all elements in the dict.

    We can pass dict instead of dictkey object to PySet_New.

      $ ./python -m pyperf timeit -o patched.json -s 'k = dict.fromkeys("abcdefghijklmnopqrstuvwxyz").keys(); s={1,2,3}' -- 'k | {1,2,3}'
  $ ./python -m pyperf compare_to master.json patched.json
  Mean +- std dev: [master] 778 ns +- 17 ns -> [patched] 550 ns +- 24 ns: 1.42x faster (-29%)

    @methane methane added 3.9 only security fixes interpreter-core (Objects, Python, Grammar, and Parser dirs) performance Performance or resource usage labels Oct 28, 2019
    @serhiy-storchaka
    Copy link
    Member

    How does it work with dict subclasses?

    @methane
    Copy link
    Member Author

    methane commented Oct 29, 2019

    How does it work with dict subclasses?

    PySet_New(iterable) uses fast path only when PyDict_CheckExact(iterable) is true.

    So there is no change for dict subclasses.

    @serhiy-storchaka
    Copy link
    Member

    But what if a dict subclass overrides __iter__? You can get different result if set(d) != set(d.keys()).

    @rhettinger
    Copy link
    Contributor

    Consider testing PyDict_CheckExact.

    @methane
    Copy link
    Member Author

    methane commented Oct 30, 2019

    done.

    @methane
    Copy link
    Member Author

    methane commented Nov 7, 2019

    New changeset 6cbc84f by Inada Naoki in branch 'master':
    bpo-38613: Optimize set operations of dict keys. (GH-16961)
    6cbc84f

    @methane methane closed this as completed Nov 7, 2019
    @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
    No one assigned
    Labels
    3.9 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
    3 participants
    @methane @rhettinger @serhiy-storchaka