[issue32846] Deletion of large sets of strings is extra slow

[Tim Peters]

Tim Peters <tim at python.org> added the comment:

Looks likely that the _major_ cause of the quadratic-time delete behavior was due to that obmalloc used a linear-time method to keep its linked list of usable arenas sorted in order of number of free pools.  When a pool became unused, its arena's count of free pools increased by one, and then order was restored by moving the arena "to the right" in the linked list, one slot at a time.

When there were only a few hundred arenas, nobody noticed.  But programs with thousands of arenas could suffer very noticeable sloth, and programs with hundreds of thousands could appear to hang (could require days to complete deleting).

This was fixed in issue #37029, using a constant-time method to restore sorted order, scheduled for release in Python 3.8.

----------
stage:  -> resolved
versions: +Python 3.8 -Python 3.9

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