1. They may not have access to the representation the subroutines store their state, as it may be platform dependent (e.g. if you're targeting LLVM you may not have access to that representation).
2. They may not track their pointers, and so find it hard to move chunks of stack around if they have internal pointers into the stack.
3. They may want to enable some specific optimizations in the special (and rare, especially when IO is involved) case of a monomorphic calls to shallow coroutines. This requires that the representation of the subroutine's state be available as a high-level node for the compiler to change.
For a statically compiled language that produces machine code and prefers stack allocation and has strict constraints on copying references, it is not so easy.
Internal pointers into the stack aren't really the reason Rust can't take this approach either, though, unfortunately. Async frames are "pinned" once they start running anyway so the ecosystem is designed around not needing to move them. Async callee frames are, in a sense, contained in their caller's frames- this makes async recursion tricky, but in exchange each static call graph uses a single allocation.
The real issue is basically naasking's #1- not that Rust loses its IR or that it's platform dependent, but that LLVM simply doesn't have the infrastructure to work with stack frames directly. A sufficiently motivated+funded team could add it but Rust doesn't have that luxury.
In fact, this is also the reason that C++20 coroutines individually heap-allocate their frames. No compiler had the infrastructure or was able to put in the work in time. There are also some thorny problems around phase ordering here- stack frame layout typically isn't determined until very very late (to enable optimizations) but program-accessible types in both C++ and Rust need to know their sizes very very early. Java can sidestep this by being slightly higher level.
The problem is that LLVM doesn't even let you see the stack layout until very late, and then only as debug info. You could probably hack something on top but it would probably wind up looking a lot like C++20, with a lot of extra allocation, or like Rust, with all the stack frame layout optimization duplicated into the frontend.
If you just want to suspend some code, subroutine calls will do – but so will any other instruction, as long as you save the values of all registers. That's what the kernel does, after all. Using the subroutine call boundary lets you save a bit of work by saving only the callee-save registers, but it doesn't make that much difference. The problem is that you still need a stack, which prevents coroutines from being lightweight enough.
If you want to move the stack, like Go does... then just like with a GC, you need to track which registers and which stack offsets contain pointers at a given point in the program. That does require some sort of safepoint, which could be a subroutine call. But that's all irrelevant from Rust's perspective, because Rust's low-level pointer model is fundamentally incompatible with moving the stack. In Go, pointers into the stack are themselves only stored on the stack and in registers – never on the heap – so the runtime can easily find them all and adjust them. If you could store pointers into the stack onto the heap, it might still be possible to adjust them, albeit at higher cost, if you had a GC-managed heap where the runtime knows where all the pointers are. But Rust doesn't even have that. Tracking all the pointers in the heap is impossible for multiple reasons:
- Rust programs don't have to use any particular runtime-provided heap; they can ask the OS for memory directly and store pointers there.
- Pointers aren't necessarily stored in an easy-to-maintain way: e.g. Rust supports tagged unions, where the interpretation of one word in memory as either a pointer or integer depends on the value of another word.
Oh, and Rust lets you convert pointers to integers (useful for hashing purposes), so moving pointers behind a program's back would have visible side effects in any case.
So moving the stack is out. That leaves two possibilities:
- Segmented stacks;
- Calculating the required stack space statically.
LLVM can generate code with segmented stack support [1], and Rust used to enable that option. It's not that bad, but it does require every function to begin by checking whether there's enough space left for its stack, and call a runtime function (__morestack) if not. That adds a measurable overhead to function calls. It also requires using a custom thread-local storage slot to track the current stack base, which means you can only call the function on threads where the runtime set up that slot, not any random C thread. That's a problem if you're writing a library meant to be used by C code, which evolved into a major use case for Rust. For these reasons, Rust nixed segmented stack support sometime before 1.0. Re-enabling it is one hypothetical reason why you might want two versions of each function.
As for calculating the required stack space statically, that wouldn't require an alternate code generation mode. But as you were discussing in another subthread, the design of most compiler pipelines makes it very difficult to expose that information to the frontend. Even if that weren't a problem, merely making it theoretically possible to statically calculate stack usage requires imposing severe limits on the program. You can't make dynamic calls where you don't know the callee, and you can't use recursion at all (because then you might need infinite space). And if only a subset of code is async-compatible... then you end up with the equivalent of colored functions anyway. So even if LLVM's pipeline could be wrangled into doing what's necessary, it would only be a small improvement over the higher-level async/await implementation that Rust currently has. (As an alternative, you might be able to create a sort of hybrid mode where only dynamic and recursive calls use segmented stacks, but that would still require an alternate code generation mode.)
The nail in the coffin is that Rust also targets WebAssembly, where you can't do any of the nice low-level things that you can on real machines. This has also been a blocker for guaranteed tail call elimination. I hate it.
Async/await also needs the same logical stack, it just captures it frame by frame. Continuations can do the same. But as you say, Rust has some particular constraints that make this hard.
> then just like with a GC, you need to track which registers and which stack offsets contain pointers at a given point in the program
Well, you don't need to track all the pointers, just pointers into the stack.
> ... The nail in the coffin is that Rust also targets WebAssembly ...
But yeah, I mentioned some reasons for why it could be hard for some languages -- internal stack pointers and lack of control over the backend are two of them.
But I find it problematic that backend problems force feature design today. If a language wants to be popular 20 years from now it needs to have the patience not to bend to its backends' limitations, particularly as it has few competitors in its niche. So if a language's designers are absolutely certain that async/await is the right design for them for the next few decades, then that's great, but if they decide they want to design a language for the next few decades based on the limitations of WebAssembly in 2019, then that's something I like less. Sometimes there's no choice and a language/feature has to ship, but this is a feature that the world can and has lived without.
This is a lesson that we all learned during the NPTL/NGPT era [1] and have subsequently forgotten and will have to relearn.
Anyway, I don't think anyone has forgotten those lessons, but they're not very relevant to modern managed runtimes. (also mioco seems to be single-threaded)
Async I/O isn't anything new, and it's stood the test of time. Nginx isn't some new experimental technology.
> Anyway, I don't think anyone has forgotten those lessons, but they're not very relevant to modern managed runtimes. (also mioco seems to be single-threaded)
They're still very relevant. Linux can spawn hundreds of thousands of kernel threads.
Anyway, we used to have an multithreaded M:N runtime in Rust, but it was removed because the performance was worse than 1:1 in practice. M:N was moved out of the standard library into the mioco library. Now it's unmaintained, because nobody actually wants M:N threads in Rust—an interesting outcome to be sure!
What do you mean? User-mode threads also use async I/O. They do just what async/await does, only without the syntax. I mean that async/await hasn't stood the test of time just yet.
> Linux can spawn hundreds of thousands of kernel threads.
Yeah, not very active ones, though. And their stacks are never really uncommitted. And the scheduler is badly optimized for many of the very uses you want in a server. On the other hand, you can spawn many millions of active fibers, schedule them how you like, and play with their state and its representation in many interesting ways (like moving a running fiber from one machine to another).
> Now it's unmaintained, because nobody actually wants M:N threads in Rust—an interesting outcome to be sure!
Just to make sure, when people say "M:N threads" they can mean a lot of very different things. In Java, they'll behave like async/await, only without the syntactic constructs. Stacks and stack frames are moved, can shrink and grow, can have various representations etc., and the scheduling is entirely pluggable. You can schedule the continuations manually, or in a scheduler of your choice, shared, or not, with ordinary tasks.
This is, from what I can tell, their main advantage in performance over other implementations. (In Rust, at least- the performance story may easily be different in garbage collected languages like Go or Java.)
Another caveat: Rust's claims to have implemented M:N in the past must be tempered a bit by two factors. First, Rust had to use segmented stacks, which Go moved away from and which Loom seems to be avoiding, precisely because they're so expensive. Second, Rust had to dispatch all IO APIs dynamically based on the currently selected runtime, which Go avoids by not having two runtimes, and which Loom can probably avoid via its scheduler implementation and/or JIT devirtualization.
They didn't decide to move off of M:N when it was exclusively M:N.
When you write "Java", you mean a specific implementation of the JVM, like the JVM reference implementation in OpenJDK, or you imply that all JVM implementations must support this to be called Java?
Edit: Is your comment related to Project Loom, aiming to add fibers and continuations to Java?
Unless you have some approach I haven't heard of, in which case, please provide a link!
That said, the extra object headers from heap-allocated activations will make up some of the difference.
It'll be interesting to see how this plays out on the JVM though.
However, the paradox you have to manage here is this: if you make this sequential/parallel determination pretty high up in the code so that there is a lot of sequential code right after an async part (async can call sync all it wants), then very little of your code is altered, but now you have the green threads problem - one long CPU-bound task that doesn’t yield.
At least with Rust, if you’ve partitioned your data properly then there can be several threads of execution running tasks on unrelated data, but in Javascript you will be punished for trying to consolidate the async bits in this fashion.
[1] true non-tail recursion is a problem of course, but it is ok for the compiler to give up if it can't statically prove that the recursion depth is less than a documented maximum.
edit: rewording
For example: convert an internal iterator to an external one (in pseudo C++, yes, yes, I know):
// This is a bog standard template function. Cont can be anything
// here as long as it is callable. It literally does the same thing
// as for_each
template<class Cont, class Iter>
Cont inside_out(Iter begin, Iter end, Cont yield){
// as long as yield lifetime is confined to the scope of
// inside_out; when Cont
// ends up being some compiler internal (possibly unique) magic
// type it should be possible to CPS convert both inside_out and
// for_each. Both rust and C++ monomorphize templates anyway so
// instantiating dedicated CPS variant is not a problem.
std::for_each(begin, end, [&](auto&& x) { yield(x); });
// for various reasons we need to return the continuation here. A
// proper language would tail call to it.
return yield;
}
...
// this is basically call/cc. It uses magic to get the current
// continuation, then invokes its first argument with it and the
// remaining arguments. The current function need to be
// Note: template functions are not first class in
// C++, but we take some liberty here.
auto cont = continuationify(inside_out, my_vec.begin(), y_vec.end());
while(not cont.done())
std::cout << cont();
Rust is close enough to C++ that it would work in the same way. I've been planning to write a paper for the C++ committee to add fire to the current coroutine controversy and proposing something like the above (which would unify stackless and stackful coroutines).
int bar(int i) { return i+1; }
/* bar takes a implicit return address in [esp+0] */
noreturn foo((*ra)(int),int x)
{
/* where (*)(RetType) is a return address */
int y = bar(x); /* x86 call pushes eip */
ra return bar(y); /* pseudo-tail-call (push ra) */
}
int quux(int x)
{
(*ret)(int); ret = (return); /* get implicit RA */
foo(ret,x);
} // unreachable
This is a bit mistaken; ancient versions of Rust (but not so ancient that they weren't using LLVM) were, like Go, everything-is-implicitly-async, and Rust used the same strategy as Go to manage stacks (to the extent that the old language reference listed Go in its (rather long) list of precursors, specifically calling out its split stack approach).
The ultimate reason that Rust switched away from Go's approach is for interoperability with C. If your stacks are the size of C stacks, and if your language doesn't feature a pervasive runtime, then interoperability with C is nearly trivial, and this was something that Rust dearly desired (and has benefited greatly from, IMO).
Ultimately one should not look at Rust's chosen approach and assume that it represents some grand rebuke of alternative approaches to asynchronicity. If you have different constraints, then a Go-style approach is lovely. For a language at the level of Rust, different tradeoffs may dominate.
in .NET stacks are different, the runtime is relatively large, yet interoperability with C is nearly trivial. From my PoV at least, I never worked on compilers, only used them a lot.
That amount is really small for .NET. See this doc https://docs.microsoft.com/en-us/cpp/dotnet/calling-native-f... it says “PInvoke has an overhead of between 10 and 30 x86 instructions per call.” That’s barely measurable. Close to the cost of a mispredicted branch. 4x cheaper than a single cache miss.
That’s if you do it correctly, i.e. only marshal value types or arrays/pointers of them, don’t use custom marshallers, etc. Also it’s important to specify correct attributes. To call `int func(const sStruct&)` C++ function, you should specify `[In] ref sStruct` in C#.
Declare a delegate in C#, apply [UnmanagedFunctionPointer] attribute specifying calling convention (on Linux you’ll likely want CallingConvention.Cdecl), pass to native code specifying [MarshalAs( UnmanagedType.FunctionPtr )] in the prototype of the DLL/SO function which accepts that pointer.
This is even more convenient than doing that in C. In C, function pointers are stateless, typical design pattern is pass accompanying `void* context` for the state. Not needed in C#, that delegate can capture whatever it wants, the runtime will do it’s marshalling magic, generating a native function and somehow associating it with the captured state.
The only caveat is lifetime. Function pointers can’t be retained by native code, they’re too simple and don’t have a ref.counter. You must ensure the .NET delegate is not garbage collected while it’s referenced by the native code, or the app will crash.
async/await aren't strictly necessary, but to avoid them you need one of:
1. a sufficiently smart compiler with whole program compilation, or
2. to compile two versions of every function, an async variant and a sync variant, or
3. every async wait captures the whole stack, thus wasting a lot of memory.
Async/await is basically a new sort of calling convention, where the program doesn't run in direct style but in continuation-passing style. This permits massive concurrency scaling with little memory overhead, but there other tradeoffs as per above.
Async/await makes perfect sense for Rust which wants to provide zero-overhead abstractions.