Scala: Mutable vs. Immutable Object Performance - OutOfMemoryError

Question

Я хотел сравнить характеристики производительности неизменяемых. Map и mutable.Map в Scala для аналогичной операции (а именно, слияние многих карт в один. См. this question). У меня есть то, что похоже на аналогичные реализации для изменяемых и неизменяемых карт (см. Ниже).

В качестве теста я сгенерировал список, содержащий 1,000,000 отдельных элементов Map [Int, Int] и передал этот список в те функции, которые я тестировал. С достаточной памятью результаты были неудивительными: ~ 1200 мс для mutable.Map, ~ 1800 мс для неизменяемых.Map и ~ 750 мс для императивной реализации с использованием mutable.Map - не уверен, что объясняет огромную разницу там, но не стесняйтесь Прокомментируйте это.

Что меня немного удивило, возможно, потому, что я немного толстое, это то, что с конфигурацией запуска по умолчанию в IntelliJ 8.1 обе изменяемые реализации попали в OutOfMemoryError, но неизменная коллекция этого не сделала. Неизменяемый тест действительно закончился, но он сделал это очень медленно - это занимает около 28 секунд. Когда я увеличил максимальную память JVM (примерно до 200 МБ, не уверен, где находится порог), я получил результаты выше.

Во всяком случае, вот что я действительно хочу знать:

Почему изменяемые реализации запустить из памяти, но неизменная реализация не делает? Я подозреваю, что неизменная версия позволяет сборщику мусора запускать и освобождать память до того, как выполняются изменчивые реализации - и все эти коллекции мусора объясняют медленность неизменяемого прогона с низкой памятью - но я хотел бы получить более подробную информацию объяснение, чем это.

Реализации ниже. (Примечание: я не утверждаю, что это лучшие реализации возможно Вы можете предложить улучшения..)

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

Ну, это действительно зависит от того, что фактический тип карты вы используете. Возможно HashMap. Теперь, изменяемые структуры, такие как производительность, обеспечивают предварительную выделение памяти, которую он ожидает использовать. Вы присоединяетесь к одному миллиону карт, поэтому окончательная карта должна быть несколько большой. Давайте посмотрим, как эти ключевые/значения добавляются:

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

Смотрите 2 * в resize линии? Изменчивый HashMap растет с удвоением каждый раз, когда у него заканчивается пространство, а неизменяемый - довольно консервативный в использовании памяти (хотя существующие ключи обычно занимают в два раза больше места при обновлении).

Теперь, как и для других проблем с производительностью, вы создаете список ключей и значений в первых двух версиях. Это означает, что до того, как вы присоединитесь к любым картам, вы уже имеете каждый Tuple2 (пары ключ/значение) в памяти дважды! Плюс накладные расходы List, что мало, но мы говорим о более чем одном миллионе элементов раз накладные расходы.

Возможно, вы захотите использовать проекцию, которая позволяет избежать этого. К сожалению, прогноз на основе Stream, что не так надёжёво для наших целей на Scala 2.7.x. Тем не менее, попробуйте вместо этого:

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

Stream не вычисляет значение до тех пор, пока это необходимо. Сборщик мусора должен также собирать неиспользуемые элементы, если вы не держите ссылку на голову Stream, что, по-видимому, имеет место в вашем алгоритме.

EDIT

Дополняя, а при/выход понимание принимает один или несколько коллекций и возвращает новую коллекцию. Так часто, как это имеет смысл, возвращаемая коллекция имеет тот же тип, что и исходная коллекция. Так, например, в следующем коде for-comprehension создает новый список, который затем сохраняется внутри l2. Это не val l2 =, который создает новый список, но для понимания.

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

Теперь давайте посмотрим на код используется в первых двух алгоритмов (минус mutable ключевое слово):

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

foldLeft оператор, здесь написано с его /: синонимами, будет вызван на объект, возвращенный понятием. Помните, что : в конце оператора инвертирует порядок объекта и параметры.

Теперь давайте рассмотрим, что это за объект, на который вызывается foldLeft. Первый генератор в этом понимании - m <- listOfMaps. Мы знаем, что listOfMaps представляет собой набор типов List [X], где X здесь не имеет особого значения. Результатом по-осмысления на List всегда является другой List. Другие генераторы не имеют отношения к делу.

Итак, вы берете этот List, получить все ключ/значение внутри каждого Map, который является составной частью этого List, и сделать новый List со всем этим. Вот почему вы дублируете все, что у вас есть.

(на самом деле, это даже хуже, чем это, потому что каждый генератор создает новую коллекцию, коллекции, созданные с помощью второго генератора только размер каждого элемента listOfMaps хотя, и сразу же после использования выбрасывается)

Следующий вопрос - на самом деле, первый, но было проще инвертировать ответ - так помогает использование projection.

Когда вы звоните projection на List, он возвращает новый объект, тип Stream (на Scala 2.7.x). Сначала вы можете подумать, что это только усугубит ситуацию, потому что теперь у вас будет три копии List, а не один. Но Stream не предварительно вычисляется. Это ленивый расчет.

Что это означает, что полученный объект, Stream, не является копией List, но, скорее, функция, которая может быть использована для вычисления Stream при необходимости. После вычисления результат будет сохранен, чтобы его не нужно было вычислять снова.

Кроме того, map, flatMap и filter из Stream все вернуть новый Stream, а значит, вы можете приковать их всех вместе, не делая одну копию List, который их создал. Поскольку для -понимания с yield используют эти самые функции, использование Stream внутри предотвращает ненужные копии данных.

Теперь предположим, что вы написали что-то вроде этого:

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

В этом случае вы не увеличиваясь ничего. После присвоения Stream до kvs данные еще не скопированы. Однако, если вторая строка выполнена, kvs вычислит каждый из своих элементов и, следовательно, будет содержать полную копию данных.

Теперь рассмотрим оригинальную форму ::

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

В этом случае Stream используется в то же время он вычислен. Давайте кратко рассмотрим, как foldLeft для Stream определяется:

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

Если Stream пуст, просто верните аккумулятор. В противном случае вычислите новый аккумулятор (f(z, head)), а затем передайте его и функцию на tailStream.

Как только f(z, head) выполнил, однако, не будет никакой ссылки на head. Или, другими словами, ничто в программе не будет указывать на headStream, а это значит, что сборщик мусора может его собирать, тем самым освобождая память.

Конечным результатом является то, что каждый элемент, созданный по-понятию, будет существовать только ненадолго, в то время как вы используете его для вычисления аккумулятора. И вы сохраняете копию всех ваших данных.

Наконец, возникает вопрос, почему третий алгоритм не извлекает из этого выгоду. Ну, третий алгоритм не использует yield, поэтому никакой копии каких-либо данных не производится. В этом случае использование projection добавляет только слой косвенности.