Недостаточно памяти при добавлении элементов в неизменяемый набор в Scala

Question

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

Итак, предположим, что моя память JVM составляет 500 МБ, а набор потребляет 400 МБ. Теперь, прежде чем добавить новый элемент, Scala пытается скопировать старый набор в новый набор (который, я думаю, снова будет использовать 400 МБ), теперь на этом этапе он уже превысил память JVM (общее количество потребляемой памяти 800) и, следовательно, выбрасывает из памяти ошибка. Код выглядит немного как ниже

private def getNewCollection(myMuttableSet:Set[MyType]): Set[MyType] = {
myMuttableSet.flatMap(c => {
      val returnedSet = doSomeCalculationsAndreturnASet // this method returns a large collection so duing the loop the collection grows exponentially 
      if (returnedSet.isEmpty) Set.empty[MyType]
      else doSomeCalculationsAndreturnASet + MyType(constArg1,constArg2)  (I have case class of MyType)     
    })
}

Просьба сообщить, если мое понимание верно.

Answer 1

Теперь, перед тем как добавить новый элемент, Scala пытается скопировать старый набор в новый набор (который, я думаю, снова будет использовать 400 МБ) теперь на этом этапе,

Это не правильно.

Неизменяемые коллекции в Scala (включая Sets) реализованы в виде постоянных структур данных , которые обычно имеют свойство, называемое «структурное совместное использование». Это означает, что когда структура обновляется, она копируется не полностью, а вместо этого большая ее часть используется повторно, и только относительно небольшая часть фактически создается заново.

Простейшим примером для иллюстрации является List, который реализован в виде односвязного списка с корнем, указывающим на голову.

Например, у вас есть следующий код:

val a = List(3,2,1)
val b = 4 :: a
val c = 5 :: b

Хотя все три списка имеют в общей сложности 3 + 4 + 5 = 12 элементов, они физически разделяют узлы, и есть только 5 List узлов.

5 →  4  →  3 →  2  → 1
↑    ↑     ↑
c    b     a   

Аналогичный принцип применим к Set. Set в Scala реализовано как HashTrie . Я не буду вдаваться в подробности об особенностях Trie , просто думаю о нем как о дереве с высоким коэффициентом ветвления. Теперь, когда это дерево обновляется, оно не копируется полностью. Копируются только те узлы, которые находятся в пути от корня дерева до нового / обновленного узла.

Для HashTrie глубина дерева не может превышать 7 уровней. Таким образом, при обновлении Set в scala вы смотрите на распределение памяти, пропорциональное O(7 * 32) (максимум 7 уровней, каждый узел, грубо говоря, массив 32) в худшем случае, независимо от размера набора.

---

Глядя на свой код, в памяти появляются следующие вещи:

1. myMuttableSet присутствует, пока getNewCollection не вернется
2. myMuttableSet.flatMap создает изменяемый буфер внизу. Кроме того, после выполнения flatMap, buffer.result скопирует содержимое изменяемого буфера в неизменяемый набор. Так что на самом деле существует короткий момент, когда существуют два набора.
3. на каждом шаге flatMap, returnedSet также сохраняет память.

Дополнительное примечание: почему вы снова вызываете doSomeCalculationsAndreturnASet, если у вас уже есть результат, который кэшируется в returnedSet? Может ли это быть корнем проблемы?

Итак, в любой данный момент времени у вас есть память (в зависимости от того, что больше):

• myMuttableSet + mutable result set buffer + returnedSet + (another?) result doSomeCalculationsAndreturnASet
• myMuttableSet + mutable result set buffer + immutable result set

В заключение, какими бы ни были ваши проблемы с памятью, добавление элемента в Set, скорее всего, не является причиной. Я предлагаю приостановить вашу программу в отладчике и использовать любой профилировщик (например, VisualVM) для создания дампов кучи на разных этапах.

Answer 2

Это не так просто, потому что это зависит от размера элементов в Set.

Создание нового Set является мелкой операцией и нескопируйте элементы в наборе, он просто создает новую оболочку (обычно хеш-таблицу), указывающую на те же объекты.

Если у вас небольшой набор больших объектов, то дублирование этого набора может не потребоватьсямного памяти, потому что объекты будут разделены между двумя наборами.Большая часть памяти используется объектами в наборе, и их не нужно копировать для создания нового набора.Таким образом, ваши 400 МБ могут стать 450 МБ и уместиться в пределах лимита памяти.

Если у вас большой набор небольших объектов, то дублирование этого набора может удвоить объем памяти.Большая часть памяти используется в самом Set и не может быть разделена между исходным набором и копией.В этом случае ваши 400 МБ могут легко приблизиться к 800 МБ.

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