Dlaczego krotki zajmują mniej miejsca w pamięci niż listy?

A tuplezajmuje mniej miejsca w pamięci w Pythonie:

>>> a = (1,2,3)
>>> a.__sizeof__()
48

podczas gdy lists zajmuje więcej miejsca w pamięci:

>>> b = [1,2,3]
>>> b.__sizeof__()
64

Co dzieje się wewnętrznie w zarządzaniu pamięcią w Pythonie?

Zakładam, że używasz CPython i 64-bitowego (mam takie same wyniki na moim CPythonie 2.7 64-bitowym). Mogą występować różnice w innych implementacjach języka Python lub jeśli masz 32-bitowy język Python.

Niezależnie od implementacji, lists mają zmienną wielkość, a tuples mają stałą wielkość.

Więc tuples może przechowywać elementy bezpośrednio w strukturze, z drugiej strony listy wymagają warstwy pośredniej (przechowuje wskaźnik do elementów). Ta warstwa pośrednia jest wskaźnikiem, w systemach 64-bitowych jest 64-bitowa, a więc 8-bajtowa.

Ale jest jeszcze jedna rzecz, którą listrobią: nadmiernie przydzielają. W przeciwnym razie list.appendbyłaby to O(n)operacja zawsze - aby ją zamortyzować O(1)(znacznie szybciej !!!), nadmiernie alokuje. Ale teraz musi śledzić przydzielony rozmiar i wypełniony rozmiar ( tuplewystarczy przechowywać jeden rozmiar, ponieważ przydzielony i wypełniony rozmiar są zawsze identyczne). Oznacza to, że każda lista musi przechowywać inny „rozmiar”, który w systemach 64-bitowych jest 64-bitową liczbą całkowitą, ponownie 8 bajtów.

Więc lists potrzebują co najmniej 16 bajtów więcej pamięci niż tuples. Dlaczego powiedziałem „przynajmniej”? Z powodu nadmiernej alokacji. Nadmierna alokacja oznacza, że ​​przydziela więcej miejsca niż potrzeba. Jednak wielkość nadmiernej alokacji zależy od tego, „jak” utworzysz listę i historię dodawania / usuwania:

>>> l = [1,2,3]
>>> l.__sizeof__()
64
>>> l.append(4)  # triggers re-allocation (with over-allocation), because the original list is full
>>> l.__sizeof__()
96

>>> l = []
>>> l.__sizeof__()
40
>>> l.append(1)  # re-allocation with over-allocation
>>> l.__sizeof__()
72
>>> l.append(2)  # no re-alloc
>>> l.append(3)  # no re-alloc
>>> l.__sizeof__()
72
>>> l.append(4)  # still has room, so no over-allocation needed (yet)
>>> l.__sizeof__()
72

Zdjęcia

Postanowiłem stworzyć obrazy towarzyszące powyższemu wyjaśnieniu. Może te są pomocne

Oto jak (schematycznie) jest on przechowywany w pamięci w twoim przykładzie. Podkreśliłem różnice z czerwonymi (z wolnej ręki) cyklami:

W rzeczywistości jest to tylko przybliżenie, ponieważ intobiekty są również obiektami Pythona, a CPython nawet ponownie wykorzystuje małe liczby całkowite, więc prawdopodobnie dokładniejsza reprezentacja (chociaż nie tak czytelna) obiektów w pamięci byłaby:

Przydatne linki:

• tuple struct w repozytorium CPython dla Pythona 2.7
• list struct w repozytorium CPython dla Pythona 2.7
• int struct w repozytorium CPython dla Pythona 2.7

Zwróć uwagę, że __sizeof__tak naprawdę nie zwraca „prawidłowego” rozmiaru! Zwraca tylko rozmiar przechowywanych wartości. Jednak gdy używasz, sys.getsizeofwynik jest inny:

>>> import sys
>>> l = [1,2,3]
>>> t = (1, 2, 3)
>>> sys.getsizeof(l)
88
>>> sys.getsizeof(t)
72

Istnieją 24 „dodatkowe” bajty. Te są prawdziwe , to jest narzut modułu odśmiecania pamięci, który nie jest uwzględniony w __sizeof__metodzie. Dzieje się tak, ponieważ generalnie nie powinieneś używać magicznych metod bezpośrednio - użyj funkcji, które wiedzą, jak sobie z nimi poradzić, w tym przypadku: sys.getsizeof(co faktycznie dodaje narzut GC do wartości zwracanej z __sizeof__).

Zagłębię się w podstawę kodu CPython, aby zobaczyć, jak obliczane są rozmiary. W swoim konkretnym przykładzie , nie nadmierne przydziały zostały wykonane, więc nie będę dotykać na tym .

Użyję tutaj wartości 64-bitowych, tak jak ty.

Rozmiar lists jest obliczany z następującej funkcji list_sizeof:

static PyObject *
list_sizeof(PyListObject *self)
{
    Py_ssize_t res;

    res = _PyObject_SIZE(Py_TYPE(self)) + self->allocated * sizeof(void*);
    return PyInt_FromSsize_t(res);
}

Oto Py_TYPE(self)makro, które przechwytuje ob_typeof self(zwracające PyList_Type), podczas gdy _PyObject_SIZEjest kolejnym makrem, które pobiera tp_basicsizez tego typu. tp_basicsizejest obliczana jako sizeof(PyListObject)gdzie PyListObjectjest strukturą instancji.

PyListObjectStruktura ma trzy pola:

PyObject_VAR_HEAD     # 24 bytes 
PyObject **ob_item;   #  8 bytes
Py_ssize_t allocated; #  8 bytes

te mają komentarze (które przyciąłem) wyjaśniające, czym są, kliknij powyższy link, aby je przeczytać. PyObject_VAR_HEADrozszerza się w trzech dziedzinach bajtowych (8 ob_refcount, ob_typei ob_size) tak 24wkładu bajtów.

Więc na razie resjest:

sizeof(PyListObject) + self->allocated * sizeof(void*)

lub:

40 + self->allocated * sizeof(void*)

Jeśli instancja listy zawiera przydzielone elementy. druga część oblicza ich wkład. self->allocatedjak sama nazwa wskazuje, zawiera liczbę przydzielonych elementów.

Bez żadnych elementów rozmiar list jest obliczany jako:

>>> [].__sizeof__()
40

tj. rozmiar struktury instancji.

tupleobiekty nie definiują tuple_sizeoffunkcji. Zamiast tego używają object_sizeofdo obliczenia swojego rozmiaru:

static PyObject *
object_sizeof(PyObject *self, PyObject *args)
{
    Py_ssize_t res, isize;

    res = 0;
    isize = self->ob_type->tp_itemsize;
    if (isize > 0)
        res = Py_SIZE(self) * isize;
    res += self->ob_type->tp_basicsize;

    return PyInt_FromSsize_t(res);
}

To, podobnie jak w przypadku lists, pobiera tp_basicsizei, jeśli obiekt ma wartość tp_itemsizeróżną od zera (co oznacza, że ​​ma instancje o zmiennej długości), mnoży liczbę elementów w krotce (którą otrzymuje za pośrednictwem Py_SIZE) tp_itemsize.

tp_basicsizeponownie używa, sizeof(PyTupleObject)gdzie PyTupleObjectstruktura zawiera :

PyObject_VAR_HEAD       # 24 bytes 
PyObject *ob_item[1];   # 8  bytes

Więc bez żadnych elementów (czyli Py_SIZEzwraca 0) rozmiar pustych krotek jest równy sizeof(PyTupleObject):

>>> ().__sizeof__()
24

co? Cóż, tutaj jest dziwactwo, dla którego nie znalazłem wyjaśnienia, tp_basicsizez tuples jest obliczane w następujący sposób:

sizeof(PyTupleObject) - sizeof(PyObject *)

dlaczego 8usuwane są dodatkowe bajty, to tp_basicsizejest coś, czego nie byłem w stanie znaleźć. (Zobacz komentarz MSeiferta w celu uzyskania możliwego wyjaśnienia)

Ale to w zasadzie różnica w twoim konkretnym przykładzie . lists również trzymać wokół wielu przydzielonych elementów, co pomaga określić, kiedy ponownie należy nadmiernie alokować.

Teraz, kiedy dodawane są dodatkowe elementy, listy rzeczywiście wykonują tę nadmierną alokację w celu osiągnięcia dołączeń O (1). Skutkuje to większymi rozmiarami, ponieważ MSeifert ładnie pokrywa się w jego odpowiedzi.

Odpowiedź MSeiferta obejmuje to szeroko; aby to uprościć, możesz pomyśleć o:

tuplejest niezmienna. Po ustawieniu nie możesz go zmienić. Dzięki temu wiesz z góry, ile pamięci musisz przydzielić dla tego obiektu.

listjest zmienna. Możesz dodawać lub usuwać elementy do lub z niego. Musi znać jego rozmiar (dla celów wewnętrznych). W razie potrzeby zmienia rozmiar.

Nie ma darmowych posiłków - te możliwości kosztują. Stąd nadmiar pamięci w przypadku list.

Rozmiar krotki jest poprzedzony prefiksem, co oznacza, że ​​podczas inicjalizacji krotki interpreter przydziela wystarczającą ilość miejsca na zawarte dane, i to jest koniec tego, dając je niezmienne (nie można ich modyfikować), podczas gdy lista jest zmiennym obiektem, co oznacza dynamikę alokacja pamięci, aby uniknąć przydzielania miejsca za każdym razem, gdy dodajesz lub modyfikujesz listę (przydziel wystarczającą ilość miejsca na zmienione dane i skopiuj do niej dane), przydziela dodatkowe miejsce na przyszłe dodawanie, modyfikacje, ... to prawie podsumowuje.