Author tim.peters
Recipients inada.naoki, nascheme, tim.peters
Date 2019-06-12.20:55:30
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1560372931.23.0.979771460507.issue37257@roundup.psfhosted.org>
In-reply-to
Content
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).
History
Date User Action Args
2019-06-12 20:55:31tim.peterssetrecipients: + tim.peters, nascheme, inada.naoki
2019-06-12 20:55:31tim.peterssetmessageid: <1560372931.23.0.979771460507.issue37257@roundup.psfhosted.org>
2019-06-12 20:55:31tim.peterslinkissue37257 messages
2019-06-12 20:55:30tim.peterscreate