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

Apply the setobject optimizations to dictionaries #63098

Closed
rhettinger opened this issue Sep 1, 2013 · 6 comments
Closed

Apply the setobject optimizations to dictionaries #63098

rhettinger opened this issue Sep 1, 2013 · 6 comments
Labels
interpreter-core (Objects, Python, Grammar, and Parser dirs) performance Performance or resource usage

Comments

@rhettinger
Copy link
Contributor

BPO 18898
Nosy @tim-one, @rhettinger, @pitrou, @vstinner, @markshannon, @ericsnowcurrently, @serhiy-storchaka
Files
  • noincref.diff: First draft to eliminate incref/decref on dummy objects
    		•

    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 2016-01-26.03:38:40.456>
created_at = <Date 2013-09-01.05:14:53.522>
labels = ['interpreter-core', 'performance']
title = 'Apply the setobject optimizations to dictionaries'
updated_at = <Date 2016-01-26.03:38:40.454>
user = 'https://github.com/rhettinger'

    bugs.python.org fields:

    activity = <Date 2016-01-26.03:38:40.454>
actor = 'rhettinger'
assignee = 'none'
closed = True
closed_date = <Date 2016-01-26.03:38:40.456>
closer = 'rhettinger'
components = ['Interpreter Core']
creation = <Date 2013-09-01.05:14:53.522>
creator = 'rhettinger'
dependencies = []
files = ['31597']
hgrepos = []
issue_num = 18898
keywords = ['patch']
message_count = 6.0
messages = ['196706', '196710', '196909', '234881', '239382', '258944']
nosy_count = 9.0
nosy_names = ['tim.peters', 'rhettinger', 'pitrou', 'vstinner', 'eli.bendersky', 'Mark.Shannon', 'eric.snow', 'serhiy.storchaka', 'Alan.Cristhian']
pr_nums = []
priority = 'low'
resolution = None
stage = None
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue18898'
versions = ['Python 3.5']
    @rhettinger
    Copy link
    Contributor Author

    Once http://bugs.python.org/issue18835 is resolved, I would like to see the various set optimizations applied to dictionaries as well:

    • Move the key before the hash in the dict struct (the key is accessed more frequently in the code and being in the first struct position allows it to be looked-up without a struct offset).

    • Don't INCREF and DECREF dummy objects. Only one reference needs to be held. See http://bugs.python.org/issue18797

    • Reduce the cost of hash collisions by inspecting nearby dict entries for matches prior to moving on to other probes elsewhere in memory. See http://bugs.python.org/issue18771

    • Make the previous improvement more effective by using aligned memory allocations for the dict tables. See http://bugs.python.org/issue18835

    Collectively, these optimizations can substantially improve dictionary performance.

    @rhettinger rhettinger added interpreter-core (Objects, Python, Grammar, and Parser dirs) performance Performance or resource usage labels Sep 1, 2013
    @ericsnowcurrently
    Copy link
    Member

    +1 This is worth trying.

    @elibendersky
    Copy link
    Mannequin

    elibendersky mannequin commented Sep 4, 2013

    I'm still interested in seeing benchmarks that show where this actually improves things and by how much. Also, whether any regressions occur and how serious they are.

    @serhiy-storchaka
    Copy link
    Member

    noincref.diff doesn't contain all necessary changes. For example dummy is increfed in dict_pop() and dict_popitem() and may be decrefed at insert.

    As in sets we can got rid of few comparisons with dummy if set dummy hashes to -1.

    @vstinner
    Copy link
    Member

    Hi, what's the status of this issue? Is anyone working one it?

    @rhettinger
    Copy link
    Contributor Author

    Hi, what's the status of this issue? Is anyone working one it?

    In the present environment, I feel like advancing this work would be an uphill battle and that much of my time investment would be wasted unnecessarily.

    That's too bad, because significant r&d time has already been invested and it has had nice payoffs with set objects.

    @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
    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
    4 participants
    @vstinner @ericsnowcurrently @rhettinger @serhiy-storchaka