4 ms·

How does the zero-cost abstraction work? Say we make a Future<Int> and then chain `.map(|x| x+1)` on a dynamic number of times (N). Presumably this requires st

How does the zero-cost abstraction work? Say we make a Future<Int> and then chain `.map(|x| x+1)` on a dynamic number of times (N). Presumably this requires storing at least N function pointers. How can we store these N function pointers with zero cost? If it only takes one allocation, where does the N-1 future store its function pointers?

Gankro 10y ago
Each chain produces a different static type. If you want to do a dynamic amount of chains (which seems strange to me? Got an example?) you would need to allocate and use dynamic dispatch, yes. Basically `MyFuture.map(x)` => `Map<MyFuture, X>` `MyFuture.map(x).map(y)` => `Map<Map<MyFuture, X>, Y>` This is obviously disgusting to expose to users, which is one of the reasons this post uses the `impl Trait` syntax to cover it up and say "well it's something with the right interface, the compiler knows it (so no need to do dynamic dispatch), don't worry about it".
- ridiculous_fish 10y ago
  Thanks for your answer. Here's a more realistic example. Say we have a file.close() function that returns a Future<Void>, indicating when the close is complete. Now we want to make a Future for closing a list of files: let fut = Future<void>::new(); let v = vec![file, file2, file3]; for file in v.into_iter() { fut = fut.and_then(file.close()); } Is this possible with this API, or would the assignment to `fut` break because we now have a different type? With traditional Futures I'd expect this to look like a sort of linked-list of closures (definitely lots of allocation). What does it end up looking like under the hood with zero-cost Rust futures?
  - tyoverby 10y ago
    You are correct in assuming that the assignment would be a type error. Similar to other languages, you'd have to allocate. In rust, it would probably look like: let mut fut: Box<Future<()>> = Box::new(Future<()>::new()); and then fut = Box::new(fut.and_then(|| file.close()));
  - dbaupp 10y ago
    As discussed elsewhere in this thread, the most direct translation of that code would also be a linked list of futures, but I don't see an alternative for that sort of structure in general (i.e. every scheme for this sort of asynchrony will have a dynamic chain of allocations). However, the library does provide various abstractions that can abbreviate certain patterns and do them more efficiently than otherwise, e.g. http://alexcrichton.com/futures-rs/futures/fn.collect.html http://alexcrichton.com/futures-rs/futures/fn.collect.html for this case.
  - chme 10y ago
    Hmm... Shouldn't iterators be turned to streams? Like this: fut = v.into_iter().map(|file| file.close()).into_future();
AndrewGaspar 10y ago
I don't have that much experience with Rust, but all modern C++ compilers would have no problem inlining a similar abstraction at compile time. Remember that they're turning the whole future chaining into a switch statement inside of a function that is re-entered until a completion state is reached. Ala async/await in C#.
pcwalton 10y ago
> Say we make a Future<Int> and then chain `.map(|x| x+1)` on a dynamic number of times (N). Each time you call `.map` it statically produces a different type, similar to how iterators work. So you can't actually do that—unless you box the trait, producing an allocation chain. Of course, in the real world you'd probably not write it that way, and you'd maintain a counter and do the add in one go, which results in a static state machine.
dbaupp 10y ago
A "zero-cost abstraction" really means that abstraction doesn't impose a cost over the optimal implementation of the task it is abstracting. Some things—like chaining a dynamic number of (arbitrary) closures—fundamentally require some sort of dynamic allocation/construction, and so a zero-cost abstraction would be one that it only does that dynamic behaviour when necessary. If you don't need the dynamic behaviour, the library is a zero-cost abstraction, by statically encoding all the pieces at the type level: like Rust's iterators, each combinator function returns a new future type that contains all information about its construction and operations. To add to this, a closure in Rust is not a function pointer, each one a specialized struct containing exactly the captures, and thus this all gets put into the type information too, and everything can be be inlined together into a single pipeline. However, if you are dynamically constructing the future you'll have to opt-in to a uniform representation for the parts (i.e. erase the type information about the different constructions). This does indeed require allocating and storing pointers, but AFAICT this is required in any implementation, i.e. this library imposes no/little extra overhead over the optimal hand-written implementation. Furthermore, the static and dynamic parts can work together: if you have parts that are statically known, these can be constructed as a single static type (with no function pointers or allocations), and then boxed up into a dynamic future as a whole unit, which can then also form part of other static chains, meaning allocations and dynamic calls only need to happen when absolutely necessary.
- ridiculous_fish 10y ago
  Thanks for your reply. I'm still trying to understand what the restrictions look like. Say I sometimes have an outstanding asynchronous operation, i.e. validating some text in a document. I want to represent this by storing a Future representing this operation: struct Document { text:String, validating: Option<Future<Bool>> }; It seems like there's a problem: in order to have a struct of this type, we need to have the type of the Future, but the only way to have the type of the Future is to create the Future (and here we have None). It this struct possible? How would I initialize it with {"foo", None}?
  - grayrest 10y ago

Gankro 10y ago

Each chain produces a different static type. If you want to do a dynamic amount of chains (which seems strange to me? Got an example?) you would need to allocate and use dynamic dispatch, yes. Basically `MyFuture.map(x)` => `Map<MyFuture, X>` `MyFuture.map(x).map(y)` => `Map<Map<MyFuture, X>, Y>` This is obviously disgusting to expose to users, which is one of the reasons this post uses the `impl Trait` syntax to cover it up and say "well it's something with the right interface, the compiler knows it (so no need to do dynamic dispatch), don't worry about it".

ridiculous_fish 10y ago
Thanks for your answer. Here's a more realistic example. Say we have a file.close() function that returns a Future<Void>, indicating when the close is complete. Now we want to make a Future for closing a list of files: let fut = Future<void>::new(); let v = vec![file, file2, file3]; for file in v.into_iter() { fut = fut.and_then(file.close()); } Is this possible with this API, or would the assignment to `fut` break because we now have a different type? With traditional Futures I'd expect this to look like a sort of linked-list of closures (definitely lots of allocation). What does it end up looking like under the hood with zero-cost Rust futures?
- tyoverby 10y ago
  You are correct in assuming that the assignment would be a type error. Similar to other languages, you'd have to allocate. In rust, it would probably look like: let mut fut: Box<Future<()>> = Box::new(Future<()>::new()); and then fut = Box::new(fut.and_then(|| file.close()));
- dbaupp 10y ago
  As discussed elsewhere in this thread, the most direct translation of that code would also be a linked list of futures, but I don't see an alternative for that sort of structure in general (i.e. every scheme for this sort of asynchrony will have a dynamic chain of allocations). However, the library does provide various abstractions that can abbreviate certain patterns and do them more efficiently than otherwise, e.g. http://alexcrichton.com/futures-rs/futures/fn.collect.html http://alexcrichton.com/futures-rs/futures/fn.collect.html for this case.
- chme 10y ago
  Hmm... Shouldn't iterators be turned to streams? Like this: fut = v.into_iter().map(|file| file.close()).into_future();

AndrewGaspar 10y ago

I don't have that much experience with Rust, but all modern C++ compilers would have no problem inlining a similar abstraction at compile time. Remember that they're turning the whole future chaining into a switch statement inside of a function that is re-entered until a completion state is reached. Ala async/await in C#.

pcwalton 10y ago

> Say we make a Future<Int> and then chain `.map(|x| x+1)` on a dynamic number of times (N). Each time you call `.map` it statically produces a different type, similar to how iterators work. So you can't actually do that—unless you box the trait, producing an allocation chain. Of course, in the real world you'd probably not write it that way, and you'd maintain a counter and do the add in one go, which results in a static state machine.

dbaupp 10y ago

A "zero-cost abstraction" really means that abstraction doesn't impose a cost over the optimal implementation of the task it is abstracting. Some things—like chaining a dynamic number of (arbitrary) closures—fundamentally require some sort of dynamic allocation/construction, and so a zero-cost abstraction would be one that it only does that dynamic behaviour when necessary. If you don't need the dynamic behaviour, the library is a zero-cost abstraction, by statically encoding all the pieces at the type level: like Rust's iterators, each combinator function returns a new future type that contains all information about its construction and operations. To add to this, a closure in Rust is not a function pointer, each one a specialized struct containing exactly the captures, and thus this all gets put into the type information too, and everything can be be inlined together into a single pipeline. However, if you are dynamically constructing the future you'll have to opt-in to a uniform representation for the parts (i.e. erase the type information about the different constructions). This does indeed require allocating and storing pointers, but AFAICT this is required in any implementation, i.e. this library imposes no/little extra overhead over the optimal hand-written implementation. Furthermore, the static and dynamic parts can work together: if you have parts that are statically known, these can be constructed as a single static type (with no function pointers or allocations), and then boxed up into a dynamic future as a whole unit, which can then also form part of other static chains, meaning allocations and dynamic calls only need to happen when absolutely necessary.

ridiculous_fish 10y ago
Thanks for your reply. I'm still trying to understand what the restrictions look like. Say I sometimes have an outstanding asynchronous operation, i.e. validating some text in a document. I want to represent this by storing a Future representing this operation: struct Document { text:String, validating: Option<Future<Bool>> }; It seems like there's a problem: in order to have a struct of this type, we need to have the type of the Future, but the only way to have the type of the Future is to create the Future (and here we have None). It this struct possible? How would I initialize it with {"foo", None}?
- grayrest 10y ago