7 ms·

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

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_scheduling.pdf https://www.scott-a-s.com/files/pldi2017_lf_elastic_scheduli...

twoodfin 6y ago
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.
- the8472 6y ago
  > 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.
- gnulinux 6y ago
  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.
  - ploxiln 6y ago
    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.
jacques_chester 6y ago
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? [0] https://materialize.io/blog-rocksdb/ https://materialize.io/blog-rocksdb/
- scott_s 6y ago
  > 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.pdf 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.
corysama 6y ago
Similarly, Microsoft is advising that Fibers and User-Mode Scheduling are not actually very useful anymore. https://devblogs.microsoft.com/oldnewthing/20191011-00/?p=102989 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.
- Const-me 6y ago
  > 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.
  - corysama 6y ago
    Anyone know where I can read up on implementing something better than something like http://www.davidespataro.it/modern-c-concurrency-synchronizing-threads-condition-variables/ 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.
    - Const-me 6y ago
      I don't know, I'm generally happy with the way modern OSes (Windows 10, Linux 5.4) do kernel scheduling. 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.
echlebek 6y ago
> machines with only 176 and 184 cores I chuckled, this seems like a massive number of cores to me. :)
Matthias247 6y ago
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.
- scott_s 6y ago
  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.

twoodfin 6y ago

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.

the8472 6y ago
> 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.
gnulinux 6y ago
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.
- ploxiln 6y ago
  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.

jacques_chester 6y ago

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? [0] https://materialize.io/blog-rocksdb/ https://materialize.io/blog-rocksdb/

scott_s 6y ago
> 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.pdf 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.

corysama 6y ago

Similarly, Microsoft is advising that Fibers and User-Mode Scheduling are not actually very useful anymore. https://devblogs.microsoft.com/oldnewthing/20191011-00/?p=102989 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.

Const-me 6y ago
> 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.
- corysama 6y ago
  Anyone know where I can read up on implementing something better than something like http://www.davidespataro.it/modern-c-concurrency-synchronizing-threads-condition-variables/ 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.
  - Const-me 6y ago
    I don't know, I'm generally happy with the way modern OSes (Windows 10, Linux 5.4) do kernel scheduling. 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.

echlebek 6y ago

> machines with only 176 and 184 cores I chuckled, this seems like a massive number of cores to me. :)

Matthias247 6y ago

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.

scott_s 6y ago
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.