Severe memory consumption when using *> operator

[dmgcodevil]

I'm new to cats-effect and decided to develop a simple app which runs an infinite loop that receives events and performs some side effects. During testing I noticed that performance decreased drastically after 5 millions messages were processed. I started investigation and figured out that the problem is related to usage of *> operator.
From official documentation
the *> operator is defined in Cats and you can treat it as an alias for lh.flatMap(_ => rh)

I created to methods: one uses flatMap to chain effects and another *>

def testFast(counter: Long): IO[Unit] = {
    IO.suspend {
      if(counter == 0) IO.unit
      else IO.pure(counter).flatMap(c => IO(println(c)).flatMap(_ => testFast(c - 1)))
    }
  }

Result:
counter = 10 000 000 total time 33597 ms
Memory consumption is fine, no GS spikes, see visualVM screenshot

Ok, now the same method but flat map has replaced with *>

def testSlow(counter: Long): IO[Unit] = {
    IO.suspend {
      if(counter == 0) IO.unit
      else IO.pure(counter).flatMap(c => IO(println(c)) *> testSlow(c - 1))
    }
  }

Result:
counter = 10 000 000 total time 62128 ms
So if fa *> fb is just a syntax sugar for fa.flatMap( _ => fb) I was expecting to get the same performance but the variant with *> is 2 times slower.

After 13-14m cycles the application has frozen almost completely.

The first thing I noticed was a constantly growing heap and periodic GC spikes, see the screenshot

I created heap dump and analyzed it using MAT and here what I found:

Class Name        |    Objects | Shallow Heap |    Retained Heap
-----------------------------------------------------------------
cats.effect.IO$Map| 25,514,513 |  612,348,312 | >= 2,449,393,256
-----------------------------------------------------------------

histogram

25m Map object of a total Retained Heap = 2GB

Then using Immediate Dominator feature I found this:

Class Name                                    | Shallow Heap | Retained Heap | Percentage
------------------------------------------------------------------------------------------
cats.effect.internals.ArrayStack @ 0x6c6bba340|           32 | 3,134,640,232 |     99.93%
------------------------------------------------------------------------------------------

dominator tree

99% of total Heap is occupied by cats.effect.internals.ArrayStack

Is it a problem with *> or I'm using it wrong ?
I was looking into the source code but I failed to find a reason of such memory consumption.

Could someone assist please ?

[mpilquist]

Try using >> instead of *> -- at first read, it sounds like a case of unguarded non-tail recursion. By using >>, you'll get monadic tail recursion.

I'd also remove the IO.suspend call -- I don't see an obvious reason it needs to be there.

[djspiewak]

@mpilquist It's worth noting that I can confirm this exact same issue with, what appears to be, the same root cause. Also worth noting that fs2 itself uses *> internally in several functions, which can mean under certain circumstances that this scenario arises outside user control.

To be clear, it appears that use of *> doesn't need to be in a hot path or loop or anything intuitive to trigger this outcome. Any use of it whatsoever in an infinite bind chain (i.e. the application itself) will defeat the trampolining and cause indefinite memory retention.

[mpilquist]

👍 The existing fs2 uses should all be safe but if you see any suspect cases please let me know. OTOH, I wouldn't be against a policy of "always favor >> over *>" in fs2 since it's so easy to make this mistake.

[djspiewak]

@mpilquist From what I can tell, there are no safe uses, unfortunately. I can add/remove a *> in quasar which sequences a println that happens once at application startup, where the right hand side is effectively the rest of the application, and that alone has a massive impact on memory retention.

[SystemFw]

in fs2 I'd just go with "use >>" , and I'm wondering if it should be an FAQ in cats/cats-effect as well

[mpilquist]

Oh interesting, so that's different than the non-tail monadic recursion issue. You're saying that ioA *> ioB has the side effect of keeping ioA and ioB on heap until the ioB expression completes b/c the strictness of params results in ioB being reachable/rooted in the object graph?

Is there a potential fix in cats-effect where we somehow null out references to ioA and ioB?

[djspiewak]

@mpilquist I haven't been able to track it down to that degree of precision, but that does appear to be the issue, approximately. Here are some heap traces (pointers go "up", from subsequent lines to previous ones):

• Trace 1: https://gist.github.com/djspiewak/a3cc734eb8f98a728e9f5dfd74d26106
• Trace 2: https://gist.github.com/djspiewak/b34a68c3e172356a3aa2b739829739c5
• Trace 3: https://gist.github.com/djspiewak/418b65053b9f264df44a2b5915c0030c

Altogether, there are 184 instances of Slice on this particular heap, which cumulatively eat up almost 4 GB of space. Each Slice is retained within a Chunk.singleton, and there is no concurrency whatsoever (the queue you see well down in the trace is a synchronousNoneTerminated). So this is one Stream holding onto every value which passes through it.

The relevant thing to see here is it's all the same instance of ArrayStack, but if you trace through to the other side of the stack, you'll find distinct instances of IO$Map or IO$Bind, indicating that the stack entries are simply not being evicted, which is broadly the issue described by OP. Removing *> usage at the start of the application (before the stream which contains Slices is even created) ameliorates the issue massively, though there's still a memory leak somewhere in this code path that I haven't tracked down (possibly related to the *> usage in fs2 itself).

[djspiewak]

Also all the code involved is open-source, so I can just push a branch and reproduction instructions if you want, but it's anything but minimal. The system as a whole is extremely complex, and I haven't been able to get it to happen on anything smaller.

[dmgcodevil]

Herein some insides:

*> - allias for productR

Method chain:

def productR[A, B](fa: F[A])(fb: F[B]): F[B] =
    map2(fa, fb)((_, b) => b)

 def map2[A, B, Z](fa: F[A], fb: F[B])(f: (A, B) => Z): F[Z] =
    map(product(fa, fb))(f.tupled)

   def product[A, B](fa: F[A], fb: F[B]): F[(A, B)] =
    flatMap(fa)(a => map(fb)(b => (a, b)))

[mpilquist]

Note the following program does not leak memory:

@ def loop: IO[Unit] = IO.unit >> loop
defined function loop

@ (IO.unit *> loop).unsafeRunSync

[djspiewak]

Is this still a thing? I haven't seen this in a while, but then I've also been careful to use >>.