bpo-43574: Dont overallocate list literals by chadnetzer · Pull Request #24954

bpo-43574: Dont overallocate list literals by chadnetzer · Pull Request #24954 · python/cpython

added 3 commits

March 20, 2021 20:00

This restores the behavior of Python versions before v3.9, where a list
initialized from a list literal allocates memory for exactly as many
elements as it contains (until a list append or other operation that
changes the list size).

The interpreter was changed in v3.9 to use the LIST_EXTEND bytecode to
initialize a new list from a literal, which caused it to overallocate.
By not performing this over-allocation on an empty list, we restored the
original behavior (though now explicitly creating an empty list and
extending it once will also not result in an over-allocation).

Ensure that lists initialized from both list-literals and iterables of known
length are initialized without over-allocation, by comparing them with
allocation of lists initialized from an unknown size where over-allocation is
expected.

The list_resize() helper is used by single-item list appends and
inserts, which normally would overallocate (to a capacity of 4) on the
first added element, and then again to 8 when the capacity is filled.
But if this over-allocation is postponed on the first added element, the
current expansion formula would then over-allocate to a capacity of 8 on
the second append/insertion.

List-literals of length 1 and 2 are not created with the list_extend()
function (which then calls list_resize()), but instead built directly as
capacity 1 or 2 lists with the BUILD_LIST opcode.  By excluding the
special case for list_resize() of empty lists when newsize is greater
than 1, its allows list append/insert to continue to over-allocate
without skipping capacity 4.

Confirm that list-literals aren't over-allocated by directly checking
their used memory, which is the combination of the size of an empty list
and the number of pointers needed for a list of exactly that length.