¿Puede ser inmutable ser un cerdo de la memoria?

Question

Digamos que tenemos una clase de memoria intensiva como Image, con métodos encadenables como Resize() y ConvertTo().

Si esta clase es inmutable, ¿no requerirá una gran cantidad de memoria cuando empiece a hacer cosas como i.Resize(500, 800).Rotate(90).ConvertTo(Gif), en comparación con una variable que se modifica a sí misma? ¿Cómo manejar una situación como esta en un lenguaje funcional?

Answer 1

Si esta clase es inmutable, ¿no requerirá una gran cantidad de memoria?

Normalmente sus requisitos de memoria para ese único objeto podría duplicarse, ya que podría tener un "viejo ejemplar" y una "nueva copia" en vivo a la vez. De modo que puede ver este fenómeno, durante la vigencia del programa, como teniendo un objeto grande más asignado que el que podría tener en un programa imperativo típico. (Los objetos que no están siendo "trabajados" simplemente se sientan allí, con los mismos requisitos de memoria que en cualquier otro idioma.)

¿Cómo manejar una situación como esta en un lenguaje funcional?

No hace absolutamente nada. O más exactamente, asignar nuevos objetos con buena salud. Si está utilizando una implementación diseñada para programación funcional, el asignador y el recolector de basura casi seguramente están sintonizados para altas tasas de asignación, y todo estará bien. Si tiene la mala suerte de intentar ejecutar un código funcional en la JVM, bueno, el rendimiento no será tan bueno como con una implementación personalizada, pero para la mayoría de los programas seguirá estando bien.

---

¿Puede dar más detalles?

Sure. Voy a tomar un ejemplo excepcionalmente simple: una imagen en escala de grises 1000x1000 con 8 bits por píxel, girada 180 grados. Esto es lo que sabemos:

• Para representar la imagen en la memoria se requiere 1MB.

• Si la imagen es mutable, es posible girar 180 grados haciendo una actualización en su lugar. La cantidad de espacio temporal necesario es suficiente para contener un píxel. Escribe un bucle doble anidada que asciende a

  for (i in columns) do 
      for (j in first half of rows) do { 
      pixel temp := a[i, j]; 
      a[i, j] := a[width-i, height-j]; 
      a[width-i, height-j] := tmp 
      } 
  

• Si la imagen es inmutable , se requiere para crear una imagen nueva entera, y temporalmente usted tiene que quedarse con la imagen antigua. El código es algo como esto:

  new_a = Image.tabulate (width, height) (\ x y -> a[width-x, height-y]) 
  

  La función tabulate asigna toda una matriz 2D, inmutable e inicializa su contenido. Durante esta operación, la imagen anterior es temporalmente ocupando la memoria. Pero cuando se completa tabulate, ya no se debe usar la imagen anterior a, y su memoria ahora está libre (es decir, elegible para reciclaje por el recolector de basura). La cantidad de espacio temporal requerido, entonces, es suficiente para contener una imagen.

• Mientras se realiza la rotación, no es necesario tener copias de objetos de otras clases; el espacio temporal es necesario solo para la imagen girada.

N.B. Para otras operaciones, como el cambio de escala o la rotación de una imagen (no cuadrada) 90 grados, es muy probable que incluso cuando las imágenes sean mutables, se necesite una copia temporal de toda la imagen, porque las dimensiones cambian. Por otro lado, las transformaciones del espacio de color y otros cálculos que se realizan píxel por píxel se pueden realizar mediante la mutación con un espacio temporal muy pequeño.

Answer 2

Sí. La inmutabilidad es un componente del intercambio eterno entre el espacio y el tiempo en la informática: sacrificas memoria a cambio de la mayor velocidad de procesamiento que obtienes en el paralelismo mediante bloqueos anteriores y otras medidas de control de acceso simultáneas.

Los lenguajes funcionales normalmente manejan operaciones de esta naturaleza dividiéndolas en granos muy finos. Su clase de imagen en realidad no contiene los bits de datos lógicos de la imagen; más bien, utiliza punteros o referencias a segmentos de datos inmutables mucho más pequeños que contienen los datos de imagen. Cuando se deben realizar operaciones en los datos de imagen, los segmentos más pequeños se clonan y mutan, y se devuelve una nueva copia de la imagen con referencias actualizadas, la mayoría de las cuales apuntan a datos que no se han copiado o modificado y se han mantenido intactos. .

Esta es una razón por la cual el diseño funcional requiere un proceso de pensamiento fundamental diferente del diseño imperativo. No solo los algoritmos se presentan de forma muy diferente, sino que las estructuras y el almacenamiento de datos también se deben diseñar de forma diferente para tener en cuenta la sobrecarga de memoria de la copia.

Answer 3

Sí, una de las desventajas del uso de objetos inmutables es que tienden a acaparar la memoria. Una cosa que me viene a la mente es algo similar a la evaluación perezosa, que es cuando se solicita una nueva copia y cuando el usuario realiza algunos cambios y luego inicializa la nueva copia del objeto.

Answer 4

En algunos casos, la inmutabilidad obliga a clonar el objeto y necesita asignar más memoria. No es necesario ocupar la memoria, porque las copias más antiguas se pueden descartar. Por ejemplo, el recolector de basura de CLR trata bastante bien esta situación, por lo que esto no es (por lo general) un gran problema.

Sin embargo, encadenar operaciones no significa en realidad clonar el objeto. Este es ciertamente el caso de las listas funcionales. Cuando los usa de la manera típica, solo necesita asignar una celda de memoria para un solo elemento (al agregar elementos al principio de la lista).

Su ejemplo con procesamiento de imágenes también se puede implementar de una manera más eficiente. Usaré la sintaxis de C# para mantener el código fácil de entender sin conocer ningún FP (pero se vería mejor en un lenguaje funcional habitual). En lugar de clonar realmente la imagen, podría simplemente almacenar las operaciones que desea hacer con la imagen. Por ejemplo algo como esto:

class Image { 
    Bitmap source; 
    FileFormat format; 
    float newWidth, newHeight; 
    float rotation; 

    // Public constructor to load the image from a file 
    public Image(string sourceFile) { 
    this.source = Bitmap.FromFile(sourceFile); 
    this.newWidth = this.source.Width; 
    this.newHeight = this.source.Height; 
    } 

    // Private constructor used by the 'cloning' methods 
    private Image(Bitmap s, float w, float h, float r, FileFormat fmt) { 
    source = s; newWidth = w; newHeight = h; 
    rotation = r; format = fmt; 
    } 

    // Methods that can be used for creating modified clones of 
    // the 'Image' value using method chaining - these methods only 
    // store operations that we need to do later 
    public Image Rotate(float r) { 
    return new Image(source, newWidth, newHeight, rotation + r, format); 
    } 
    public Image Resize(float w, float h) { 
    return new Image(source, w, h, rotation, format); 
    } 
    public Image ConvertTo(FileFormat fmt) { 
    return new Image(source, newWidth, newHeight, rotation, fmt); 
    } 

    public void SaveFile(string f) { 
    // process all the operations here and save the image 
    } 
} 

La clase no crea realmente un clon de todo el mapa de bits cada vez que se invoca un método. Solo realiza un seguimiento de lo que se debe hacer más tarde, cuando finalmente intentarás guardar la imagen.En el siguiente ejemplo, el Bitmap subyacente se crearía una sola vez:

var i = new Image("file.jpg"); 
i.Resize(500, 800).Rotate(90).ConvertTo(Gif).SaveFile("fileNew.gif"); 

En resumen, el código es el que está clonando el objeto y en realidad se está creando una nueva copia de la clase cada vez que Image llamar a alguna operación. Sin embargo, eso no significa que la operación sea costosa en cuanto a la memoria: puede ocultarse en la biblioteca funcional, que puede implementarse de muchas maneras (pero preservar aún la importante transparencia referencial ).

Answer 5

Depende del tipo de estructuras de datos utilizadas, su aplicación en un programa determinado. En general, la inmutabilidad no tiene que ser demasiado costosa en la memoria.

Puede haberse dado cuenta de que las estructuras de datos persistentes utilizadas en los programas funcionales tienden a evitar las matrices. Esto se debe a que las estructuras de datos persistentes suelen reutilizar la mayoría de sus componentes cuando se "modifican". (En realidad no se modifican, por supuesto. Se devuelve una nueva estructura de datos, pero la anterior es la misma que antes). See this picture para tener una idea de cómo puede funcionar el uso compartido de la estructura. En general, las estructuras de árbol se ven favorecidas, porque se puede crear un nuevo árbol inmutable a partir de un árbol inmutable antiguo, solo reescribiendo la ruta desde la raíz hasta el nodo en cuestión. Todo lo demás puede reutilizarse, haciendo que el proceso sea eficiente tanto en tiempo como en memoria.

En cuanto a su ejemplo, hay varias formas de resolver el problema, además de copiar una matriz masiva completa. (Eso en realidad sería terriblemente ineficiente.) Mi solución preferida sería usar un árbol de fragmentos de matriz para representar la imagen, lo que permite una copia relativamente escasa de las actualizaciones. Tenga en cuenta una ventaja adicional: podemos a un costo relativamente bajo almacenar múltiples versiones de nuestros datos.

No me refiero a argumentar que la inmutabilidad es siempre y en todas partes la respuesta: la verdad y la rectitud de la programación funcional deben moderarse con pragmatismo, después de todo.

Answer 6

respuesta corta, tangencial: en lenguaje FP estoy familiarizado con (scala, erlang, clojure, F #), y para las estructuras de datos habituales: matrices, listas, vectores, tuplas, necesita comprender copias superficiales/profundas y cómo se implementó:

por ej.

Scala, clone() vs. objeto constructor de copia

Does Scala AnyRef.clone perform a shallow or deep copy?

Erlang: el paso de mensajes de datos en una estructura superficial copiado puede estallar un proceso:

http://groups.google.com/group/erlang-programming/msg/bb39d1a147f72800