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.

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

PyObject_Free is O(N) where N = # of arenas #81210

Closed
methane opened this issue May 24, 2019 · 8 comments
Closed

PyObject_Free is O(N) where N = # of arenas #81210

methane opened this issue May 24, 2019 · 8 comments
Assignees
@tim-one
Labels
3.8 only security fixes interpreter-core (Objects, Python, Grammar, and Parser dirs) performance Performance or resource usage

Comments

@methane
Copy link
Member

methane commented May 24, 2019

BPO 37029
Nosy @tim-one, @methane, @friedelwolff
PRs
  • bpo-37029: keep usable_arenas in sorted order without searching #13612
    		•
    Files
  • arena.py: Big test case - needs over 80GB of RAM
  • result.txt
  • free_arenas.txt: output with 2x and 4x strings
    		•

    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/tim-one'
closed_at = <Date 2019-06-01.02:19:40.540>
created_at = <Date 2019-05-24.05:33:57.956>
labels = ['interpreter-core', '3.8', 'performance']
title = 'PyObject_Free is O(N) where N = # of arenas'
updated_at = <Date 2019-06-03.20:51:08.950>
user = 'https://github.com/methane'

    bugs.python.org fields:

    activity = <Date 2019-06-03.20:51:08.950>
actor = 'tim.peters'
assignee = 'tim.peters'
closed = True
closed_date = <Date 2019-06-01.02:19:40.540>
closer = 'tim.peters'
components = ['Interpreter Core']
creation = <Date 2019-05-24.05:33:57.956>
creator = 'methane'
dependencies = []
files = ['48378', '48382', '48385']
hgrepos = []
issue_num = 37029
keywords = ['patch']
message_count = 8.0
messages = ['343344', '343734', '344024', '344082', '344083', '344141', '344383', '344474']
nosy_count = 3.0
nosy_names = ['tim.peters', 'methane', 'fwolff']
pr_nums = ['13612']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue37029'
versions = ['Python 3.8']
    @methane
    Copy link
    Member Author

    methane commented May 24, 2019

    Reported here:

    @methane methane added 3.8 only security fixes interpreter-core (Objects, Python, Grammar, and Parser dirs) performance Performance or resource usage labels May 24, 2019
    @methane methane changed the title PyObject_Free is O(N^2) where N = # of arenas PyObject_Free is O(N) where N = # of arenas May 24, 2019
    @tim-one
    Copy link
    Member

    tim-one commented May 28, 2019

    Created a PR and assigned myself to this bug.

    @tim-one tim-one self-assigned this May 28, 2019
    @tim-one
    Copy link
    Member

    tim-one commented May 31, 2019

    Added file arena.py. This adds some code to the OP's original test, to print out build time and teardown time, and display obmalloc stats.

    You'll need at least 80GB of RAM to run it - I don't have that much. Building the tree may take on the order of an hour, but the time to tear it down is what's interesting here. Apparently 3.7.3 needs more than 4 hours to reclaim the memory.

    @methane
    Copy link
    Member Author

    methane commented May 31, 2019

    master:

    build time 0:48:53.664428
    teardown time 4:58:20.132930

    patched:

    build time 0:48:08.485639
    teardown time 0:01:10.466707

    About 250x speedup!

    @tim-one
    Copy link
    Member

    tim-one commented May 31, 2019

    Thank you so much, Inada! That's very good to hear :-)

    @tim-one
    Copy link
    Member

    tim-one commented Jun 1, 2019

    New changeset 1c263e3 by Tim Peters in branch 'master':
    bpo-37029: keep usable_arenas in sorted order without searching (bpo-13612)
    1c263e3

    @tim-one tim-one closed this as completed Jun 1, 2019
    @friedelwolff
    Copy link
    Mannequin

    friedelwolff mannequin commented Jun 3, 2019

    I had a bit of time and access to a pretty big machine, so I ran the remove-arena-search branch with the same number of iterations, but also 2x and 4x as many. I attach the output in case it is interesting. The timings seem to be growing linearly with the number of strings. The teardown finishes within minutes.

    @tim-one
    Copy link
    Member

    tim-one commented Jun 3, 2019

    Thank you, Friedl! I appreciate the extra confirmation - and especially on even bigger test cases :-)

    @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

    @tim-one tim-one

    Labels
    3.8 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
    @methane @tim-one