5 ms·

Preemptive is safer for liveliness since it avoids 'starvation' (one task's poll taking too long), however it in practice almost always more expensive in memory

by f_devd 3y ago

Preemptive is safer for liveliness since it avoids 'starvation' (one task's poll taking too long), however it in practice almost always more expensive in memory and time due to the implicit state. In async, only the values required to do a poll need to be held (often only references), while for threads the entire stack & registers needs to be stored at all times, since at any moment it could be interrupted and it will need to know where to continue from. And since it needs to save/overwrite all registers at each context switch (+ scheduler/kernel handling), it takes more time overall. In general threads are a good option if you can afford the overhead, but assuming threads as a default can significantly hinder performance (or make near impossible to even run) where Rust needs to.

avodonosov 3y ago
@f_devd, I think you are mistaken. Not that I want to discourage anyone from using async/await. I am glad async/await solves people problems, especially when people do not have a ready to use alternative as my perfect ideal threads. But just to reduce the number of people who are mistaken in the Internet :) I think the only real problem that makes threads really expensive for embedded systems is statically allocated large stack. If stack size is managed dynamically, it can be small thus allowing many threads. The other expenses should be tolerable. Embedded systems don't require high computational throughput, I think. All implementation approaches used for async/await can be used for threads, and vice versa, because they are basically the same thing. > In async, only the values required to do a poll need to be held (often only references), while for threads the entire stack & registers needs to be stored at all times, since at any moment it could be interrupted and it will need to know where to continue from. Well, it seems opposite - the approach you attribute to threads can be more efficient here. If async function, when blocked, holds in its Feature state record only the part of local vars and parameters that is needed to continue execution, the function needs to copy them from the stack. And that's redundant copying and memory allocation for Feature state records. Note, this happens at every element of function call chain, so the Future state records act as stack frames. And this stack copying is most likely done in individual assignments, var by var. And I am afraid this allocation and copying can happen every time the async function blocks. Reusing Future state records may be non-trivial, given that next time the top-level async function we are await'ing for may block in some other internal branch. Compared to saving the stack which is just saving two registers: stack base and stack pointer. > And since it needs to save/overwrite all registers at each context switch (+ scheduler/kernel handling), it takes more time overall. Saving registers is cheap. Also there is no magic, when next async function is activated by async function scheduler, it uses the registers as it wants, so register values of previously blocked async function need to be saved somehow - this happens when the most nested function copies it local vars to the Future state record. Speaking of preemption requiring kernel - not necessarily. It can be done in user space. A thread can yield control to scheduler when it invokes a blocking function (as Java virtual threads currently do). In addition to that, other preemption points can be used - function calls, allocations, maybe loop boundaries. This approach lies in between the cooperative threading and full preemption. If we consider preemption by timer interrupts. First, it only happens if the thread haven't yet yielded control by calling a blocking function. Second, if preemption by timer happens, kernel can pass control to the user space scheduler in the application runtime instead of applying kernel's heavy weight scheduler (is kernel scheduler really more heavy weight?). Moreover, I've just searched for user space interrupts, and it looks like new processors provide such a feature. The first link in search currently is https://lwn.net/Articles/871113/ https://lwn.net/Articles/871113/. Green threads scheduling is mentioned as one of the use cases. So, in short, I don't see why threads would be inherently less performant than async/await.
- f_devd 3y ago
  I think you might be confusing Runtime, OS and bare-metal primitives. Java virtual threads are possible because there is always the runtime which code will return to, and since it's already executing in a VM the concept of Stack/Heap Store/Loads don't really matter for performance. > Compared to saving the stack which is just saving two registers: stack base and stack pointer. In embedded you might not have a stack base, just a stack pointer, this means in order to switch to a different stack you need to copy 2 stacks. (I might be wrong here; I know some processors have linear stacks, but this might be more uncommon). On bare metal this dynamic changes significantly, in order to "switch contexts" with preemption the following steps are needed (omitting the kernel switch ops): - Receive interrupt - Mask interrupts - Store registers to heap - Store stack to heap - Calculate next preemption time (scheduler) - Set interrupt for next preemption time - Load stack from heap - Load registers from heap - Unmask interrupts - Continue execution using program counter While for async/await everything already in place on the stack/heap so a context switch is: - Call Future.poll function - If Poll::Ready, make parent task new Future and (if it exists) call it - If Poll::Pending, go to next Future in Waker queue Async/await (in rust) is without a runtime, and without copies or register stores/loads; it can be implemented on any cpu. On embedded tasks can also decide how they want to be woke, so if you want to do low-power operation you can make an interrupt which calls `wake(future)` and it will only poll that task after the interrupt has hit, meaning any time the Waker queue is empty it knows it can sleep with interrupts enabled. > so register values of previously blocked async function need to be saved somehow The difference is that we know exactly which values are needed instead of not knowing what we need from the stack/registers. User-space interrupts would make it easier to do preemption in user-space but this is yet another feature you can't make assumptions about (especially since there has been only a single gen of processors which support it).
  - gpderetta 3y ago
    Yes, of course a non-cooperative switch is more expensive than a cooperative one. But the thread model does not require preemption or even time-slice scheduling. But with async/await cooperative switch is the only option.

by f_devd 3y ago

avodonosov 3y ago

@f_devd, I think you are mistaken. Not that I want to discourage anyone from using async/await. I am glad async/await solves people problems, especially when people do not have a ready to use alternative as my perfect ideal threads. But just to reduce the number of people who are mistaken in the Internet :) I think the only real problem that makes threads really expensive for embedded systems is statically allocated large stack. If stack size is managed dynamically, it can be small thus allowing many threads. The other expenses should be tolerable. Embedded systems don't require high computational throughput, I think. All implementation approaches used for async/await can be used for threads, and vice versa, because they are basically the same thing. > In async, only the values required to do a poll need to be held (often only references), while for threads the entire stack & registers needs to be stored at all times, since at any moment it could be interrupted and it will need to know where to continue from. Well, it seems opposite - the approach you attribute to threads can be more efficient here. If async function, when blocked, holds in its Feature state record only the part of local vars and parameters that is needed to continue execution, the function needs to copy them from the stack. And that's redundant copying and memory allocation for Feature state records. Note, this happens at every element of function call chain, so the Future state records act as stack frames. And this stack copying is most likely done in individual assignments, var by var. And I am afraid this allocation and copying can happen every time the async function blocks. Reusing Future state records may be non-trivial, given that next time the top-level async function we are await'ing for may block in some other internal branch. Compared to saving the stack which is just saving two registers: stack base and stack pointer. > And since it needs to save/overwrite all registers at each context switch (+ scheduler/kernel handling), it takes more time overall. Saving registers is cheap. Also there is no magic, when next async function is activated by async function scheduler, it uses the registers as it wants, so register values of previously blocked async function need to be saved somehow - this happens when the most nested function copies it local vars to the Future state record. Speaking of preemption requiring kernel - not necessarily. It can be done in user space. A thread can yield control to scheduler when it invokes a blocking function (as Java virtual threads currently do). In addition to that, other preemption points can be used - function calls, allocations, maybe loop boundaries. This approach lies in between the cooperative threading and full preemption. If we consider preemption by timer interrupts. First, it only happens if the thread haven't yet yielded control by calling a blocking function. Second, if preemption by timer happens, kernel can pass control to the user space scheduler in the application runtime instead of applying kernel's heavy weight scheduler (is kernel scheduler really more heavy weight?). Moreover, I've just searched for user space interrupts, and it looks like new processors provide such a feature. The first link in search currently is https://lwn.net/Articles/871113/ https://lwn.net/Articles/871113/. Green threads scheduling is mentioned as one of the use cases. So, in short, I don't see why threads would be inherently less performant than async/await.

f_devd 3y ago
I think you might be confusing Runtime, OS and bare-metal primitives. Java virtual threads are possible because there is always the runtime which code will return to, and since it's already executing in a VM the concept of Stack/Heap Store/Loads don't really matter for performance. > Compared to saving the stack which is just saving two registers: stack base and stack pointer. In embedded you might not have a stack base, just a stack pointer, this means in order to switch to a different stack you need to copy 2 stacks. (I might be wrong here; I know some processors have linear stacks, but this might be more uncommon). On bare metal this dynamic changes significantly, in order to "switch contexts" with preemption the following steps are needed (omitting the kernel switch ops): - Receive interrupt - Mask interrupts - Store registers to heap - Store stack to heap - Calculate next preemption time (scheduler) - Set interrupt for next preemption time - Load stack from heap - Load registers from heap - Unmask interrupts - Continue execution using program counter While for async/await everything already in place on the stack/heap so a context switch is: - Call Future.poll function - If Poll::Ready, make parent task new Future and (if it exists) call it - If Poll::Pending, go to next Future in Waker queue Async/await (in rust) is without a runtime, and without copies or register stores/loads; it can be implemented on any cpu. On embedded tasks can also decide how they want to be woke, so if you want to do low-power operation you can make an interrupt which calls `wake(future)` and it will only poll that task after the interrupt has hit, meaning any time the Waker queue is empty it knows it can sleep with interrupts enabled. > so register values of previously blocked async function need to be saved somehow The difference is that we know exactly which values are needed instead of not knowing what we need from the stack/registers. User-space interrupts would make it easier to do preemption in user-space but this is yet another feature you can't make assumptions about (especially since there has been only a single gen of processors which support it).
- gpderetta 3y ago
  Yes, of course a non-cooperative switch is more expensive than a cooperative one. But the thread model does not require preemption or even time-slice scheduling. But with async/await cooperative switch is the only option.