▲ 147 points
back
62 comments
I was massively surprised a few years ago how efficient Linux thread context switching could be.
I designed and implemented a dynamic scheduler for a streaming dataflow language a few years ago [1]. We wanted a runtime system which could have hundreds of OS-level threads execute thousands of dataflow operators that communicate in a dataflow manner. Threads should not be statically assigned portions of the dataflow graph so that we could elastically add or remove OS-level threads based on observed performance.
We compared that scheduler to some other options, including just giving every operator in the graph its own dedicated thread. One test application was a simple 1,000 operator pipeline. We used two machines, one with 176 cores, the other 184 cores. To my surprise, with the pipeline application, the dedicated thread model beat my fancy scheduler in raw performance by up to a factor of 2. Keep in mind that that's 1,000 threads, all doing work, on machines with only 176 and 184 cores.
Of course, you would not want to do this in practice, even though the raw performance was so high: the machine was so massively oversubscribed during such experiments that it could barely keep up with a simple interactive shell.
But, my intuition had been wrong: I had thought that surely having 10x the number of threads as cores would mean the overall performance would crawl because of context switching time. It did not. See section 5.1 of my paper below for the experiment.
[1] Low-Synchronization, Mostly Lock-Free, Elastic Scheduling for Streaming Runtimes, PLDI 2017, https://www.scott-a-s.com/files/pldi2017_lf_elastic_scheduli...
This matches my experience: Linux is very good at maximizing throughput, even when significantly over-subscribed.
Two broad gotchas:
- If the "task workflow" of an application involves a pipeline of N threads performing logically connected operations in sequence, the direct and indirect cost of N context switches is going to put a lower bound on latency and resource consumption for each task. This gets worse if the N threads aren't all in the same process, and TLB flushes enter the picture.
- Without careful priority tuning, at high levels of over-subscription, latency becomes highly variable, as you saw in an interactive shell. There's no free lunch; if you want predictable latency you need to reserve cycles that would otherwise be available to maximize throughput.
If you assign maximum niceness to worker threads, and minimum niceness to all threads that deal with your shell (i.e. bash or ssh etc) does it improve the predictability of latency? A couple years ago I tried to do something like this really quick, but wasn't able to get good latency. I'm wondering if it's possible if you do it right.
These days, niceness is considered not adequate for this kind of thing ... you should get better results if you put all the worker threads in one cgroup, and your ssh/shell in another cgroup, with the cpu group scheduler enabled, and this should keep fairness for your interactive shell.
> Without careful priority tuning
Which might be as simple as marking the throughput tasks as SCHED_BATCH. It'll make their latency even worse but preserve throughput, give priority to the shell and reduce context switches on an oversubscribed system even further.
Or you could use taskset/cgroups to reserve 1 hyperthread for interactive things.
Similarly, Microsoft is advising that Fibers and User-Mode Scheduling are not actually very useful anymore. https://devblogs.microsoft.com/oldnewthing/20191011-00/?p=10...
Combine this with Linus's recent rant about how avoiding the kernel during thread synchronization is counter-productive leads me to think that threads + a synchronized queue built with a mutex and a condition variable is simply the simplest and most effective way to go wide.
Windows fibers and the fibers Gor Nishanov rants about as being bad in C++ have very little to do with user-mode threads in managed runtimes like Java or Go despite sharing superficial similarities. In particular, a managed runtime knows exactly how code uses the stack and understands its representation, and Java does not have pointers into the stack. This means that stacks can be moved and resized very, very cheaply. The constraints and capabilities that matter the most simply don't transfer from one language or environment to another.
> threads + a synchronized queue built with a mutex and a condition variable is simply the simplest and most effective way to go wide.
Implementing an efficient synchronized queue is relatively hard. OSes already have many cross-thread queues in their user-facing APIs.
On Linux I usually use mq_send / mq_receive, on Windows PostThreadMessage/GetMessage, SubmitThreadpoolWork, or PostQueuedCompletionStatus/GetQueuedCompletionStatus. On iOS and OSX there’s grand central dispatch.
Anyone know where I can read up on implementing something better than something like http://www.davidespataro.it/modern-c-concurrency-synchronizi... without running into the kernel scheduling problems Linus ranted about?
Besides the issues like how the return values of size() and empty() can be invalidated before the functions return. And, how it would be nice to have some better support for move semantics in there.
Do you have a link to Linus’s post? Would be much appreciated.
Actually your example is not that oversubscribed.
I've seen a couple of big production webservers which are running a threadpool of 1000 threads on < 100 cores. And they perform by far not as bad as all the new hype around async IO tells us.
One key here is however that those threads typically all run very independent workloads. If there would be a massive amount of synchronization between those threads or lots of context-switching due to message passing between them it would likely be worse.
In my experiment, every thread communicated with two other threads through lock-free queues, and each thread’s work depended on receiving that work form another thread. In other words, the threads were very dependent on each other, and they all had lots of work.
There was a blog post that showed up on HN yesterday by the Materialize folks[0]. They found that it was more efficient to have a single thread managing all the dataflow operations for a graph than to distribute operators across multiple cores.
Broadly, the cost of moving data between cores is much higher than the throughput achieved by caching warmup effects of dedicating cores to single operators.
While I have lazily not looked at the paper, is there a possibility that the control scheme happened to be faster because closely-related threads landed on cores together?
> They found that it was more efficient to have a single thread managing all the dataflow operations for a graph than to distribute operators across multiple cores.
That's going to depend on operator cost. Since we target general stream computing, our operator costs vary widely - operators can be as cheap as a simple filter, to as expensive as speech-to-text. We also had follow-up work [1] which tried to dynamically figure out which sections of the graph are best handled by a single thread.
> While I have lazily not looked at the paper, is there a possibility that the control scheme happened to be faster because closely-related threads landed on cores together?
Certainly possible, but I doubt that's the case. I'm more inclined to believe it could be because they landed on cores which share the same NUMA node - which, if that's the case, then kudos to the Linux kernel scheduler for detecting and acting on such affinity. Because even if it happens sometimes by accident, if it happened enough to make such a consistent difference in performance, it would almost certainly have to be a policy. But we did not dig into if there was any core or NUMA node affinity helping out the over-subscription case.
[1] Automating Multi-level Performance Elastic Components for IBM Streams, Middleware 2019, https://www.scott-a-s.com/files/middleware2019_multi_elastic...
edit after reading the Materialize blog post: Our system benefits from the same fusion optimization where operators can be executed in the same process, in the same thread, as simple functions calls. Our language allows developers to easily control the threading model of different sections of their application, as well as just letting the system try to find the best one.
> machines with only 176 and 184 cores
I chuckled, this seems like a massive number of cores to me. :)
This seems to be a response to Google's switchto work in the Linux kernel, which is motivated by task-switching costs, as per this 2013 LPC presentation: http://pdxplumbers.osuosl.org/2013/ocw//system/presentations...
Note the parenthetical in the article: "And that is how user-mode threads help: they increase L by orders of magnitude with potentially millions of user-mode threads instead of the meager thousands the OS can support (but don’t expect a 1000x increase in capacity; we’ve neglected computation costs and are bound to hit bottlenecks in the auxiliary services.)"
This is something I'd like to see more of a focus on. For the generator use case, I can easily see how the kernel thread spawn operation is the bottleneck. But for the thread-per-connection server use case, I'm not sure how expensive this cost is relative to all the other work that the thread does. My suspicion is that Amdahl's Law is going to quickly rear its head here. Take stack size for example: assuming the kernel stack is 10kB, if your thread itself uses 10kB of stack, you've cut the theoretical memory advantage of M:N down from the cited 1000x to a mere 2x…
> This seems to be a response to Google's switchto work in the Linux kernel
Actually, it's a response to a discussion where somebody asked, "isn't it all about context-switch cost?" But user-scheduled kernel thread is something we had in mind when designing Loom, and we've made sure we can be compatible with them. We've introduced the concept of a pluggable custom scheduler, and that could be used for kernel threads just as it's used for virtual threads. The user can choose a thread implementation -- all kernel, all user-mode, or part kernel/part usermode -- without changing any code. It's all an implementation detail.
> My suspicion is that Amdahl's Law is going to quickly rear its head here.
That depends. Amdahl's law is about accelerating one job by parallelising it, while here we're more concerned with Little's law, which is about the rate of independent requests you can process.
> Take stack size for example: assuming the kernel stack is 10kB, if your thread itself uses 10kB of stack, you've cut the theoretical memory advantage of M:N down from the cited 1000x to a mere 2x…
Ah, except that's not so easy to do. It's very hard to have "tight" stacks that are managed by the kernel for the reasons I mentioned here: https://news.ycombinator.com/item?id=24082951
> Amdahl's law is about accelerating one job by parallelising it,
Amdahl's law is about the limitations of improving the speed of something, but not necessarily through parallelization. Its main point is that if you have some overall task, and you then speed up some subtask within it, the improvement to the overall time is limited to the contribution from the subtask.
In context of pcwalton's comment, I think they meant that thread creation time may be tiny compared to the amount of time a newly created thread will do work in a server context. If that is the case, improving the thread creation time will have limited benefit to serve time.
> Amdahl's law is about the limitations of improving the speed of something, but not necessarily through parallelization.
Right, but the goal here is not to improve the speed of something, but rather to handle as many different, mostly independent somethings as possible, without necessarily improving their speed (latency), at all. Amdahl's law comes into effect in the delta between mostly and completely.
> they meant that thread creation time may be tiny compared to the amount of time a newly created thread will do work in a server context. If that is the case, improving the thread creation time will have limited benefit to serve time.
Right, this is the same argument as for the context-switch overhead. Still, I have to say that both virtual thread creation and context-switching are much better than for OS thread, but the point of the post was to show that in many common use cases that is not where most of the benefit comes from; rather it comes from the number of threads you can have.
For example, if thread creation time was high but you could create millions of them, you could create all of them up front and pool them and still get most/all of the benefits. But if thread creation time was low but you could only have a few thousand, then you'd still lose big because of Little's law.
> But for the thread-per-connection server use case, I'm not sure how expensive this cost is relative to all the other work that the thread does
The answer for the basic thread-per-connection servers you are referring to is pretty easy: It does not matter at all, since servers use thread-pools and allocate the treads only once. Any reuse of threads is free, and the cost is purely context-switching.
The story might be a bit different if servers also start multiple sub-tasks (or child-threads) while processing a request. E.g. if you are running a HTTP/2 as a protocol, you will need multiple tasks just to handle the individual streams on the TCP connection, plus 1 or 2 tasks that perform the shared connection operations. In that case you might not want to spawn a thread (or allocate one from a thread-pool) for each item, but either have a lightweight thread alternative or go back to the old very basic eventloop model. Let's say you want to handle 1k TCP connections - which is in the medium range for public server. Having a thread-pool of size 1k is OK. But now if each of those connections could carry 100 concurrent requests (which is kind of a default limit for HTTP/2), you already get a huge amount of concurrency.
The article explains that the primary benefit of user-mode green-thread fibers is not switching speed, but that they are much cheaper than OS threads, so you can have many more of them. The costs are paid in memory usage and also the operating system also has to do considerable bookkeeping for threads.
However, Netty has offered strong support for callback style IO under the JVM for a long time. This effectively allows the same efficiencies. Of course it is also possible to do without Netty. Therefore the real advantage of Loom user-mode threads and co-routines is syntactical programming convenience. That's the real innovation in Loom!
> Therefore the real advantage of Loom user-mode threads and co-routines is syntactical programming convenience. That's the real innovation in Loom!
It's an interesting alternative to Async-Await / Haskell Monads / F# workflows for sure; and a better fit for Java. But I think some credit is also due for languages like C#, F# and Haskell for providing some healthy competition and prior art in this area.
The relevant prior art is in Scheme (and OCaml, a bit), Erlang and Go, and we do credit them where relevant. Nevertheless, there are a few innovations in Java, both in implementation and design. For example, Java allows you to provide a custom scheduler for virtual threads.
I am very impressed with the recent changes happening to Java, all of which seem very carefully thought out and planned, keep up the good work!
Netty approach should be inferior because of the followings:
It doesn't have access to the JVM profiling and semantics It doesn't yet use io uring unlike loom (but there is an active gsoc that should fill this gap) It doesn't use restartable sequences unlike loom.
I expect Netty to support Loom instead of their current mechanism, when it becomes available. The thing I wait the most is keeping the standard jdbc API but making it seamlessly truly asynchronous/non socket blocking, that would actually allow Java frameworks to win the TechEmpower benchmarck
I thought the memory cost of threads was more of a JVM thing (default 1mb stack) than an OS thing (pages that aren't mapped/resident don't cost much).
What's the cost to the kernel besides a few structs?
Once a page is committed, it cannot be uncommitted until the thread dies, because the OS can't be sure how much of the stack is actually used. It cannot even assume that only addresses above sp are used. Also, the granularity is that of a page, which could be significantly larger than a whole stack of some small, "shallow" thread, and we want lots of small threads.
> the OS can't be sure how much of the stack is actually used. It cannot even assume that only addresses above sp are used
A nitpick, and a possible optimization opportunity.
If there are any unmasked signal handlers not using SA_ONSTACK, the OS can reasonably assume the thread doesn't care about memory below sp - redzone (redzone is 128 bytes on AMD64) and therefore there would be no harm in reclaiming it.
How many parked "fibers" do you think a 32-bit JVM might be able to handle once loom is ready for prime time? A thousand? A million? Somewhere in between?
Well, there is a cap on the number of PIDs you can have going, I think. Also, it is my understanding that thread switching causes TLB flushes, which can be expensive. You can also fit several stackless thread contexts within a single page, depending on the size of the context, whereas you'll certainly never get more than one stackful thread into a single page.
The word performance is a bit misleading here. A key reason to use co-routines is not necessarily maxing out CPUs but IO. Non-blocking IO and co-routines allow handling many connections on very modest hardware. Blocking IO and languages that don't handle concurrency very well (scripting languages like ruby or python) deal with this by forking multiple processes, each of which typically can only do one thing at the time. Java historically worked around this by using threads.
Using processes doesn't scale nearly as well and you typically run out of memory before you run out of CPU this way. Using threads like Java does scales a bit better but there are only so many threads you can juggle. Co-routines or green threads combined with non blocking IO is much better and is also becoming common on the JVM where pretty much most modern frameworks support this. And of course if you use Kotlin, co-routines provide a really solid implementation and programming model for this.
This is also the reason for the popularity of go and node.js, which aren't known for their particular ability to get the last bit of performance out of CPUs but do scale rather nicely when it comes to handling non blocking IO asynchronously.
> Co-routines or green threads combined with non blocking IO is much better and is also becoming common on the JVM where pretty much most modern frameworks support this.
Appreciate the insightful comment.
Basically, the ideal utilization of compute resource (cpu and ram) is engineering for both async I/O and and maximizing cpu threads, correct?
I agree, mostly.
I can't say I am very confident in understanding / implementing concurrent threading in any language. I am working on trying to get it, but sometimes I don't know if it is worth the mental over head or the added code complexity.
Single threaded async alone took me a while to grasp, and I am sure I still have gaps in my knowledge. But mentally modeling a single threaded execution is trivial.
I guess I try maximize for my own understanding and efficiency versus maximizing for performance.
This is the first time I've heard of the .java TLD, but sadly only Oracle and its affiliates are allowed to register domains[0].
[0]: https://www.oracle.com/a/ocom/docs/registration-policy-java-...
See also this thread from 2 days ago on Sub-10 ms Latency in Java: Concurrent GC with Green Threads. There's some discussion of Project Loom there.
I wonder if kernel aware green threads will obscolete conventional green threads such as in Loom.
https://www.phoronix.com/scan.php?page=news_item&px=Google-U...
User-scheduled kernel threads mostly address the context-switch question (and, more generally, the choice of an appropriate scheduling algorithm), but don't help as much with the footprint, and so with the level of concurrency, L, and that's where the biggest win is. To do that requires a deeper knowledge of how the language makes use of the stack than the OS can do. Still, they have their uses, too, and the expectation is that when they arrive, Java will support them, too, as a third implementation of threads.
To do that requires a deeper knowledge of how the language makes use of the stack than the OS can do.
I often hear that argument but isn't the reverse argument also true?
While the JVM has access to information and language semantics useful for threading, that the kernel doesn't have access to.
Doesn't the kernel have access to useful information for threading that the JVM green threads doesn't have access to?
The one information that come to my mind is being aware of all threads from all programs and not only the ones from the JVM.
So could next generation green threads have some access to some of this information? Could this enable greater performance?
If so, how? Could Google futex wait help there?
they have their uses, too, and the expectation is that when they arrive, Java will support them, too, as a third implementation of threads. Great to hear that but I hope that their use cases will be well defined and not overlap too much with loom. wild idea : could the JVM loom scheduler at runtime convert a green thread into google thread & vice versa? That could help performance, especially on pathological cases?
Finally, I believe that say 1000 green threads actually reduce to a thread pool of kernel threads encapsulated by the JVM, if this belief is correct, then the real kernel threads underlying the green threads could benefit from being futex wait kernel threads?
Sounds rather like 'Light-weight processes', something Solaris used, but eventually retired. [0]
Can anyone comment on the similarities/differences?
Linux switched to 1:1 threading (NPTL, added 2.4.4) before epoll existed (added 2.4.44). And in general M:N threading disappeared before massively concurrent asynchronous I/O architectures became popular.[1] Before the latter came, M:N threading was needless complexity; e.g. nobody was actively using and evolving scheduler activation kernel interfaces. And many of the benefits of M:N threading can't be realized when shoehorned into the POSIX thread model; e.g. concept of multiple, user-controlled schedulers or of explicitly passing control flow to a specific thread (yield/resume, switchto) have no place in that model.
[1] Solaris had /dev/poll and NetBSD had kqueue before M:N threading went away, but the developments were relatively close in time and definitely before O(1) polling became widely used outside a few high-profile projects.
Solaris had them as part of its original threading support, and Windows does as well, but they get seldom used.
I think the Go scheduler makes a good case for multiplexing a large number of user-mode threads (or goroutines) over a limited number of OS threads: whenever a goroutine needs to make a blocking syscall (e.g. writing to a socket), the work is offloaded to a "network poller" thread, and meanwhile the Go scheduler can continue to service other runnable goroutines.
It seems to me that this allows Go programs to maximize the use of their OS-thread time slices without being preempted on each syscall. Does anybody care to comment on how this impacts throughput and latency?
In my mind user-mode threads are much more about engineering productivity than raw performance. The comparison is wasteful blocking network calls using threads written in a simple synchronous way vs efficient user mode threads making network calls in a non blocking way also written synchronously.
Today to get non blocking efficiencies you need to write async code bc without loom there is no otb user mode threads, even if user mode threads aren’t as efficient in raw numbers it’s still waaay ahead of the predominant way threads are used today in Java (mostly wrt network calls).
Are there any online resources that provide an overview of various advanced concurrency patterns in various programming languages.
I would like to understand various trade-offs between multiple approaches.
If interested in aggregated Project Loom news: https://inside.java/tag/loom
This site seems to have a lot interesting articles. I have been trying to read about things like this on OpenJDK. But this site seems to be very easy to navigate on (unlike openjdk). It is also highly likely that I am an idiot.