In Scala, wie vergleichen unveränderliche und veränderbare Sätze und Karten in Bezug auf Garbage Collection?

Question

Ich schreibe einen Code, der das Aufnehmen von Sätzen und Karten mit "kleinen" (zB kurzen Strings oder einfachen Fallklassen) Objekten beinhaltet, während man durch eine große Struktur rekurriert und an jedem Punkt einen kleinen (normalerweise 1, manchmal a Handvoll) Objekte zum Set oder zur Karte. Es scheint, als ob die Verwendung von veränderbaren Mengen und Karten eine deutliche Beschleunigung gegenüber unveränderlichen darstellt, aber ich habe Schwierigkeiten, den Unterschied quantitativ zu bewerten.

Macht es Sinn, dass Scalas Garbage Collection eine erhebliche Verlangsamung verursacht, wenn ich unveränderliche Datenstrukturen verwende? Würde die Verwendung veränderbarer Datenstrukturen dies beheben?

Answer 1

Die Scala immutable-Kollektionen sind überraschend effizient. Vor allem, wenn sich eine Struktur verändert, werden viele Strukturen wiederverwendet.

Aber wenn Sie viele Änderungen vornehmen, könnte eine veränderbare Struktur besser passen. Genau das macht die Scala Collection API an vielen Stellen intern: Verwenden Sie eine veränderbare Datenstruktur, um neue Sachen zu erstellen und erst als letzten Schritt, erstellen Sie eine unveränderliche und geben Sie sie zurück.

Answer 2

Scala Veränderbare Datenstrukturen gewinnen durch Vorbelegung von Speicher effizienter als unveränderbare Datenstrukturen. Sie eignen sich besser für viele Inserts (weshalb sie veränderbar sind). Werfen Sie einen Blick auf die Implementierung der Funktion + = in der Standard wandelbar Sammlung, eine HashMap, die Karte erweitert:

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 implementiert eine veränderbare Map HashTable mit, die addEntry definiert

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) 
} 

die Größe der Sammlung jedes Mal verdoppelt wird der Schwellenwert erreicht ist. Wenn Sie also immer wieder n ganze Einträge gleichzeitig einer leeren veränderbaren Datenstruktur hinzufügen, müssen Sie nur die Größe des Protokolls (n) ändern. Ich habe die Implementierung der unveränderlichen Datenstruktur nicht eingehend betrachtet, aber ich gehe davon aus, dass Sie die Größe jedes Einsatzes ändern müssen. Daher Ihre Leistungsunterschiede.