Функция перенаправления параметра Stream в другую функцию сохраняет ссылку - PullRequest
Новая
       26

Функция перенаправления параметра Stream в другую функцию сохраняет ссылку

0 голосов
/ 06 сентября 2018

Я могу написать функцию обработки потока, drop(n,s), которая масштабируется до очень больших потоков. Но когда я пишу другую функцию, nth(n,s), которая принимает поток s и перенаправляет его на drop(n,s), создается впечатление, что nth() "держит голову" потока. Это приводит к OutOfMemoryError для больших n.

Вот код: 

import scala.annotation.tailrec
import scala.collection.immutable.Stream.cons

object Streams {

  def iterate[A](start: A, f: A => A): Stream[A] =
    cons(start, iterate(f(start), f))

  def inc(n:Int) = n + 1

  def naturals() =
    iterate(1, inc)

  @tailrec def drop[T](n : Int, s : Stream[T]) : Stream[T] =
    if (n <= 0 || s.isEmpty) s
    else drop(n-1, s.tail)

  // @inline didn't seem to help
  def nth[T](n : Int, s : Stream[T]) =
    drop(n,s).head

  def N = 1e7.toInt

  def main(args: Array[String]) {
    println(drop(N,naturals()).head) // works fine for large N
    println(nth(N, naturals())) // results in OutOfMemoryError for N set to 1e7.toInt and -Xmx10m
  }

}

Мой опыт в этом вопросе Java: почему этот метод Java протекает - и почему встраивание в него исправляет утечку? приводит меня к мысли, что сгенерированный Scala код для nth() не используется достаточно агрессивен при расчистке s перед вызовом drop(). Уловка библиотеки Clojure (уловка Java) (см. Связанный вопрос) здесь не работает, потому что все параметры функции Scala val с (не var с), поэтому их нельзя назначить (null).

Как написать масштабируемое nth() в терминах drop()?

Вот связанная ошибка компилятора Scala 2009-2011 гг. (reduceLeft() реализована в терминах foldLeft()): https://issues.scala -lang.org / browse / SI-2239

Я не могу сказать из этого жучка Scala, как они это исправили. В билете было предложение, что единственный способ исправить это - дублировать код foldLeft() в reduceLeft(). Я действительно надеюсь, что это не ответ.

Обновление : ответ Андрея Тюкина https://stackoverflow.com/a/52209383/156550 исправляет это. Теперь у меня есть: 

// have to call by name (s) here, otherwise we hold on to head!
def nth[T](n : Int, s : => Stream[T]) =
  drop(n,s).head

И nth(n,s) Масштаб отлично.

1 Ответ

0 голосов
/ 06 сентября 2018

Вот быстрое и грязное решение, которое принимает всего два дополнительных символа: 

def nth[T](n : Int, s: => Stream[T]) = drop(n,s).head

Вот что происходит без =>:

  • Когда поток s передается в качестве аргумента nth, это ссылка на уже существующее значение, ранее созданное naturals().
  • Из-за .head drop(n, s) должен возвращать поток в кадр стека nth, поэтому кадр стека nth не может быть отброшен, и поэтому nth удерживает ссылку s.
  • Поскольку ссылка на параметр s поддерживается фреймом стека nth, пока работает drop, все отброшенные префиксы фактически не могут быть собраны мусором (это потому, что Stream гарантирует, что если вы держитесь за его голову и повторяйте его несколько раз, он вернет те же результаты).

Теперь, если вы добавите =>, произойдет следующее:

  • Кадр стека nth все еще не может быть сброшен из-за .head
  • Но : nth не содержит ссылку на начало потока, переданного в drop. Он содержит только ссылку на thunk , который производит Stream.
  • Сам thunk не занимает сколько-нибудь значительного объема памяти и не содержит никаких ссылок на заголовок созданного потока, поэтому префикс потока можно собирать мусором.

Дополнительное примечание (тест Димы):

Обратите внимание, что если сам thunk просто возвращает ссылку на уже существующий Stream, то поведение остается таким же, как и без =>. Например, если ваш inc был определен следующим образом: 

def inc(i: Int): Int = {
  println(System.currentTimeMillis())
  i + 1
}

затем вызывает 

val s = naturals()
nth(10, s)
nth(5, s)

будет печатать текущее время только десять раз (не 15).

...