Può essere immutabile un maiale memoria?

Question

Diciamo che abbiamo una classe ad alta intensità di memoria come un Image, con metodi concatenabili come Resize() e ConvertTo().

Se questa classe è immutabile, non ci vorrà un'enorme quantità di memoria quando comincio a fare cose come i.Resize(500, 800).Rotate(90).ConvertTo(Gif), rispetto a una mutabile che si modifica? Come gestire una situazione come questa in un linguaggio funzionale?

Answer 1

Se questa classe è immutabile, non ci vorrà un'enorme quantità di memoria?

Tipicamente le vostre esigenze di memoria per questo singolo oggetto potrebbe raddoppiare, perché si potrebbe avere una "vecchia copia" e di una "nuova copia" dal vivo in una sola volta. Quindi è possibile visualizzare questo fenomeno, nel corso della durata del programma, come con un oggetto di dimensioni maggiori assegnato a rispetto a un tipico programma imperativo. (Gli oggetti che non vengono "lavorati" siedono lì, con gli stessi requisiti di memoria di qualsiasi altra lingua.)

Come gestire una situazione come questa in un linguaggio funzionale?

Non fare assolutamente nulla. O più accuratamente, alloca nuovi oggetti in buona salute. Se si utilizza un'implementazione progettata per la programmazione funzionale, l'allocatore e il garbage collector sono quasi certamente ottimizzati per i tassi di allocazione elevati e tutto andrà bene. Se hai la sfortuna di provare a eseguire codice funzionale sulla JVM, beh, le prestazioni non saranno altrettanto buone come con un'implementazione su misura, ma per la maggior parte dei programmi andrà comunque bene.

---

Puoi fornire maggiori dettagli?

Sicuro. Prenderò un esempio eccezionalmente semplice: immagine in scala di grigi 1000x1000 con 8 bit per pixel, ruotata di 180 gradi. Ecco cosa sappiamo:

• Per rappresentare l'immagine in memoria richiede 1 MB.

• Se l'immagine è modificabile, è possibile ruotare di 180 gradi eseguendo un aggiornamento in posizione. La quantità di spazio temporaneo necessaria è sufficiente per contenere un pixel. Si scrive un ciclo doppiamente nidificato che ammonta 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 
      } 
  

• Se l'immagine è immutabili, è richiesto per creare un'intera nuova immagine, temporaneamente si deve appendere sulla vecchia immagine. Il codice è qualcosa di simile:

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

  la funzione tabulate alloca un intero array 2D immutabile, e inizializza il suo contenuto. Durante questa operazione, la vecchia immagine è temporaneamente occupata nella memoria. Ma quando tabulate viene completato, la vecchia immagine a non deve più essere utilizzata e la sua memoria è ora libera (vale a dire, può essere riciclata dal garbage collector). La quantità di spazio temporaneo richiesta, quindi, è sufficiente per contenere un'immagine.

• Mentre la rotazione è in corso, non è necessario disporre di copie di oggetti di altre classi; lo spazio temporaneo è necessario solo per l'immagine da ruotare.

N.B. Per altre operazioni come riscalare o ruotare un'immagine (non quadrata) di 90 gradi, è molto probabile che anche quando le immagini sono mutevoli, sarà necessaria una copia temporanea dell'intera immagine, poiché le dimensioni cambiano. D'altra parte, le trasformazioni dello spazio dei colori e altri calcoli eseguiti pixel per pixel possono essere fatti usando la mutazione con uno spazio temporaneo molto piccolo.

Answer 2

Sì. L'immutabilità è una componente dell'eterno compromesso spazio-tempo nel calcolo: sacrifichi la memoria in cambio della maggiore velocità di elaborazione ottenuta nel parallelismo, escludendo i blocchi e altre misure di controllo dell'accesso simultanee.

I linguaggi funzionali in genere gestiscono operazioni di questo tipo immettendole in grani molto fini. La tua classe Image in realtà non contiene i bit di dati logici dell'immagine; piuttosto, utilizza puntatori o riferimenti a segmenti di dati immutabili molto più piccoli che contengono i dati dell'immagine. Quando è necessario eseguire operazioni sui dati dell'immagine, i segmenti più piccoli vengono clonati e mutati e una nuova copia dell'immagine viene restituita con riferimenti aggiornati, la maggior parte dei quali punta a dati che non sono stati copiati o modificati e sono rimasti intatti .

Questo è uno dei motivi per cui il design funzionale richiede un processo di pensiero fondamentale diverso dal design imperativo. Non solo gli algoritmi sono strutturati in modo molto diverso, ma anche l'archiviazione e le strutture dei dati devono essere strutturate in modo diverso per tenere conto della memoria di sovraccarico della copia.

Answer 3

Sì, uno degli svantaggi dell'utilizzo di oggetti immutabili è che tendono a occupare memoria, Una cosa che mi viene in mente è qualcosa di simile alla valutazione pigra, ovvero quando viene richiesta una nuova copia che fornisce un riferimento e quando l'utente esegue alcune modifiche quindi inizializza la nuova copia dell'oggetto.

Answer 4

In alcuni casi, l'immutabilità ti costringe a clonare l'oggetto e ha bisogno di allocare più memoria. Non è necessario occupare la memoria, perché le copie più vecchie possono essere scartate. Ad esempio, il garbage collector CLR gestisce abbastanza bene questa situazione, quindi non è (di solito) un grosso problema.

Tuttavia, il concatenamento di operazioni non significa in realtà la clonazione dell'oggetto. Questo è certamente il caso per gli elenchi funzionali. Quando li usi nel modo tipico, devi solo allocare una cella di memoria per un singolo elemento (quando aggiungi elementi in cima all'elenco).

L'esempio di elaborazione delle immagini può anche essere implementato in modo più efficiente. Userò la sintassi C# per mantenere il codice di facile comprensione senza conoscere FP (ma apparirebbe migliore in un linguaggio funzionale usuale). Invece di clonare effettivamente l'immagine, puoi semplicemente memorizzare le operazioni che vuoi fare con l'immagine. Per esempio qualcosa di simile:

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 classe non crea un clone di tutta la bitmap ogni volta che si richiama un metodo. Tiene solo traccia di ciò che deve essere fatto dopo, quando finalmente tenterai di salvare l'immagine.Nel seguente esempio, sarebbero creati una sola volta il sottostante Bitmap:

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

In sintesi, il codice sembra che stai clonando l'oggetto e il gioco è in realtà la creazione di una nuova copia della classe Image ogni volta che si chiama qualche operazione Tuttavia, ciò non significa che l'operazione sia costosa in termini di memoria - ciò può essere nascosto nella libreria funzionale, che può essere implementata in tutti i modi (ma conserva l'importante trasparenza referenziale ).

Answer 5

Dipende dal tipo di strutture dati utilizzate, dalla loro applicazione in un dato programma. In generale, l'immutabilità non deve essere eccessivamente costosa in memoria.

Avrete notato che le strutture di dati persistenti utilizzate nei programmi funzionali tendono a evitare gli array. Questo perché le strutture di dati persistenti in genere riutilizzano la maggior parte dei loro componenti quando sono "modificati". (Naturalmente non vengono modificati, viene restituita una nuova struttura dati, ma quella precedente è la stessa) See this picture per avere un'idea di come può funzionare la condivisione della struttura. In generale, le strutture ad albero sono favorite, perché un nuovo albero immutabile può essere creato da un vecchio albero immutabile solo riscrivendo il percorso dalla radice al nodo in questione. Tutto il resto può essere riutilizzato, rendendo il processo efficiente sia nel tempo che nella memoria.

Per quanto riguarda il vostro esempio, ci sono diversi modi per risolvere il problema oltre alla copia di un intero massiccio. (Che in realtà sarebbe orribilmente inefficiente.) La mia soluzione preferita sarebbe quella di utilizzare un albero di blocchi di array per rappresentare l'immagine, consentendo una copia relativamente piccola degli aggiornamenti. Nota un ulteriore vantaggio: possiamo a costi relativamente contenuti memorizzare più versioni dei nostri dati.

Non intendo sostenere che l'immutabilità è sempre e ovunque la risposta - la verità e la rettitudine della programmazione funzionale dovrebbero essere mitigate dal pragmatismo, dopotutto.

Answer 6

Risposta tangenziale breve: nel linguaggio FP ho familiarità con (scala, erlang, clojure, F #) e per le solite strutture dati: matrici, elenchi, vettori, tuple, è necessario comprendere le copie superficiali/profonde e come implementato:

es.

Scala, clone() oggetto vs. costruttore di copia

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

Erlang: message passing una struttura di dati poco profonde copiata può far saltare un processo:

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