Serialización de memoria de Python

Question

Me preguntaba si alguien podría saber la respuesta a lo siguiente.

Estoy usando Python para construir un árbol de sufijos basado en caracteres. Hay más de 11 millones de nodos en el árbol que se ajustan a aproximadamente 3 GB de memoria. Esto se redujo desde 7 GB mediante el método de clase ranura en lugar del método Dict.

Cuando serializo el árbol (usando el protocolo más alto) el archivo resultante es más de cien veces más pequeño.

Cuando vuelvo a cargar el archivo encurtido, vuelve a consumir 3 GB de memoria. ¿De dónde viene esta sobrecarga adicional, es algo relacionado con el manejo por parte de Pythons de las referencias de memoria a instancias de clase?

actualización

Gracias larsmans y Gurgeh para sus muy útiles explicaciones y consejos. Estoy usando el árbol como parte de una interfaz de recuperación de información sobre un corpus de textos.

Originalmente almacené los niños (máximo de 30) como una matriz Numpy, luego probé la versión de hardware (ctypes.py_object*30), la matriz de Python (ArrayType), así como el diccionario y los tipos de conjunto.

Las listas parecían funcionar mejor (usando guppy para perfilar la memoria, y __slots__['variable',...]), pero todavía estoy tratando de aplastarlo un poco más si puedo. El único problema que tuve con las matrices es tener que especificar su tamaño por adelantado, lo que causa un poco de redundancia en términos de nodos con un solo hijo, y tengo bastantes de ellos. ;-)

Después de que se construye el árbol, intento convertirlo en un árbol probabilístico con un segundo pase, pero puedo hacerlo cuando se construye el árbol. Como el tiempo de construcción no es demasiado importante en mi caso, el array.array() suena como algo que sería útil probar, gracias por la sugerencia, realmente apreciada.

Te voy a decir cómo va.

Answer 1

Si intenta conservar en vinagre una lista vacía, se obtiene:

>>> s = StringIO() 
>>> pickle.dump([], s) 
>>> s.getvalue() 
'(l.' 

y de manera similar '(d.' para un vacío dict. Eso es tres bytes. El in-memory representation of a list, sin embargo, contiene

• un contador de referencia
• un identificador de tipo, a su vez contiene un puntero al nombre del tipo y la información de la contabilidad para la asignación de memoria
• un puntero a un vector de punteros a elementos reales
• y aún más información de contabilidad.

En mi máquina, que tiene punteros de 64 bits, el objeto de lista cabecera sizeof un pitón es de 40 bytes, por lo que es un orden de magnitud. Supongo que un dict vacío tendrá un tamaño similar.

Entonces, tanto list y dict utiliza una estrategia de sobreasignación para obtener amortized O(1) performance por sus principales operaciones, malloc supone cargas, hay alineación, miembro de atributos que puede o no puede ni siquiera ser consciente de y varios otros factores que se obtiene la segunda orden de magnitud.

Resumiendo: salmuera es un buen algoritmo de compresión de objetos de Python :)

Answer 2

¿Usted construye su árbol una vez y luego lo utiliza sin modificar aún más? En ese caso, es posible que desee considerar el uso de estructuras separadas para la construcción dinámica y el uso estático.

Los dictados y los objetos son muy buenos para la modificación dinámica, pero no son muy eficientes en el uso del espacio en un escenario de solo lectura. No sé exactamente para qué está usando el árbol de sufijos, pero podría dejar que cada nodo se representara mediante una 2-tupla de un array.array ordenado ('c') y una tupla igualmente larga de subnodos (una tupla en su lugar de un vector para evitar la sobreasignación). Atraviesa el árbol utilizando el módulo bisect para buscar en la matriz. El índice de un carácter en la matriz corresponderá a un subnodo en el subnodo-tupla. De esta forma evitas dictados, objetos y vectores.

Puede hacer algo similar durante el proceso de construcción, quizás utilizando un subnodo-vector en lugar de subnodo-tupla. Pero, por supuesto, esto hará que la construcción sea más lenta, ya que la inserción de nuevos nodos en un vector ordenado es O (N).