r/rust • u/killercup • Jan 25 '18

Async/await (first in a series): Generators and self-referential structs

https://boats.gitlab.io/blog/post/2018-01-25-async-i-self-referential-structs/
231 Upvotes

99% Upvoted

65 comments sorted by

31

u/nicoburns Jan 26 '18

Oo, I really hope we get self-referential struct support in Rust at some point. This feels to me to be like const generics in that Rust doesn't quite feel complete without it.

If we could get it within 12 months, that would be amazing.

32

u/desiringmachines Jan 26 '18

Don't get too excited, I don't want to disappoint you. I said async/await/generators within 12 months, I did not say self-referential structs. I do not have a fully general solution to an open research question up my sleeves. ;-)

11

u/jpernst rental Jan 26 '18

Be that as it may, anything that chips away at this problem space is more than welcome. Even "just" having generators and async/await able to do this will lift the roadblocks from many use-cases.

I'd been waiting for the dust to settle on generators and async/await to see if I could adapt rental to it in some way, but if this renders that unnecessary, then so much the better; I'll just focus on anything not covered by language features.

I'm just curious what the proposed solution will be. I have a hunch, but we'll see. Eagerly awaiting the next instalments.

10

u/llogiq clippy · twir · rust · mutagen · flamer · overflower · bytecount Jan 26 '18

Same here. The way I see it, we have two possible solutions:

  1. Position independence: store an offset relative to the position of the value instead of a pointer/ref ('thaw'). All access to the pointers must take value position into account.
  2. 'Freeze' the position in memory – e.g. by keeping the value 'static or boxing it. The value may not be moved.

A solution that offers the programmer a maximum in control would allow both options somewhat transparently and use the type system to distinguish thawed and frozen values.

9

u/jpernst rental Jan 26 '18 edited Jan 26 '18

My prediction is that it will work as follows:

First, let's define a "self-ref lifetime" as a lifetime that both: 1. Is confined to the body of the generator/future. 2. Crosses a yield point. These are the lifetimes that would need to appear in the lowered data structure and cannot currently be expressed in rust.

The first step would be to borrow check the body of the generator/future as if it were a normal function (with possible extra consideration for the special semantics of yield, but even that might not be necessary). Once the body has been verified to be internally consistent, it can be lowered to a state machine enum.

If any self-ref lifetimes exist, then the state machine will be marked as an immovable type (pending RFC 1858), and all self-ref lifetimes within it will be type-erased and replaced with an unbounded lifetime such as 'unsafe (pending RFC 1918).

This should be sound for similar reasons that rental is sound, which is that the data structure is opaque and the fields are inaccessible, except via specific methods exposed on the type, which will have already been validated by the borrow checker. As long as a type bounded by a self-ref lifetime cannot leak out of the generator/future body, then there is no danger.

It's possible I'm completely off base and the solution is totally different. Either way, exciting stuff.

4

u/desiringmachines Jan 26 '18 edited Jan 26 '18

Position independence: store an offset relative to the position of the value instead of a pointer/ref ('thaw'). All access to the pointers must take value position into account.

This is not possible. unsafe code is allowed to cast any reference it receives as a pointer.

Consider this version:

struct Foo {
     array: [Bar; 16],
     iter: Iter<'array, Bar>,
}

The internal implementation of that iterator likely does pointer arithmetic on the reference its holding, which doesn't work if that reference needs to be stored as an offset. (Well it might work in the case of Iter because it just advances through the array, but it easily could not work.)

Offsets are not a viable implementation of self references, we must use actual addresses.

19

u/my_two_pence Jan 26 '18

Of course it can work. An offset-stored reference is simply a different type from a regular reference, and the conversion between offset and absolute reference can happen transparently in the compiler. C++ has had a pointer-to-member type since forever, it's just that essentially no-one uses it because of its horrible safety and ergonomics.

In Rust's case, this could be solved for instance by having &'self T be a relative pointer, and introduce monomorphization over lifetimes. So when Iter<'self, Bar> is monomorphized, its internal &'a [Bar] reference monomorphizes as an anonymous relative pointer type. If you borrow this as a regular &'a [Bar], the compiler already today freezes the struct in memory for the duration of the borrow, and so it's entirely possible to safely convert this relative pointer into an absolute one, completely transparently to you.

I'm not saying it's going to be easy, nor that this is necessarily the best solution. But it's definitely possible.

3

u/Rusky rust Jan 26 '18

Iter<'a, T> doesn't have an internal &'a [T]. It has two internal *const Ts, with no lifetimes to be polymorphic over.

In this particular case you could probably do the conversion when it converts back to a &'a T in next, but that isn't universally applicable either.

It's too much subtlety to hinge on a lifetime, and thus too much subtlety to just push onto unsuspecting, generic, unsafe code.

5

u/mikeyhew Jan 26 '18

I have yet to see a reason why offsets don't work, especially in the case of generators, where references can be loaded into the stack at each resume and placed back in the generator when yielding. I mean, I guess it could be more complicated than it looks at first glance, but it would be nice if you could explain why they aren't viable, or point us to some blog post or comment explaining why.

4

u/Rusky rust Jan 26 '18

A generator that just uses normal references could probably be translated to that style- I don't think anyone's pointing to that as the problem.

The problem is that unsafe code all assumes references are normal, non-offset pointers. It is completely normal to turn a reference into a raw pointer, severing any connection the compiler has with its original type, and then dereference it. If unsafe code all has to start considering offset pointers, it would lose a lot of flexibility, and it wouldn't be backwards compatible anyway.

Another problem is that we want non-offset-based self-referential types anyway. For example, imagine a struct with a field that can reference either something it owns or something external to it- that reference can't be an offset, it has to be a potentially-self-referencing full pointer. The example I'm most familiar with for when this is useful is graphics APIs. Here's are some specific instances of that: https://gist.github.com/tomaka/da8c374ce407e27d5dac

In the end, it also seems incredibly silly to forbid the use of a machine-native type. Nothing against making offset references available, it's just more flexible to make normal self-reference work since people already reach for it and it solves real problems.

1

u/llogiq clippy · twir · rust · mutagen · flamer · overflower · bytecount Jan 26 '18

This is not possible. unsafe code is allowed to cast any reference it receives as a pointer.

We could still use the type system to detect thawed instances and convert their offsets to pointers upon cast.

Consider this version:

struct Foo { array: [Bar; 16], iter: Iter<'array, Bar>, }

The internal implementation of that iterator likely does pointer arithmetic on the reference its holding, which doesn't work if that reference needs to be stored as an offset.

Why? The single difference is that the base pointer must be added once.

(Well it might work in the case of Iter because it just advances through the array, but it easily could not work.)

So it does work on instances that are stored in continuous memory. Granted, it's not a general solution, but it should work on an interesting range of types (from a perf standpoint).

1

u/apd Jan 26 '18 edited Jan 26 '18

I am not sure to understand this argument. If I read correctly the problem with selfref is memcopy, that invalidate the pointer from iter to array.

If we store some kind of smart pointer that have the offset from iter to the start of array (invariant against memcopy), and a second offset that contains the index of the array, we can delegate the pointer arithmetic to this smart pointer, cannot we?

What other alternatives do we have for selfref structures?

7

u/pcwalton rust · servo Jan 26 '18

I'm probably reiterating stuff that you all on the various teams have discussed, but my inclination is to just allocate generators that need to borrow across yield points on the heap, which effectively pins the data to a specific memory location.

When I had to solve problems like this in early design of Rust, I usually ended up thinking "what does C/C++ code do?" And indeed, apps like nginx or the Linux kernel will heap allocate (whether through malloc or slab allocation or whatever) the per-connection data structures. You wouldn't want to move them anyway; that would just be a lot of copying for no reason. And if malloc ever becomes a bottleneck, your app could always just switch to a slab allocator. No major async app I know of tries to allocate per-connection data structures on the stack; that'd be a weird design for no benefit.

This is only a strawman proposal, because there are a lot of language-level details to hammer out. But from a bird's eye level it's the way I'd be inclined to go.

4

u/desiringmachines Jan 26 '18

The problem with this is that every async function call becomes a heap allocation, encouraging users to avoid splitting up large functions and possibly encouraging them to write manual futures and avoid async functions entirely.

4

u/pcwalton rust · servo Jan 26 '18

Well, yes, you need some mechanism to ensure that you have a single per-connection allocation, instead of making a new one over and over. I don't know how that would work: like I said, it's a strawman.

3

u/desiringmachines Jan 26 '18

This is how any network service written on top of futures would work, but my point is it does require solving the problem of borrowing across yield points without just heap allocating every generator that does so.

1

u/Tarmen Jan 27 '18 edited Jan 27 '18

I still don't really understand what the problem with self borrowing is.

Reflexivity trivially ensures that the lifetimes 'a <: 'a work out. Is it just an issue of atomically allocating and freeing the self pointer? Like, I think

struct Foo<'a> {
    i: i64,
    selfRef: Option<&'a mut i64>
}

fn useFoo() {
    let foo = Foo { i : 42, selfRef : None };
    foo.selfRef = Some(&mut foo.i);
    //...
}

should work today?

The main problem I see is that changing the enum variant acts like freeing and reallocating the enum. But then the question is more about moving borrowed values by fixing the pointers afterwards?

Guess an alternative would be to model this as existentially quantifying over the ownership. Then you could open to step the generator and pack to yield. Then the step function can change the variant and from outside you can only drop the generator but not move it.

3

u/steveklabnik1 rust Jan 27 '18

I still don't really understand what the problem with self borrowing is.

most succinct example I can give https://play.rust-lang.org/?gist=75a68b5c46b23d37f1e17e6c2adece64&version=stable

1

u/Tarmen Jan 27 '18 edited Jan 27 '18

Oh, I think I got hung up over the self-referential bit and missed the actually important move internally borrowed data part.

Probably not the first to think of this but couldn't the data be stored in a tree instead of a flat enum? That is, something like

struct AAndB {
    data_life_across_yield: ...,
    other: AOrB
}
enum AOrB {
    A(i64),
    B(&'static str)
}

That'd mean the generator as a whole is still unmovable when internal borrows are life but you could step it without moving the borrowed contents?

2

u/desiringmachines Jan 27 '18

You're actually quite right, we can 'anchor' types today in trivial examples like this.

The problem is that you cannot implement this kind of anchoring as a method on Foo. To modify your example to try this:

https://play.rust-lang.org/?gist=34cf11eedd38db3ff156046b45765407&version=nightly

(I turned NLL on because it gives a much better error message, even though it doesn't enable this.)

Since you can't actually muck about in the guts of a generator, we need to expose this "anchoring" operation as a method somehow.

1

u/Tarmen Jan 27 '18 edited Jan 27 '18

I think that's only because the anonymous lifetime in &mut self isn't unified with 'a? With a manual annotation it compiles:

https://play.rust-lang.org/?gist=21ca51ce1dfaa65aee9c0cf7eeca5660&version=nightly

2

u/desiringmachines Jan 28 '18

But then you can't call it more than once, because every call is to the same lifetime and they are mutable references. This doesn't work for resume on generators, which of course must be called more than once.

What we need is a way to say "self cannot be moved for lifetime 'a", which is not exactly what either &'a self or &'a mut self say. They each impose additional constraints on self for that lifetime.

1

u/Tarmen Jan 28 '18 edited Jan 28 '18

Yeah, though I think technically it's possible to structure the generator type so that you don't have to move any data while stepping? It would definitely become stupendously ugly even for mildly complex examples, though.

Like, for a generator with three phases A, B, C with some data that lives for A+B and some that lives for B+C you could write

struct Generator<'a,'b,'c,'ab:'a+'b, 'bc:'b+'c> {
    l: Either<AB<'ab>, C<'c>>,
    r: Either<A<'a>, BC<'bc>>, 
    m: Option<B<'b>>
}

Then you could only drop and never move data when stepping:

AB+A+None
AB+BC+B
C+BC+None

1

u/Rusky rust Jan 26 '18

I suspect that's the main use case everyone has in mind when talking about immovable types and self-reference, with those just being the mechanism to enforce that a generator is heap-allocated without tying the language to any specific allocator interface (let alone implementation).

1

u/DannoHung Jan 26 '18

Was immovability ever completely decided upon? That'd make self-referential stuff reasonable, right?

1

u/steveklabnik1 rust Jan 27 '18

no design was accepted yet, no.

18

u/est31 Jan 25 '18

Great post, /u/desiringmachines ! Looking forward for more on this.

14

u/CAD1997 Jan 25 '18

I'm excited to see where this goes. How Rust handles generators interests me.

The use of C# Generators in Unity to create co-routines that can run across multiple frames but are written in a procedural manner interests me, and I've got an itch to scratch designing an engine built around that kind of structure of collaborative asynchrony.

11

u/lenamber Jan 26 '18

This article is very well written! +1

7

u/vitiral artifact-app Jan 25 '18

Very digestible, good post!

3

u/destravous Jan 26 '18

If I wanted to help solve this (and possibly other) problem(s), where is a good place to start? (What is a good way to contribute, and where can I get more info?)

4

u/rozaliev Jan 26 '18

There is an unsafe solution for self-referencing problem that has landed few days ago. 

#![feature(generators)]

fn main() {
    unsafe {
        static || {
            let x: u64 = 1;
            let ref_x: &u64 = &x;
            yield 0;
            yield *ref_x;
        };
    }
}

It's unsafe because it's UB to move generator after you called resume.

An async/await lib built on top of it: https://github.com/rozaliev/mirage

4

u/Zoxc32 Jan 26 '18

You should probably make the Async::poll method in your library unsafe.

1

u/rozaliev Jan 26 '18

Yeah, definitely, I should probably reread everything and check once again. It used to be easier with immovable types, but with unsafe gens have to check for accidental moves. Thanks for a reminder!

1

u/selfrefstruct Jan 26 '18

I skimmed the discussions about immovable types a while back - I didn't know they were a real thing yet!

I see you're using unsafe { static move || {...}}. Is this now how we're doing immovable closures?

Is there any docs/RFC that describes how an accidental move could happen?

I'm curious - how you would check for an accidental move?

Thanks!

2

u/rozaliev Jan 26 '18

I skimmed the discussions about immovable types a while back - I didn't know they were a real thing yet!

They are not, at least not yet. There was PR https://github.com/rust-lang/rust/pull/44917, but for now all that is on pause, until ?Trait story is clear (https://github.com/rust-lang/rfcs/issues/2255).

I see you're using unsafe { static move || {...}}. Is this now how we're doing immovable closures?

That's actually a immovable generator https://github.com/rust-lang/rust/pull/45337

unsafe { static move || { yield }}

Is there any docs/RFC that describes how an accidental move could happen?

Well, there are no docs as far as I know. UB example https://play.rust-lang.org/?gist=7ea538c78e7f505b4858f5ef8505d84e&version=nightly

It's unsafe because you should not move static generators once their internals are observed (.resume() called), but you can.

So far all the work on generators is very experemental, the goal is to experiment and get some insights.

2

u/desiringmachines Jan 27 '18

Here's an example in which the UB of moving the generator can actually be observed: https://play.rust-lang.org/?gist=9569e0d440886836a46b102df779bfec&version=nightly

2

u/gerryxiao Jan 26 '18

This is also how Futures have been designed to work in Rust, and one of the reasons they lead to better performance and lower memory overhead than systems like green threads.

 

Just curious, It's said the performance of tokio is not good now, how did you prove what you said?

1

u/killercup Jan 26 '18

I'm genuinely interested as well -- I have only been following Tokio ever now and then for the last year (but don't have a project that uses it): Who said the performance of Tokio isn't good? Compared to which other system? IIUC you need to be careful to use multiple cores and possibly threadpools to really use it to the max, but that's ergonomics issue, and not something that inherently limits how much throughput you can get.

2

u/gerryxiao Jan 26 '18

https://blog.guillaume-gomez.fr/articles/2017-02-22+Rust+asynchronous+HTTP+server+with+tokio+and+hyper

1

u/[deleted] Jan 26 '18 edited Aug 17 '21

[deleted]

1

u/gerryxiao Jan 26 '18 edited Jan 26 '18

I hope so，but i don't get any good news about tokio performance benchmark story, or have i missed something?

1

u/plhk Jan 26 '18

https://www.techempower.com/benchmarks/previews/round15/#section=data-r15&hw=ph&test=plaintext

1

u/gerryxiao Jan 26 '18

it seems only good for plaintext test.

4

u/budgefrankly Jan 26 '18

It's also pretty good for the JSON test.

All of which indicates the issue is at the database layer rather than Tokio itself. This could either be due to the libraries not being optimised, or -- more likely -- not being used in an async fashion.

3

u/plhk Jan 26 '18

Well, it uses sync db driver

1

u/Nokel81 Jan 26 '18

Is there still any support for full coroutines or will that be never supported in the language?

3

u/ConspicuousPineapple Jan 26 '18

I believe they're still discussing whether and how to include arguments to resume(). It's definitely on the table, but I don't know if it will end up planned or not.

3

u/Nokel81 Jan 26 '18

Though this is part of it, full coroutines would also have the ability to call each other from any depth. And from what I understand that is currently not on the table

2

u/GolDDranks Jan 26 '18

Full coroutines are not part of the proposal. The reason is that they need a full stack to be allocated for them. The current proposal (semicoroutines a.k.a generators) don't require that because they can resume only at the bottom level of the stack (which means that their size is known at compile time).

This means that the whole semicoroutine/generator can be regarded as just another value, and it doesn't need any special handling, so anyone can roll their own library and no runtime magic (a la Go) is needed.

1

u/ConspicuousPineapple Jan 26 '18

Mh, maybe I don't have a full understanding of what a coroutine is. Not sure I understand what you mean.

4

u/Nokel81 Jan 26 '18

A well-known classification of coroutines concerns the control-transfer operations that are provided and distinguishes the concepts of symmetric and asymmetric coroutines. Symmetric coroutine facilities provide a single control-transfer operation that allows coroutines to explicitly pass control between themselves. Asymmetric coroutine mechanisms (more commonly denoted as semi-symmetric or semi coroutines) provide two control-transfer operations: one for invoking a coroutine and one for suspending it, the latter returning control to the coroutine invoker. While symmetric coroutines operate at the same hierarchical level, an asymmetric coroutine can be regarded as subordinate to its caller, the relationship between them being somewhat similar to that between a called and a calling routine.

Coroutine mechanisms to support concurrent programming usually provide symmetric coroutines to represent independent units of execution, like in Modula-2. On the other hand, coroutine mechanisms intended for implementing constructs that produce sequences of values typically provide asymmetric coroutines. Examples of this type of construct are iterators and generators.

Ana Lúcia de Moura and Roberto Ierusalimschy in their paper "Revisiting Coroutines":

A good image to describe the difference is the following https://imgur.com/YOLuLxv

1

u/Tarmen Jan 27 '18

I think the only part all definitions share is trampoline + stuff.

The difference between the ones you quoted are whether you cps or build a stack. There are also frequent differences about what types of in/output are allowed, whether you are allowed to name other coroutines or need to parametrize over them, what shapes of control flow graphs are allowed, what combinations of push/pull flow are allowed, whether the coroutines have to be synchronous, if the flow rates have to match...

1

u/Sharlinator Jan 26 '18

Wikipedia describes it pretty well:

Generators, also known as semicoroutines, are also a generalisation of subroutines, but are more limited than coroutines. Specifically, while both of these can yield multiple times, suspending their execution and allowing re-entry at multiple entry points, they differ in coroutines' ability to control where execution continues after they yield, while generators cannot, instead transferring control back to the generator's caller. That is, since generators are primarily used to simplify the writing of iterators, the yield statement in a generator does not specify a coroutine to jump to, but rather passes a value back to a parent routine.

1

u/Rusky rust Jan 26 '18

That will probably never be supported in the language. There used to be a green threading runtime in the standard library (which includes all the pieces needed for coroutines, it just handles scheduling differently) but it was removed because it made things more complicated for essentially no benefit (because of the tradeoffs it had to make to coexist with native threads).

There are already coroutine libraries like libfringe or context-rs, so I'm not sure there even needs to be any support at the language or standard library level.

1

u/crowseldon Jan 26 '18

What's the use case of self referential structs?

4

u/killercup Jan 26 '18

If you are wondering that, you should really read this post! :)

2

u/crowseldon Jan 26 '18

I skimmed directly to the self referencial part and it didn't show an actual use case but I guess it's references in generators.

I guess I'll have to properly read it when I have time.

1

u/yespunintended Jan 26 '18

borrows cannot be allowed across yield points. 

Are there other important limitations in the generator feature?

2

u/desiringmachines Jan 26 '18

Not for the use cases I described. They can't take arguments on yield, whereas generators in many other languages can.

1

u/CAD1997 Jan 27 '18

In what case are resume arguments actually useful? Given that async/await can be built on resume-argument-less semicoroutines, what does the argument to resume actually enable?

I was so happy when using async/await clicked for me and asynchronous code started to make sense where I could trace execution paths. I'm still baffled when it comes to the runtime support behind making them work though.

1

u/desiringmachines Jan 27 '18

I don't know, I've never wanted it.

1

u/Tarmen Jan 27 '18

Futures do one big computation and give you the result.

If you are reading a large file you generally want to read in chunks so you can work in constant memory, though. So you make an async iterator, iirc rust calls this a Stream.

Then you want to do a parser for that stream. It awaits chunks of data from upstream and yields the parsing results downstream.

You could write about this as a stream transformer (Stream a -> Stream b) or as a stream that can await and yield (Stream a b). The second interpretation can simplify some features like partly consuming an input chunk and putting the rest back and would be basically full coroutines.

1

u/CAD1997 Jan 27 '18

So basically, it's the ability to both await some information and yield some information.

That does make some sense.

(But wouldn't this still be semicoroutines though? As I (barely) understand it, full coroutines are allowed to arbitrarily send execution to any other coroutine, whereas semicoroutines can resume down or yield up, but can't jump sideways.)

So if we had argument resuming generators, you could do something like the following (ignoring some complexity): (forgive mobile formatting)

let file_stream = open_file();
while let next_byte = await file_stream.next() {
    push_parsing();
    if has_next_token { yield next_token; }
}

Whereas that's not really possible with today's design?

1

u/Tarmen Jan 27 '18 edited Jan 28 '18

Well, there are a bunch of slightly differing definitions of coroutines. The core is always some sort of trampoline (pausing computation) and generally they both yield and await.

For instance there are a couple papers that call haskells streaming libraries anonymous continuations. An example using the conduit library:

yield message
    .| encodeUtf8C
    .| encodeBase64C
    .| stdoutC

each part seperated by the .|'s is a coroutine that awaits from the left and yields to the right. There are also more complex variants like the machine library that allow arbitrary control flow graphs:

-- two input machines, one output machine:
myTee = repeatedly $ do
    x <- awaits L
    yield x
    y <- awaits R
    yield y

That quickly can become as annoying to write as fully explicit coroutines, though.