Скала:Изменяемый противНеизменяемая производительность объекта - OutOfMemoryError

Question

Я хотел сравнить характеристики производительности immutable.Map и mutable.Map в Scala для аналогичной операции (а именно, объединения множества карт в одну.Видишь этот вопрос).У меня есть то, что кажется похожими реализациями как для изменяемых, так и для неизменяемых карт (см. Ниже).

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

Что меня немного удивило, возможно, потому, что я немного сгущаю краски, так это то, что при конфигурации запуска по умолчанию в 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

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

Редактировать

Дополняя, понимание for / yield принимает одну или несколько коллекций и возвращает новую коллекцию.Так часто, как это имеет смысл, возвращаемая коллекция имеет тот же тип, что и исходная коллекция.Так, например, в следующем коде 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 оператор, здесь написанный с его /: синонимичный, будет вызван для объекта, возвращаемого for-comprehension.Помните, что a : в конце оператор инвертирует порядок объектов и параметров.

Теперь давайте рассмотрим, что это за объект, на котором 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 из a 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)), а затем передайте его и функцию в tail из числа Stream.

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

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

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