Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Zero-cost futures in Rust

aturon.github.io

Post reply on HN
Print view View original

81–90 of 348 posts

Re: Zero-cost futures in Rust

#81

Post by dukerutledge »

GolDDranks wrote: post #79
dukerutledge wrote: post #73

Earlier quoted context omitted.

So, existentially quantified types?

Yes. However, there isn't full support of existential types in the horizon – only returning them from a function (and using them inside the caller, as the type inference allows this). This resolves some specific pain points of the current Rust experience. There may or may not be some extensions (like storing them in fields of structs) in the future. Note that Rust supported existentials before too, in the form of tra…

Yeah, since rust is eager existential types seem like a necessary evil.

Re: Zero-cost futures in Rust

#82

Post by Gankro »

ridiculous_fish wrote: post #78

How does the zero-cost abstraction work? Say we make a Future 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?

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.map(x).map(y)` => `Map, 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".

Re: Zero-cost futures in Rust

#83

Post by AndrewGaspar »

ridiculous_fish wrote: post #78

How does the zero-cost abstraction work? Say we make a Future 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?

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#.

Re: Zero-cost futures in Rust

#84

Post by rdtsc »

As mentioned in the post, given Rust wants to operate in the same space as C, this approach makes sense. However from a higher level, building more complex concurrent systems, dealing with futures/deferred-s/promises and/or a central select/epoll/kqueue reactor loop gets daunting and doesn't mix with complex business rules.

Deferred based approach has been a round for many years. I experienced it by using Twisted (Python framework) for 5 or so years. And early on it was great However when we switched to using green threads, the logic and amount of code was greatly simplified.

So wondering if Rust provides any ability to add that kind of an N:M threading approach. Perhaps via an extension, macro or some other mechanism.

Note that in C, it being C such things can be done with some low level trickery. Here is a library that attempt that:

http://libmill.org/

And there were a few others before, but none have taken off enough to become mainstream.

Re: Zero-cost futures in Rust

#85

Post by comex »

astn wrote: post #63
masklinn wrote: post #32

Earlier quoted context omitted.

> 2 - no allocation : , does'nt the lambda closure need to be allocated somewhere ? I expect it is embedded in the state machine structure. In Rust (and C++) lambdas/closures are "value types".

In C++ lambdas have limited size (about 3 machine words). If it's context is larger than that, the data may be allocated on heap (if compiler can't optimize that allocation out).

What you're talking about is std::function, a wrapper around raw lambda objects that performs dynamic dispatch. Since any lambda can be wrapped in std::function yet std::function, like all C++ types, must have a fixed size, it uses the heap as you say.

If you stick to the raw lambdas, however, the compiler knows the size and doesn't need to use the heap. Only problem is that their type can't be named. In C++, you can work around this with auto.

Without getting too much into it, Rust has a similar distinction between raw lambdas and Box. This library uses the former.

Re: Zero-cost futures in Rust

#86

Post by pcwalton »

ridiculous_fish wrote: post #78

How does the zero-cost abstraction work? Say we make a Future 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?

> Say we make a Future 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.

Re: Zero-cost futures in Rust

#87

Post by steveklabnik »

rdtsc wrote: post #84

As mentioned in the post, given Rust wants to operate in the same space as C, this approach makes sense. However from a higher level, building more complex concurrent systems, dealing with futures/deferred-s/promises and/or a central select/epoll/kqueue reactor loop gets daunting and doesn't mix with complex business rules. Deferred based approach has been a round for many years. I experienced it by using Twisted (Py…

Yes, this is the lowest layer of the story. For actually writing an app, writing something higher-level makes sense: consider the relationship between raw futures and Finagle, for example. You have to build out the lower layers before you can add the upper ones, though.

Rust doesn't natively supply anything like green threads, as they have too heavy of requirements. But there are librarys that can implement them, since Rust is so low-level: https://crates.io/crates/mioco as an example.

Re: Zero-cost futures in Rust

#88

Post by dbaupp »

ridiculous_fish wrote: post #78

How does the zero-cost abstraction work? Say we make a Future 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.

Re: Zero-cost futures in Rust

#89

Post by aturon »

jerf wrote: post #76
Manishearth wrote: post #47

I'm rather surprised by the benchmark; I would expect the Go benchmark to be faster than Java (and the fact that it isn't may indicate some improvements that can be done to fasthttp by learning from rapidoid or minihttp). Then again, the difference isn't that much, so it just could be implementation details that would require a total refactor to fix.

You may find this makes somewhere more sense to think of it as ~5.3 microseconds per request for fasthttp vs. ~4.8 microseconds for Java vs. ~4.3 for Rust. It's 40 microseconds or so for the standard lib Go. I'm just eyeballing the graph but this should be close enough (dominated by local CPU variances and such). Just as some people point out that "gallons per mile" is a more intuitively useful way of thinking, I thi…

Thanks for this comment! I actually totally agree with this perspective, and wish I'd used your suggested scale in the post.

Re: Zero-cost futures in Rust

#90

Post by alexcrichton »

michaelmior wrote: post #66

Curious if someone has tried this and Eventual[0] with any thoughts on how they compare. https://github.com/carllerche/eventual

The futures crate is intended to be the successor to eventual, the author of which, Carl, helped us with some key insights in the futures crate as well.
Post reply on HN