4 ms·

TCO isn't about fast performance, it's about stack depth. I like Quasar, but I suspect you removed reduction scheduling because function-call-site reductions,

TCO isn't about fast performance, it's about stack depth. I like Quasar, but I suspect you removed reduction scheduling because function-call-site reductions, as erlang does natively, is not great when implemented in-language, as it blows up a number of optimizations and muddies the register picture. That said, I think MCRed is doing a slight disservice even he's got good intentions; erlang is amazing for what it does, quasar is pretty nifty and doubtless has many superior use cases; even go has a lot of utility in the concurrency space. Let a billion processes bloom.

pron 11y ago
> TCO isn't about fast performance, it's about stack depth. Sure, but again, it's certainly doable (and has been done). > I suspect you removed reduction scheduling because function-call-site reductions, as erlang does natively, is not great when implemented in-language, as it blows up a number of optimizations and muddies the register picture. We removed it because it's unhelpful, and let me explain why. Any preemption that's based on time-slices/reduction -- basically, preemption at any point other than the thread blocking on something -- means that the thread still wants more CPU, but you can't allow it to have it because there are others that need it. This is fine when you have roughly the same number of such CPU-hungry threads as CPU cores, or even a bit higher -- not when you have 100,000 of those or 1M. So the number of CPU hungry threads must be very low, or your system is grossly under-provisioned. Now, Erlang has to do it because all Erlang processes are scheduled in user mode, but even in Erlang this doesn't help if you have more than a few such processes. OTOH, on the JVM, where you can pick if you want user-mode or kernel scheduling, you can simply choose the kernel to schedule those few CPU-hungry threads. The kernel does it much better than anything in userspace can. If you don't have CPU-hungry threads, but well-behaving threads that occasionally become CPU-hungry, it still doesn't help because the work stealing scheduler can very easily deal with such occasional behavior. In short, time-slice/reduction based preemption in the user-mode scheduler simply doesn't help you in any way. Erlang does it because it has no other scheduler and it must support (a few) processes that behave that way.
- felixgallo 11y ago
  I think your intuitions are incorrect. 1. Preemptive multitasking is strictly better in almost all cases than cooperative multitasking, when you have more processes, not fewer; especially when these processes are heterogenous. Throughput decreases over the best-case cooperative scenario, but jitter significantly decreases, and most importantly, you -- the user, the operator, or the programmer -- have a strong guarantee that the schedulers will never lock up because someone wrote code wrong. That guarantee alone is why every operating system abandoned a cooperative model and pushed schedulers as close as possible to preemptive multitasking. 2. Kernel scheduling is radically worse than user-space scheduling in nearly every scenario. The kernel schedulers are necessarily very generic and workload-agnostic; kernel threads and the thread management infrastructure are incredibly heavyweight and slow relative to user space; the context switching penalty is gigantic; processes relying on kernel scheduling are forced to compete with other processes on the system; and the list goes on. This is why unikernels, exokernels, and user-space tcp implementations like onload are growing prevalent, especially in the low-latency space.
  - pron 11y ago
    > Preemptive multitasking is strictly better in almost all cases than cooperative multitasking, when you have more processes Sorry I didn't make myself clear. Quasar most certainly employs preemptive multitasking, just not time-slice- (or reduction-) based. > Kernel scheduling is radically worse than user-space scheduling Except when descheduling on time-slices. Remember two facts: 1/ your hardware can only support very few threads that require time-slice preemption so those task-switching costs are negligible, and 2/ no other thread is dependent on low-latency access to data produced a thread that is descheduled on a time-slice, so the latency doesn't matter much either. None of that is my intuition. I've been profiling and measuring this stuff for a few years now, and I'm a huge proponent of userspace scheduling. Adding time-slice preemption didn't make things any worse -- it just didn't make them any better either, so we took it out, and we tell users to use kernel scheduling for those threads. If the user makes a mistake, we recognize it at runtime and tell her that kernel scheduling might be better for that thread.

pron 11y ago

> TCO isn't about fast performance, it's about stack depth. Sure, but again, it's certainly doable (and has been done). > I suspect you removed reduction scheduling because function-call-site reductions, as erlang does natively, is not great when implemented in-language, as it blows up a number of optimizations and muddies the register picture. We removed it because it's unhelpful, and let me explain why. Any preemption that's based on time-slices/reduction -- basically, preemption at any point other than the thread blocking on something -- means that the thread still wants more CPU, but you can't allow it to have it because there are others that need it. This is fine when you have roughly the same number of such CPU-hungry threads as CPU cores, or even a bit higher -- not when you have 100,000 of those or 1M. So the number of CPU hungry threads must be very low, or your system is grossly under-provisioned. Now, Erlang has to do it because all Erlang processes are scheduled in user mode, but even in Erlang this doesn't help if you have more than a few such processes. OTOH, on the JVM, where you can pick if you want user-mode or kernel scheduling, you can simply choose the kernel to schedule those few CPU-hungry threads. The kernel does it much better than anything in userspace can. If you don't have CPU-hungry threads, but well-behaving threads that occasionally become CPU-hungry, it still doesn't help because the work stealing scheduler can very easily deal with such occasional behavior. In short, time-slice/reduction based preemption in the user-mode scheduler simply doesn't help you in any way. Erlang does it because it has no other scheduler and it must support (a few) processes that behave that way.

felixgallo 11y ago
I think your intuitions are incorrect. 1. Preemptive multitasking is strictly better in almost all cases than cooperative multitasking, when you have more processes, not fewer; especially when these processes are heterogenous. Throughput decreases over the best-case cooperative scenario, but jitter significantly decreases, and most importantly, you -- the user, the operator, or the programmer -- have a strong guarantee that the schedulers will never lock up because someone wrote code wrong. That guarantee alone is why every operating system abandoned a cooperative model and pushed schedulers as close as possible to preemptive multitasking. 2. Kernel scheduling is radically worse than user-space scheduling in nearly every scenario. The kernel schedulers are necessarily very generic and workload-agnostic; kernel threads and the thread management infrastructure are incredibly heavyweight and slow relative to user space; the context switching penalty is gigantic; processes relying on kernel scheduling are forced to compete with other processes on the system; and the list goes on. This is why unikernels, exokernels, and user-space tcp implementations like onload are growing prevalent, especially in the low-latency space.
- pron 11y ago
  > Preemptive multitasking is strictly better in almost all cases than cooperative multitasking, when you have more processes Sorry I didn't make myself clear. Quasar most certainly employs preemptive multitasking, just not time-slice- (or reduction-) based. > Kernel scheduling is radically worse than user-space scheduling Except when descheduling on time-slices. Remember two facts: 1/ your hardware can only support very few threads that require time-slice preemption so those task-switching costs are negligible, and 2/ no other thread is dependent on low-latency access to data produced a thread that is descheduled on a time-slice, so the latency doesn't matter much either. None of that is my intuition. I've been profiling and measuring this stuff for a few years now, and I'm a huge proponent of userspace scheduling. Adding time-slice preemption didn't make things any worse -- it just didn't make them any better either, so we took it out, and we tell users to use kernel scheduling for those threads. If the user makes a mistake, we recognize it at runtime and tell her that kernel scheduling might be better for that thread.