Блог

Проблема с памятью связана с приведенной ниже процедурой умножения разреженной матрицы.

Отлично работает для очень больших разреженных очень разреженных матриц, но по мере увеличения плотности матриц она останавливается.

Похоже, здесь происходит утечка памяти.

kk <- (A.colPtrs(jj) to (A.colPtrs(jj 1) -1)) // сбой здесь

 def sparseMatrixMultiply(A:CSCMatrix[Double], B:CSCMatrix[Double]) = {
      val n = B.cols
      val Bvals = B.activeValuesIterator.toArray
      val Avals = A.activeValuesIterator.toArray

      val entries =
          for {
            j <- (0 to (n-1))/*.par*/
            k <- (B.colPtrs(j) to (B.colPtrs(j   1)-1))
            jj = B.rowIndices(k) 
            kk <- (A.colPtrs(jj) to (A.colPtrs(jj   1)-1)) //  get stuck here 
            i = A.rowIndices(kk) 
          } yield {
            println(s"$j $k $jj $kk $i ${Bvals(k)} ${Avals(kk)}")
            (i, j, Bvals(k) * Avals(kk))
          }
        }

      val coo = SparseMatrix.fromCOO(A.rows,B.cols, entries/*.seq*/)

      //converting back to breeze CSCMatrix
      new breeze.linalg.CSCMatrix[Double](coo.values, coo.numRows, coo.numCols, coo.colPtrs, coo.rowIndices)
    }
 

Я попытался разделить его на отдельные блоки, но на том же шаге итерации быстро заканчивается память

kk <- (A.colPtrs(jj) to (A.colPtrs(jj 1) -1))

Это просто слишком быстрое выделение памяти для GC? или все экземпляры диапазона сохраняются до завершения for / yield

ищете представление о том, как GC управляет памятью для понимания / понимания

Спасибо

for понимание — это синтаксис для вложенных карт и плоских карт. То, что вы сделали, это:

 for {
  j <- (0 to (n-1))/*.par*/
  k <- (B.colPtrs(j) to (B.colPtrs(j   1)-1))
  jj = B.rowIndices(k) 
  kk <- (A.colPtrs(jj) to (A.colPtrs(jj   1)-1)) //  get stuck here 
  i = A.rowIndices(kk) 
} yield {
  println(s"$j $k $jj $kk $i ${Bvals(k)} ${Avals(kk)}")
  (i, j, Bvals(k) * Avals(kk))
}
 

что

 (0 to (n-1)).flatMap { j =>
  (B.colPtrs(j) to (B.colPtrs(j   1)-1)).flatMap { k =>
    val jj = B.rowIndices(k)
    (A.colPtrs(jj) to (A.colPtrs(jj   1)-1)).map { kk =>
      val i = A.rowIndices(kk)
      println(s"$j $k $jj $kk $i ${Bvals(k)} ${Avals(kk)}")
      (i, j, Bvals(k) * Avals(kk))
    }
  }
}
 

Каждое вложение — это замыкание, которое:

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

Итак, если у вас, например, в среднем по 10 элементов, вводимых каждым вложением, вы создаете продукт из 10 x 10 x 10 элементов с помощью промежуточных шагов (10 элементов, каждый из которых имеет замыкание, которое создает 10 элементов, каждый создает замыкание, которое создает конечный результат, и самое внутреннее должно быть сглажено,и затем среднее вложение должно быть сглажено, а самый внешний результат должен быть сглажен). Хотя ваши проблемы предполагают, что количество промежуточных объектов намного превышает порядок 1000.

Это много промежуточных результатов, и это не утечка памяти. Вот как это должно работать. Вся эта память собирается после выхода из for comprehension. Диапазоны легки сами по себе, но когда вы используете .map и .flatMap преобразуете их в, IndexedSeq которая, скорее всего, будет какой-то нетерпеливой, запоминающей структурой данных, которая сразу вычислит конечный результат, не позволяя JVM что-либо забывать (поскольку интерфейс гарантирует только IndexedSeq , что трудно предположить, какой именно, это может бытьили List Vector , но у вас нет никаких гарантий).

Вы можете попробовать преобразовать каждый диапазон в LazyList (2.13) или Stream (2.12 и ранее) и перед переходом к fromCOO преобразованию этой отложенной структуры данных в Iterator or Iterable . Этот способ понимания позволил бы создать структуру, которая выделяет и запоминает только столько, сколько необходимо для вычисления следующего элемента, и сразу же забывает все, что больше не нужно. Что-то вроде:

 val entries = for {
  j <- (0 to (n-1)).to(LazyList)
  k <- (B.colPtrs(j) to (B.colPtrs(j   1)-1)).to(LazyList)
  jj = B.rowIndices(k) 
  kk <- (A.colPtrs(jj) to (A.colPtrs(jj   1)-1)).to(LazyList)
  i = A.rowIndices(kk) 
} yield {
  println(s"$j $k $jj $kk $i ${Bvals(k)} ${Avals(kk)}")
  (i, j, Bvals(k) * Avals(kk))
}

SparseMatrix.fromCOO(A.rows,B.cols, entries.toIterable)