classification
Title: PyObject_Free is O(N) where N = # of arenas
Type: performance Stage: resolved
Components: Interpreter Core Versions: Python 3.8
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: tim.peters Nosy List: fwolff, inada.naoki, tim.peters
Priority: normal Keywords: patch

Created on 2019-05-24 05:33 by inada.naoki, last changed 2019-06-03 20:51 by tim.peters. This issue is now closed.

Files
File name Uploaded Description Edit
arena.py tim.peters, 2019-05-31 05:15 Big test case - needs over 80GB of RAM
result.txt inada.naoki, 2019-05-31 15:51
free_arenas.txt fwolff, 2019-06-03 05:59 output with 2x and 4x strings
Pull Requests
URL Status Linked Edit
PR 13612 merged tim.peters, 2019-05-28 06:01
Messages (8)
msg343344 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2019-05-24 05:33
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
msg343734 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2019-05-28 06:05
Created a PR and assigned myself to this bug.
msg344024 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2019-05-31 05:15
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.
msg344082 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2019-05-31 15:51
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!
msg344083 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2019-05-31 16:01
Thank you so much, Inada!  That's very good to hear :-)
msg344141 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2019-06-01 02:16
New changeset 1c263e39c4ed28225a7dc8ca1f24953225ac48ca by Tim Peters in branch 'master':
bpo-37029:  keep usable_arenas in sorted order without searching (#13612)
https://github.com/python/cpython/commit/1c263e39c4ed28225a7dc8ca1f24953225ac48ca
msg344383 - (view) Author: Friedel Wolff (fwolff) Date: 2019-06-03 05:59
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.
msg344474 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2019-06-03 20:51
Thank you, Friedl!  I appreciate the extra confirmation - and especially on even bigger test cases :-)
History
Date User Action Args
2019-06-03 20:51:08tim.peterssetmessages: + msg344474
2019-06-03 05:59:52fwolffsetfiles: + free_arenas.txt
nosy: + fwolff
messages: + msg344383

2019-06-01 02:19:40tim.peterssetstatus: open -> closed
resolution: fixed
stage: patch review -> resolved
2019-06-01 02:16:08tim.peterssetmessages: + msg344141
2019-05-31 16:01:53tim.peterssetmessages: + msg344083
2019-05-31 15:51:44inada.naokisetfiles: + result.txt

messages: + msg344082
2019-05-31 05:15:49tim.peterssetfiles: + arena.py

messages: + msg344024
2019-05-28 06:05:01tim.peterssetassignee: tim.peters
messages: + msg343734
2019-05-28 06:01:51tim.peterssetkeywords: + patch
stage: patch review
pull_requests: + pull_request13516
2019-05-24 12:40:43inada.naokisettitle: PyObject_Free is O(N^2) where N = # of arenas -> PyObject_Free is O(N) where N = # of arenas
2019-05-24 05:33:57inada.naokicreate