python
`collections.deque` freelist blocks could be chained together
Feature or enhancement
Proposal:
Convert freeblocks to a single pointer, and chain the free blocks through the rightlink (or the leftlink for small-endian).
Justification:
When the deque freelist was moved from global to per-instance, the freelist array was simply moved into the structure, adding MAXFREEBLOCKS = 16 pointers (128 bytes) to the static overhead of the struct, bringing it from 104 bytes to 232 bytes.
But the blocks can be chained directly, so the freelist could be a linked list of blocks, reducing freeblocks to a single pointer and saving 120 bytes.
In the grand scheme of things this is not huge savings especially as deque preallocates a block (528 bytes) on creation, but it's still 15% less overhead on deques up to 64 elements.
As an aside, and probably pretty minor, as far as I can tell deque_dealloc calls deque_clear which calls freeblock, this should shift up to MAXFREEBLOCKS into the freelist (freeing the rest), then actually free those during the second pass.
Couldn't deque_dealloc set numfreeblocks to MAXFREEBLOCKS to ensure all live blocks are freed immediately, to avoid the extra work of shifting them to the freelist?
Has this already been discussed elsewhere?
This is a minor feature, which does not need previous discussion elsewhere
Links to previous discussion of this feature:
No response
