Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Generator size: borrowed variables are assumed live across following yield points #59087

Open
Matthias247 opened this issue Mar 11, 2019 · 18 comments

Comments

@Matthias247
Copy link
Contributor

@Matthias247 Matthias247 commented Mar 11, 2019

Maybe a duplicate of #52924, but maybe also something else.

I observed that the sizes of Futures generated by async fns can grow exponentially.
The following code shows an async fn, which produces a 1kB future. Each layering in another async fn doubles it's size:

#![feature(async_await)]

async fn i_am_1kb() -> bool
{
    let x: [u8; 1*1024] = [0; 1*1024];
    async{}.await;
    let _sum: u8 = x.iter().sum();
    true
}

fn main() {
    let fut1 = i_am_1kb();
    dbg!(std::mem::size_of_val(&fut1));

    let composed_1 = async {
        let inner = i_am_1kb();
        inner.await;
    };
    dbg!(std::mem::size_of_val(&composed_1));

    let composed_2 = async {
        let inner = i_am_1kb();
        dbg!(std::mem::size_of_val(&inner));
        inner.await;
    };
    dbg!(std::mem::size_of_val(&composed_2));

    let composed_3 = async {
        let inner = async {
            let inner = async {
                i_am_1kb().await;
            };
            dbg!(std::mem::size_of_val(&inner));
            inner.await;
        };
        dbg!(std::mem::size_of_val(&inner));
        inner.await;
    };
    dbg!(std::mem::size_of_val(&composed_3));
}

Output:

[src/main.rs:16] std::mem::size_of_val(&fut1) = 1032
[src/main.rs:22] std::mem::size_of_val(&composed_1) = 1036
[src/main.rs:29] std::mem::size_of_val(&composed_2) = 2072
[src/main.rs:44] std::mem::size_of_val(&composed_3) = 4168

It doesn't matter whether the statement between the future generation and await! references the future or not. A simply println("") will have the same effect.
Only if the future is directly awaited (as in composed_1) the size will stay constant.

cc @cramertj , @nikomatsakis , @Nemo157

@cramertj
Copy link
Member

@cramertj cramertj commented Mar 11, 2019

Closing as a sub-issue of #52924. (I've edited the top message in that thread to reference this one)

@cramertj
Copy link
Member

@cramertj cramertj commented Mar 11, 2019

@Nemo157
Copy link
Member

@Nemo157 Nemo157 commented Mar 11, 2019

There definitely seems to be something causing locals to be unnecessarily put into the generator struct instead of staying as true-locals. Using a simplified function (with the same i_am_1kb as above)

async fn composed() {
    let inner = i_am_1kb();
    { let _foo = &inner; }
    await!(inner);
}

and running cargo rustc -- -Z dump-mir=generator to dump the mir, the liveness analysis shows that inner is correctly considered dead after being moved to pinned in the await! macro (and so is not alive over a yield), but it is still being put in the generator.

@Zoxc
Copy link
Contributor

@Zoxc Zoxc commented Mar 11, 2019

@Nemo157 The generator transformation conservatively assumes that any borrow can be converted to a raw pointer and the locals can be accessed with that until their storage slot is dead. That's why inner is considered live during the await! here.

@cramertj
Copy link
Member

@cramertj cramertj commented Mar 11, 2019

Yeah, @eddyb and I discussed this at the all-hands, and that making a type implement Copy is actually a potential perf regression here, which is weird. For non-Copy types, you can assume no accesses after moving out of them, but for Copy types you can't necessarily do this.

@Nemo157
Copy link
Member

@Nemo157 Nemo157 commented Mar 11, 2019

Ok, so an optimisation to fix this example would be to add a less conservative check that can see when the borrow definitely wasn’t converted to a raw pointer. That seems relatively straightforward to check when the borrow never enters any unsafe code.

@cramertj
Copy link
Member

@cramertj cramertj commented Mar 11, 2019

add a less conservative check that can see when the borrow definitely wasn’t converted to a raw pointer

Note that for this to be very useful at all it would have to be able to see through functions (via MIR inlining) and intrinsics (e.g. size_of_val above).

@cramertj cramertj reopened this Mar 11, 2019
@cramertj cramertj changed the title async/await: Not directly awaiting an async fn doubles it's size Generator size: borrowed variables are assumed live across following yield points Mar 11, 2019
@Nemo157
Copy link
Member

@Nemo157 Nemo157 commented Mar 11, 2019

Can it not trust the lifetimes on safe functions signatures? size_of_val does not have a lifetime dependency so should be relied on to not stash a raw pointer to the reference away somewhere. (I guess this is an UCG question whether safe function boundaries are barriers that require safety to be upheld, and whether future unsafe code can allow prior safe code to violate lifetimes, i.e. is something like this sound or not).

@cramertj
Copy link
Member

@cramertj cramertj commented Mar 11, 2019

No, lifetimes in function signatures cannot necessarily be used to determine the scope of accesses to the resulting pointer. Without a memory model it's completely unclear when accesses would or wouldn't be allowed to the underlying memory. @RalfJung's work on stacked borrows is the only thing I'm aware of that would allow proper analysis, and in general anywhere there's a ref-to-ptr conversion, all bets are sort of off.

@tmandry
Copy link
Contributor

@tmandry tmandry commented Mar 11, 2019

I want to emphasize that this is still a problem even when the variable is not borrowed:

It doesn't matter whether the statement between the future generation and await! references the future or not. A simply println("") will have the same effect.

So there is likely progress to be made here without doing the analysis being discussed by @Nemo157 / @cramertj.

@Nemo157
Copy link
Member

@Nemo157 Nemo157 commented Mar 12, 2019

From skimming the MIR of

async fn composed() {
    let inner = i_am_1kb();
    { foo(); fn foo() { } }
    await!(inner);
}

it looks like that could be related to the unwind edge from the function call (and println! expands to a few function calls). Another optimization related to the one mentioned in #52924 that could fix this would be to suppress moving values where their lifetimes only intersect during the move, essentially re-using the same stack slot for both inner and pinned (from inside await!) and turning the move into a no-op.

(I tried a couple of other random snippets of code and couldn't see anything else done by println!() that caused the doubled size).

EDIT: Actually, because of how drop chains work it looks like it's going to be more complex than that since inner and pinned have overlapping lifetimes, I have a simpler example for which I'll try and create a chart of the MIR and open a separate issue about this.

@Nemo157
Copy link
Member

@Nemo157 Nemo157 commented Mar 12, 2019

Opened #59123 about the unwinding and drop interaction.

@nikomatsakis
Copy link
Contributor

@nikomatsakis nikomatsakis commented Mar 12, 2019

We discussed this issue and decided to label it as deferred for the purposes of stabilization -- it's a bit too broad. We might consider trying to fix specific instances of this problem. Certainly, to start, we would want to fix #52924 and revisit.

@cramertj
Copy link
Member

@cramertj cramertj commented Mar 19, 2019

#57478 contains a similar issue.

@tmandry
Copy link
Contributor

@tmandry tmandry commented Jul 8, 2019

The size growth in this issue now goes away when the size_of_val calls are replaced with an empty println!() (this was #59123).

However, I think we should leave this issue open to track the general behavior that borrowing a future and then awaiting it causes us to double-allocate space for it, with #62321 tracking the specific case of size_of_val.

@tmandry
Copy link
Contributor

@tmandry tmandry commented Jul 8, 2019

Here's the solution I mentioned in #62321 (comment):

  1. Smarter dataflow analysis that tells us when no more borrows or pointers of any kind exist (e.g. similar to what the borrow checker is doing, but stricter so we don't make unsafe code UB).
  2. If we want to handle cases like foo(&x), we'll need to inline those functions in MIR so we can apply our analysis (1) to them.

As noted by @cramertj and @withoutboats, there is an alternative that resolves most cases we care about: get rid of the move in await. This requires

  1. A drop with guaranteed move elision: either std::mem::drop, or an internal one we can lower to (#62508)
  2. Recognizing our future is StorageDead after it's dropped (#61015), so we don't break the existing optimization (PR #60187)
@tmandry
Copy link
Contributor

@tmandry tmandry commented Jul 8, 2019

I meant to say: Right now I prefer the approach of getting rid of the move in await, unless we hit some unforeseen problem with it.

Resolving the general problem of borrow-then-move would be nice, but it doesn't seem like the most bang for our buck at this point.

@tmandry tmandry mentioned this issue Jul 9, 2019
2 of 4 tasks
@eddyb
Copy link
Member

@eddyb eddyb commented Jul 9, 2019

It would be so much easier to do that drop in place and have borrowck understand the value is no longer accessible, if we were desugaring await in MIR building.
We can probably use an intrinsic for this. I think move_init_val has similar special handling?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
8 participants