Tamaño de la lista en memoria

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

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 64bit, 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 32 bits Python2.7: 48 36

¿Puede alguien 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?

Aquí hay una sesión interactiva más completa que me ayudará a explicar lo que está pasando (Python 2.6 en Windows XP de 32 bits, pero en realidad 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 añade un elemento, crece mucho más.

El motivo de esto son los detalles de la implementación en Objects/listobject.c , en la fuente de CPython.

Lista vacía

Cuando se crea una lista vacía [] , no se asigna ningún 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; 

Así que 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

Al llamar append en una lista vacía, esto es lo que sucede:

  • PyList_Append llama a 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 de 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; } 

Vamos a hacer algunas matematicas

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

Por lo tanto, 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 asignación list_resize de list_resize , el siguiente tamaño más grande disponible después de 1 es 4, por lo que se asignará un lugar para 4 punteros. 4 * 4 = 16 bytes, y 36 + 16 = 52.

De hecho, todo tiene sentido 🙂

Lo siento, el comentario anterior fue un poco brusco.

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

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

  1. el artículo extra 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 lo extra.

ya que (2) es caro (copiar cosas, incluso punteros, lleva un tiempo proporcional al número de cosas que se copiarán, por lo que crece a medida que las listas se vuelven grandes) queremos hacerlo con poca frecuencia. así que en lugar de simplemente agregar un poco más de espacio, agregamos una porción completa. por lo general, el tamaño de la cantidad agregada es similar a lo que ya está en uso; de esa manera, las matemáticas calculan que el costo promedio de asignar memoria, distribuido en muchos usos, solo es proporcional al tamaño de la lista.

así que 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 “agarre un nuevo trozo” descrito anteriormente que agrega más.

pero no conozco los detalles exactos; así es como funcionan en general los arreglos dynamics. la implementación exacta de las listas en python se ajustará con precisión para que sea óptima para los progtwigs típicos de python. Así que todo lo que realmente digo es que no puede confiar en el tamaño de una lista para decirle exactamente cuánto contiene, ya que puede contener espacio adicional, y la cantidad de espacio libre adicional es difícil de juzgar o predecir.

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

[actualización] ver excelente respuesta de Eli. Él / ella explica que tanto [] como [1] están asignados exactamente, pero que al agregarse a [] asigna una porción adicional. el comentario en el código es lo que estoy diciendo más arriba (esto se denomina “sobre asignación” y la cantidad es proporcional a lo que tenemos para que el costo promedio (“amortizado”) sea proporcional al tamaño).

Aquí hay una demostración rápida del patrón de crecimiento de la lista. Cambiar el tercer argumento en el rango () cambiará la salida para que no se vea como los comentarios en listobject.c, pero el resultado cuando simplemente se agrega 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