Async and Await in Rust: a full proposal • Hacker News Board

Re: Async and Await in Rust: a full proposal

#131

Post by Rusky » Mon, Jul 16, 2018, 2:33 AM UTC

canndrew2016 wrote: post #125

withoutboats wrote: post #116

Earlier quoted context omitted.

I don't have time to write a whole essay, so let me just establish my credentials: - I wrote the generic associated types RFC (how Rust will implement higher kinded polymorphism). - I wrote the const generics RFC (the closest Rust will get to dependent types). - I wrote the async/await RFC, as well as the linked blog post. That is to say that I am intimately familiar with how Rust's type system can be extended to sup…

> Monads as implemented in pure functional programming languages like Haskell cannot usefully abstract over asynchronous and synchronous IO in Rust for a variety of reasons having to do with the way the type system exposes low level details by virtue of Rust being a systems programming language. I do not believe that `do` notation could be a useful mechanism for achieving either the ergonomics or the performance that…

A Rust-flavored effect system is quite a bit different from do-notation. You're probably right that such a thing could achieve the same ergonomics and efficiency as built-in async/await, but you're also probably right that it would be a huge amount of complexity.

When people say that monads and do-notation don't work in Rust, they're talking about a user-level Monad trait and a simple CPS transform built on top of it:

- Such a monad trait is impossible to write even with HKT because it would have to abstract over both Option/Result (type constructors) and Iterator/Future (traits)

- Such a CPS transform would be extremely limited (not composable with built-in loop structures) and/or extremely tricky around TCE, lifetimes, and allocation (the typical type for `>>=` would involve `Fn` trait objects...).

Effects bypass this by leaving the CPS transform in the compiler, instead only exposing delimited continuations to userspace. Which is basically what async/await does, just non-generically.

Re: Async and Await in Rust: a full proposal

#132

Post by canndrew2016 » Mon, Jul 16, 2018, 2:41 AM UTC

withoutboats wrote: post #129

canndrew2016 wrote: post #125

Earlier quoted context omitted.

> Monads as implemented in pure functional programming languages like Haskell cannot usefully abstract over asynchronous and synchronous IO in Rust for a variety of reasons having to do with the way the type system exposes low level details by virtue of Rust being a systems programming language. I do not believe that `do` notation could be a useful mechanism for achieving either the ergonomics or the performance that…

The first part of your comment is unresponsive to mine; the last part is pretty rude & factually wrong (we are not motivated to implement an effect system right now; we understand the theory). Sticking to the first part: an effect system is not what the user I was responded to was talking about. They were talking about building do notation on top of type classes with higher kinded polymorphism, which cannot effective…

> The first part of your comment is unresponsive to mine;

I interpreted OP's comment as complaining about the lack of more general abstractions in Rust that would allow you to implement async/await. Your comment specifically mentioned Haskell-style monads (eg. a `Monad` trait), but that's not the only way to implement something like this.

> the last part is offensive & wrong

Quoting steveklabnik:

> it’s an open research problem if do notation can work in Rust. Until that’s solved at all, we’re just not sure it’s possible. ... "Open question" doesn't mean "impossible", mind you. But nobody has ever come up with a design. In the meantime, we have users to support...

Isn't this what I was saying? "We don't know how to do it, so we're going with the easier option."

Edit: To be clear, I don't think async/await we've ended up with is necessarily in the wrong direction. But I also don't think that "we thoroughly explored the design space of do/monads/effects and concluded that they were impossible to implement ergonomically/efficiently" is really true.

Re: Async and Await in Rust: a full proposal

#133

Post by Rusky » Mon, Jul 16, 2018, 2:46 AM UTC

AndyKelley wrote: post #8

This is exciting. It allows programmers to model their problems in code that fully accounts for the parallelism. For comparison, here is async/await in Zig: https://ziglang.org/documentation/master/#Coroutines Zig decided to go the other way - when you async call a function, it does eagerly evaluate until the first suspend point. This is less overhead than immediately suspending, plus it removes the dependency of the…

> when you async call a function, it does eagerly evaluate until the first suspend point. This is less overhead than immediately suspending, plus it removes the dependency of the language feature on a userland event loop.

This seems wrong. There's no more overhead for Rust's approach- which to be clear immediately suspends only the callee, not the entire stack of async functions. In fact, if you immediately await the future, the control flow is literally no different from eagerly evaluating until the first suspend point.

There is also already no dependency on a userland event loop. This is, again, because only the callee is immediately suspended. It's still entirely up to specific leaf future implementations to interact with (or not) the event loop.

Re: Async and Await in Rust: a full proposal

#134

Post by eddyb » Mon, Jul 16, 2018, 2:49 AM UTC

gpderetta wrote: post #98

pcwalton wrote: post #95

Earlier quoted context omitted.

We already have stackful coroutines. They're called threads. If for some reason you want M:N threading, we have that too, via the mioco library. (If you think mioco's M:N threading will provide far superior performance to regular 1:1 threads, though, you will probably be disappointed.) If you look at the performance numbers of these approaches, you'll see why stackless coroutines are desired.

I want stackfull coroutines, with custom, fast user space scheduling and task switching with guaranteed optimisation to a single stack frame and no allocation where possible. I also want the ability to convert internal iterators to internal iterators with no overhead and even (especially) if the internal iteration function has not been specifically marked (i.e. no red/blue functions). Hey, a man can dream.

> guaranteed optimisation to a single stack frame and no allocation where possible

You are literally describing stackless coroutines. And the generator state transform is that optimization.

If you want to get this without using generators explicitly, it's still stackless coroutines just not how Rust supports stackless coroutines. There was some discussion about making it more implicit but no progress was made in the implicit direction.

Re: Async and Await in Rust: a full proposal

#135

Post by kuon » Mon, Jul 16, 2018, 2:51 AM UTC

lapinot wrote: post #101

And yet we somehow don't acknowledge the fact that this is just do-notation for some specific monad--yeah, that powerful abstraction that can't be expressed in Rust because we don't allow higher-order polymorphism. Don't get me wrong, i'm bitter because i feel like Rust really is almost in the right direction for the future of language design. Yet there is a long time before we get a language with a really precise ty…

I have been doing programming, including functional programming for more than two decades, I still don't really know what a "monad" is. Each time someone explains it to me, I understand something different.

Re: Async and Await in Rust: a full proposal

#136

Post by eddyb » Mon, Jul 16, 2018, 2:52 AM UTC

pcwalton wrote: post #95

gpderetta wrote: post #71

I'm somewhat disappointed that rust is going with async style stackless continuations. I'm a huge fan of stackfull coroutines/continuations as they are much more elegant and flexible. The downside is that they need a full stack, but I strongly believe (but can't prove) that rust has enough annotations and lifetime capabilities that it should be able to guarantee single frame allocation (or even no allocation for full…

We already have stackful coroutines. They're called threads. If for some reason you want M:N threading, we have that too, via the mioco library. (If you think mioco's M:N threading will provide far superior performance to regular 1:1 threads, though, you will probably be disappointed.) If you look at the performance numbers of these approaches, you'll see why stackless coroutines are desired.

I would also mention https://github.com/edef1c/libfringe which pretty much solves context-switches (by replacing them with compiler-generated minimal stack spills/restores).

But as you might be able to tell from their APIs, you still have to allocate stacks somehow.

Re: Async and Await in Rust: a full proposal

#137

Post by eddyb » Mon, Jul 16, 2018, 3:01 AM UTC

Nemo157 wrote: post #45

kbumsik wrote: post #24

As an embedded system dev, I'm wondering if these async features can be implemented on bare-metal (or without runtime)? Maybe I'm dumb and it might be a wild thought but it would be great if I could easily integrate async language features with hardware interrupts.

Definitely. We’re currently blocked with the builtin await using thread local storage, but that’s planned to be removed and replaced with something that will work without an OS before stabilisation. I have had the old macro based async code in Rust running on a Cortex M device, completely runtime free. Once the TLS stuff is sorted I plan to port this forward to work with the builtin syntax.

I don't understand why people don't just support TLS in non-userspace code. It's so convenient for a bunch of things, and sadly Rust, for now, has nothing in between "fully explicit argument passing" and "scoped global state".

Re: Async and Await in Rust: a full proposal

#138

Post by kibwen » Mon, Jul 16, 2018, 3:22 AM UTC

canndrew2016 wrote: post #125

withoutboats wrote: post #116

Earlier quoted context omitted.

I don't have time to write a whole essay, so let me just establish my credentials: - I wrote the generic associated types RFC (how Rust will implement higher kinded polymorphism). - I wrote the const generics RFC (the closest Rust will get to dependent types). - I wrote the async/await RFC, as well as the linked blog post. That is to say that I am intimately familiar with how Rust's type system can be extended to sup…

> Monads as implemented in pure functional programming languages like Haskell cannot usefully abstract over asynchronous and synchronous IO in Rust for a variety of reasons having to do with the way the type system exposes low level details by virtue of Rust being a systems programming language. I do not believe that `do` notation could be a useful mechanism for achieving either the ergonomics or the performance that…

I'm scratching my head at the premise of this comment. The grandparent is positing that monads/do-notation would not be useful in Rust; this one appears to be trying to accuse it of saying that an effect system in Rust is impossible? Nowhere does withoutboats say anything about an effect system, or that anything is impossible. Did you reply to the wrong comment?

Re: Async and Await in Rust: a full proposal

#139

Post by AndyKelley » Mon, Jul 16, 2018, 3:25 AM UTC

kibwen wrote: post #94

AndyKelley wrote: post #8

This is exciting. It allows programmers to model their problems in code that fully accounts for the parallelism. For comparison, here is async/await in Zig: https://ziglang.org/documentation/master/#Coroutines Zig decided to go the other way - when you async call a function, it does eagerly evaluate until the first suspend point. This is less overhead than immediately suspending, plus it removes the dependency of the…

Can you explain "this is less overhead than immediately suspending"? AFAICT Rust's approach is as low-overhead as it gets, since the inherent separation between future creation and future execution means that future creation doesn't need to have any cost at all. I'm also not sure it makes sense to refer to Rust's behavior as "immediately suspending", since it's not suspending anything: until someone chooses to start…

My understanding is that Rust uses LLVM coroutines[1]. In order to have the behavior where the function does not start executing immediately, you would follow the example that you can find by searching for "injected suspend point, so that the coroutine starts suspended". So what this looks like is:

* Function call

* The coroutine creates its frame (I believe this maps to "future creation".)

* Function return (the injected immediate suspend)

* (sometime later) Put the work on the event loop

* Function call (suspend resume)

* Function executes until a suspend point

Eager execution has no injected immediate suspend, so it looks like this:

* Function call

* The coroutine creates its frame

* The function executes until a suspend point (function return)

That's it. The coroutine is responsible for making sure that it gets resumed appropriately if it suspends. Await doesn't do anything with an event loop; it just suspends and then puts the suspended coroutine handle in the target coroutine's frame with an AtomicRMW. If it turns out the target coroutine already completed, then it grabs the result, destroys the target coroutine, and cancels suspending (which is a jmp instruction). Otherwise the suspend completes and the target coroutine will resume the suspended one when it completes.

> If you have a program that only uses async & await and no concurrency primitives, the code in your program will execute in a defined, statically known, linear order.

This is true with eager execution as well. You can see some examples here [2].

One more side note, how eager execution was valuable to me in the self-hosted compiler:

    pub async fn renderToLlvm(comp: *Compilation, fn_val: *Value.Fn, code: *ir.Code) !void {
        fn_val.base.ref();
        defer fn_val.base.deref(comp);
        // ...
    }

At the callsite we make an async call to renderToLlvm, passing in a ref-counted fn_val. If the body didn't execute immediately, the callsite might deref fn_val and destroy it before renderToLlvm gets a chance to add a reference, but because of eager execution, the ref is guaranteed.

[1]: http://llvm.org/docs/Coroutines.html

[2]: https://github.com/ziglang/zig/blob/363f4facea7fac2d6cfeab9d...

Re: Async and Await in Rust: a full proposal

#140

Post by Matthias247 » Mon, Jul 16, 2018, 3:31 AM UTC

gpderetta wrote: post #115

Matthias247 wrote: post #55

Earlier quoted context omitted.

Maybe because most future implementations (e.g. in Javascript, the proposed C++ solution, Seastar, etc) work by scheduling a continuation on an event loop. Which obviously requires at least some form of dynamic memory for queuing up these continuations.

I think seastar futures are allocation free. Standard c++ futures are not really a paragon of efficiency or good design. Still no GC though.

I haven't read the code, but there are 2 areas where I expect allocations:

- The continuation which is passed to .then, and which is typically a closure, must be type-erased, which requires an allocation. Storing the continuation in a std::function would allocate too. A short glance at https://github.com/scylladb/seastar/blob/master/core/future.... also confirms that there is a make_unique there.

- Since continuations are most likely not called inline on completion but deferred into the next eventloop iteration there needs to be a dynamically sized queue to hold the ready continuations. I am not 100% sure if that's the case for seastar too, but I would guess so.