10 ms·
The future of M:N threading
- notacoward 13y agoM:N threading has been a great idea in theory for at least twenty years, but during that whole time actually implementing it has always ended in tears. The unexpected blocking in I/O or page faults etc. always trips it up. That's why it works great for HPC, not so much elsewhere. There's far more "bang for the buck" in making 1:1 threading work better.
- burntsushi 13y agoI'm under the impression that M:N threading has been implemented in Haskell, Erlang and Go. I think it's been reasonably successful in all three.
- pcwalton 13y agoFrom what I've heard Go is considering moving to this 1:1 model as well, at least on Linux. This is the reason for the Linux patches mentioned in the thread.
- cespare 13y agoDo you have a source for that?
- fmstephe 13y agoCan you post a link to some discussion around this? A google didn't turn up anything obvious. Thanks.
- dbaupp 13y agoIt's hinted at in the video linked in the email[1]: > Over the past year we've been looking at how a uniform, performant, synchronous programming model can be implemented across all of Google's core languages (C++, Java, Go, Python), while maintaining compatibility with existing code. https://www.youtube.com/watch?v=KXuZi9aeGTw https://www.youtube.com/watch?v=KXuZi9aeGTw
- notacoward 13y agoIf you have direct language support, the runtime can either anticipate blocking ops and make sure there are enough other threads still running, or detect that an execution thread has already blocked (from a supervisor thread) and spawn a new one. How well that works depends on what you're doing. Computation is the trivial case. Network stuff is almost as good, because sockets are pretty good about not blocking when you've asked them not to. Filesystems aren't quite as good, so you have to use AIO and other tricks. Page faults are worst of all. Then you have to deal with NUMA scheduling issues yourself because the OS can no longer do it for you, and so on. So yeah, if you have a really good runtime you can see some significant gains on some systems and workloads. More often you'll get very modest gains, and you'll have some extremely subtle bugs that cause a precipitous drop in performance e.g. when you start paging. That's "ending in tears" for the poor schlep who has to debug that stuff. It can be done but, as I said, it's not the best bang for the buck.
- asdasf 13y ago>M:N threading has been a great idea in theory for at least twenty years, but during that whole time actually implementing it has always ended in tears. Not always: http://www.haskell.org/ghc/ http://www.haskell.org/ghc/
- masklinn 13y agoOr http://erlang.org http://erlang.org
- saosebastiao 13y agoI'm not sure I understand. Are you saying that a 1:1 threading model without preemption will be more performant than an M:N threading model without preemption? How would this affect the performance of applications that spin up thousands of tasks?
- limsup 13y agoIf you restrict yourself to 64 bit systems, you can essentially go back to using OS threads with blocking I/O because the address space is so large. You can fit thousands of 2MB call stacks into the processes address space and rely on the OS and MMU to manage the memory. The problem that created the whole non-blocking, async domain was the memory needed for the thread's call stacks. You don't have enough address space to place a bunch of 2MB call stacks for each thread, if you're handling tens of thousands of connections.
- masklinn 13y ago> The problem that created the whole non-blocking, async domain was the memory needed for the thread's call stacks. You don't have enough address space to place a bunch of 2MB call stacks for each thread, if you're handling tens of thousands of connections. c10k is (almost) 15 years old, updating it for today are the OS and MMU going to manage 10 million threads and stacks for that many connections?
- rdtsc 13y ago2MB call stacks? Mine are 10MB: $ ulimit -s $ 10240 I can only spawn 200 threads in the worst case and keep them active before system starts swapping. Yes memory space is large by anytime those have to run they'd have to be brought up into the working set. EDIT: nevermind, _wmd pointed out that stack memory is still virtual and it only be brought into the physical memory as needed.
- MrBuddyCasino 13y agoNow I'm confused. This comment says that the stack memory is not allocated by the OS unless actually needed: https://news.ycombinator.com/item?id=6728030 https://news.ycombinator.com/item?id=6728030 Is this not true?
- kibwen 13y agoBackground: The author of this proposal, Daniel Micay (a.k.a. strcat, a.k.a. thestinger), is the most prolific volunteer contributor to the Rust compiler [1], and is fairly obsessed with eliminating design hazards that could lead to Rust not being competitive with C++ in terms of performance. For example, he was the driving force behind Rust's recent widespread switch from internal iterators to external iterators, and wrote most of the external iterator libraries himself. [1] https://github.com/mozilla/rust/graphs/contributors https://github.com/mozilla/rust/graphs/contributors EDIT: To whoever removed the [Rust-dev] annotation from the title of this submission, please put it back. It adds valuable context, and it's in the title of the page itself, so you're violating HN's naming policy by removing it.
- web007 13y agoThe annotation is critically important. Seeing a link to [mozilla.org] with talk about threading, I assumed it was something to do with Firefox (which I care about) versus Rust (which I don't).
- saosebastiao 13y agoBut the M:N system is already written, and it seems as though it works extremely well. In fact, it is one of the things I like most about the language, and one of the reasons why I prefer it over C++ (as well as D and Nimrod for that matter). This decision probably puts it closer to C++, but I can't see how that is a good thing.
- pcwalton 13y agoNote that this is not a decision; it's not by a core team member.
- jmount 13y agoI can't find the reference, but I remember a grand old rant that threads only progressed so far because Solaris at the time had an very costly process-fork cost compared to other Unices and Windows.
- zokier 13y agoProcess spawning has been (and still is!) quite expensive on Windows, I've always associated the push for threads with that, ie being kludge for crappy kernels :)
- dbaupp 13y agoWhat about shared memory?
- jmount 13y agoTrue: forks have very different semantics than threads. Just thought the thread architecture would be less complicated if divisions of responsibilities were different.
- arielweisberg 13y ago100k+ concurrent threads is a realistic starting point for M:N threading. As long as native threads require a separate preallocated stack that never shrinks there will always be a mismatch compared to the capabilities you get running thread per core event based code. Making M:N threads a first class POSIX feature is a good starting point as long as it also allows you to express the intended locality of groups of threads. Locality isn't optional anymore. The slowdowns he reports also map to scale up issues you see when you don't think about keeping frequently accessed mutable data local and shared nothing to an OS thread. M:N threads are just an abstraction around a stack and registers that frees you from having to bind up a bunch of related state into a series of objects and maps. It's awesome, I want it, but nothing is quite there yet. At least not if you want something like Java or C/C++ performance. Work stealing across cores is really nice, but I am not sure it is always the behavior you want. A programmer can tell when migrating a task across cores is going to hurt more than waiting a little longer to get to it. I also think any discussion of M:N threads or multi-threading is also incomplete if it doesn't also include garbage collection as a means of passing data between threads. Right now we have languages that are garbage collected and treat native memory as a second class citizen and non-GC languages that make multi-threading a headache. GC is great for multi-threading, but not so great for hundreds of gigabytes of variable lifetime objects. Even if the GC can handle it, GC still has unacceptable 2x space overhead. I don't want much :-) The youtube video doesn't load for me :-(
- viraptor 13y agoWith the nice tuning and code standards you don't need the gigabytes of variable lifetime objects. Of course the whole environment needs to be available in the right way, but for example it's not uncommon in erlang to see thousands of processes that have the memory size adjusted enough to never GC and finish quickly. Then you collect the whole process, rather than separate objects. Immutability also helps here. Not many languages can afford doing that and of course there may be lots of features that prevent similar behaviour.
- rdtsc 13y agoIn Erlang GC is boringly easy. It has separate heaps for processes and processes are isolated. The price to pay is copying some data between processes and handling immutability. But boring is good. They manage a pauseless and concurrent GC without a sweat.
- bch 13y agoSome jump points for the interested on historical implementations other M:N projects (I remember this specifically for the case of NetBSDs work in this area): http://en.wikipedia.org/wiki/Scheduler_activations http://en.wikipedia.org/wiki/Scheduler_activations http://web.mit.edu/nathanw/www/usenix/freenix-sa/freenix-sa.html http://web.mit.edu/nathanw/www/usenix/freenix-sa/freenix-sa....
- brassybadger 13y agoInteresting analogy: Erlang implements an M:N scheduling model, where it starts an OS thread for each CPU core (by default), and (preemptively) schedules its own lightweight processes on top of these threads. However, unlike OS threads, these are very lightweight: when they are created, they only need a few hundred bytes. Erlangers have been using the one process per request model for a very long time, and Erlang applications achieve massive concurrency via this. To me it seems it is possible to do M:N right, but you need more abstraction and a different design. M:N seems to work well in Erlang-like cases (very lightweight processes on top of a kernel threads).
- stormbrew 13y agoThis is what Rust was doing, more or less, before they removed segmented stacks.
- eeperson 13y agoIf you have 1:1 threads in a language, can't you implement M:N threading as a library? Looking at projects like Akka[1] makes me think this is the case. Is there reason this can't be done that I am missing? Why would you want M:N threads baked in to the runtime? [1] http://akka.io/ http://akka.io/
- arielweisberg 13y agoThose are usually leaky abstractions that don't allow you to do blocking operations with the idiomatic APIs and libraries of the language. You have to use the wrappers provided by the threading library which are typically incomplete and prevent you from using standard tools.
- brassybadger 13y agoI have no experience with Akka, but what you write makes sense. Even Clojure concurrency primitives feel weird sometimes when one wants to mix them with low-level Java libraries. Another option is to do it at the language level - see my comment on Erlang.
- eeperson 13y agoAren't blocking operations also a problem if M:N threads are baked in to the runtime? If all of the idomatic APIs are using non-blocking IO then would there still be a problem?
- arielweisberg 13y agoWhen M:N threads are truly baked in (either at the runtime level or the OS) blocking an M thread doesn't block the underlying N thread. An example would be Erlang which is a runtime built from the ground up to support lightweight threads where reading or writing to a socket of using the built in APIs won't block the underlying OS thread. You can still sabotage the runtime by writing your own native library and doing blocking operations from there, but the pitfalls are more obvious in that scenario. If the underlying concurrency and network/disk IO primitives are truly non-blocking for lightweight threads then everything built on top of them will also be non-blocking. Non-blocking for the underlying OS thread that is. That is where co-routines and other co-routine like libraries are a leaky abstraction. If you step into one of those blocking APIs in a third party or standard library you will block the underlying OS thread. This means you can't integrate with existing code or tools easily and you are always vulnerable to accidentally doing so.
- halayli 13y agoLthread (http://github.com/halayli/lthread http://github.com/halayli/lthread) is basically an M:N threading model. You can run an lthread scheduler per core.
- dbaupp 13y agoHow is this relevant? The post is about the problems with M:N threading models, and why they aren't a good fit for Rust.
- skybrian 13y agoIf you're interested in this area you might like this talk from the Linux plumbers' conference: "Over the past year we've been looking at how a uniform, performant, synchronous programming model can be implemented across all of Google's core languages (C++, Java, Go, Python), while maintaining compatibility with existing code." https://www.youtube.com/watch?v=KXuZi9aeGTw https://www.youtube.com/watch?v=KXuZi9aeGTw
- steven2012 13y agoIf I remember correctly, this was the threading model used by Solaris. I'm sure there are many applications that make use of M:N threading, but for the server I worked on (~3000 concurrent connections and 50+ threads), this actually hindered the multi-tasking performance of the server. I remember investigating and figuring out this was the reason, and switching back to 1:1 made the performance increase.
- MichaelGG 13y agoThe note about Windows User-Mode Scheduling is really neat - it makes mmap much more usable when you can switch out on a page fault. Is there such a thing available for Linux?
- onedognight 13y agoThere is no User-Mode scheduling in the Linux Kernel to my knowledge, but the video[1] mentioned the post describes Linux patches that add support for it. [1] https://www.youtube.com/watch?v=KXuZi9aeGTw https://www.youtube.com/watch?v=KXuZi9aeGTw
- MichaelGG 13y agoShame. mmap is so handy, but blocking on page faults makes it annoying to work with.
- deweerdt 13y ago> Rust's tasks are often called lightweight but at least on Linux the only optimization is the lack of preemption. I'm surprised by this, I would have expected that voluntary preemption saves you from having to save the FP registers as well. Is the absence of the optimization a non-x86 thing?
- deweerdt 13y ago> Rust's tasks are often called lightweight but at least on Linux the only optimization is the lack of preemption. I'm surprised by this, I would have expected that voluntary preemption saves you from having to save the FP registers as well. Is the absence of the optimization a non-x86 thing?