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

Vec::pop() sometimes returns value inefficiently. #85365

Open
human-0 opened this issue May 16, 2021 · 5 comments
Open

Vec::pop() sometimes returns value inefficiently. #85365

human-0 opened this issue May 16, 2021 · 5 comments
Labels
A-collections Area: `std::collection` C-bug Category: This is a bug. I-slow Issue: Problems and improvements with respect to performance of generated code. T-libs Relevant to the library team, which will review and decide on the PR/issue.

Comments

@human-0
Copy link

human-0 commented May 16, 2021

I tried this code:

#[repr(align(32))]
#[derive(Copy, Clone)]
pub struct Data {
    u64s: [u64; 4],
    options: Option<(u64, u8, Option<u8>)>
}

pub fn len_minus_one(mut vec: Vec<Data>, value: &mut Data) {
   *value = vec[vec.len() - 1];
   vec.pop();
}

pub fn pop(mut vec: Vec<Data>, value: &mut Data) {
   *value = vec.pop().unwrap();
}

I expected to see this happen: The two functions generate similar assembly.

Instead, this happened: Vec::pop() uses far less efficient copying.

Meta

rustc --version --verbose:

<version>
binary: rustc
commit-hash: 88f19c6dab716c6281af7602e30f413e809c5974
commit-date: 2021-05-03
host: x86_64-pc-windows-msvc
release: 1.52.0
LLVM version: 12.0.0

It also happens on Nightly, although the generated assembly is much better.

Edit: It appears to be related to an Option holding the value, because the same behaviour is observed when using vec.get(vec.len() - 1).copied().unwrap() but not *vec.get(vec.len() - 1).unwrap().
Playground Link

@human-0 human-0 added the C-bug Category: This is a bug. label May 16, 2021
@jonas-schievink jonas-schievink added the I-slow Issue: Problems and improvements with respect to performance of generated code. label May 16, 2021
@LeSeulArtichaut LeSeulArtichaut added the T-libs Relevant to the library team, which will review and decide on the PR/issue. label May 17, 2021
@human-0
Copy link
Author

human-0 commented May 18, 2021

It seems that it is not specific to Vec::pop(), but Option in general. It even occurs with just *value = Some(data).unwrap();.

Playground Link

@nikic
Copy link
Contributor

nikic commented May 18, 2021

@human-0 Those playground links are the same :)

@human-0
Copy link
Author

human-0 commented May 18, 2021

Fixed.

@scottmcm
Copy link
Member

scottmcm commented May 18, 2021

@Moxinilian this seems like an issue that the match optimization you're working on in #85133 could potentially be able to help with (after MIR inlining), if you're looking for more test cases.

Here's another simple place where the mir-opt would be nice (though LLVM already handles it fine): https://rust.godbolt.org/z/oevPf6d6h

bors added a commit to rust-lang-ci/rust that referenced this issue Jul 25, 2021
…jgillot

MIR opt: separate constant predecessors of a switch

For each block S ending with a switch, this pass copies S for each of S's predecessors that seem to assign the value being switched over as a const. This is done using a somewhat simple heuristic to determine what seems to be a const transitively.

More precisely, this is what the pass does:
- find a block that ends in a switch
- track if there is an unique place set before the current basic block that determines the result of the switch (this is the part that resolves switching over discriminants)
- if there is, iterate over the parents that have a reasonable terminator and find if the found determining place is likely to be (transitively) set from a const within that parent block
- if so, add the corresponding edge to a vector of edges to duplicate
- once this is done, iterate over the found edges: copy the target block and replace the reference to the target block in the origin block with the new block

This pass is not optimal and could probably duplicate in more cases, but the intention was mostly to address cases like in rust-lang#85133 or rust-lang#85365, to avoid creating new enums that get destroyed immediately afterwards (notably making the new try v2 `?` desugar zero-cost).

A benefit of this pass working the way it does is that it is easy to ensure its correctness: the worst that can happen is for it to needlessly copy a basic block, which is likely to be destroyed by cleanup passes afterwards. The complex parts where aliasing matters are only heuristics and the hard work is left to further passes like ConstProp.

# LLVM blocker

Unfortunately, I believe it would be unwise to enable this optimization by default for now. Indeed, currently switch lowering passes like SimplifyCFG in LLVM lose the information on the set of possible variant values, which means it tends to actually generate worse code with this optimization enabled. A fix would have to be done in LLVM itself. This is something I also want to look into. I have opened [a bug report at the LLVM bug tracker](https://bugs.llvm.org/show_bug.cgi?id=50455).

When this is done, I hope we can enable this pass by default. It should be fairly fast and I think it is beneficial in many cases. Notably, it should be a sound alternative to simplify-arm-identity. By the way, ConstProp only seems to pick up the optimization in functions that are not generic. This is however most likely an issue in ConstProp that I will look into afterwards.

This is my first contribution to rustc, and I would like to thank everyone on the Zulip mir-opt chat for the help and support, and especially `@scottmcm` for the guidance.
@the8472 the8472 added the A-collections Area: `std::collection` label Feb 8, 2022
@scottmcm
Copy link
Member

@human-0 Did you really mean mut vec: Vec<Data> here? I would have expected vec: &mut Vec<Data>, which means the function isn't dropping the Vec any more and thus there's way less stuff generated.

There's still a small difference between the two, though: https://rust.godbolt.org/z/M7v1PMjfv

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
A-collections Area: `std::collection` C-bug Category: This is a bug. I-slow Issue: Problems and improvements with respect to performance of generated code. T-libs Relevant to the library team, which will review and decide on the PR/issue.
Projects
None yet
Development

No branches or pull requests

6 participants