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

Missed optimization when using split_first #109328

Closed
xTachyon opened this issue Mar 18, 2023 · 4 comments · Fixed by #125347
Closed

Missed optimization when using split_first #109328

xTachyon opened this issue Mar 18, 2023 · 4 comments · Fixed by #125347
Labels
A-LLVM Area: Code generation parts specific to LLVM. Both correctness bugs and optimization-related issues. C-enhancement Category: An issue proposing an enhancement or a PR with one. C-optimization Category: An issue highlighting optimization opportunities or PRs implementing such E-needs-test Call for participation: An issue has been fixed and does not reproduce, but no test has been added. I-slow Issue: Problems and improvements with respect to performance of generated code. T-compiler Relevant to the compiler team, which will review and decide on the PR/issue.

Comments

@xTachyon
Copy link
Contributor

Impl 1:

pub fn f(input: &mut &[u64]) -> Option<u64> {
    match input {
        [] => None,
        [first, rest @ ..] => {
            *input = rest;
            Some(*first)
        }
    }
}

Impl 2:

pub fn f(input: &mut &[u64]) -> Option<u64> {
    let (first, rest) = input.split_first()?;
    *input = rest;
    Some(*first)
}

Godbolt: https://godbolt.org/z/aasq15z7a

These functions should be equivalent, but the second function generates one more if than the first one. This also happens when using .get(0) and then doing the slicing manually. I expected the impls to generate the same code.

@xTachyon xTachyon added the C-bug Category: This is a bug. label Mar 18, 2023
@JakobDegen JakobDegen added A-LLVM Area: Code generation parts specific to LLVM. Both correctness bugs and optimization-related issues. I-slow Issue: Problems and improvements with respect to performance of generated code. labels Mar 18, 2023
@JakobDegen
Copy link
Contributor

Quoting myself on Zulip:

I've seen this before too. The extra comparison is a null pointer check and is going to be the result of something creating a Option<&T>

@JakobDegen JakobDegen added C-enhancement Category: An issue proposing an enhancement or a PR with one. T-compiler Relevant to the compiler team, which will review and decide on the PR/issue. and removed C-bug Category: This is a bug. labels Mar 18, 2023
@nikic
Copy link
Contributor

nikic commented Mar 19, 2023

This is a metadata preservation failure during SimplifyCFG speculation: https://llvm.godbolt.org/z/frs8o853f

Preserving !nonnull here used to be illegal, but thanks to https://reviews.llvm.org/D141386 we are allowed to preserve it now. Only need to drop !noundef.

@nikic nikic self-assigned this Mar 22, 2023
@nikic
Copy link
Contributor

nikic commented Mar 22, 2023

Upstream patch: https://reviews.llvm.org/D146629

@nikic nikic added the E-needs-test Call for participation: An issue has been fixed and does not reproduce, but no test has been added. label Aug 14, 2023
@nikic nikic removed their assignment Aug 14, 2023
@nikic
Copy link
Contributor

nikic commented Aug 14, 2023

Fixed by #114048, needs codegen test.

@workingjubilee workingjubilee added the C-optimization Category: An issue highlighting optimization opportunities or PRs implementing such label Oct 8, 2023
tesuji added a commit to tesuji/rustc that referenced this issue May 20, 2024
tesuji added a commit to tesuji/rustc that referenced this issue Jun 8, 2024
tesuji added a commit to tesuji/rustc that referenced this issue Jun 9, 2024
bors added a commit to rust-lang-ci/rust that referenced this issue Jun 9, 2024
bors added a commit to rust-lang-ci/rust that referenced this issue Jun 10, 2024
bors added a commit to rust-lang-ci/rust that referenced this issue Jun 11, 2024
bors added a commit to rust-lang-ci/rust that referenced this issue Jun 13, 2024
@bors bors closed this as completed in 7ac6c2f Jun 14, 2024
matthiaskrgr added a commit to matthiaskrgr/rust that referenced this issue Jun 30, 2024
… r=Mark-Simulacrum

Small fixme in core now that split_first has no codegen issues

rust-lang#109328 (comment)

BTW, I have a crate implementing exactly this kind of an iterator: https://github.com/GrigorenkoPV/head-tail-iter and I was wondering if it would be worthwhile to try and make an ACP for it to get it included in std (or maybe itertools). My only doubt is that it kinda incentives writing O(n^2) algorithms and is not the hard to replace with a `while let` loop (just as in this PR).
matthiaskrgr added a commit to matthiaskrgr/rust that referenced this issue Jun 30, 2024
… r=Mark-Simulacrum

Small fixme in core now that split_first has no codegen issues

rust-lang#109328 (comment)

BTW, I have a crate implementing exactly this kind of an iterator: https://github.com/GrigorenkoPV/head-tail-iter and I was wondering if it would be worthwhile to try and make an ACP for it to get it included in std (or maybe itertools). My only doubt is that it kinda incentives writing O(n^2) algorithms and is not the hard to replace with a `while let` loop (just as in this PR).
matthiaskrgr added a commit to matthiaskrgr/rust that referenced this issue Jun 30, 2024
… r=Mark-Simulacrum

Small fixme in core now that split_first has no codegen issues

rust-lang#109328 (comment)

BTW, I have a crate implementing exactly this kind of an iterator: https://github.com/GrigorenkoPV/head-tail-iter and I was wondering if it would be worthwhile to try and make an ACP for it to get it included in std (or maybe itertools). My only doubt is that it kinda incentives writing O(n^2) algorithms and is not the hard to replace with a `while let` loop (just as in this PR).
rust-timer added a commit to rust-lang-ci/rust that referenced this issue Jun 30, 2024
Rollup merge of rust-lang#126906 - GrigorenkoPV:fixme-split_at_first, r=Mark-Simulacrum

Small fixme in core now that split_first has no codegen issues

rust-lang#109328 (comment)

BTW, I have a crate implementing exactly this kind of an iterator: https://github.com/GrigorenkoPV/head-tail-iter and I was wondering if it would be worthwhile to try and make an ACP for it to get it included in std (or maybe itertools). My only doubt is that it kinda incentives writing O(n^2) algorithms and is not the hard to replace with a `while let` loop (just as in this PR).
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
A-LLVM Area: Code generation parts specific to LLVM. Both correctness bugs and optimization-related issues. C-enhancement Category: An issue proposing an enhancement or a PR with one. C-optimization Category: An issue highlighting optimization opportunities or PRs implementing such E-needs-test Call for participation: An issue has been fixed and does not reproduce, but no test has been added. I-slow Issue: Problems and improvements with respect to performance of generated code. T-compiler Relevant to the compiler team, which will review and decide on the PR/issue.
Projects
None yet
Development

Successfully merging a pull request may close this issue.

4 participants