IO.syncStep(n).unsafeRunSync() fails with StackOverflowError

[migesok]

This code works for me on 3.5.7 but fails on 3.6.0 (OpenJDK 21 on M1 Mac OS):

import cats.effect.*
import cats.syntax.all.*

object Main extends App {
  val syncStepSize = 1000000

  val io = for {
    ref <- Ref.of[IO, Int](0)
    _ <- Vector.fill(100000)(1).traverse_[IO, Unit](n => ref.update(_ + n))
    result <- ref.get
  } yield result

  println(io.syncStep(syncStepSize).unsafeRunSync())
}

Exception in thread "main" java.lang.StackOverflowError
	at cats.effect.IO$FlatMap.ioe(IO.scala:2235)
	at cats.effect.SyncStep$.interpret(IO.scala:2355)
	at cats.effect.SyncStep$.interpret(IO.scala:2356)
	at cats.effect.SyncStep$.interpret(IO.scala:2356)
	at cats.effect.SyncStep$.interpret(IO.scala:2356)
	at cats.effect.SyncStep$.interpret(IO.scala:2356)
	at cats.effect.SyncStep$.interpret(IO.scala:2356)
	at cats.effect.SyncStep$.interpret(IO.scala:2356)
        ...

I'm not sure if it's a bug or an expected behaviour. It was sure unexpected for me 😄

I tried to debug it a little bit but got lost in syncStep and SyncIO implementations.

[durban]

Thanks for the report! Can you tell us the versions of Cats in the two cases?

As far as I can tell, the syncStep interpreter is stack-unsafe for a long time. However, I think traverse (in Cats) used to have extra things for stack safety, but now it detects IO (or similar), and assumes they have a stack-safe flatMap. And IO#flatMap is stack-safe... if executed by the "normal" interpreter. It seems it is not, if executed by the syncStep interpreter. (So that's why I'm asking for Cats versions.)

In any case, we should fix this.

[migesok]

In this project I didn't specify the cats version explicitly so I get the one defined by cats-effect:

• for 3.6.0: sbt: org.typelevel:cats-core_2.13:2.11.0:jar
• for 3.5.7: sbt: org.typelevel:cats-core_2.13:2.9.0:jar

Is it possible to make syncStep stack-safe or is it by design?
I can try to contribute if it's straightforward to do.

[qxrein]

IO.flatMap is stack-safe only under the primary interpreter, which uses trampolining to avoid stack overflows. syncStep is a different interpreter designed for partial evaluation (for REPL or debugging). It trades stack safety for precision in chunking computations. This is why i believe traverse + syncStep combination fails syncStep does not guarantee the same level of stack safety as the main interpreter, due to its design philosophy.

[djspiewak]

I took a look at this fairly briefly and tried to page some of the context back into mind. I think this is really the root of the problem here:

val syncStepSize = 1000000

As @qxrein noted, syncStep really isn't designed to be run over so many contiguous stages. In fact, as suggested by evolution-gaming/cats-helper#330, the intended value here is autoYieldThreshold or something thereabouts. We originally looked into making this something we could plumb in for users automatically but it has some really complicated implications, since the configuration is on the IORuntime which we don't have inside of syncStep. We should probably add a note to the scaladoc suggesting users lean on that.

autoYieldThreshold by default is 1024. This btw is related to an internal configuration parameter, MaxStackDepth, which is actually a safety check that is used inside of IO's regular interpreter for deeply chained map invocations. More specifically, it is actually possible to hit stack-unsafe cases within the IO interpreter itself, where the stack depth can end up being arbitrarily deep. In such cases, the interpreter has to weigh performance (which would suggest going full steam ahead on stack-based recursion) vs safety (which would suggest carefully trampolining to allow for arbitrary depth on the heap, at the cost of several more allocations per map). In the end, the interpreter balances both: for any number of sequential maps less than 512, it uses stack-based calls; once it hits that threshold, it trampolines once (by allocating a new IO during interpretation, effectively converting map into flatMap + pure) and resets the counter.

This syncStep situation is very similar. So, I would recommend you set your size to either 512 or, at most, 1024.

[qxrein]

The IORuntime config block is a real headache - 512 or 1024 helps, but I’d rather see syncStep take a configurable threshold directly. Docs feel like a Band-Aid here.

[djspiewak]

but I’d rather see syncStep take a configurable threshold directly

I mean, it does, it just doesn't have a default.

We could add an overload which takes an IORuntime if we want to go super overkill, but we wouldn't touch most of it so I'm… skeptical. This is definitely an annoying one. I guess another alternative is we could just add a default parameter value.

[qxrein]

looks like adding a default parameter seems more functional and maintainable

[migesok]

@djspiewak @qxrein thanks a lot for explanation! Now it makes more sense to me. I don't really insist on fixing stepSync at all but it would be nice if that behaviour was documented.

[armanbilge]

In fact, as suggested by evolution-gaming/cats-helper#330, the intended value here is autoYieldThreshold or something thereabouts.

Hmm, well not necessarily. In Doobie I used Int.MaxValue when syncStepping into WeakAsync. In that case, the assumption is that the effect we are stepping into also implements auto-ceding.

https://github.com/typelevel/doobie/blob/67a44cf48b225ff3021c887133e7f9f10733e8cb/modules/free/src/main/scala/doobie/WeakAsync.scala#L60-L62

I think we should try and fix syncStep, if possible ...

[djspiewak]

It's possible. We would need to wrap in defer every n recursive interprets (probably 512). That should still be way more efficient than what traverse used to do, which was always pessimistically wrapping in Eval.

[qxrein]

In Doobie I used Int.MaxValue when syncStepping into WeakAsync. In that case, the assumption is that the effect we are stepping into also implements auto-ceding.

@armanbilge this appears to be a special case that works because - Doobie controls the execution context, it's used with database operations that naturally yield.