classification
Title: obmalloc: stop simple arena thrashing
Type: performance Stage: resolved
Components: Interpreter Core Versions: Python 3.9
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: tim.peters Nosy List: methane, nascheme, tim.peters
Priority: normal Keywords: patch

Created on 2019-06-12 20:55 by tim.peters, last changed 2019-06-13 03:46 by tim.peters. This issue is now closed.

Pull Requests
URL Status Linked Edit
PR 14039 merged tim.peters, 2019-06-13 02:16
Messages (2)
msg345407 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2019-06-12 20:55
Scenario:  all arenas are fully used.  A program then runs a loop like:

while whatever:
    p = malloc(n)
    ...
    free(p)
    
At the top, a new arena has to be created, and a single object is taken out of a single pool.  At the bottom, that object is freed, so the arena is empty again, and so is returned to the system.  Which cycle continues so long as the loop runs.  Very expensive.

This is "something like" what happens in practice, and has been reported anecdotally for years, but I've never been clear on _exactly_ what programs were doing in such cases.  Neil S pointed out this recent report here:

https://mail.python.org/pipermail/python-dev/2019-February/156529.html

Which may or may not be relevant.  Inada?

The "fix" proposed there:

-    if (nf == ao->ntotalpools) {
+    if (nf == ao->ntotalpools && ao != usable_arenas) {

doesn't appeal to me, because it can lead to states where obmalloc never returns empty arenas, no matter how many pile up.  For example, picture a thousand arenas each with just one used pool.  The head of the arena list becomes free, so is left alone, but moves to the end of the list (which is sorted by number of free pools).  Then the new head of the list becomes free, and ditto.  On & on.  We're left with a list containing a thousand wholly unused arenas.

So I suggest instead:

+    if (nf == ao->ntotalpools && ao->nextarena != NULL) {

That is, instead of exempting the head of the list, exempt the tail of the list.  In the example above, the first 999 arenas are returned to the system, but the last one remains in the list for reuse.  In general, the change would allow for at most one empty arena in the list.

We can't in general predict the future, but this would be enough to stop the thrashing in the specific scenario given at the top, with no apparent serious failure modes (potentially "wasting" one arena is minor).
msg345453 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2019-06-13 03:41
New changeset d1c85a27ea9fe70163cad3443d5e534d94f08284 by Tim Peters in branch 'master':
bpo-37257:  obmalloc:  stop simple arena thrashing (#14039)
https://github.com/python/cpython/commit/d1c85a27ea9fe70163cad3443d5e534d94f08284
History
Date User Action Args
2019-06-13 03:46:07tim.peterssetstatus: open -> closed
resolution: fixed
stage: patch review -> resolved
2019-06-13 03:41:19tim.peterssetmessages: + msg345453
2019-06-13 02:16:51tim.peterssetkeywords: + patch
stage: test needed -> patch review
pull_requests: + pull_request13903
2019-06-12 21:26:54tim.peterssettype: performance
2019-06-12 20:55:31tim.peterscreate