Allow empty list append/insert to overallocate

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.
python · chadnetzer · Mar 21, 2021 · Mar 21, 2021 · Mar 21, 2021 · Mar 22, 2021
commit 657d51fcb25d7653fff91c044fde3452b2bce056
diff --git a/Objects/listobject.c b/Objects/listobject.c
@@ -58,8 +58,11 @@ list_resize(PyListObject *self, Py_ssize_t newsize)
         return 0;
     }
 
-    if (Py_SIZE(self) == 0 || newsize == 0) {
-        /* Don't overallocate for lists that start empty or are set to empty. */
+    if (newsize == 0 || (Py_SIZE(self) == 0 && newsize > 1)) {
+        /* Don't overallocate empty lists that are extended by more than 1
+         * element.  This helps ensure that list-literals aren't
+         * over-allocated, but still allows it for empty-list append/insert.
+         */
         new_allocated = newsize;
     }
     else {