Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Stream and LazyList `find` leaks #11443

Open
OlegYch opened this Issue Mar 22, 2019 · 33 comments

Comments

Projects
None yet
4 participants
@OlegYch
Copy link

commented Mar 22, 2019

using 2.13.0-M5-1775dba (published on 16-Feb-2019)

this throws OOME

//  type S[A] = Stream[A]
//  val S = Stream
  type S[A] = LazyList[A]
  val S = LazyList

  S.iterate(1)(_ + 1).find(_ => false)

this correctly runs forever:

    @annotation.tailrec def find[A](s: S[A])(p: A => Boolean): Option[A] = {
      s.headOption match {
        case Some(x) if p(x) => Some(x)
        case None => None
        case _ => find(s.tail)(p)
      }
    }
    find(S.iterate(1)(_ + 1))(_ => false)   

perhaps find should be overriden in the same way Stream#foreach is?

@NthPortal

This comment has been minimized.

Copy link

commented Mar 24, 2019

If I'm not mistaken, since find returns Option[A], this fix is binary compatible?

@OlegYch

This comment has been minimized.

Copy link
Author

commented Mar 24, 2019

@NthPortal i suspect adding tailrec breaks bincompat, though can't be sure

i've found a couple other functions with the same problem though - collect and collectFirst
(though collect is only broken in LazyList)

@OlegYch

This comment has been minimized.

Copy link
Author

commented Mar 24, 2019

ie with -Xmx50m

Stream.iterate(1)(_ + 1).collect{ case i if i > 10000000 => i }.headOption //works
LazyList.iterate(1)(_ + 1).collect{ case i if i > 10000000 => i }.headOption //fails with OOME
Stream.iterate(1)(_ + 1).collectFirst{ case i if i > 10000000 => i } //fails with OOME
LazyList.iterate(1)(_ + 1).collectFirst{ case i if i > 10000000 => i } //fails with OOME
@smarter

This comment has been minimized.

Copy link

commented Mar 24, 2019

Making a method tailrec doesn't break binary-compatibility.

@NthPortal

This comment has been minimized.

Copy link

commented Mar 25, 2019

The concern was whether or not adding an override (since the method is not currently defined in LazyList) is binary compatible

@SethTisue SethTisue added this to the 2.13.1 milestone Mar 27, 2019

@SethTisue

This comment has been minimized.

Copy link
Member

commented Mar 27, 2019

The concern was whether or not adding an override (since the method is not currently defined in LazyList) is binary compatible

it appears so: lightbend/migration-manager@e607d19

but also, it's reallllllly really time to enable MiMa now on the 2.13.x branch, I am making a note to myself to finally do that this week

@SethTisue

This comment has been minimized.

Copy link
Member

commented Mar 27, 2019

as an exercise, I verified the bincompat as follows. the change is clearly backwards compatible, the question is whether it's forward compatible, that is, whether code compiled when the override is present still works if the override is removed

given

trait A {
  def foo = 2
}

class B extends A {
  override def foo = 3
}

compiling (new B).foo gives

      10: invokevirtual #72                 // Method B.foo:()I

note the reference to B.foo. if we change B to just class B extends A with no override, recompile B, and then re-rerun the existing bytecode for (new B).foo without regenerating it, there is no linkage error and 2 is returned as expected

a useful reference on these issues is https://docs.oracle.com/javase/specs/jls/se8/html/jls-13.html , which states:

here is a list of some important binary compatible changes that the Java programming language supports: [..] Moving a method upward in the class hierarchy

which is what is happening here when considering the forward-compat side.

anyway, all this is surely old hat, but I just wanted to go over it again for myself

@smarter

This comment has been minimized.

Copy link

commented Mar 27, 2019

Yeah adding/removing an override in a class is fine I think, I'm not so sure that this also the case when doing the same in a trait given the complicated encoding used.

@SethTisue

This comment has been minimized.

Copy link
Member

commented Apr 10, 2019

JVM Hijinx Corner: as we were just discussing on Gitter, it's pretty awesome that the reason the @tailrec version can run forever is that the generated bytecode overwrites this before looping:

      19: invokevirtual #474                // Method tail:()Lscala/collection/immutable/LazyList;
  ...
      24: astore_0
      25: goto          0
@SethTisue

This comment has been minimized.

Copy link
Member

commented Apr 10, 2019

@NthPortal are you interested in addressing collect and collectFirst as well in your PR?

@NthPortal

This comment has been minimized.

Copy link

commented Apr 10, 2019

@SethTisue yeah, I can try to do that

@NthPortal

This comment has been minimized.

Copy link

commented Apr 10, 2019

should we have a tailrec implementation in LinearSeqOps instead? (the tailrec could be a private or static method)

@NthPortal

This comment has been minimized.

Copy link

commented Apr 10, 2019

a few things I've discovered:

  1. collect was already tail-recursive, but still OOMed
  2. filter appears to OOM as well
  3. both of these are despite the fact that they pass the GC tests in LazyListTest
@OlegYch

This comment has been minimized.

Copy link
Author

commented Apr 10, 2019

yep i confirm filter has regressed as well (compared to Stream)
both filter and collect in LazyStream are implemented via private tailrec method, but they are themselves not tail recursive
perhaps moving that function to an object will do the trick, this is what Stream.collect seems to be doing

@NthPortal

This comment has been minimized.

Copy link

commented Apr 10, 2019

the question is though, why don't the *_allows_GC tests catch that it's not actually being collected?

I will certainly look into moving the methods to the companion, though I'm concerned there are other methods for which this is a problem that we haven't caught. It's not clear to me why some tail-recursive methods work fine (such as my new implementation of find) and some don't. And until/unless we can get a reliable fix to the *_allows_GC tests, it's difficult to check what works and what doesn't.

@NthPortal

This comment has been minimized.

Copy link

commented Apr 11, 2019

Update: the reason the *_allows_GC tests did not catch the problem with filter is because they only checked the case of retaining all values, not of dropping all values.

@NthPortal

This comment has been minimized.

Copy link

commented Apr 11, 2019

moving collectTrampoline and collectState to the companion had no effect

in class:

  // removing @inline makes no difference, I've checked
  @inline private def collectTrampoline[B](pf: PartialFunction[A, B]): LazyList[B] =
    newLL(collectState(pf))

  @tailrec
  private def collectState[B](pf: PartialFunction[A, B]): State[B] =
    if (isEmpty) State.Empty
    else {
      val marker = Statics.pfMarker
      val res = pf.applyOrElse(head, ((_: A) => marker).asInstanceOf[A => B])
      if (res.asInstanceOf[AnyRef] eq marker) tail.collectState(pf)
      else sCons(res, tail.collectTrampoline(pf))
    }

in companion:

  private def collectTrampoline[A, B](ll: LazyList[A], pf: PartialFunction[A, B]): LazyList[B] =
    newLL(collectState(ll, pf))

  @tailrec
  private def collectState[A, B](ll: LazyList[A], pf: PartialFunction[A, B]): State[B] =
    if (ll.isEmpty) State.Empty
    else {
      val marker = Statics.pfMarker
      val res = pf.applyOrElse(ll.head, ((_: A) => marker).asInstanceOf[A => B])
      if (res.asInstanceOf[AnyRef] eq marker) collectState(ll.tail, pf)
      else sCons(res, collectTrampoline(ll.tail, pf))
    }

anyone have any idea where the reference to the beginning of the LazyList is being held onto in either method pair? I'm out of ideas

@OlegYch

This comment has been minimized.

Copy link
Author

commented Apr 11, 2019

@NthPortal have you tried testing Stream with this framework? these fail for me:

  @Test
  def filter_all_out_foreach_allows_GC(): Unit = {
    assertStreamOpAllowsGC(_.filter(_ => false).foreach(_), _ => ())
  }

  @Test
  def collect_all_out_foreach_allows_GC(): Unit = {
    assertStreamOpAllowsGC(_.collect{case -1 => 1}.foreach(_), _ => ())
  }

perhaps allowsGC helpers are not what they seem

@OlegYch

This comment has been minimized.

Copy link
Author

commented Apr 11, 2019

oh, they need for at least some values to be retained to have a chance to force gc

@OlegYch

This comment has been minimized.

Copy link
Author

commented Apr 11, 2019

any idea why this fails?

assertStreamOpAllowsGC((ll, check) => ll.collect({ case i if { check(i); false } => i }), _ => ())
@OlegYch

This comment has been minimized.

Copy link
Author

commented Apr 11, 2019

this doesn't

assertStreamOpAllowsGC((ll, check) => ll.collect{case i if i > 100 => 1}.foreach(check), _ => ())
@OlegYch

This comment has been minimized.

Copy link
Author

commented Apr 11, 2019

hm, one reason might be that Stream.collect doesn't actually drop head reference, but Stream is less memory intensive than LazyStream

@NthPortal

This comment has been minimized.

Copy link

commented Apr 12, 2019

my best guess as to the source of the leak is that newLL(=> X) (an alias for new LazyList(() => X)) captures the start of the LazyList in a closure, and that closure doesn't stop being referenced until the next State is resolved. if that is the case:

  • there are a lot of method implementations in LazyList that need to be changed
  • the implementations cannot use tail recursion
  • the implementations need to either:
    • use vars and while loops (so that the closure captures the var as an ObjectRef, which will not hold on to the start of the LazyList)
    • use LazyList.from(iterator.<op>)

OlegYch added a commit to OlegYch/sbt-zinc-559 that referenced this issue Apr 12, 2019

OlegYch added a commit to OlegYch/sbt-zinc-559 that referenced this issue Apr 12, 2019

OlegYch added a commit to OlegYch/scala that referenced this issue Apr 12, 2019

@OlegYch

This comment has been minimized.

Copy link
Author

commented Apr 12, 2019

hm i'm having trouble with Stream tests on current 2.13 branch and on v2.13.0-RC1 tag

Stream methods like filter and collect fail there while they don't on a separate project using 2.13.0-RC1

can someone tell me what's the difference between https://github.com/OlegYch/sbt-zinc-559/tree/scala-11443 and https://github.com/OlegYch/scala/tree/scala-11443

@NthPortal

This comment has been minimized.

Copy link

commented Apr 23, 2019

@OlegYch I took a look and am just as mystified as you are

@OlegYch

This comment has been minimized.

Copy link
Author

commented Apr 23, 2019

well good news is that this kind of ad-hoc tests work for LazyList with latest changes
no idea why Stream fails

@OlegYch

This comment has been minimized.

Copy link
Author

commented Apr 23, 2019

does it fail for you @NthPortal ?

@NthPortal

This comment has been minimized.

Copy link

commented Apr 23, 2019

@OlegYch I only looked at the code; I did not run it. I am (un?)fortunately in the middle of two major life changes atm, so I don't have a ton of time right now. I'll see how soon I can take a look.

Honestly, Stream is in a sorry state right now. It never really got un-abstracted when LazyList split, so it is currently made up of an abstraction over only itself, which is quite messy.

@OlegYch

This comment has been minimized.

Copy link
Author

commented Apr 23, 2019

it is quite easy to reproduce, just add javaOptions in Test := Seq("-Xmx10M"), in junit project and run

object StreamFilterTest extends App {
  val str = Stream.iterate(1)(_ + 1).filter(_ > 10000000).headOption
  println(str)
}

i'm guessing it's some kind of difference in scalac options used during publishing

@OlegYch

This comment has been minimized.

Copy link
Author

commented Apr 23, 2019

i mean, it should behave the same using 2.13.0-RC1 tag and binary, right?

@SethTisue

This comment has been minimized.

Copy link
Member

commented Apr 23, 2019

local builds aren't bootstrapped (that is unless you follow the "local bootstrap" instructions in the scala/scala README), published builds (including the builds published on https://scala-ci.typesafe.com/artifactory/scala-pr-validation-snapshots/ for as-yet-unmerged PRs) are bootstrapped, that's a possible way for differences to creep in.

there's also the question of whether the optimizer is enabled, that seems like a likely source of discrepancies

(sorry I don't have time today to take a closer look at whether these observations might be relevant to this particular case)

@smarter

This comment has been minimized.

Copy link

commented Apr 23, 2019

published builds (including the builds published on https://scala-ci.typesafe.com/artifactory/scala-pr-validation-snapshots/ for as-yet-unmerged PRs)

That doesn't seem to be true based on what I've seen: scala/scala#7980 (comment)

@SethTisue

This comment has been minimized.

Copy link
Member

commented Apr 25, 2019

@smarter open a scala-dev ticket and let's discuss?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.