[issue43574] Regression in overallocation for literal list initialization in v3.9+

[Inada Naoki]

Inada Naoki  added the comment:

Relating issue: https://twitter.com/nedbat/status/1489233208713437190
Current overallocation strategy is rough. We need to make it more smooth.

--
versions: +Python 3.11 -Python 3.9

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue43574] Regression in overallocation for literal list initialization in v3.9+

[Inada Naoki]

Change by Inada Naoki :


--
nosy: +methane

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue43574] Regression in overallocation for literal list initialization in v3.9+

[Raymond Hettinger]

Change by Raymond Hettinger :


--
nosy: +rhettinger

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue43574] Regression in overallocation for literal list initialization in v3.9+

[Kevin Mills]

Change by Kevin Mills :


--
nosy: +Zeturic

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue43574] Regression in overallocation for literal list initialization in v3.9+

[Gregory P. Smith]

Change by Gregory P. Smith :


--
nosy: +gregory.p.smith

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue43574] Regression in overallocation for literal list initialization in v3.9+

[STINNER Victor]

Change by STINNER Victor :


--
nosy:  -vstinner

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue43574] Regression in overallocation for literal list initialization in v3.9+

[Chad Netzer]

Chad Netzer  added the comment:

For bpo-43574, my initial plan was to change list_resize() so that it wouldn't
overallocate empty lists that were resized to be bigger, thus restoring the
overallocation behavior for list-literals to be like that of earlier Python
releases.

However, the list_resize() helper is also used by list appends and inserts, as
well as other list methods that change list sizes.  This proposed strategy of
not-overallocating any resize that starts with an empty list also affects
their behavior, and with the list-overallocation calculation that was
introduced with bpo-38373, this causes unexpected side-effects on the amount
of overallocation used for appending/inserting with an empty list.

Therefore, my updated proposal handles this by changing the overallocation
behavior in list_resize() only when empty lists are increased by an amount
greater than 1 during list_resize().  This basically retains the behavior of
not overallocating list-literals, while not changing the behavior for list
append/insert on an empty list.

To understand why this updated proposed change won't also cause overallocation
for length-1 literals, see below how length-1 and length-2 list-literals are
compiled using BUILD_LIST instead of LIST_EXTEND:

```
Python 3.9.2 (default, Mar 26 2021, 23:27:12)
>>> import dis
>>> def foo():
...   [1]
...
>>> dis.dis(foo)
  2   0 LOAD_CONST   1 (1)
  2 BUILD_LIST   1
  4 POP_TOP
  6 LOAD_CONST   0 (None)
  8 RETURN_VALUE
>>> def bar():
...   [1,2]
...
>>> dis.dis(bar)
  2   0 LOAD_CONST   1 (1)
  2 LOAD_CONST   2 (2)
  4 BUILD_LIST   2
  6 POP_TOP
  8 LOAD_CONST   0 (None)
 10 RETURN_VALUE
>>> def baz():
...   [1,2,3]
...
>>> dis.dis(baz)
  2   0 BUILD_LIST   0
  2 LOAD_CONST   1 ((1, 2, 3))
  4 LIST_EXTEND  1
  6 POP_TOP
  8 LOAD_CONST   0 (None)
 10 RETURN_VALUE
```


Hence, the change to list_resize(), which is called by list_extend() but not
the BUILD_LIST opcode, won't impact list-literals of length 1 and 2.


And to show how the originally proposed change (no overallocation for
list_resize() of empty lists) inadvertently changed how list append/insert
overallocation worked, let's first take a look at how current Python (3.9+)
works:

```
>>> l = []
>>> l.__sizeof__()
40
>>> l.append("a")  # First append will overallocate to capacity 4
>>> l.__sizeof__()
72
>>> l.append("b")
>>> l.__sizeof__()
72
>>> l.append("c")
>>> l.__sizeof__()
72
>>> l.append("d")
>>> l.__sizeof__()
72
>>> l.append("e")
>>> l.__sizeof__()
104
>>> l2 = ["a"]  # Length 1 (and 2) literals don't overallocate
>>> l2.__sizeof__()
48
>>> # However, note that the first append will overallocate to capacity 8
>>> l2.append("b")
>>> l2.__sizeof__()
104
```

Note that the list-literal of length 1 isn't overallocated, and that
appending to it skips the capacity 4 list and goes straight to capacity 8.

However, with my originally proposed change, this overallocation behavior is
duplicated even for lists that start empty, because the first append then
effectively becomes a non-overallocated list of length and capacity 1, which
means that the second append overallocates to capacity 8.

Here was the overallocation behavior of my first proposal, when an empty list
was appended:
```
Python 3.10.0a6+ (heads/bpo43574-dont-overallocate-list-literals:7436223a71, 
Apr  3 2021, 16:32:22) [Clang 12.0.0 (clang-1200.0.32.29)] on darwin
>>> l = []
>>> l.__sizeof__()
40
>>> l.append("a")
>>> l.__sizeof__()  # No overallocation on first append
48
>>> l.append("b")
>>> l.__sizeof__()  # Second append jumps to capacity 8, skipping 4
104
```

This is unexpected and likely undesirable behavior, as lists being created
empty and then appended to should be expected to follow the same documented 4,
8, 16, 24, ...  growth pattern for bpo-38373.

Fixing this is fairly simple because of the special-casing for length 1 and 2
list-literals, just by checking for the use of append/insert on an empty list.
Because they both change the size of a length 0 list to length 1, and the
list_resize() for literals always kicks in for changing to lengths 3 or more,
this updates proposal will retain the current empty-list insert/append
overallocation behavior, while still allowing list-literals of length 1 or
more to not overallocate.

With this updated proposal, avoiding a change to the behavior of an empty list
append/insert, the overallocation for list-literals is still removed, and the
current overallocation behavior for empty lists being appended is preserved:
```
Python 3.10.0a6+ (heads/bpo43574-dont-overallocate-list-literals-v2:56b361221d, 
Apr  3 2021, 17:35) [Clang 12.0.0 (clang-1200.0.32.29)] on darwin
>>> l = []
>>> 

[issue43574] Regression in overallocation for literal list initialization in v3.9+

[Brandt Bucher]

Change by Brandt Bucher :


--
nosy: +brandtbucher

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue43574] Regression in overallocation for literal list initialization in v3.9+

[Chad Netzer]

Change by Chad Netzer :


--
keywords: +patch
pull_requests: +23712
stage:  -> patch review
pull_request: https://github.com/python/cpython/pull/24954

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue43574] Regression in overallocation for literal list initialization in v3.9+

[Dong-hee Na]

Change by Dong-hee Na :


--
nosy: +corona10

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue43574] Regression in overallocation for literal list initialization in v3.9+

[Dong-hee Na]

Change by Dong-hee Na :


--
nosy: +serhiy.storchaka, vstinner

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue43574] Regression in overallocation for literal list initialization in v3.9+

[Chad Netzer]

New submission from Chad Netzer :

In Python v3.9+ there was a regression in the amount of used memory for
list-literals, due to switching to using list_extend() to allocate memory for
the new list to accomodate the literal elements.

Example, in Python v3.8.x (and before):
```
$ python38
Python 3.8.5 (default, Sep  4 2020, 02:22:02)
>>> [1].__sizeof__()
48
>>> [1,2].__sizeof__()
56
>>> [1,2,3].__sizeof__()
64
```

whereas for v3.9 (and later):
```
$ python39
Python 3.9.2 (default, Feb 19 2021, 17:09:53)
>>> [1].__sizeof__()
48
>>> [1,2].__sizeof__()
56
>>> [1,2,3].__sizeof__()
104  # a 60% increase in memory allocated
```

However, this seems like an unintented regression, and is a side-effect of the
new way of building the lists from literals, using the list_extend() function 
(via
list_resize(), which overallocates).  In particular, a consequence is that
making a copy of the list that's initialized from a literal can end up using
less memory:
```
$ python39
Python 3.9.2 (default, Feb 19 2021, 17:09:53)
>>> a = [1,2,3]
>>> b = list(a)  # Same behavior if list.copy() or slice copy is performed
>>> a.__sizeof__()
104
>>> b.__sizeof__()
64
```

Prior to v3.9, the byte-code for making a list from a literal had the
"BUILD_LIST" opcode with an explicit length argument, allowing allocation of
the exact amount of memory needed for the literal.  As of v3.9, the
LIST_EXTEND opcode is used, instead.  I believe the simplest way of restoring
the old behavior is to change list_extend() to not overallocate when the list
being extended currently has 0 elements.


Ie. a minimal-change patch to restore the previous behavior (though with a
side-effect of removing the overallocaton of a list that is initialzed empty,
and then immediately extended):

diff --git a/Objects/listobject.c b/Objects/listobject.c
index e7987a6d35..7820e033af 100644
--- a/Objects/listobject.c
+++ b/Objects/listobject.c
@@ -75,8 +75,9 @@ list_resize(PyListObject *self, Py_ssize_t newsize)
 if (newsize - Py_SIZE(self) > (Py_ssize_t)(new_allocated - newsize))
 new_allocated = ((size_t)newsize + 3) & ~(size_t)3;

-if (newsize == 0)
-new_allocated = 0;
+/* Don't overallocate for lists that start empty or are set to empty. */
+if (newsize == 0 || Py_SIZE(self) == 0)
+new_allocated = newsize;
 num_allocated_bytes = new_allocated * sizeof(PyObject *);
 items = (PyObject **)PyMem_Realloc(self->ob_item, num_allocated_bytes);
 if (items == NULL) {



Relevant/related bugs/PRs:
# Switched to initializing list literals w/ LIST_EXTEND
https://bugs.python.org/issue39320
https://github.com/python/cpython/pull/17984

# Commit where over-allocation of list literals first appeared
https://bugs.python.org/issue38328
https://github.com/python/cpython/pull/17114
https://github.com/python/cpython/commit/6dd9b64770af8905bef293c81d541eaaf8d8df52

https://bugs.python.org/issue38373
https://github.com/python/cpython/pull/18952
https://github.com/python/cpython/commit/2fe815edd6778fb9deef8f8044848647659c2eb8

--
components: Interpreter Core
messages: 389207
nosy: Chad.Netzer
priority: normal
severity: normal
status: open
title: Regression in overallocation for literal list initialization in v3.9+
type: resource usage
versions: Python 3.10, Python 3.9

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com