scala - 为什么 Stream.filter 不会耗尽内存？

Question

这两个表达应该是同一个意思:

Stream.from(1).filter(_ < 0).head
Stream.from(1).find(_ < 0)

应该循环直到它们返回 Int.MinValue .而这正是带有 filter 的版本。确实如此，但使用 find OutOfMemoryError被生产。但是查看它们的实现，我无法弄清楚两个版本都不会产生 OutOfMemoryError .

这是Stream.filter的实现:

override def filter(p: A => Boolean): Stream[A] = {
  // optimization: drop leading prefix of elems for which f returns false
  // var rest = this dropWhile (!p(_)) - forget DRY principle - GC can't collect otherwise
  var rest = this
  while (!rest.isEmpty && !p(rest.head)) rest = rest.tail
  // private utility func to avoid `this` on stack (would be needed for the lazy arg)
  if (rest.nonEmpty) Stream.filteredTail(rest, p)
  else Stream.Empty
}

find继承自 LinearSeqOptimized ，根据这个定义:

override /*IterableLike*/
def find(p: A => Boolean): Option[A] = {
  var these = this
  while (!these.isEmpty) {
    if (p(these.head)) return Some(these.head)
    these = these.tail
  }
  None
}

它们都有一个 while 循环来丢弃 Stream 的元素。不满足谓词。因为 this应该保持对Stream开头的引用所有这些创建的元素都应该在内存中累积，直到空间用完为止。除非我真的误解了这里发生的事情，Stream.filter正在以某种方式消除 this从它进入 while 循环之前的堆栈帧。评论在 Stream.filter为什么dropWhile is not used 看起来像一个提示，但我不知道它指的是什么。

我的下一步是学习如何反汇编和读取 JVM 字节码，但我真的希望有人知道这里发生了什么。

Answer 1

它结合了 HotSpot 和 Scala 特征的实现方式。

如果我用 -Xint 关闭 HotSpot , Stream.filter也会以 OutOfMemoryException 死掉.在生成的字节码本身中，this和变量 rest和 these存储在不同的内存位置，但因为 this仅用于初始化这些变量 我相信 HotSpot 足够聪明，可以简单地为 this 重用内存位置.这解释了为什么Stream.filter不会耗尽内存。

HotSpot 优化为 Stream.filter也应适用于 LinearSeqOptimized.find ，但是由于特性的实现方式，请引用 this被保留下来。当一个方法在 trait 内部实现时，Scala 将该方法编译为静态方法。当一个类从该特性继承时，Scala 创建一个调用静态方法的小 stub 方法。所以即使 HotSpot 优化了 LinearSeqOptimized.find 的静态方法 stub 方法的堆栈帧仍然引用了 this .