Cats-effect: Add basic concurrency constructs (Queue etc)

[Daenyth]

The concept here is that there are a bunch of concurrent utilities that we could have which are very, very commonly needed, but which aren't available. They should all be implemented on top of the Concurrent typeclass and in the concurrent module. Queue is an obvious one, but there are definitely others.

https://gitter.im/typelevel/cats-effect-dev?at=5f6797fb89b38d09213dd022

Utilities to add:

• [ ] Queue
• [ ] Dequeue
• [ ] PriorityQueue
• [ ] CountDownLatch
• [ ] CyclicBarrier
• [ ] ReentrantLock

[RaasAhsan]

Thoughts on Lock and ReentrantLock types? The main criticism around MVar is that it's exceptionally easy to run into a deadlock, but I think we can provide safer variant of it in the library focused on mutual exclusion. Obviously there's still room for deadlocks, but those are usually scoped at a higher semantic level. Reentrancy will also require some notion of fiber identity.

I believe @ChristopherDavenport also has a couple microlibraries that expose useful concurrent types like MapRef and KeySemaphore. He's very vocal about handing these things off to somebody else, so the question is what do we want to bring in :)

[djspiewak]

ReentrantLock is particularly tricky to get right, and there are certainly cases where it's helpful. I'd be in favor of including it, particularly since we have the ability to make it resource-safe. Also it may be interesting to see if we can devise a concept of fiber identity which is more narrowly-defined such that this can be done in a generic way.

[Avasil]

👍 for including some of Chris's microlibraries

From other suggestions, I would love to see PriorityQueue !

[Daenyth]

@RaasAhsan I'm not super familiar with those apis. When I was skimming over the java.concurrent package before, I didn't think those were priorities due to being able to use a Semaphore with size 1 as a cheap lock. Do you think there's a good level of value adding those anyway? Or did I miss a more nuanced api design than it just being lock/unlock pairs?

[RaasAhsan]

@Daenyth Oh yeah you are right, we don't really need a Lock since we have Semaphore. ReentractLock is more interesting from an implementation standpoint, but I'm not actually sure how useful it would be. Another one is RWLock, which I think may have practical use cases. I've seen people ask about that one in the Gitter channel too.

[SystemFw]

yeah Semaphore is enough for a simple lock. ReentrantLock is interesting but I don't think we can implement it, we need a concept of fiber identity. ForRWLock you can largely reuse the implementation of MVar.

[vasilmkd]

Starting work on Queue.

[TimWSpence]

I can have a go at PriorityQueue if nobody else is tackling it?

[TimWSpence]

I can have a go at Dequeue as well :) Back to Okasaki I go!

[TimWSpence]

I've picked up CountDownLatch and CyclicBarrier as well