python - punteros - ¿Por qué las tuplas ocupan menos espacio en la memoria que las listas?

punteros python

Question

Una tuple ocupa menos espacio de memoria en Python:

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

mientras que la list s ocupa más espacio en la memoria:

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

¿Qué sucede internamente en la administración de memoria de Python?

Answer 1

El tamaño de la tupla tiene el prefijo, lo que significa que en la inicialización de la tupla el intérprete asigna suficiente espacio para los datos contenidos, y ese es el final de la misma, dado que es inmutable (no se puede modificar), mientras que una lista es un objeto mutable, lo que implica dinámica asignación de memoria, por lo que para evitar asignar espacio cada vez que agrega o modifica la lista (asigna suficiente espacio para contener los datos modificados y los copia), asigna espacio adicional para futuras adiciones, modificaciones, ... eso es más o menos lo resume.

Answer 2

La respuesta de MSeifert lo cubre ampliamente; para simplificarlo, puede pensar en:

tuple es inmutable. Una vez que se establece, no puede cambiarlo. Entonces, sabe de antemano cuánta memoria necesita asignar para ese objeto.

list es mutable. Puede agregar o quitar elementos a él o desde él. Tiene que saber el tamaño de la misma (por implicación interna). Se redimensiona según sea necesario.

No hay comidas gratis , estas capacidades tienen un costo. De ahí la sobrecarga en memoria para las listas.

Answer 3

Profundizaré en la base de código de CPython para que podamos ver cómo se calculan realmente los tamaños. En su ejemplo específico , no se han realizado sobreasignaciones, por lo que no mencionaré eso .

Voy a usar valores de 64 bits aquí, como tú.

El tamaño de la list s se calcula a partir de la siguiente función, 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);
}

Aquí Py_TYPE(self) es una macro que toma el ob_type de self (devuelve PyList_Type ) mientras que _PyObject_SIZE es otra macro que toma tp_basicsize de ese tipo. tp_basicsize se calcula como sizeof(PyListObject) donde PyListObject es la estructura de la instancia.

La estructura PyListObject tiene tres campos:

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

estos tienen comentarios (que recorté) que explican lo que son, siga el enlace de arriba para leerlos. PyObject_VAR_HEAD expande en tres campos de 8 bytes ( ob_refcount , ob_type y ob_size ) por lo que una contribución de 24 bytes.

Entonces por ahora res es:

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

o:

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

Si la instancia de la lista tiene elementos asignados. La segunda parte calcula su contribución. self->allocated , como su nombre lo indica, contiene el número de elementos asignados.

Sin ningún elemento, se calcula que el tamaño de las listas es:

>>> [].__sizeof__()
40

es decir, el tamaño de la estructura de la instancia.

tuple objetos tuple no definen una función tuple_sizeof . En cambio, usan object_sizeof para calcular su tamaño:

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);
}

Esto, como para la list s, toma tp_basicsize y, si el objeto tiene un tp_itemsize distinto de cero (lo que significa que tiene instancias de longitud variable), multiplica el número de elementos en la tupla (que se obtiene a través de Py_SIZE ) con tp_itemsize .

tp_basicsize nuevamente usa sizeof(PyTupleObject) donde la estructura PyTupleObject contiene :

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

Entonces, sin ningún elemento (es decir, Py_SIZE devuelve 0 ) el tamaño de las tuplas vacías es igual al tamaño de sizeof(PyTupleObject) :

>>> ().__sizeof__()
24

eh? Bueno, aquí hay una rareza para la que no he encontrado una explicación, el tp_basicsize de tuple s se calcula de la siguiente manera:

sizeof(PyTupleObject) - sizeof(PyObject *)

por qué se eliminan 8 bytes adicionales de tp_basicsize es algo que no he podido descubrir. (Ver el comentario de MSeifert para una posible explicación)

Pero, esta es básicamente la diferencia en su ejemplo específico . list también guardan una serie de elementos asignados que ayudan a determinar cuándo volver a asignar demasiado.

Ahora, cuando se agregan elementos adicionales, las listas realmente realizan esta sobreasignación para lograr los anexos O (1). Esto da como resultado tamaños más grandes, ya que MSeifert cubre muy bien en su respuesta.

Answer 4

Supongo que está utilizando CPython y con 64 bits (obtuve los mismos resultados en mi CPython 2.7 de 64 bits). Podría haber diferencias en otras implementaciones de Python o si tiene un Python de 32 bits.

Independientemente de la implementación, las list son de tamaño variable, mientras que las tuple son de tamaño fijo.

Para que las tuple puedan almacenar los elementos directamente dentro de la estructura, las listas necesitan una capa de indirección (almacena un puntero a los elementos). Esta capa de indirección es un puntero, en sistemas de 64 bits que es de 64 bits, por lo tanto, 8 bytes.

Pero hay otra cosa que hacen las list : se asignan en exceso. De list.append contrario, list.append sería una operación O(n) siempre , para amortizar O(1) (¡mucho más rápido!) Se sobreasigna. Pero ahora tiene que hacer un seguimiento del tamaño asignado y el tamaño llenado (las tuple solo necesitan almacenar un tamaño, porque el tamaño asignado y el llenado siempre son idénticos). Eso significa que cada lista tiene que almacenar otro "tamaño" que en sistemas de 64 bits es un entero de 64 bits, nuevamente 8 bytes.

Entonces las list necesitan al menos 16 bytes más de memoria que las tuple . ¿Por qué dije "al menos"? Debido a la sobreasignación. La sobreasignación significa que asigna más espacio del necesario. Sin embargo, la cantidad de sobreasignación depende de "cómo" crea la lista y el historial de anexos / eliminaciones:

>>> 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

Imágenes

Decidí crear algunas imágenes para acompañar la explicación anterior. Quizás estos son útiles

Así es como se almacena (esquemáticamente) en la memoria en su ejemplo. Destaqué las diferencias con los ciclos rojos (manos libres):

En realidad, eso es solo una aproximación porque los objetos int también son objetos Python y CPython incluso reutiliza enteros pequeños, por lo que una representación probablemente más precisa (aunque no tan legible) de los objetos en la memoria sería:

Enlaces útiles:

• estructura de tuple en el repositorio de CPython para Python 2.7
• estructura de la list en el repositorio de CPython para Python 2.7
• int struct en el repositorio de CPython para Python 2.7

Tenga en cuenta que __sizeof__ realmente no devuelve el tamaño "correcto"! Solo devuelve el tamaño de los valores almacenados. Sin embargo, cuando usa sys.getsizeof el resultado es diferente:

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

Hay 24 bytes "extra". Estos son reales , esa es la sobrecarga del recolector de basura que no se tiene en cuenta en el método __sizeof__ . Esto se debe a que generalmente no se supone que use métodos mágicos directamente; use las funciones que saben cómo manejarlos, en este caso: sys.getsizeof (que en realidad agrega la sobrecarga de GC al valor devuelto por __sizeof__ ).