[Python-Dev] Have a big machine and spare time? Here's a possible Python bug.

Tim Peters tim.peters at gmail.com
Fri May 24 21:04:43 EDT 2019

> I'll note that the approach I very briefly sketched before
> (restructure the list of arenas to partition it into multiple lists
> partitioned by number of free pools) "should make" obmalloc
> competitive with malloc here ...

But it's also intrusive, breaking up a simple linked list into a
mutli-headed beast.  That affects all code using it, not just the
parts mutating it.

So instead I suggest leaving `usable_arenas` entirely alone, but add a
vector of "search fingers", say,

static struct arenaobject* nfp2lasta[MAX_NUMBER_OF_FREE_POOLS_POSSIBLE + 1];

mapping a count of free pools to (a pointer to) the last arena object
in usable_arenas with that number of free pools.

Then the search loop in py_malloc_free() can be replaced with a single
array lookup.:  it leaps directly to where the search loop ends now.
For example, if we free a pool in an arena that had 23 free pools,
then the arena object's count of free pools has to be increased to 24,
and the arena object unlinked from its current position in
usable_arenas and inserted immediately after nfp2lasta[23].  Note that
usable_arenas is a doubly linked list, so there's no _need_ at all to
iterate over it.  Each node in the list knows what's immediately
before and after it.  And since a free pool count can only increase by
1, it's always correct to move the arena immediately after the last
arena with the same original free pool count.

Key invariants:

1. nfp2lasta[n] is NULL if and only if no arena in usable_arenas has
nfreepools == n.

2. nfp2lasta[pa->nfreepools] == pa if and only if pa is the only arena
in usable_arenas with that many free pools.

So, in the example above,  nfp2lasta[23] has to be set to NULL if and
only if the arena in question was the only one with 23 free pools
(which can be determined cheaply via invariant #2).

And nfp2lasta[24] has to be set to point to the arena in question if
and only if nfp2lasta[24] is NULL.

Tricky bit:  if the arena in question is the only one with a given
original free pool count, no pointers in arena objects need to be
changed at all.  Following the sketch above literally would leave you
trying to insert it after itself, which wouldn't end well  ;-)

Anyway, this "feels like a right solution" to me, eliminating all
searches with simple (albeit delicate) constant-time code, and
requiring code changes only where an arena's number of free pools can

More information about the Python-Dev mailing list