Scala: Mutable vs. Immutable Object Performance - OutOfMemoryError

Question

Chciałem porównać charakterystykę działania immutable.Map i Mutable.Map w Scali dla podobnej operacji (czyli scalenia wielu map w jedną. Patrz: this question). Mam to, co wydaje się być podobnymi implementacjami dla map zmiennych i niezmiennych (patrz poniżej).

Jako test wygenerowałem listę zawierającą 1 000 000 pojedynczej mapy [Int, Int] i przekazałem tę listę do funkcji, które testowałem. Przy wystarczającej pamięci wyniki nie były zaskakujące: ~ 1200ms dla mutable.Map, ~ 1800ms for immutable.Map i ~ 750ms dla imperatywnej implementacji przy użyciu mutable.Map - nie jestem pewna, co wyjaśnia ogromną różnicę, ale nie krępuj się skomentuj to również.

Co mnie zaskoczyło, być może dlatego, że jestem trochę grubszy, jest to, że z domyślną konfiguracją uruchamiania w IntelliJ 8.1, obie zmienne implementacje uderzają w OutOfMemoryError, ale niezmienna kolekcja nie. Test niezmienny przebiegał do końca, ale działo się to bardzo powoli - zajmuje to około 28 sekund. Kiedy zwiększyłem maksymalną pamięć JVM (do około 200 MB, nie wiem, gdzie jest próg), otrzymałem wyniki powyżej.

W każdym razie, oto co naprawdę chcę wiedzieć:

Dlaczego Zmienne implementacje zabraknie pamięci, ale niezmienne implementacja nie? Podejrzewam, że niezmienna wersja umożliwia uruchamianie garbage collectora i zwalnianie pamięci zanim zrobią to zmienne implementacje - a wszystkie te garbage collections wyjaśniają powolność niezmiennego biegu z niską pamięcią - ale chciałbym bardziej szczegółowego wyjaśnienie niż to.

Wykonania poniżej. (Uwaga: Nie twierdzę, że są to najlepsze możliwe implementacje Zapraszam do sugerują ulepszeń..)

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

Cóż, to naprawdę zależy od tego, co rzeczywiste typ mapy używasz. Prawdopodobnie HashMap. Teraz struktury zmienne, takie jak ta, zwiększają wydajność poprzez wstępną alokację pamięci, której spodziewa się użyć. Dołączasz do miliona map, więc ostateczna mapa musi być nieco większa. Zobaczmy, w jaki sposób te kluczowe/wartości dodawane:

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

Zobacz 2 * w linii resize? Zmienny HashMap rośnie przez podwojenie za każdym razem, gdy zabraknie miejsca, podczas gdy niezmienny jest dość konserwatywny w użyciu pamięci (chociaż istniejące klucze będą zwykle zajmować dwukrotnie więcej miejsca po aktualizacji).

Teraz, podobnie jak w przypadku innych problemów z wydajnością, tworzysz listę kluczy i wartości w dwóch pierwszych wersjach. Oznacza to, że przed dołączeniem do dowolnych map masz już w pamięci każdą z nich Tuple2 (pary klucz/wartość)! Plus narzut w wysokości List, który jest mały, ale mówimy o ponad milionie elementów razy narzut.

Możesz użyć projekcji, która to ominie. Niestety, projekcja oparta jest na Stream, co nie jest bardzo niezawodny do naszych celów w Scala 2.7.x. Nadal, spróbuj zamiast tego:

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

Stream nie obliczyć wartość dopóki nie jest potrzebne. Śmieciarz powinien również zbierać nieużywane elementy, o ile nie zachowujesz odniesienia do głowy Stream, co wydaje się mieć miejsce w twoim algorytmie.

EDIT

Uzupełniając, A dla/wydajność zrozumienie wykonuje jeden lub więcej zbiorów i powrót do nowego zbioru. Tak często, jak ma to sens, kolekcja powracająca jest tego samego typu, co oryginalna kolekcja. Na przykład w poniższym kodzie zrozumiałe wyrażenie tworzy nową listę, która następnie jest przechowywana wewnątrz l2. Nie jest to val l2 =, która tworzy nową listę, ale jest przeznaczona do zrozumienia.

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

Teraz spójrzmy na kod używany w pierwszych dwóch algorytmów (minus mutable kluczowe):

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

Operator foldLeft tu napisane z jego /: synonimami, zostanie wywołany na obiekt zwracany przez For-Comprehension. Pamiętaj, że : na końcu operatora odwraca kolejność obiektu i parametry.

Teraz zastanówmy się, jaki przedmiot to jest, na który jest wywoływany foldLeft. Pierwszym generatorem tego zrozumienia jest m <- listOfMaps. Wiemy, że listOfMaps jest zbiorem typu Lista [X], gdzie X nie ma tu znaczenia. Wynik dla zrozumienia dla List jest zawsze inny List. Inne generatory nie są istotne.

więc wziąć to List, uzyskać wszystkie kluczowe/wartości wewnątrz każdego Map który jest składnikiem tego List i zrobić nowy List z tym wszystkim. Dlatego powielacie wszystko, co macie.

(w rzeczywistości, to nawet gorzej, bo każdy generator tworzy nową kolekcję; zbiory utworzone przez drugi generator to tylko wielkość każdego elementu listOfMaps choć i są natychmiast usuwane po użyciu)

Następne pytanie - w rzeczywistości pierwsze, ale łatwiej było odwrócić odpowiedź - w jaki sposób pomaga użycie projection.

Po wywołaniu projection na List, zwraca on nowy obiekt typu Stream (w Scala 2.7.x). Na początku możesz myśleć, że to tylko pogorszy sprawę, ponieważ będziesz mieć trzy kopie z List, zamiast jednego. Ale Stream nie jest wstępnie obliczony. Jest to obliczone leniwie .

Co to znaczy, że otrzymany obiektu, Stream, nie jest kopią List, ale raczej to funkcja, która może być użyta do obliczyć Stream razie potrzeby. Po obliczeniu wynik zostanie zachowany, aby nie trzeba go było ponownie obliczać.

Również map, flatMap i filter z Stream wszystkich powrócić nową Stream, co oznacza, że ​​można je wszystkie razem łańcuch bez pojedynczą kopię List który je stworzył. Ponieważ do zrozumienia z yield korzystać z tych samych funkcji, użycie Stream wewnątrz zapobiec niepotrzebnych kopii danych.

Teraz załóżmy, że napisał coś takiego:

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

W tym przypadku niczego nie zyskuje. Po przypisaniu Stream do kvs dane nie zostały jeszcze skopiowane. Po wykonaniu drugiej linii kvs wyliczy każdy z jej elementów, a zatem będzie przechowywać pełną kopię danych.

Teraz rozważmy formę oryginalną ::

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

W tym przypadku Stream jest używany w tym samym czasie jest ona wyliczana. Załóżmy na chwilę spojrzeć na to, jak foldLeft dla Stream jest zdefiniowana:

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

Jeśli Stream jest pusta, po prostu wrócić akumulatora. W przeciwnym razie obliczyć nowy akumulator (f(z, head)), a następnie przekazać go i funkcję do tail z Stream.

Po wykonaniu f(z, head), nie będzie już żadnego odniesienia do head. Innymi słowy, nic w programie nie wskazuje na head z head z Stream, a to oznacza, że ​​garbage collector może go zbierać, co zwalnia pamięć.

Rezultatem końcowym jest to, że każdy element wytworzony przez for-understanding będzie istniał krótko, podczas gdy użyjesz go do obliczenia akumulatora. W ten sposób można zachować kopię wszystkich swoich danych.

Wreszcie pojawia się pytanie, dlaczego trzeci algorytm nie korzysta z niego. Cóż, trzeci algorytm nie używa yield, więc nie jest tworzona żadna kopia jakichkolwiek danych. W tym przypadku użycie tylko projection dodaje warstwę dwukierunkową.