5 ms·
When we implemented the Go and Erlang lightweight-thread approach for the JVM in Quasar[1], we quickly realized that CSP/actors, while going a long way towards
by pron 13y ago
When we implemented the Go and Erlang lightweight-thread approach for the JVM in Quasar[1], we quickly realized that CSP/actors, while going a long way towards sane concurrency, are not sufficient. Every application eventually needs some shared mutable state (even if it's implemented at the database layer). One approach is to have a single fiber (or goroutine) in charge of managing state (Clojure does that with agents), but that doesn't scale for multiple writers. Neither does a global lock over the entire data store.
Good concurrent data structures that allow multiple concurrent writers are necessary. Java has some good basic ones like ConcurrentHashMap, ConcurrentSkipListMap, and ConcurrentLinkedQueue. Clojure takes that a step further with transactional refs. For more interesting kinds of data it's better to have a good in-memory transactional database.
So for truly "sane concurrency" you need both lightweight threads with CSP and/or actors, plus a transactional, concurrent (preferably in-memory) data store[2].
[1]: https://github.com/puniverse/quasar https://github.com/puniverse/quasar
[2]: http://blog.paralleluniverse.co/2013/10/16/spaceships2/ http://blog.paralleluniverse.co/2013/10/16/spaceships2/
- nonsequitarian 13y agoWell stated.
- wcummings 13y agoErlang has ets, which meets some of your requirements (not transactional, but mnesia is)
- saryant 13y agoIsn't this the primary use case for Clojure's agents?
- pron 13y agoNo. Like I said, agents allow a single writer at a time. Refs are more like it, but it's really hard to build a good concurrent data structure (like a B tree) efficiently with refs.
- sesm 13y agoAs far as I understand, refs are not intended for implementing data structures. Instead, they should be used to provide concurrent access to immutable data structures. So the "Clojure way" solution would be to efficiently implement an immutable B-tree and then expose a ref to it.
- pron 13y agoAn atom would do that much more efficiently that a ref. Refs are there for more complex types of mutation (like mutating more than one persistent DS transactionally). Also, B-trees are a mutable data structure. "Immutable" B-trees aren't B-trees. Clojure's own persistent DS tries are quite efficient, but not nearly as scalable as a concurrent B-Tree, which easily supports lots of concurrent writes. AFAIK, there are no persistent data-structures that efficiently scale writes.
- ehsanu1 13y agoAnd Rust has the `sync` crate which has a variety of concurrency mechanisms and primitives: http://static.rust-lang.org/doc/master/sync/index.html http://static.rust-lang.org/doc/master/sync/index.html No STM of course, but RWArc allows for multiple writers, or you can just uses Arc if immutable sharing is acceptable, or just message passing via Chan (in the standard library) if sharing data concurrently is not required. Lots of options.
- pron 13y agoBut those are just what they are - primitives, rather than data structures. RWArc allows just a single writer.
- jmgrosen 13y agoNo, RWArc definitely allows more than one writer. One writer at a time, sure, but you can have multiple tasks try to write to it at the same time and the first will get access while the others will block. EDIT: Oh, I see what you mean now; sorry, I misinterpreted. Carry on.
- ehsanu1 13y agoYou are correct, you'd use them to implement your own concurrent data structures per requirements. But I do think they're slightly higher level primitives than most languages provide, and there is some nice flexibility in the options available, in terms of control over sharing/mutability and mechanism. RWArc allows multiple writers, but each blocks until the "active" writer gives up its lock. But I suppose you mean that you can't have concurrent writes, so I understand this might not be suitable for the use-cases you were talking about.
- pron 13y agoI think the Rust people have made the right choice at every juncture given the language requirements. It's a very impressive language, but it, too, has its sweet spots. There's a reason why Java has attracted so much concurrency research in the past decade, and why it's usually years ahead of almost any other platform in that respect: no, it's not (just) the platform-agnostic memory model, which later inspired C++11's (heck, it was done by the same people), but its world-class garbage collector(s). While it's possible to implement lock-free data structures without a good GC (with RCU), it's very difficult to do so in a general enough manner while still staying efficient. Java's GC, along with its memory model and direct access to CPU concurrency primitives (CASes since Java 5 and fences since Java 8), combined with Doug Lea's inspired implementations[1], have made the JVM the premier choice for anyone who wants to take advantage of cutting-edge concurrency. [1]: http://www.youtube.com/watch?v=sq0MX3fHkro http://www.youtube.com/watch?v=sq0MX3fHkro EDIT: The Doug Lea talk linked above is probably the best overview of what doing low-level concurrency on modern hardware entails. In particular, it demonstrates interactions among abstractions layers and dispels myths that claim that having less software layers is always better (hardware already has so many layers as it is, that some software layers can actually help, if only to hide the hardware's complexity).
- axman6 13y agoSounds like you've basically explained several of the common concurrency features of Haskell. Haskell has the advantage that any pure data structure (ie, not using mutable references, which is almost all data structures we use) can be used concurrently and atomically using IORefs and atomicModifyIORef. If you need transactional guarantees, then software transactional memory (STM) is just as easy to use. For both these situations, it's laziness and purity that gives us these things essentially for free. Of course you could create more advanced concurrent mutable structures as other languages have, but IORefs and STM get you a very long way when coupled with GHC's extremely light weight threading and high performance IO (which is getting even better in GHC 7.8, to be released soon). To learn more, Simon Marlow's excellent book is available for free online [1] and in dead tree and eBook forms from O'Reilly. It's very clear, with a great balance of how to use things practically, how they work, and how to make them work their best. [1] http://chimera.labs.oreilly.com/books/1230000000929/index.html http://chimera.labs.oreilly.com/books/1230000000929/index.ht...
- tel 13y agoThere are also things like acid-state [0] if you want transactional, in-memory, and persisted data stores. [0] http://hackage.haskell.org/package/acid-state http://hackage.haskell.org/package/acid-state
- bad_user 13y agoSpeaking of the JVM, Scala has immutable data-structures. You stick one of those suckers into an AtomicReference and presto you've got a thread-safe data-structure. And for more complicated scenarios, you also have Scala-STM: http://nbronson.github.io/scala-stm/ http://nbronson.github.io/scala-stm/ Even though the concurrent data-structures in Java's library are efficient and well built, they remain error-prone because thread-safe operations are not composable. Working with immutable data-structures in a high concurrency scenario is the best thing since sliced bread. I do agree with your point - sane concurrency implies using the right abstractions for the job and there are cases in which you need shared memory storage. The JVM is in fact great because it does 1:1 multithreading, because the GC is so good that it allows you to be a little wasteful and because it provides the required concurrency primitives to build whatever abstraction on top that you desire. For Scala + the JVM, just to enumerate - you've got actors by means of Akka and it's pretty capable as it's flexible and it allows you to manipulate/coordinate entire clusters of remote actors (and of course there's Quasar that does the lightweight threads thing and I'd love a comparison between the two btw), you've got the Future/Promise concept baked in and with a sane design [2], with C#'s "async" by means of a library that will be part of the standard [3], you've got great immutable data-structures that also have parallel extensions [4], you've got RxJava/RxScala for processing streams of events reactively [5], or Iteratee IO for safe processing of data streams [6], or shared transactional memory that I mentioned above [7] and of course things inherited from Java, like NIO which in spite of its flaws it's the sanest cross-platform abstraction over native APIs for async I/O, plus as I've said, the best cross-platform concurrency primitives you can get (e.g. I still get boners every time I use ReentrantReadWriteLock). [1] http://akka.io/ http://akka.io/ [2] http://docs.scala-lang.org/overviews/core/futures.html http://docs.scala-lang.org/overviews/core/futures.html [3] https://github.com/scala/async https://github.com/scala/async [4] http://docs.scala-lang.org/overviews/parallel-collections/overview.html http://docs.scala-lang.org/overviews/parallel-collections/ov... [5] https://github.com/Netflix/RxJava https://github.com/Netflix/RxJava [6] http://www.playframework.com/documentation/2.2.x/Iteratees http://www.playframework.com/documentation/2.2.x/Iteratees [7] http://nbronson.github.io/scala-stm/ http://nbronson.github.io/scala-stm/
- pron 13y ago> ... immutable data-structures. You stick one of those suckers into an AtomicReference and presto you've got a thread-safe data-structure. Thread-safe – yes (and Clojure does this beautifully; in fact any Clojure DS is thread-safe); concurrent – not really, because you can only have one writer at a time, which simply doesn't scale for large data structures. > I'd love a comparison between the two btw Quasar has true lightweight threads (M:N multithreading as in Go or Erlang), and an (optional) actor system built on top. Quasar actors can and should block as much as you want, have selective receive (just like Erlang), and are especially easy to use. Also, Quasar has Java and Clojure APIs that feel natural and idiomatic in both languages.
- swah 13y agoI remember reading some criticism about the STM: https://groups.google.com/forum/#!topic/clojure/XHqWLMcsH-c https://groups.google.com/forum/#!topic/clojure/XHqWLMcsH-c I wonder if nowadays people can generally use it without never having to think about locks?