Rozmiar listy w pamięci

[24]} oto pełniejsza interaktywna sesja, która pomoże mi wyjaśnić, co się dzieje (Python 2.6 na Windows XP 32-bit, ale to naprawdę nie ma znaczenia): {]}

>>> import sys
>>> sys.getsizeof([])
36
>>> sys.getsizeof([1])
40
>>> lst = []
>>> lst.append(1)
>>> sys.getsizeof(lst)
52
>>> 

Zauważ, że pusta lista jest nieco mniejsza niż ta z [1]. Gdy element jest dołączany, jednak rośnie znacznie większy.

Pusta lista

Po utworzeniu pustej listy [] nie ma miejsca na elementy są przydzielane - widać to w PyList_New. 36 bajtów to ilość miejsca wymaganego dla samej struktury danych listy na maszynie 32-bitowej.

Lista z jednym elementem

Podczas tworzenia listy z pojedynczym elementem [1], miejsce na jeden element jest przydzielane oprócz pamięci wymaganej przez samą strukturę danych listy. Ponownie można to znaleźć w PyList_New. Biorąc pod uwagę size jako argument, oblicza:

nbytes = size * sizeof(PyObject *);

A następnie ma:

if (size <= 0)
    op->ob_item = NULL;
else {
    op->ob_item = (PyObject **) PyMem_MALLOC(nbytes);
    if (op->ob_item == NULL) {
        Py_DECREF(op);
        return PyErr_NoMemory();
    }
    memset(op->ob_item, 0, nbytes);
}
Py_SIZE(op) = size;
op->allocated = size;

Widzimy więc, że za pomocą size = 1 przydzielane jest miejsce na jeden wskaźnik. 4 bajty (na moim 32-bitowym pudełku).

Dodawanie do pustej listy

Podczas wywoływania append na pustej liście, oto co się dzieje:

• PyList_Append rozmowy app1
• W tym celu należy skontaktować się z Działem obsługi klienta.]}
• app1 następnie wywołuje list_resize z size+1 (1 w naszym przypadku)
• list_resize ma ciekawą strategię alokacji, podsumowaną w tym komentarzu ze źródła.

Here it jest:

/* This over-allocates proportional to the list size, making room
* for additional growth.  The over-allocation is mild, but is
* enough to give linear-time amortized behavior over a long
* sequence of appends() in the presence of a poorly-performing
* system realloc().
* The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
*/
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

/* check for integer overflow */
if (new_allocated > PY_SIZE_MAX - newsize) {
    PyErr_NoMemory();
    return -1;
} else {
    new_allocated += newsize;
}

Let ' s do some math

Zobaczmy, jak liczby, które cytowałem w sesji na początku mojego artykułu, są osiągane.

Tak więc 36 bajtów jest wielkością wymaganą przez samą strukturę danych listy na 32-bitach. W przypadku pojedynczego elementu miejsce jest przydzielane na jeden wskaźnik, czyli 4 dodatkowe bajty - łącznie 40 bajtów. Jak na razie ok.

Gdy app1 jest wywołana na pustej liście, wywołuje list_resize z size=1. Zgodnie z algorytmem over-allocation list_resize, następny największy dostępny rozmiar po 1 to 4, więc miejsce na 4 wskaźniki zostanie przydzielone. 4 * 4 = 16 bajtów, a 36 + 16 = 52.

Rzeczywiście, wszystko ma sens: -)