On the Performance of User-Mode Threads and Coroutines
inside.java
inside.java
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...
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.
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.
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?
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.
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.
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.
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.
OS queues rarely expose methods like size() or empty(). In their multi-consumer queues they normally only expose variants of enqueue() and dequeue(). Peeking or checking for empty size is only there for single consumer queues, like win32 message queue.
Here’s the implementation of queues in Linux: https://github.com/torvalds/linux/blob/4334f30ebf395b204c6cb... I never worked on that kernel, but on the first sight it looks like they’re using a combination of locks and lock-free stuff there.
I chuckled, this seems like a massive number of cores to me. :)
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.
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…
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 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.
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.
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.
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!
What's the cost to the kernel besides a few structs?
Can you force yourself to list a few disadvantages of virtual threads over native threads?
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.
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.
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
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.
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.
[0]: https://www.oracle.com/a/ocom/docs/registration-policy-java-...
https://www.phoronix.com/scan.php?page=news_item&px=Google-U...
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?
I don't know. Any ideas?
> Great to hear that but I hope that their use cases will be well defined and not overlap too much with loom.
Supporting them would be a part of Loom.
> could the JVM loom scheduler at runtime convert a green thread into google thread & vice versa? That could help performance, especially on pathological cases?
Virtual threads' schedulers aren't in the VM. They're written in Java and are pluggable. But the answer to your question is yes, it's possible -- and not too hard, even -- but I don't know how much it would help.
I would like to ask you two other things: Firstly I have seen in the Loom document that it will use restartable sequences. I find such creative use of modern Linux technology an awesome thing to do. But you might need to delay support for them: https://www.phoronix.com/scan.php?page=news_item&px=Glibc-Re...
Finally, I would really like you to attempt a comparison of Loom with current Kotlin coroutines. I'm sure that you have learnt a bit from them as they honestly are the state of the art most ergonomic coroutine I have ever seen, especially regarding the following points: Exceptions just works Beautiful structured concurrency You can trivially specify and adjust on the fly the "scheduler" through both its context and its dispatcher Great cancelation support Colorless (no pollution with a completable future) Beautiful integration with reactive streams reinvented, through flow.
I don't expect Java Loom to be able to syntactically be as beautiful and simple as Kotlin coroutines but it would really be an accident to not be as expressive. So I hope that you will borrow all of their concepts as it's well thought, maximally expressive yet simple.
So a comparison on the surface level features would be nice. But what interest me the most would be a comparison of how technically kotlin coroutines currently works and in what way loom will outperform them? (as you can already have ~1 million of coroutines) I expect better performance as you have access e.g to io_uring.
I hope that Kotlin coroutines will be able to be transparently reimplemented using Loom threads, and therefore it would be very nice that the Loom's architects communicate with Kotlin architects on interoperability and reuse / synergies. Both communities bring great progress on the JVM and it's beautiful to contemplate.
Can anyone comment on the similarities/differences?
[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.
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?
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).
I would like to understand various trade-offs between multiple approaches.