SOE in Eval.defer

[mpilquist]

We encountered a stack overflow when using Eval.defer in FS2 with cats 0.9:

[info] fs2.SegmentSpec *** ABORTED *** (5 seconds, 363 milliseconds)
[info]   java.lang.StackOverflowError:
[info]   at fs2.Segment.$anonfun$stage$1(Segment.scala:16)
[info]   at fs2.Segment.$anonfun$stage$1$adapted(Segment.scala:15)
[info]   at fs2.Segment$$anon$6.$anonfun$stage0$33(Segment.scala:233)
[info]   at cats.Eval$Call$$anon$10.$anonfun$start$3(Eval.scala:240)
[info]   at cats.Eval$Compute.loop$1(Eval.scala:279)
[info]   at cats.Eval$Compute.value(Eval.scala:293)
[info]   at cats.Eval$Call.value(Eval.scala:229)
[info]   at cats.Eval$Compute.loop$1(Eval.scala:289)
[info]   at cats.Eval$Compute.value(Eval.scala:293)
[info]   at cats.Eval$Call.value(Eval.scala:229)
[info]   at cats.Eval$Compute.loop$1(Eval.scala:289)
[info]   at cats.Eval$Compute.value(Eval.scala:293)
[info]   at cats.Eval$Call.value(Eval.scala:229)
[info]   at cats.Eval$Compute.loop$1(Eval.scala:289)
[info]   at cats.Eval$Compute.value(Eval.scala:293)
[info]   at cats.Eval$Call.value(Eval.scala:229)
[info]   at cats.Eval$Compute.loop$1(Eval.scala:289)
[info]   at cats.Eval$Compute.value(Eval.scala:293)
[info]   at cats.Eval$Call.value(Eval.scala:229)
[info]   at cats.Eval$Compute.loop$1(Eval.scala:289)
[info]   at cats.Eval$Compute.value(Eval.scala:293)
[info]   at cats.Eval$Call.value(Eval.scala:229)
[info]   at cats.Eval$Compute.loop$1(Eval.scala:289)
[info]   at cats.Eval$Compute.value(Eval.scala:293)
[info]   at cats.Eval$Call.value(Eval.scala:229)
[info]   at cats.Eval$Compute.loop$1(Eval.scala:289)
[info]   at cats.Eval$Compute.value(Eval.scala:293)
[info]   at cats.Eval$Call.value(Eval.scala:229)
[info]   at cats.Eval$Compute.loop$1(Eval.scala:289)
[info]   at cats.Eval$Compute.value(Eval.scala:293)
[info]   at cats.Eval$Call.value(Eval.scala:229)
[info]   at cats.Eval$Compute.loop$1(Eval.scala:289)
[info]   at cats.Eval$Compute.value(Eval.scala:293)

Changing all uses of Eval.defer(c) to Eval.now(()).flatMap(_ => c) fixes. I haven't been able to minimize yet.

[non]

Oh no!

I'll definitely be waiting to see if we can a semi-minimized case. @mpilquist if you have ideas about the shape I can try to help trigger this bug.

Worst-case we can always replace Eval.defer with the snippet you gave since they should be equivalent (although currently I think defer is a bit faster).

[mpilquist]

This is our test that exposes the issue:

    "staging stack safety" in {
      val N = 100000
      val s = (0 until N).foldLeft(Segment.singleton(0))((s,i) => s map (_ + i))
      s.sum(0).run shouldBe (0 until N).sum
    }

(A Segment is a lazy, potentially infinite, fully fused sequence.)

Segment.singleton uses Eval.later and Segment#map results in an Eval.defer(something.map(...)). I'm still missing something though b/c the following doesn't SOE:

(0 until 1000000).foldLeft(Eval.later(0))((acc, i) => Eval.defer(acc.map(_ + i))).value

I'll keep playing with it. If you want to try yourself, clone https://github.com/functional-streams-for-scala/fs2 and checkout db221ff367ce14a9442bbf954523aac83b9dd490. Then in Segment.scala, change evalDefer to:

  private def evalDefer[A](e: => Eval[A]): Eval[A] = Eval.defer(e)
  // private def evalDefer[A](e: => Eval[A]): Eval[A] = Eval.now(()) flatMap { _ => e }

Then run testOnly *SegmentSpec.

[johnynek]

can this be something we can fix before cats 1.0?

cc @kailuowang

[mpilquist]

I am under the impression that #1888 didn’t fix this issue but I will try latest with fs2 and report back.

[johnynek]

@mpilquist if it doesn't, why didn't the test prove safety?

[kailuowang]

it's true that the system closed this one automatically by mistake. I am reopening it pending @mpilquist's report.

[mpilquist]

@johnynek Still broken with cats 1.0.0-SNAPSHOT.

Take a look here: mpilquist/fs2@375bec2

Running coreJVM/testOnly *SegmentSpec results in:

[info] fs2.SegmentSpec *** ABORTED *** (2 seconds, 292 milliseconds)
[info]   java.lang.StackOverflowError:
[info]   at fs2.Segment$$anon$9$$Lambda$4478/548709067.get$Lambda(Unknown Source)
[info]   at fs2.Segment$$anon$9.$anonfun$stage0$60(Segment.scala:508)
[info]   at fs2.Segment$$anon$9.$anonfun$stage0$60$adapted(Segment.scala:504)
[info]   at fs2.Segment.$anonfun$stage$1(Segment.scala:33)
[info]   at fs2.Segment.$anonfun$stage$1$adapted(Segment.scala:32)
[info]   at fs2.Segment$$anon$9.$anonfun$stage0$61(Segment.scala:508)
[info]   at cats.Eval$Call$$anon$10.$anonfun$start$3(Eval.scala:271)
[info]   at cats.Eval$Compute.loop$1(Eval.scala:310)
[info]   at cats.Eval$Compute.value(Eval.scala:324)
[info]   at cats.Eval$Call.value(Eval.scala:257)
[info]   at cats.Eval$Compute.loop$1(Eval.scala:320)
[info]   at cats.Eval$Compute.value(Eval.scala:324)
[info]   at cats.Eval$Call.value(Eval.scala:257)
[info]   at cats.Eval$Compute.loop$1(Eval.scala:320)
[info]   at cats.Eval$Compute.value(Eval.scala:324)
[info]   at cats.Eval$Call.value(Eval.scala:257)
[info]   at cats.Eval$Compute.loop$1(Eval.scala:320)
[info]   at cats.Eval$Compute.value(Eval.scala:324)
[info]   at cats.Eval$Call.value(Eval.scala:257)
[info]   at cats.Eval$Compute.loop$1(Eval.scala:320)
[info]   at cats.Eval$Compute.value(Eval.scala:324)
[info]   at cats.Eval$Call.value(Eval.scala:257)
[info]   at cats.Eval$Compute.loop$1(Eval.scala:320)
...

Last I talked to @non about this, we weren't sure if the issue lies in FS2 or in Cats. I've been assuming the issue is Cats because everything works fine when using the commented out definition of the private evalDefer method here. Maybe that reasoning doesn't hold up though.

[johnynek]

Those line numbers don't seem to line up with the latest. For one, Compute was renamed FlatMap.

Are you sure you are trying the latest?

I agree that if you get SOE when you rewrite defer as unit.flatMap then the bug is with Eval since those should be the same.

In fact, I'd love to see us have consistent evidence that the defer strategy we have is faster since it is certainly more complex to verify to be correct.

[mpilquist]

@johnynek Thanks for spotting that. Coursier was evicting the SNAPSHOT dependency in favor of 1.0.0-MF. Once I got that straightened out, I had to upgrade cats-effect to 1.0.0-SNAPSHOT and deal with various breakages since the MF release.

Anyway, good news is that the FS2 tests pass now. Closing this issue as fixed...