[New-bugs-announce] [issue37257] obmalloc: stop simple arena thrashing

[Tim Peters]

New submission from Tim Peters <tim at python.org>:

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).

----------
assignee: tim.peters
components: Interpreter Core
messages: 345407
nosy: inada.naoki, nascheme, tim.peters
priority: normal
severity: normal
stage: test needed
status: open
title: obmalloc:  stop simple arena thrashing
versions: Python 3.9

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue37257>
_______________________________________