Scala:Mutevole vsImmutabile Oggetto Prestazioni OutOfMemoryError

Question

Ho voluto confrontare le caratteristiche e le prestazioni di immutabile.Mappa e mutevole.Mappa in Scala per una simile operazione (vale a dire, la fusione di molte mappe in uno solo.Vedere questa domanda).Io sono quello che sembrano essere simili implementazioni sia mutabili e immutabili mappe (vedi sotto).

Come test, ho generato un Elenco contenente 1.000.000 di un singolo elemento della Mappa[Int, Int] e superato questa lista nelle funzioni stavo testando.Con memoria sufficiente, i risultati sono stati una sorpresa:~1200ms per mutabile.Mappa, ~1800ms per immutabile.Mappa e ~750ms per un imperativo implementazione tramite mutevole.Mappa -- non so cosa conti per l'enorme differenza che c', ma sentitevi liberi di commentare, troppo.

Cosa mi sorprende un po', forse perché mi sto facendo un po ' di spessore, è che con il default eseguire la configurazione in IntelliJ 8.1, sia mutevole implementazioni di colpire un OutOfMemoryError, ma immutabile collezione non.L'immutabile test è stato eseguito per il completamento, ma molto lentamente, ci vogliono circa 28 secondi.Quando ho aumentato il max memoria della JVM (a circa 200MB, non so dove la soglia è), ho ottenuto i risultati di cui sopra.

Comunque, ecco cosa voglio davvero sapere:

Perché fare il mutevole implementazioni esaurito la memoria, ma l'immutabile implementazione non? Ho il sospetto che il immutabile versione permette il garbage collector per l'esecuzione e liberare la memoria prima che la mutevole implementazioni di fare-e di tutti quelli garbage collection di spiegare la lentezza del immutabile di memoria insufficiente esegui -- ma vorrei una spiegazione più dettagliata rispetto a quella.

Implementazioni di seguito.(Nota:Non ho la pretesa che questi sono i migliori implementazioni possibili.Sentitevi liberi di suggerire miglioramenti.)

  def mergeMaps[A,B](func: (B,B) => B)(listOfMaps: List[Map[A,B]]): Map[A,B] =
    (Map[A,B]() /: (for (m <- listOfMaps; kv <-m) yield kv)) { (acc, kv) =>
      acc + (if (acc.contains(kv._1)) kv._1 -> func(acc(kv._1), kv._2) else kv)
    }

  def mergeMutableMaps[A,B](func: (B,B) => B)(listOfMaps: List[mutable.Map[A,B]]): mutable.Map[A,B] =
    (mutable.Map[A,B]() /: (for (m <- listOfMaps; kv <- m) yield kv)) { (acc, kv) =>
      acc + (if (acc.contains(kv._1)) kv._1 -> func(acc(kv._1), kv._2) else kv)
    }

  def mergeMutableImperative[A,B](func: (B,B) => B)(listOfMaps: List[mutable.Map[A,B]]): mutable.Map[A,B] = {
    val toReturn = mutable.Map[A,B]()
    for (m <- listOfMaps; kv <- m) {
      if (toReturn contains kv._1) {
        toReturn(kv._1) = func(toReturn(kv._1), kv._2)
      } else {
        toReturn(kv._1) = kv._2
      }
    }
    toReturn
  }

Answer 1

Beh, in realtà dipende da cosa il tipo di Mappa che si sta utilizzando.Probabilmente HashMap.Ora, mutevole strutture come che ottenere prestazioni pre-allocazione di memoria si prevede di utilizzare.Si stanno unendo un milione di mappe, in modo che il finale della mappa è destinata ad essere un po ' grande.Vediamo come queste chiavi/valori aggiunti:

protected def addEntry(e: Entry) { 
  val h = index(elemHashCode(e.key)) 
  e.next = table(h).asInstanceOf[Entry] 
  table(h) = e 
  tableSize = tableSize + 1 
  if (tableSize > threshold) 
    resize(2 * table.length) 
} 

Vedere la 2 * nel resize linea?Il mutevole HashMap cresce, raddoppiando ogni volta che si esaurisce lo spazio, mentre l'immutabile è abbastanza conservatore in memoria di utilizzo (se esistente chiavi di solito occupano il doppio dello spazio quando è stato aggiornato).

Ora, come per altri problemi di prestazioni, la creazione di un elenco di chiavi e valori nelle prime due versioni.Che significa che, prima di partecipare a qualsiasi mappe, si dispone già di ogni Tuple2 (le coppie chiave/valore) in memoria due volte!Più l'overhead di List, che è piccolo, ma stiamo parlando di più di un milione di elementi per la testa.

Si potrebbe utilizzare una proiezione, che evita che.Purtroppo, la proiezione si basa su Stream, che non è molto affidabile per i nostri scopi su Scala 2.7.x.Ancora, invece, provare questo:

for (m <- listOfMaps.projection; kv <- m) yield kv

Un Stream non calcolare un valore fino a quando non è necessario.Il garbage collector dovrebbe raccogliere gli elementi inutilizzati, così, come se non mantenere un riferimento al Stream's testa, che sembra essere il caso nel vostro algoritmo.

MODIFICA

A complemento, una per/rendimento comprensione richiede una o più raccolte e restituire una nuova collezione.Come spesso ha senso, il ritorno della collezione è dello stesso tipo dell'originale collezione.Così, per esempio, nel codice seguente, per la comprensione crea un nuovo elenco, che viene poi memorizzato all'interno l2.Non è val l2 = che crea il nuovo elenco, ma per la comprensione.

val l = List(1,2,3)
val l2 = for (e <- l) yield e*2

Ora, diamo un'occhiata al codice utilizzato nei primi due algoritmi (meno il mutable parola chiave):

(Map[A,B]() /: (for (m <- listOfMaps; kv <-m) yield kv)) 

Il foldLeft operatore, qui scritti, con la sua /: sinonimo, verrà richiamato in oggetto restituito dalla per la comprensione.Ricordate che un : alla fine di un operatore inverte l'ordine degli oggetti e dei parametri.

Ora, prendiamo in considerazione ciò che l'oggetto è questo, in cui foldLeft viene chiamato.Il primo generatore in questo per-la comprensione del testo m <- listOfMaps.Sappiamo che listOfMaps è una raccolta di tipo List[X], dove X non è davvero rilevante qui.Il risultato di una comprensione su un List è sempre un altro List.Gli altri generatori non sono pertinenti.

Quindi, si prende questo List, avere tutte le chiavi/valori all'interno di ogni Map che è un componente di questa List, e una nuova List con tutto questo.Ecco perché sono la duplicazione di tutto quello che hai.

(in realtà, è ancora peggio, perché ogni generatore crea una nuova raccolta;le collezioni create dalla seconda generatore sono solo la dimensione di ogni elemento di listOfMaps però, e sono immediatamente gettati dopo l'uso)

La prossima domanda-in realtà, il primo, ma era più facile per invertire la risposta, è come l'uso di projection aiuta.

Quando si chiama projection su un List, restituisce un nuovo oggetto di tipo Stream (su Scala 2.7.x).In un primo momento si potrebbe pensare che questo sarà solo peggiorare le cose, perché ora avrete tre copie del List, invece di una sola.Ma un Stream non è pre-calcolata.È pigramente calcolate.

Ciò significa che se l'oggetto risultante, il Stream, non e ' una copia del List, ma, piuttosto, una funzione che può essere utilizzata per calcolare il Stream quando richiesto.Una volta calcolata, il risultato sarà tenuto in modo tale che esso non deve essere calcolato nuovamente.

Inoltre, map, flatMap e filter di un Stream tutti ritorno di un nuovo Stream, il che significa che è possibile concatenare tutti insieme, senza fare una sola copia del List che li ha creati.Dal momento che per la genericità con yield utilizzare queste funzioni, l'uso di Stream all'interno del evitare inutili copie di dati.

Ora, supponi di aver scritto qualcosa di simile a questo:

val kvs = for (m <- listOfMaps.projection; kv <-m) yield kv
(Map[A,B]() /: kvs) { ... }

In questo caso non guadagnando nulla.Dopo l'assegnazione di Stream per kvs, i dati non è stato copiato.Una volta che la seconda riga è eseguita, però, kvs sarà calcolata ciascuno dei suoi elementi, e, pertanto, tenere una copia completa dei dati.

Ora consideriamo la forma originale::

(Map[A,B]() /: (for (m <- listOfMaps.projection; kv <-m) yield kv)) 

In questo caso, il Stream è utilizzato allo stesso tempo è calcolato.Andiamo a vedere brevemente come foldLeft per un Stream è definito:

override final def foldLeft[B](z: B)(f: (B, A) => B): B = { 
  if (isEmpty) z 
  else tail.foldLeft(f(z, head))(f) 
} 

Se il Stream è vuota, solo ritorno accumulatore.In caso contrario, consente di calcolare un nuovo accumulatore (f(z, head)) e poi passarlo e la funzione per la tail del Stream.

Una volta f(z, head) ha eseguito, però, non ci sarà nessun residuo di riferimento per la head.O, in altre parole, nulla in qualsiasi punto del programma sarà indicando il head del Stream, e questo significa che il garbage collector può raccogliere, in modo da liberare memoria.

Il risultato finale è che ogni elemento prodotto dalla per-comprensione esiste da poco tempo, mentre lo si utilizza per calcolare l'accumulatore.E questo è il modo per salvare mantenere una copia dei tuoi dati.

Infine, c'è la questione del perché il terzo algoritmo non trarre beneficio da esso.Beh, il terzo algoritmo di non utilizzare yield, in modo che nessuna copia di tutti i dati di qualsiasi tipo è stato fatto.In questo caso, l'utilizzo di projection solo aggiunge un livello di indirezione.