python - Tamaño de la lista en la memoria

python-3.x

Question

Acabo de experimentar con el tamaño de las estructuras de datos de Python en la memoria. Escribí el siguiente fragmento:

import sys
lst1=[]
lst1.append(1)
lst2=[1]
print(sys.getsizeof(lst1), sys.getsizeof(lst2))

Probé el código en las siguientes configuraciones:

• Windows 7 de 64 bits, Python3.1: la salida es: 52 40 por lo que lst1 tiene 52 bytes y lst2 tiene 40 bytes.
• Ubuntu 11.4 32 bits con Python3.2: la salida es 48 32
• Ubuntu 11.4 32bit Python2.7: 48 36

¿Alguien puede explicarme por qué los dos tamaños difieren aunque ambos son listas que contienen un 1?

En la documentación de python para la función getsizeof encontré lo siguiente: ...adds an additional garbage collector overhead if the object is managed by the garbage collector. ¿Podría ser este el caso en mi pequeño ejemplo?

Answer 1

Aquí hay una demostración rápida del patrón de crecimiento de la lista. Cambiar el tercer argumento en el rango () cambiará el resultado para que no se parezca a los comentarios en listobject.c, pero el resultado al agregar simplemente un elemento parece ser perfectamente exacto.

allocated = 0
for newsize in range(0,100,1):
if (allocated < newsize):
new_allocated = (newsize >> 3) + (3 if newsize < 9 else 6)
allocated = newsize + new_allocated;
print newsize, allocated

Answer 2

Aquí hay una sesión interactiva más completa que me ayudará a explicar qué está sucediendo (Python 2.6 en Windows XP de 32 bits, pero realmente no importa):

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

Tenga en cuenta que la lista vacía es un poco más pequeña que la que tiene [1] . Sin embargo, cuando se agrega un elemento, crece mucho más.

La razón para esto es los detalles de implementación en Objects/listobject.c , en el origen de CPython.

Lista vacía

Cuando se crea una lista vacía [] , no se asigna espacio para los elementos; esto se puede ver en PyList_New . 36 bytes es la cantidad de espacio requerido para la estructura de datos de la lista en una máquina de 32 bits.

Lista con un elemento

Cuando se crea una lista con un solo elemento [1] , el espacio para un elemento se asigna además de la memoria requerida por la propia estructura de datos de la lista. De nuevo, esto se puede encontrar en PyList_New . Dado el size como argumento, calcula:

nbytes = size * sizeof(PyObject *);

Y luego tiene:

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;

Entonces vemos que con size = 1 , se asigna espacio para un puntero. 4 bytes (en mi caja de 32 bits).

Anexando a una lista vacía

Cuando llamas a append en una lista vacía, esto es lo que sucede:

• PyList_Append llamadas app1
• app1 pregunta por el tamaño de la lista (y obtiene 0 como respuesta)
• app1 luego llama a list_resize con size+1 (1 en nuestro caso)
• list_resize tiene una estrategia de asignación interesante, resumida en este comentario desde su fuente.

Aquí está:

/* 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;
}

Hagamos algo de matemática

Veamos cómo se alcanzan los números que cité en la sesión al comienzo de mi artículo.

Entonces, 36 bytes es el tamaño requerido por la estructura de datos de la lista en 32 bits. Con un solo elemento, el espacio se asigna para un puntero, por lo que son 4 bytes adicionales, un total de 40 bytes. OK hasta ahora.

Cuando se llama a app1 en una lista vacía, llama a list_resize con size=1 . De acuerdo con el algoritmo de list_resize de list_resize , el siguiente tamaño más grande disponible después de 1 es 4, por lo que se asignarán 4 punteros. 4 * 4 = 16 bytes, y 36 + 16 = 52.

De hecho, todo tiene sentido :-)

Answer 3

lo siento, el comentario anterior fue un poco brusco.

lo que sucede es que estás viendo cómo se asignan las listas (y creo que tal vez solo querías ver qué tan grandes eran, en ese caso, usa sys.getsizeof() )

cuando algo se agrega a una lista, una de dos cosas puede suceder:

1. el artículo adicional cabe en el espacio libre

2. Se necesita espacio adicional, por lo que se crea una nueva lista, se copian los contenidos y se agrega algo adicional.

ya que (2) es costoso (copiar cosas, incluso punteros, lleva tiempo proporcional a la cantidad de cosas que se copiarán, por lo que crece a medida que las listas aumentan) queremos hacerlo con poca frecuencia. entonces, en lugar de solo agregar un poco más de espacio, agregamos un trozo entero. generalmente, el tamaño de la cantidad añadida es similar a lo que ya está en uso: de ese modo, las matemáticas resuelven que el costo promedio de asignar memoria, distribuido en muchos usos, es solo proporcional al tamaño de la lista.

entonces, lo que estás viendo está relacionado con este comportamiento. no conozco los detalles exactos, pero no me sorprendería si [] o [1] (o ambos) son casos especiales, donde solo se asigna suficiente memoria (para ahorrar memoria en estos casos comunes), y luego se agrega hace el "agarrar un nuevo pedazo" descrito anteriormente que agrega más.

pero no sé los detalles exactos, así es como funcionan las matrices dinámicas en general. la implementación exacta de las listas en python estará finamente ajustada para que sea óptima para los programas típicos de python. así que todo lo que realmente estoy diciendo es que no se puede confiar en el tamaño de una lista para decirle exactamente cuánto contiene: puede contener espacio extra y la cantidad de espacio libre adicional es difícil de juzgar o predecir.

Una alternativa clara a esto es hacer listas como pares (value, pointer) , donde cada puntero apunta a la siguiente tupla. de esta forma puede hacer crecer las listas de forma incremental, aunque la memoria total utilizada es mayor. esa es una lista vinculada (lo que Python usa es más parecido a un vector o una matriz dinámica).

[actualización] vea la excelente respuesta de Eli. él / ella explica que ambos [] y [1] se asignan exactamente, pero que agregar a [] asigna un pedazo adicional. el comentario en el código es lo que estoy diciendo arriba (esto se llama "sobreasignación" y el monto es proporcional a lo que tenemos para que el costo promedio ("amortizado") sea proporcional al tamaño).