In Scala, come si confrontano insiemi e mappe immutabili e modificabili in relazione alla garbage collection?

Question

Sto scrivendo un codice che implica l'utilizzo di insiemi e mappe con oggetti "piccoli" (ad esempio, stringhe corte o classi di casi semplici) mentre si ricorre attraverso una struttura grande, aggiungendo ogni volta un piccolo (di solito 1, a volte un manciata) oggetti sul set o sulla mappa. Sembra come se l'uso di insiemi e mappe mutevoli offra una significativa accelerazione rispetto a quelli immutabili, ma ho difficoltà a valutare quantitativamente la differenza.

Ha senso che la garbage collection di Scala causi un significativo rallentamento quando utilizzo strutture di dati immutabili? L'uso di strutture dati mutabili potrebbe risolvere questo problema?

Answer 1

Le collezioni immutabili di Scala sono sorprendentemente efficienti. Principalmente perché quando una struttura viene cambiata, molta della struttura viene riutilizzata.

Ma se si apportano molte modifiche, le strutture mutabili potrebbero essere più idonee. In realtà questo è ciò che l'API Scala Collection fa internamente in molti punti: usa una infrastruttura mutabile per costruire nuove cose e solo come ultimo passaggio, crea un valore immutabile e restituiscilo.

Answer 2

Scala Le strutture dati mutevoli acquisiscono efficienza rispetto a quelle immutabili mediante la pre-allocazione della memoria. Sono più adatti a molti inserti (quindi perché sono mutevoli). Date un'occhiata alla implementazione della funzione + = nella raccolta predefinita mutevole, una HashMap, che mappa si estende:

https://github.com/scala/scala/blob/v2.9.2/src/library/scala/collection/mutable/HashMap.scala#L84

def += (kv: (A, B)): this.type = { 
    val e = findEntry(kv._1) 
    if (e == null) addEntry(new Entry(kv._1, kv._2)) 
    else e.value = kv._2 
    this 
} 

HashMap implementa un mutevole Mappa utilizzando HashTable, che definisce addEntry

https://github.com/scala/scala/blob/v2.9.2/src/library/scala/collection/mutable/HashTable.scala#L117

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

la dimensione della collezione è raddoppiato ogni volta che viene raggiunta la soglia. Pertanto, se si aggiungono ripetutamente un elemento alla volta a una struttura di dati mutabile vuota, sarà necessario solo ridimensionare le log (n) volte. Non ho approfondito l'immutabile implementazione della struttura dati, ma suppongo che dovrai ridimensionare su ogni inserto. Da qui la tua disparità di prestazioni.