Co powoduje [* a] ogólną alokację?

136

Wygląda na list(a)to, że totalocate, [x for x in a]totalocates w niektórych momentach i [*a]totalocate przez cały czas ?

Rozmiary do n = 100

Oto rozmiary n od 0 do 12 i wynikowe rozmiary w bajtach dla trzech metod:

0 56 56 56
1 64 88 88
2 72 88 96
3 80 88 104
4 88 88 112
5 96 120 120
6 104 120 128
7 112 120 136
8 120 120 152
9 128 184 184
10 136 184 192
11 144 184 200
12 152 184 208

Obliczony w ten sposób, odtwarzalny w repl.it , przy użyciu Python 3. 8 :

from sys import getsizeof

for n in range(13):
    a = [None] * n
    print(n, getsizeof(list(a)),
             getsizeof([x for x in a]),
             getsizeof([*a]))

Więc: jak to działa? Jak działa [*a]totalocate? Jakiego mechanizmu używa do tworzenia listy wyników na podstawie danych wejściowych? Czy używa iteratora ai używa czegoś takiego list.append? Gdzie jest kod źródłowy?

( Colab z danymi i kodem, który wytworzył obrazy).

Powiększanie do mniejszego n:

Rozmiary do n = 40

Pomniejszanie do większego n:

Rozmiary do n = 1000

Stefan Pochmann
źródło
1
Fwiw, rozszerzając swoje przypadki testowe, wydawałoby się, że rozumienie listy zachowuje się jak pisanie pętli i dołączanie każdego elementu do listy, podczas gdy [*a]wydaje się zachowywać jak używanie extendna pustej liście.
jdehesa
4
Pomocne może być spojrzenie na kod bajtu wygenerowany dla każdego z nich. list(a)działa całkowicie w C; może przydzielać wewnętrzny węzeł buforowy po węźle podczas iteracji a. [x for x in a]po prostu LIST_APPENDdużo zużywa , więc podąża za normalnym wzorcem „ogólnie przydzielać trochę, w razie potrzeby ponownie przydzielać” normalnej listy. [*a]używa BUILD_LIST_UNPACK, które ... nie wiem, co to robi, poza tym, że najwyraźniej cały czas
nadmiar
2
Również w Pythonie 3.7, wydaje się, że list(a)i [*a]są identyczne, a obie overallocate porównaniu [x for x in a], więc ... sys.getsizeofnie może być właściwym narzędziem do wykorzystania tutaj.
chepner
7
@chepner Myślę, że sys.getsizeofto właściwe narzędzie, to po prostu pokazuje, że list(a)używałeś do generalocate. Właściwie to, co nowego w Python 3.8 wspomina: „Konstruktor listy nie dokonuje ogólnej alokacji [...]” .
Stefan Pochmann
5
@chepner: To był błąd naprawiony w 3.8 ; Konstruktor nie powinien ogólnie przydzielać.
ShadowRanger

Odpowiedzi:

81

[*a] wykonuje wewnętrznie C odpowiednik :

  1. Zrób nowy, pusty list
  2. Połączenie newlist.extend(a)
  3. Powraca list.

Jeśli więc rozszerzysz swój test na:

from sys import getsizeof

for n in range(13):
    a = [None] * n
    l = []
    l.extend(a)
    print(n, getsizeof(list(a)),
             getsizeof([x for x in a]),
             getsizeof([*a]),
             getsizeof(l))

Wypróbuj online!

zobaczysz wyniki dla getsizeof([*a])i l = []; l.extend(a); getsizeof(l)są takie same.

Zazwyczaj jest to właściwe postępowanie; podczas extending zazwyczaj spodziewasz się dodać więcej później, i podobnie w przypadku ogólnego rozpakowywania, zakłada się, że wiele rzeczy zostanie dodanych jeden po drugim. [*a]to nie jest normalny przypadek; Python zakłada, że ​​do list( [*a, b, c, *d]) jest dodawanych wiele elementów lub iteracji , więc ogólna alokacja oszczędza pracę w typowym przypadku.

W przeciwieństwie do tego, listskonstruowany z jednego, zalecanego iterowalnego (z list()) może nie rosnąć lub kurczyć się podczas użytkowania, a ogólne przydziały są przedwczesne, dopóki nie zostanie udowodnione inaczej; Ostatnio Python naprawił błąd, który spowodował, że konstruktor ogólnie przydzielił się nawet dla danych wejściowych o znanym rozmiarze .

Jeśli chodzi o listrozumienie, są one faktycznie równoważne powtarzanym appends, więc widzisz końcowy wynik normalnego wzorca wzrostu ogólnej alokacji podczas dodawania elementu na raz.

Żeby było jasne, nic z tego nie stanowi gwarancji językowej. Tak właśnie implementuje to CPython. Języku specyfikacji Python ogół obojętny konkretnych wzorców wzrostu w list(oprócz poręczającym amortyzowane O(1) appendS i popS z końcu). Jak zauważono w komentarzach, konkretne wdrożenie ponownie zmienia się w wersji 3.9; chociaż nie będzie to miało wpływu [*a], może to wpłynąć na inne przypadki, w których to, co kiedyś było „buduje tymczasowe tuplepojedyncze elementy, a następnie extendz tuple„ teraz staje się wieloma aplikacjami LIST_APPEND, które mogą się zmienić, gdy wystąpi ogólna alokacja i jakie liczby zostaną uwzględnione w obliczeniach.

ShadowRanger
źródło
4
@StefanPochmann: Przeczytałem wcześniej kod (dlatego już to wiedziałem). Jest to moduł obsługi bajtówBUILD_LIST_UNPACK , który używa _PyList_Extendjako równoważnika C wywoływania extend(tylko bezpośrednio, a nie poprzez wyszukiwanie metod). Połączyli go ze ścieżkami budowania tuplez rozpakowaniem; tuplenie ładują się ogólnie przy budowaniu fragmentarycznym, więc zawsze rozpakowują się na list(aby skorzystać z ogólnej alokacji) i przechodzą tuplena koniec, kiedy jest to wymagane.
ShadowRanger
4
Zauważ, że ten pozornie zmienia się w 3.9 , gdzie budowa odbywa się z odrębnych bytecodes ( BUILD_LIST, LIST_EXTENDdla każdego coś się rozpakować, LIST_APPENDdla pojedynczych elementów), zamiast ładowania wszystkiego na stosie przed budową cały listz jednej instrukcji kodu bajtowego (to pozwala kompilator wykonywać optymalizacje że instrukcja all-in-one nie pozwalają, jak wdrożenie [*a, b, *c]jak LIST_EXTEND, LIST_APPEND, LIST_EXTENDw / o konieczności owinąć bw jedno- tupledo spełnienia wymagań BUILD_LIST_UNPACK).
ShadowRanger
18

Pełny obraz tego, co się dzieje, w oparciu o inne odpowiedzi i komentarze (zwłaszcza odpowiedź ShadowRanger , która wyjaśnia również, dlaczego tak się dzieje).

Demontaż programów, które BUILD_LIST_UNPACKsą używane:

>>> import dis
>>> dis.dis('[*a]')
  1           0 LOAD_NAME                0 (a)
              2 BUILD_LIST_UNPACK        1
              4 RETURN_VALUE

Który jest obsługiwany wceval.c , która buduje pustą listę i rozciąga go (z a):

        case TARGET(BUILD_LIST_UNPACK): {
            ...
            PyObject *sum = PyList_New(0);
              ...
                none_val = _PyList_Extend((PyListObject *)sum, PEEK(i));

_PyList_Extend wykorzystuje list_extend :

_PyList_Extend(PyListObject *self, PyObject *iterable)
{
    return list_extend(self, iterable);
}

Który wywołuje list_resizez sumą rozmiarów :

list_extend(PyListObject *self, PyObject *iterable)
    ...
        n = PySequence_Fast_GET_SIZE(iterable);
        ...
        m = Py_SIZE(self);
        ...
        if (list_resize(self, m + n) < 0) {

I to ogólnie rzecz biorąc, co następuje:

list_resize(PyListObject *self, Py_ssize_t newsize)
{
  ...
    new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);

Sprawdźmy to. Oblicz oczekiwaną liczbę miejsc za pomocą powyższej formuły i oblicz oczekiwany rozmiar bajtu, mnożąc go przez 8 (ponieważ używam tutaj 64-bitowego Pythona) i dodając rozmiar bajtu pustej listy (tj. Stały narzut obiektu listy) :

from sys import getsizeof
for n in range(13):
    a = [None] * n
    expected_spots = n + (n >> 3) + (3 if n < 9 else 6)
    expected_bytesize = getsizeof([]) + expected_spots * 8
    real_bytesize = getsizeof([*a])
    print(n,
          expected_bytesize,
          real_bytesize,
          real_bytesize == expected_bytesize)

Wynik:

0 80 56 False
1 88 88 True
2 96 96 True
3 104 104 True
4 112 112 True
5 120 120 True
6 128 128 True
7 136 136 True
8 152 152 True
9 184 184 True
10 192 192 True
11 200 200 True
12 208 208 True

Dopasowuje oprócz tych n = 0, które list_extendfaktycznie są skrótami , więc tak naprawdę to też pasuje:

        if (n == 0) {
            ...
            Py_RETURN_NONE;
        }
        ...
        if (list_resize(self, m + n) < 0) {
Stefan Pochmann
źródło
8

Będą to szczegóły implementacji interpretera CPython, więc mogą nie być spójne dla innych tłumaczy.

To powiedziawszy, możesz zobaczyć, gdzie list(a)przychodzi zrozumienie i zachowania:

https://github.com/python/cpython/blob/master/Objects/listobject.c#L36

Specjalnie do zrozumienia:

 * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
...

new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);

Tuż pod tymi liniami jest to, list_preallocate_exactktóre jest używane podczas połączenia list(a).

Niespokojny
źródło
1
[*a]nie dodaje pojedynczych elementów pojedynczo. Posiada własny dedykowany kod bajtowy, który wykonuje wstawianie zbiorcze za pośrednictwem extend.
ShadowRanger
Gotcha - Chyba nie kopałem wystarczająco daleko. Usunięto sekcję[*a]
Randy