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?
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.
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:
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}?
The construct wouldn't be valid as written for the reasons you mention. The blog post for this discussion glosses over the details by writing `impl Future<Item = Bool>` instead of the concrete type a future would have to have in Rust today.
I'm not an expert but one of the ongoing dicussions in the impl Trait RFC is where the construct can show up. The preliminary version can only appear as a return type from a function where the compiler can always determine the exact details at compile time depending on the chain of calls. I believe typing out the entire type of the future in the struct would work but, again, I only somewhat know my way around the language.
These are the two options. In the first, Box<Future> stores a "trait object", that is, a tuple of (data ptr, vtable ptr). In the second, there will be a struct for each type used to generate a StaticFoo.
impl Future for i32 {}
impl Future for f64 {}
fn main() {
let d = DynamicFoo {
text: String::from("foo"),
validating: Some(Box::new(5) as Box<Future>),
};
let s1 = StaticFoo {
text: String::from("foo"),
validating: Some(5),
};
let s2 = StaticFoo {
text: String::from("foo"),
validating: Some(5.0),
};
}
> 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.
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.
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".
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?
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).
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#.
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?