Cats-effect: Consider providing optimized versions of `IO.sequence`

[Avasil]

Default implementations of sequence-like operations are very inefficient and I don't think there is a way to overload their definition but we could provide alternative optimized versions.

Monix does it for TraversableOnce, e.g.

def gather[A, M[X] <: TraversableOnce[X]](in: M[Task[A]])
    (implicit cbf: CanBuildFrom[M[Task[A]], A, M[A]]): Task[M[A]]

which is optimized version of parSequence. This is implementation.

There is also very simple Task.sequence. We also have unordered versions and traverse (Task.wander) equivalent.

Do you think it makes sense to introduce it in either Cats-Effect or separate library?

I have a benchmark:

[info] Benchmark                                Mode  Cnt      Score     Error  Units
[info] SequenceBenchmark.catsParSequenceIO     thrpt   20    609.564 ±  14.155  ops/s
[info] SequenceBenchmark.catsParSequenceTask   thrpt   20    447.448 ±   8.034  ops/s
[info] SequenceBenchmark.catsSequenceIO        thrpt   20   6680.011 ± 524.972  ops/s
[info] SequenceBenchmark.catsSequenceTask      thrpt   20   7474.614 ± 670.785  ops/s
[info] SequenceBenchmark.monixGatherTask       thrpt   20    994.218 ±  11.195  ops/s
[info] SequenceBenchmark.monixGatherUnordered  thrpt   20   1094.078 ±  29.580  ops/s
[info] SequenceBenchmark.monixSequenceTask     thrpt   20  18090.827 ± 285.865  ops/s

Note the difference between catsSequenceTask (default sequence from cats) and monixSequenceTask (Task.sequence)
source code

[alexandru]

Usage of TraversableOnce and CanBuildFrom will never fly in Cats-Effect, I have a feeling about it 🙂

A sequence implementation would have to use Traverse. The problem with Traverse is that it relies on folds (foldLeft) and on Applicative to work. In other words there isn't much optimization potential as long as you use Traverse, the current implementation is kind of imposed on you.

And that's why Traverse sucks compared with TraversableOnce + CanBuildFrom. But that's a holy crusade I don't want to get into.

[djspiewak]

I'm trying to decide which side of this holy crusade I fall down on. I mean, CanBuildFrom is awful, but it's the awful we have (if not the awful we deserve).