GeezerVison

Hello, and thanks for your contribution!

I'm a bot set up to make sure that the project can legally accept this contribution by verifying everyone involved has signed the PSF contributor agreement (CLA).

CLA Missing

Our records indicate the following people have not signed the CLA:

@chadnetzer

For legal reasons we need all the people listed to sign the CLA before we can look at your contribution. Please follow the steps outlined in the CPython devguide to rectify this issue.

If you have recently signed the CLA, please wait at least one business day
before our records are updated.

You can check yourself to see if the CLA has been received.

Thanks again for the contribution, we look forward to reviewing it!

A Python core developer has requested some changes be made to your pull request before we can consider merging it. If you could please address their requests along with any other requests in other reviews from core developers that would be appreciated.

Once you have made the requested changes, please leave a comment on this pull request containing the phrase I have made the requested changes; please review again. I will then notify any core developers who have left a review that you're ready for them to take another look at this pull request.

I have made the requested changes; please review again.

Let me know if the test_overallocation tests (Lib/test/test_list.py) seem reasonable, or overkill.

Thanks for making the requested changes!

@pitrou: please review the changes made to this pull request.

I'll let other people review before merging this.

Hmmm. The list_resize() function is used elsewhere in Objects/listobject.c, and in particular is called on lists (empty or otherwise) when inserting, appending, etc. So this PR will have an effect on empty lists in those areas as well, not just for list_extend(). This will essentially delay overallocation for empty lists in those situations (until after the first insert, append, etc), and possibly affect the amount of overallocation afterwards.

In the interest of fairness, I'll gather some examples to show the behavior change, at least to help decide if any of those situations will suffer a negative consequence as a result. (I'll edit this comment to with the examples, when ready)

Edit: Okay, so there is an additional complication with this change; really it's meant to target list_extend(), which is now used to initialize new lists from literals of length 2 or more, but it's implemented by changing list_resize(), which is used by more than list_extend(). And in particular, it also changes the behavior of appending or inserting to an empty list, by also not overallocating on that first append.

However, the current behavior (unpatched 3.10alpha), for an empty list, is to overallocate on the first append/insert, to allow space for 4 elements, and then overallocate again (to space for 8 elements) when the 4 elements are added. With this patch to list_resize(), however, the first append will not overallocate and so when appending the second item to that list, it will overallocate directly to 8 elements (skipping the overallocation for 4 items entirely).

Overall this is likely undesirable, and certainly not intended by this fix, it's just a side-effect of doing the work in the common helper (list_resize()) for list extend/append/insert/etc.

Here's an example of the list append/insert behavior change, to clarify:

$ ./python.exe
Python 3.10.0a6+ (remotes/gh/master:20a5b7e986, Mar 23 2021, 17:07:20) [Clang 12.0.0 (clang-1200.0.32.29)] on darwin
>>> # Here's the current insert behavior without the proposed [bpo-43574](https://bugs.python.org/issue43574) patch
>>> l = []
>>> l.__sizeof__()
40
>>> l.append("eggs")  # first append overallocates by 3 slots (ie. 4 total, 1 used)
>>> l.__sizeof__()
72
>>> l.append("ham")  # additional appends don't overallocate until 4 slots are used
>>> l.__sizeof__()
72

but with the patch, which (unintentionally) delays the over-allocation of the first append to an empty list

# Now w/ [bpo-43574](https://bugs.python.org/issue43574) patch (no overallocation for extends on empty lists)
$ ./python.exe
Python 3.10.0a6+ (heads/bpo43574-dont-overallocate-list-literals:7436223a71, Mar 23 2021, 17:40:29) [Clang 12.0.0 (clang-1200.0.32.29)] on darwin
>>> l = []
>>> l.__sizeof__()
40
>>> l.append("eggs")  # No overallocation on first append
>>> l.__sizeof__()
48
>>> l.append("ham")  # So the second append skips 4 total items, and allocates space for 8 items
>>> l.__sizeof__()
104

So, I think that warrants a delay in merging and some further consideration of how to handle this; I can think of a few ways to "fix" this, but not without some additional complication. Basically because we want to signal that initializing a list from a known number of items shouldn't overallocate, but adding to an already created list should be able to do so, which isn't quite expressible in the helper functions we have currently, imo. Or possibly we don't care about over-allocating when initializing from a known number of items (though it's a regression), but maybe we want to ensure that a known 3 or 4 item list doesn't immediately over-allocate to 8 items (before any appends, etc.) is what we want to change...

Edit 2: I think I have 1 or 2 fairly straightforward ways to adjust this PR to remain on-target for restoring list-literal overallocation behavior, w/o also inadvertently affecting list append/insert over-allocation behavior, but will have to wait until the weekend to follow up w/ the details (fyi).

I made a small but significant tweak to my original proposal, and added a lot of of commentary to the bug tracker issue. Basically, the latest tweak restores the existing list append/insert behavior for empty lists, while still reverting back to the long-standing behavior of not overallocating list-literals (which, for length 3 or more, are created by using the list_extend() helper)

A Python core developer has requested some changes be made to your pull request before we can consider merging it. If you could please address their requests along with any other requests in other reviews from core developers that would be appreciated.

Once you have made the requested changes, please leave a comment on this pull request containing the phrase I have made the requested changes; please review again. I will then notify any core developers who have left a review that you're ready for them to take another look at this pull request.

This PR is stale because it has been open for 30 days with no activity.

This missed the boat for inclusion in Python 3.9 which accepts security fixes only as of today.

Is this PR still relevant since #31816 was merged?

Is this PR still relevant since #31816 was merged?

I think no. This PR and the #87740 can be closed.