12 ms·
No More Callbacks: 10,000 Actors, 10,000 Threads, 10,000 Spaceships
- CookWithMe 13y agoMy first thought was "why don't they use Akka"? > Akka has no true lightweight threads (the actors are actually callbacks) Would you care to elaborate? I'm not too familiar with the internals of Akka, but they definitely don't use "heavyweight" threads (which I assume are threads that are 1:1 mapped to OS threads). Also, I didn't get "the actors are actually callbacks". Yes, there may be callbacks involved internally (why not?), but there is a big difference whether I am sending a message to an actor (which may be processed at any time) vs. calling a callback (which is immediately executed on the very same thread that I'm running on). Sorry if this sounds dismissive, but I'd really like to learn why you choose to implement your own solution, because you've obviously put some time into evaluating what is out there.
- pron 13y agoSee my reply to jaimefjorge
- hp 13y agohttps://github.com/scala/async https://github.com/scala/async is the syntactic sugar to write sequential nonblocking code in Scala (no callbacks). Though functional-style code works well also if you know it.
- pron 13y ago[cloned comment] Essentially, Quasar provides async and await for all JVM languages. async is called `Fiber.start()`, and await is called `Fiber.park`. Other than working for all JVM languages, Quasar fibers are more general in that they can spawn many functions (they have a stack), while async is limited to a single expression block. Because of this, we can hide the "await" deep inside the JDBC call stack. Under the hood, they are similar: both instrument your code. Only async does this at the language level (it's a Scala macro), while fibers do it at the bytecode level.
- jaimefjorge 13y agoWell written, good description and nice demo. Would love to see more on how this is different to (or better than) Akka. The programming model is actually close to Akka (with actor systems, supervision, receive method, message passing, etc). The article states that Akka has no true lightweight threads. The guys behind Akka have put it running with 50M messages/second[1] and perfomance vs erlang seems to be good as well [2][3]. Perhaps a benchmark would be great. Thanks for sharing. [1] http://letitcrash.com/post/20397701710/50-million-messages-per-second-on-a-single-machine http://letitcrash.com/post/20397701710/50-million-messages-p... [2] http://uberblo.gs/2011/12/scala-akka-and-erlang-actor-benchmarks http://uberblo.gs/2011/12/scala-akka-and-erlang-actor-benchm... [3] http://musings-of-an-erlang-priest.blogspot.pt/2012/07/i-only-trust-benchmarks-i-have-rigged.html http://musings-of-an-erlang-priest.blogspot.pt/2012/07/i-onl... (discussing millions of messages is a good signal IMHO).
- pron 13y agoThe main capability provided by Quasar is the fiber, or the lightweight thread. It is the same as a normal Java thread in the sense that it can block – on IO, on a DB call, or on a synchronization mechanism. This makes the programming experience very natural. The actor and the channel abstractions build upon fibers. Akka doesn't have lightweight threads at all. You implement a message-handling method, but it must not block on, say, a DB call, lest it block the entire thread it runs in. An Akka actor simply must not issue a DB call: it's as simple as that. With Quasar things are different: you pull messages rather than implement a callback; you can block: on IO, DB, lock or anything else. The programming then is not only simpler, but also more powerful. For example, Quasar supports selective receive - just like Erlang.
- saryant 13y ago> Akka doesn't have lightweight threads at all. You implement a message-handling method, but it must not block on, say, a DB call, lest it block the entire thread it runs in. An Akka actor simply must not issue a DB call: it's as simple as that. That's not quite true. Yes, you block that thread but this is why you configure actors with blocking calls to use their own dispatcher. For DB queries you typically put querying actors onto a thread-pool dispatcher where pool size ~= available DB connections. Selective receive is also quite easy to implement in Akka using stash().
- IgorPartola 13y ago> Writing correct and efficient multi-threaded code is at once necessary and extremely difficult. I do not agree with this. The original statement he is quoting says "can be very challenging". Yes, if you are designing something very state heavy and your design is somehow flawed or too complex then you can run into issues. However, in most cases threads are no more complex than callbacks, actors, etc. In fact, from what I've seen, concurrent code eventually all converges to some semblance of the actor model anyways. Where the actors/green threads/etc. really shine is having huge numbers of them. OS threads still have very large overhead compared to lighter weight green threads, so you can spin up many magnitudes more of them than you have CPU cores. Also, in lots of languages multi-core != concurrent. You can have 10,000 actors using a single core. In fact writing a scheduler that can efficiently distribute actors between different cores is probably where the complexity Doron Rajwan refers to lies.
- zurn 13y agoIt's also not generally necessary.
- chriswarbo 13y ago> However, in most cases threads are no more complex than callbacks, actors, etc. In fact, from what I've seen, concurrent code eventually all converges to some semblance of the actor model anyways. Threads are the WorseIsBetter approach to concurrency; they're incredibly simple to implement, but that just means that the difficulties are pushed on to the users (ie. developers using the framework/library). Threads may be a good idea for code which has no 'design flaws' and is not 'too complex', but as we all know everything has bugs and everything is more complex than it seems. The arguments in favour of higher-level concurrency models are basically the same as for tests and version control: if you don't use them, you're making a dangerous gamble which may cause a large price down the road. Concurrency models like callbacks and actors can make dangerous things more difficult; if we use the callback examples from the article: > It’s hard for a programmer to reason about which line of code executes on which thread, and passing information from one callback to another is cumbersome as well. Of course, this is the point of callbacks. The callback model tells us to reason using function arguments and function calls, so of course we can't map lines of code to threads, since neither lines of code or thread have any place in a callback model. Likewise for passing data between callbacks; the problem with threads is that everything is shared all of the time, which makes it incredibly difficult to enforce invariants. When using callbacks, everything is local by default and transfering data between threads requires explicit channels, eg. free variables. In the actor model the safety comes from messages having no ordering or latency guarantees, so we can't assume that our data is always up to date. With higher-level concurrency models we end up screaming at our IDEs as we try to contort our code to fit the paradigm. This is how it should be, since this means nothing's gone wrong. With low-level concurrency models, the machine gladly accepts our dangerously broken code, the number of interleavings is so huge that our tests never hit an error case (or more likely, some of the bugs are so obscure that it never occurred to us to test them). Six months later the application explodes and as we sift through the pieces we find the true extent of the problem, and discover that subtley corrupt output has permeated through every aspect of the business and we can't anything that's been done since that code went live.
- knodi 13y agoI'm not a fan of this approach. I like what Go does with channels and I like what D does with synchronized functions. Its simple and powerful and no magic. Fuck magic.
- pron 13y agoQuasar gives you channels just like Go: you can have primitive channels, you can select from several channels at once, or anything else you'd do with Go. As a bonus, it performs better than Go.
- tuxychandru 13y agoHave you published the benchmark source codes used for the comparison, anywhere? I am interested in figuring out the bottlenecks that make go perform worse.
- ChuckMcM 13y agoNice exemplar. Back when Java was being created, James Gosling was pretty insistent that concurrency be lightweight and scalable. When I ported it from SunOS 4 so Solaris 2.0 I had to move from the really light weight setjump()/longjmp() threads that he had implemented, into the thread system that Solaris had defined. There was a huge negative impact on performance (as I recall about 15x slower). That sucked because one of the coolest demos at the time had a little world in it where 'Fang' (the Java mascot) lived and a bunch of things in that world were all animated with threads. Looking at the 'fiber' model for threads I think they are much closer to what we should have done in the first place. The thought was to have a billion threads on a SPARCStation 10 (that is like an old Pentium machine now). We never got close but it was a great goal. Definitely going to have to go back and revisit this topic now. Thanks for the excellent demo to play with!
- justinsb 13y agoI also remember user-space threading in Java (where N threads would be multiplexed onto M kernel threads), although my understanding was that we moved to the 1:1 threading model because it was faster and had fewer pathological edge cases. It sounds like you're saying that it wasn't faster? Can you explain a bit more about the motivation if so? Any thoughts on whether we should have user-space threading in the JVM today? Maybe it could be implemented in RoboVM as an experiment (rather than wrestling with the JVM immediately)?
- ChuckMcM 13y agoSo the "original" move to native threads was motivated by the fact that Sun didn't want Java to be SunOS only (there were a number of SunOSism's in it when it was Oak). That the system threading system would improve independently of the language and have fewer edge cases were put forth as good reasons to do that. Initially it was slower because context switches are slower, and anything that had to context switch into and out of the kernel was thus slower. Later there were other reasons. "User level" or as I prefer "Single Context" [1] threads have the ability to be very fast because they have extra knowledge about what is going on and access to other address spaces (so you don't have to save something if you know how it's used). There has been lots of great work on this since the early 90's when this decision was made so I suspect the issue would be significantly less. [1] At the time kernel threads were 'single context' and quite fast. Fast enough to be used for interrupts. There is a great paper on the threading system in Solaris which describes them. -- http://dl.acm.org/citation.cfm?id=202217 http://dl.acm.org/citation.cfm?id=202217
- newobj 13y agoTitle: "...10,000 Threads..." Post: "...10,000 Fibers..." sigh
- rdtsc 13y agoEdit "...10,000 Actors..." Comments "...10,000 Co-routines ... " ;-)
- ericHosick 13y agoWe are working on a fully composable frame and concurrency is done as follows (upper-case = Object, lower-case = property): AsyncRun ( part SomeObject ) multiple items can run in parallel like this: AsyncRun ( part SomeObjectA SomeObjectB .. ) synchronization: AsyncSync ( part AsyncRun ( part SomeObjectA SomeObjectB .. )) locking a property: AsyncRun ( part AsyncLock ( lockName = "someName", part = SaveUser ( ... ) ) ) On main thread (for UI/UX): MainThreadRun ( part SomeObject )
- regi 13y agoInteresting. I'm attempting to do pretty much the same thing in C: http://github.com/reginaldl/librinoo http://github.com/reginaldl/librinoo
- sramsay 13y agoWell done, man. Seriously. Every time someone starts talking about how x language makes it "easy" to do some kind of backflip, I start peering over the fence. Then someone almost immediately implements it in a C library -- or indeed, gets there first. But have you given any thought to the critical and urgent problem of running 10,000 Actors, 10,000 Threads, and 10,000 Spaceships?
- regi 13y agoWe often forget that even though this common problem of replacing callbacks is getting more critical and urgent, people already thought about it and gave some solutions. Maybe not in higher level languages (although I think Go does a great job there). In C, I have in mind glibc's ucontext for example. I'm trying to improve that through rinoo. So to answer your question, if you look at the wiki section you'll see test results I've done running 20,000 Actors. Of course, once you handle "actors" correctly (which should definitely be called fiber) you shouldn't use that many Threads (if too many you'll end up spending most CPU cycles scheduling your threads). However, rinoo handles multi-threading as well. I'm currently writing doc about it.
- vendakka 13y agoLooks very nice! Does this play well with existing JVM threading support? More specifically, if there is a call to a synchronized method inside of a fiber and another JVM thread has entered the monitor, will this block the entire fiber scheduling thread? The reason I ask is I'd like something that plays well with legacy code.
- pron 13y agoA synchronized method would block the entire thread, but calls to ReentrantLock.lock, or any other java.util.concurrent class, can be turned from thread-blocking to fiber blocking.
- Morgawr 13y agoI'm going to be "that" guy and ask... why actors? Why not agents? The concept of agents (as defined by Rich Hickey in a lot of his Clojure talks) is all about a globally shared, immutable and persistent state on which you can act upon. With actors you still need to have the actor handle its own mailbox of requests and then handle them, the actor has to define its behavior. With agents you don't have to ask for the world to stop to communicate, you can read the current snapshot of the world (aka no request to view the state, no database queries) and send transformation functions on the data of that specific agent, which will be then processed by the agent's thread in an ordered way. I'd love to see more insight on the choice for this, it's interesting as I am currently working on a similar project.
- rdtsc 13y ago> I'm going to be "that" guy and ask... why actors? Why not agents? Because actor is an establish paradigm and that has been around for a while. I haven't heard Hickey's talk on "agents" but based on your description, how are agents radically different? What stops actors from reading the snapshots of the world? They can 1) subscribe to "world" actor and get publication when it changes or 2) if database is immutable (I guess you are hinting at Datomic or Clojure's datastructures here?) an actor can also call a function. Remember actors in practice are there to help isolate concurrency contexts. Reading truly immutable data is safe so actors could just periodically read this immutable data (just think of the database a function). It would be awkward having to process messages from mailbox, timing out, then reading world state, process world state, going back to processing messages. Etc. I like 1) better. > the actor has to define its behavior. How does an agent bypass defining its behavior? Doesn't an agent have a piece of code that specifies what that agent does. > and send transformation functions on the data of that specific agent, which will be then processed by the agent's thread in an ordered way. So this basically centralizes the state of all the agents in one central location that is an immutable database? Hmm interesting. It is a different way of looking it at it I guess. Each actor usually handles its own internal state privately. I guess we also assume that there is something underneath that constantly distributes all these incrementing tree of states across a whole system. I don't know I would rather think of actors explicitly choosing to send their state to a system half way across the world rather than rely on another layer of distributing state. Maybe it is just a matter of a mental model here...
- EGreg 13y agoHow does this compare with Grand Central Dispatch on the Mac?
- roryokane 13y agoI can't compare the principles by which they work, but in terms of which to choose, I think you will never have to make that decision, since GCD is only for (Objective-)C programs, while Quasar is only for the JVM.
- meowface 13y agoIs this similar to green threads / "greenlets" in Python? They look to be the same concept.
- fzzzy 13y agoOne thing required for an Actor model that is missing from greenlets and Python in general is the ability to have isolated contexts. Basically, each Actor should have its own global state and shouldn't be able to share state with any mechanism other than message passing. In Python with greenlets, state can leak between green threads through module globals and other module state.
- meowface 13y agoWell, greenlets can and do have their own isolated contexts, but you're right, they can indeed leak state. Thanks for the clarification.
- pron 13y agoI'm not too familiar with Python greenlets, but I believe they don't exploit multi-core hardware as well due to the GIL. Quasar fibers run and scale extremely well on multi-core hardware.
- fzzzy 13y agoOne can always start up multiple Python processes, though.
- pron 13y agoYou can, but communication between processes is usually more difficult than communication between threads. Sometimes you want to do more than pass messages. For example, you might want to do something as simple as increment a single counter. Sharing a counter efficiently among processes is not so easy.
- 13y ago
- perlgeek 13y ago>On my 4-core (8 virtual cores) i7 MacBook, with 10,000 spaceships, I get close to 10 simulation cycles per second. [...] > When running the simulation synchronously, i.e. with a phaser, performance drops to about 8 cycles per second on my development machine. > Performance – we are able to fully exploit the computing power of modern multi-core hardware. So, 25% faster with 8 cores is "fully exploit the computing power of modern multi-core hardware". WTF?
- wtetzner 13y agoWhen he says he's using a phaser, he means that updates happen in lockstep. Each update still happens on multiple cores, but each fiber will not move on to the next update until all of the other fibers have finished the current update. So it's not synchronous in the sense that it's running everything sequentially.
- pron 13y agoExactly. Still parallel, but don't start the next cycle until the previous one has completed.
- Morgawr 13y ago8 cores != 8x speedup
- frozenport 13y agoI think the approach is interesting but I don't understand how this considered theoretical. 10,000 elements for an N-Body problem is expected. What I am more confused about is how this considered peak optimization. Assuming they are utilizing doubles and doing both read and write I get the following computation: (10000x10x8x2 bytes per second) or 12 Megabits per second vs the theoretical bandwidth of a PCIe of 40 Gbs? Are they computationally limited and what is their memory access pattern?
- pron 13y agoThis is far from an optimal simulation, because the framework is so general. The spatial database gives you true isolated transactions that require (fiber-blocking) locks. In fact, the code is very naive, and that's our main point. Even naive code can scale well with this approach. We care more about scaling than sheer performance. So your calculation is wrong, as we're not trying to approach a theoretical limit (which would require optimizing the algorithm) but to demonstrate scaling of a naive algorithm. For example, instead of a single spatial join, each spaceship queries its surroundings: this is asymptotically (n^2 vs n) worse than a single join.
- mpweiher 13y agoAnd we nowadays have the hardware resources to run this on one CPU per spaceship, at least theoretically: http://blog.metaobject.com/2007/09/or-transistor.html http://blog.metaobject.com/2007/09/or-transistor.html Needs some interconnect, of course...
- auvrw 13y agoconcurrency --- albeit not at this scale --- is something that that you sometimes have to deal at a low level with when writing android apps. animating custom views, for example, often winds up involving direct use of Runnable s rather than (what i assume are) system-level AsyncTask s. a lot of the die-callbacks-die neatness on the java side of this relies on a coroutine library, but that library doesn't run on android. there is a continuation library that does > http://commons.apache.org/sandbox/commons-javaflow/ http://commons.apache.org/sandbox/commons-javaflow/ which could be used to create coroutines and from there user-level threads ... but if we just want some generic kind of concurrency-niceness on a java virtual machine, might it make more sense to use scala rather than write your own lightweight thread library? is the user-space thread implementation really necessary or even helpful if you're abstracting toward actors anyway? do these questions even make sense to anyone?
- pron 13y agoQuasar gives you fibers. On top of them you can build actors, Go-channels, or data flow variables. Scala gives you no advantage here. None of its concurrency constructs really require Scala. There is no reason not to implement them in Java and use them in any JVM language. More specifically, Quasar actors are more general and powerful than Scala actors because they run in true lightweight threads and can block. Also, a lot of people don't like Scala.
- dschiptsov 13y agoThe other day some guys proudly re-implemented jemalloc in pure Java - https://blog.twitter.com/2013/netty-4-at-twitter-reduced-gc-overhead https://blog.twitter.com/2013/netty-4-at-twitter-reduced-gc-... now these guys re-implemented a half of Erlang.) Isn't it better (and bitter) to face the reality and just use Erlang or Go or at least to ask oneself why should everything be stuffed into JVM in 2013?)
- pron 13y agoGo has nothing to do with it. The JVM is a superset of Go, and Go's strengths lie mostly in a short startup time. Erlang is a different matter. We love Erlang. But the JVM ecosystem is not only two or three orders of magnitude bigger, but the JVM serves other requirements as well like excellent performance (performance is not Erlang's strongest suit, and more than a few Erlang projects require C code to meet performance requirements). Some projects will be best served by Erlang, but many will benefit from Erlang's capabilities on the JVM. In short – Erlang is awesome, the JVM is awesome, extremely popular and very successful. Why not combine their strengths? We already have a full Erlang implementation for the JVM, and we think that Pulsar (Quasar's Clojure API) really brings together the best of both Erlang and Clojure. There are many technical advantages to using the JVM, too. Because it has really good low-level concurrency constructs, you can implement state-of-the-art concurrent data structures in Java. This is downright impossible in Erlang, as in all pure functional languages. This is as it should be, because these languages work at a higher level. The problem is that BEAM, Erlang's VM, operates at the same level, too, so if you want to write a concurrent DS for Erlang you'll need to do that in C. It's a lot harder than it may seem, because many of these data structures require a good GC, and the BEAM the GC can't help because it only manages process-private heaps.
- dschiptsov 13y agoI am really appreciate your drive and effort, thank you for the reply. In my opinion, however, as I could gather from the writings of mr. Armstrong, (one of) the fundamental problem with JVM is that it lacks a process isolation, and when it crashes, everything crashes completely. He explicitly pointed out this in his thesis - JVM cannot provide fault-tolerance due to being a mere user-level multi-thread process. As a person who had experience of running huge Java crapware like Business Objects I could tell that yes, it crashes and it crashes often, and when it crashes there are situations in which there is no way to preserve data integrity and plain re-installation is required. I am also not quite sure about any superior concurrency constructs which aren't based on OS primitives, but I am not Java guy. Go is a way of doing things without a VM.)
- stevefturner 13y agoI think I'm being dense... can someone explain the difference between a 'blocking' fiber and Ada's task/rendezvous constructs? Both seem like synchronous message passing mechanisms?