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

[methane]

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]

Reported here:

• https://stackoverflow.com/questions/56228799/python-hangs-indefinitely-trying-to-delete-deeply-recursive-object
• https://mail.python.org/pipermail/python-dev/2019-May/157635.html

[tim-one]

Created a PR and assigned myself to this bug.

[tim-one]

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]

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]

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

[tim-one]

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

[friedelwolff]

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]

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