unorderedTraverse throws a Stackoverflow Error

[g-jozsef]

Hi, I created a reproducible snippet to cause a stackoverflow with an unorderedTraverse (please note this a toy example but reproduces an issue I have with a custom type)

import cats.syntax.all._
val m: Map[Int, Int] = (1 to 500).map(x => x -> x).toMap
println("testing Option monad")
val works = m.unorderedTraverse(x => x.some)
println(works)
println("testing tuple")
val stackOverflow = m.unorderedTraverse(x => (x, x))
println(stackOverflow)

this prints

testing Option monad
Some(HashMap(69 -> 69, 101 -> 101, 479 .....
testing tuple

then throws a Stackoverflow error (please note, if you are using Scastie to test it it'll just hang instead of throwing an error)

Used versions:
scala 2.13.11
cats: 2.9.0

I noticed that bumping it from 2.6.1 to 2.7.0 causes the stackoverflow error (2.6.1 works even with bigger maps, 2.7.0 starts throwing a stackoverflow)

on discord I was pointed to this PR as a possible culprit: https://github.com/typelevel/cats/pull/3960/files#diff-ae2886c56207543c424a468a43f0ad91e61e7d2aa4117d05951bdd56830f6a5bR659 since that PR is mentioned in the release notes for 2.7.0

[johnynek]

I don't see how that PR can do it, but maybe. The code you are running is here I think:

cats/core/src/main/scala/cats/instances/map.scala

Line 42 in 9ad3aa5

def unorderedTraverse[G[_], A, B](

and that code is just not stack safe.

To make it stack safe, we could need to have a similar tree style approach as the PR you linked.

Or, and I think this is simpler, internal to the unorderedTraverse for Map just call .toList on the Map, do the traverse there, then call .toMap. If you are converting toList however, I imagine converting to Vector and using traverseViaChain then converting to Map will be more efficient?

cats/core/src/main/scala/cats/data/Chain.scala

Line 995 in 9ad3aa5

def traverseViaChain[G[_], A, B](

[johnynek]

we should definitely add this test though, and while we are at it see if there are other UnorderedTraverse instances that may also have an issue.

[g-jozsef]

I think the key takeaway here is that it was stack safe in 2.6.1 and I think this was an unexpected side effect of 2.7.0

[johnynek]

I think we should do a git bisect to find the issue. There were a lot of changes. I don't see how the code you linked is even in the call graph of this example (it may be, I just don't see how).

Also, the current code is not stack safe which you can clearly see (it builds up a linear depth computation).

It is interesting that the difference seems to be with Tuple2 applicative though, and it works here with Option.

Lastly, I'd note that 500 is pretty low to be causing stack overflows. I wonder if the Option example works with say 10000?

[g-jozsef]

Tested it with 10000:
val m: Map[Int, Int] = (1 to 10000).map(x => x -> x).toMap
it constructed the map and Scastie hangs after testing Option monad

[TonioGela]

I don't see how that PR can do it, but maybe. The code you are running is here I think:

cats/core/src/main/scala/cats/instances/map.scala

Line 42 in 9ad3aa5

def unorderedTraverse[G[_], A, B](

and that code is just not stack safe.

To make it stack safe, we could need to have a similar tree style approach as the PR you linked.

Or, and I think this is simpler, internal to the unorderedTraverse for Map just call .toList on the Map, do the traverse there, then call .toMap. If you are converting toList however, I imagine converting to Vector and using traverseViaChain then converting to Map will be more efficient?

cats/core/src/main/scala/cats/data/Chain.scala

Line 995 in 9ad3aa5

def traverseViaChain[G[_], A, B](

I might take a look at it. Writing tests to check for SO should be easy.