Cats-effect: Should we provide a cats.Parallel instance for IO?

[alexandru]

I know we talked about the boundaries of cats-effect and that the implementation in cats-effect should not be concerned with parallelism or race conditions.

However we now have cats.Parallel in cats-core and providing a default instance for IO makes a lot of sense.

Otherwise defining that in fs2 is difficult due to having to use a newtype (for which we don't have an agreed upon encoding) or to essentially deal with orphaned instances, which we try to avoid. So at the very least, due to Cats 1.0-RC1 having a Parallel in it, I think we should have another discussion about it.

I'm fine either way, I just think Parallel is very cool and maybe we should provide that instance.

UPDATE: for reference there's — Why not both.

UPDATE 2: PR — https://github.com/typelevel/cats-effect/pull/115

[djspiewak]

Hmm, you're correct that it is almost certainly best for us to provide this instance. I'm dubious about its value on a type without resource management, but the fact that it's in cats-core sort of short circuits that whole discussion in my eyes. I'm leaning in favor of adding this.

@mpilquist thoughts?

[alexandru]

One thought about making IO safer — our problem is that something like parMap2 (both) can leave opened resources if any of the tasks completes in error. And those opened resources can turn into a leak if the program triggers that task repeatedly, or something.

Well, given that IO cannot cancel a running task, we can say that parMap2 operations should complete only when all of the tasks complete. So between io1 and io2, if on evaluation io1 completes in error, then we wait for io2 to complete before emitting that error.

This way the program's logic can properly apply back-pressure. The only problem is if io1 completing in error will influence the result of io2 to never complete. But in such a case these IO refs are doing concurrency on the same shared state, so they aren't fit for being evaluated in parallel anyway.

[alexandru]

And we'll still not have firstCompletedOf / race operations.

[djspiewak]

Yeah I think these are good points. The fact that preemption is actually impossible with IO avoids a ton of the pathological scenarios, and strongly carrots users away from constructing arguably all of the others.

[mpilquist]

I’m generally on board. I assume this mans adding Ref from fs2. And not adding any of the async data structures. What about stuff like race, unsafeRunAsync, and other small utilities?

[djspiewak]

I have to look at Parallel more closely, but I'm pretty sure it can be done without Ref. AFACT, Ref is a strictly more powerful mechanism for parallelism.

[alexandru]

If we want to do the minimal amount of work required for Parallel and thus implement a parallel map2, then all you need is to synchronize a variable, either by means of synchronize blocks or probably even better with a j.u.c.a.AtomicReference — on top of JS it can just be a var and we can simply push platform specific code for this one.

And that variable has to be the current state of a FSM with 3 or 4 states:

• started
• left completed
• right completed
• both completed (optional, since on this state you just need to send the signal and we don't need future-like caching, but mentioned for completeness)

So we could simply use:

var state: Either[A, B] = null

And synchronize on it in a platform-specific way.

And then you just start those IOs with unsafeRunAsync and do that synchronization in the passed callbacks — ugly, but basic stuff.

[alexandru]

The only problem is that by doing the above the operation will not be stack safe, unless we make it stack safe by using some kind of ExecutionContext when calling those callbacks — an internal global and trampolined one works too.

[alexandru]

If you're interested in a proof of concept, let me know.

[SystemFw]

@alexandru you are not _that_ far away from Ref (minus the indirection through an actor)

[mpilquist]

FS2 recently got SyncRef, which is an AtomicReference backed implementation of most of the Ref API that requires only a Sync instance for F. We could define something like this in cats-effect and use it to implement the Parallel interface.

No rush necessarily, but I'd really like to have cats-effect 1.0 within a day or two of cats 1.0. We should at least decide whether such Parallel support is pre or post 1.0.

[LukaJCB]

+1 on a SyncRef backed instance for 1.0

[mpilquist]

Bumping this... I'd like to propose adding the FS2 0.10.0-M9 Ref and Promise types to cats-effect:

• Ref
• Promise

[jdegoes]

👎 on adding Promise, 👍 on adding something similar to Ref.

Promise is opinionated, heavyweight, and neither primitive nor composable (e.g. timedGet, cancellableGet — artifacts of F leaking into the interface and spreading upward).

A Promise can be defined in 1 line of code:

def promise[A]: IO[(A => IO[Unit], IO[A])] = 
  MVar.emptyMVar[A].map(v => ((a: A) => v.put(a).fork.toUnit, v.read))
...
// Silly example
for {
  p <- promise[Int]
  (set, io) = p
  _ <- set(42).fork // Do it in a different thread
  v <- io // Or for timeout version: io.timeout(1.second)
} yield v

Since this 1-line definition is so simple and since the choice for some aspects of promise behavior may vary, it's better to leave it outside the library.

Ref or something even more similar to MVar would be extremely useful. Note that having composable semantics for cancellation, interruption, and so forth (ideal properties of a Ref), would require MonadFork (or something like it) and the removal of methods like timedGet, so may be better discussed after #93 is resolved.

[SystemFw]

A few thoughts.

Promise is ... neither primitive nor composable (e.g. timedGet, cancellableGet)

This has nothing to do with Promise, an MVar would have exactly the same problems until the cats effect typeclasses get stronger (which @jdegoes does mention)

Promise is opinionated

That's undoubtedly true. Although I obviously like Promise since I made it, seeing some usage in anger would help clarify its value as an abstraction.

Imho it's better than MVar (at least in the context of fs2) since it introduces way less opportunities for blocking and risk of deadlock but I'm not opposed to MVar in principle, if it proves to be a better fit.

(I can expand on why I think Ref + Promise > MVar if required, but better to not spam the thread prematurely :) )

[jdegoes]

That's undoubtedly true. Although I obviously like Promise since I made it, seeing some usage in anger would help clarify its value as an abstraction.

What theoretical advantage does it have over this 1 line definition:

def promise[A]: IO[(A => IO[Unit], IO[A])] = 
  MVar.emptyMVar[A].map(v => ((a: A) => v.put(a).fork.toUnit, v.read))

By _theoretical_, I mean in a hypothetical future where the existing type class hierarchy has been replaced?

Why prefer 126 lines of code that conflate separate concerns, versus 1 line of code that does not?

Imho it's better than MVar (at least in the context of fs2) since it introduces way less opportunities for blocking and risk of deadlock but I'm not opposed to MVar in principle, if it proves to be a better fit.

I hate the deadlock opportunities presented by MVar (or Ref). But I am not ambitious enough to argue for removal of Ref / MVar and a fast STM. 😉

Improper use of MVar can trivially result in type-safe and non-obvious deadlock, as can most concurrency primitives (locks, semaphores, blocking queues, etc.), but it can also trivially and efficiently solve common concurrency issues.

IMO if you're going to bake something like this into cats-effect, then it's better to provide the 1 non-opinionated, composable building block with which most problems can be solved, then provide special-cased abstractions like Promise.

Note that purescript-aff needed a Promise until it adopted fork/join and got an improved MVar (called AVar). Then there was no need for it. When the building blocks have the right shape, you can assemble them to solve all the problems.

(I can expand on why I think Ref + Promise > MVar if required, but better to not spam the thread prematurely :) )

It is definitely not spam, I'd say it is the point of the thread. 😄

[SystemFw]

First point: STM is miles better than everything else :)

that conflate separate concerns

I guess this is my first point of disagreement, I feel like it's MVar that's mixing in different concerns: concurrent mutable state, and synchronisation. Otoh, this is now clearly separated: Ref handles concurrent state, Promise handles synchronisation.

if you have both Ref and MVar, there is now overlap of functionality (both can be modified, for example), so it's less orthogonal than Ref + Promise.
If instead you decide to ditch Ref and go with MVar only, you are now paying the cost of synchronisation even when you only need concurrent state (Ref.setAsync is just F.delay(lazySet) on an AtomicReference, hard to beat).
A similar point can be made with respect to constraints, we can downgrade Ref to Sync only.

non-opinionated, composable building block with which most problems can be solved, then provide special-cased abstractions like Promise.

But that's the thing, I don't think that Promise is special-cased. A single MVar is more powerful than a single Promise, but it's rarely the case that you can get away with a single MVar, and once you need to use multiple MVars, Ref + Promise can be used directly, in a more orthogonal way, to implement complex concurrent structures (we have queues, semaphores, topics and so on in fs2).

More importantly, a Promise is easier to reason about imho, it starts empty, then it becomes full and that's it. Whereas with an MVar you can go back and forth multiple times, and block either a reader or a writer in each transition.

At least in fs2, we would need both Ref in its current form _and_ a synchronisation primitive, at which point I'd rather have both be as orthogonal as possible.

When the building blocks have the right shape, you can assemble them to solve all the problems.

agreed on this one.

That being said, I don't want my disagreement to come across as too strong. When I started my work on concurrency in fs2, I wanted to indeed create an MVar, but then realised it wasn't actually needed, and we could achieve the same effect with a simpler, more orthogonal primitive.
However, I can see the argument for going with something that's more powerful for cats-effect, or (even better imho) wait and see how Ref + Promise stand the test of external usage.

[alexandru]

First point: STM is miles better than everything else :)

Just my 2 cents on this one — STM always has non-obvious performance characteristics and is less than ideal whenever throughput is something you care about.

Instead of orchestrating several variables with STM, it's always better to do it with a single atomic reference in which you wrap those 3 variables in a single state / value that gets evolved. This is because it's much easier to reason about performance or possible deadlocks or live-locks and STM does more or less the same thing anyway, but with overhead added, along with non-obvious behavior.

Basically in terms of concurrency you can't find a better primitive than AtomicReference. It is low-level, but it's honest and the more you diverge, the less generic the solution becomes.

---

Case in point — an implementation of cats.Parallel[IO, ?] is possible using a simple AtomicReference.

For performance reasons we could also use getAndSet for synchronizing our internal variable. getAndSet is optimized with platform intrinsics starting with Java 8, so it's lighter than a compareAndSet loop. This Ref implementation I'm looking at does not expose getAndSet.

---

Guess that what I'm getting at is that purely for cats.Parallel we don't necessarily need to expose any new public data types.

Personally I don't care for the internal implementation to be done in terms of "FP primitives" — I think we went beyond that in the implementation of IO itself and I don't see why the implementation of a parMap2 should be held at higher standards.

---

I do like Ref. Promise seems heavy – it can definitely be useful, but I don't feel that cats-effect is the home for it. I also don't like the name, because it's in conflict with the standard library 😀

Maybe we need a separate project for concurrency stuff built on top of the cats-effect type classes. We could have MVar there as well. I've got a pretty cool implementation in Monix, so I can contribute one.

[jdegoes]

I guess this is my first point of disagreement, I feel like it's MVar that's mixing in different concerns: concurrent mutable state, and synchronisation.

I agree. But Promise conflates interruption (a concern of IO) with retrieval (timedGet, cancellableGet). These are different concerns and should be handled at different levels in an orthogonal way.

Otoh, this is now clearly separated: Ref handles concurrent state, Promise handles synchronisation.

This is a good argument. I still do not like the conflation of concerns in Promise but these can be fixed, and the separation of concurrency from synchronization is compelling. 👍

I'll think about this more.

If instead you decide to ditch Ref and go with MVar only, you are now paying the cost of synchronisation even when you only need concurrent state (Ref.setAsync is just F.delay(lazySet) on an AtomicReference, hard to beat).

I think the orthogonality (of concurrency/synchronization) is more compelling because MVar can be implemented with a single AtomicReference. If anything, building more complex structures (such as concurrent queues) on top of an MVar (that is implemented with a single AtomicReference) may be somewhat more performant than building them on top of Promise + Ref (not that I consider this a compelling argument one way or the other, because I don't).

[SystemFw]

But Promise conflates interruption (a concern of IO) with retrieval (timedGet, cancellableGet). These are different concerns and should be handled at different levels in an orthogonal way.

Oh, I perfectly agree with this one! I find it very annoying, but it's not MVar vs Promise, it's F being not powerful enough. I would love to have an interruptible F and remove those two :)

This is a good argument.

I knew the word "orthogonal" would get to you :P

Re the performance argument: it's a good point, in fs2 I went for a balance between performance and elegance (e.g. implementing Promise on top of Ref rather than directly in terms of AtomicReference), since we were already gaining quite a lot compared to the previous Actor-based Ref (very sloppy benchmarking on my part, I will admit, but it did improve roughly by an order of magnitude)

[jdegoes]

Oh, I perfectly agree with this one! I find it very annoying, but it's not MVar vs Promise, it's F being not powerful enough. I would love to have an interruptible F and remove those two :)

Well, you know which ticket to upvote. 😆

I knew the word "orthogonal" would get to you :P

I am utterly powerless against the seductive power of orthogonality. 😉

Re the performance argument: it's a good point, in fs2 I went for a balance between performance and elegance (e.g. implementing Promise on top of Ref rather than directly in terms of AtomicReference), since we were already gaining quite a lot compared to the previous Actor-based Ref (very sloppy benchmarking on my part, I will admit, but it did improve roughly by an order of magnitude)

This is a vastly better version of Ref than the one I remember, btw — very clean. Nicely done. 👍

[jdegoes]

On further thought, 👍 to Ref or something like it (renamed, as per @alexandru's suggestion—perhaps AtomicRef or IORef), and also 👍 to a modified version of Promise without any of the timeout conflation (i.e. a _purely_ synchronization primitive).

[LukaJCB]

I believe this can be closed now :)

[alexandru]

👍 forgot to mention the issue in my PR, closing.