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.

Sign up for GitHub

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

Jump to bottom

Derive(PartialOrd) generates pretty bad code #49505

Closed
nox opened this issue Mar 30, 2018 · 4 comments · Fixed by #49881
Closed

Derive(PartialOrd) generates pretty bad code #49505

nox opened this issue Mar 30, 2018 · 4 comments · Fixed by #49881
Assignees
@varkor
Labels
C-enhancement Category: An issue proposing an enhancement or a PR with one. I-slow Issue: Problems and improvements with respect to performance of generated code. WG-compiler-performance Working group: Compiler Performance WG-llvm Working group: LLVM backend code generation

Comments

@nox
Copy link
Contributor

nox commented Mar 30, 2018 •
edited
Loading 

#[automatically_derived]
#[allow(unused_qualifications)]
impl <T: ::std::cmp::PartialOrd> ::std::cmp::PartialOrd for Option<T> {
    #[inline]
    fn partial_cmp(&self, __arg_0: &Option<T>)
     -> ::std::option::Option<::std::cmp::Ordering> {
        {
            let __self_vi =
                unsafe { ::std::intrinsics::discriminant_value(&*self) } as
                    isize;
            let __arg_1_vi =
                unsafe { ::std::intrinsics::discriminant_value(&*__arg_0) } as
                    isize;
            if true && __self_vi == __arg_1_vi {
                match (&*self, &*__arg_0) {
                    (&Option::Some(ref __self_0),
                     &Option::Some(ref __arg_1_0)) =>
                    match ::std::cmp::PartialOrd::partial_cmp(&(*__self_0),
                                                              &(*__arg_1_0)) {
                        ::std::option::Option::Some(::std::cmp::Ordering::Equal)
                        =>
                        ::std::option::Option::Some(::std::cmp::Ordering::Equal),
                        __cmp => __cmp,
                    },
                    _ =>
                    ::std::option::Option::Some(::std::cmp::Ordering::Equal),
                }
            } else { __self_vi.partial_cmp(&__arg_1_vi) }
        }
    }
    #[inline]
    fn lt(&self, __arg_0: &Option<T>) -> bool {
        {
            let __self_vi =
                unsafe { ::std::intrinsics::discriminant_value(&*self) } as
                    isize;
            let __arg_1_vi =
                unsafe { ::std::intrinsics::discriminant_value(&*__arg_0) } as
                    isize;
            if true && __self_vi == __arg_1_vi {
                match (&*self, &*__arg_0) {
                    (&Option::Some(ref __self_0),
                     &Option::Some(ref __arg_1_0)) =>
                    (*__self_0) < (*__arg_1_0) ||
                        !((*__arg_1_0) < (*__self_0)) && false,
                    _ => false,
                }
            } else { __self_vi.lt(&__arg_1_vi) }
        }
    }
    #[inline]
    fn le(&self, __arg_0: &Option<T>) -> bool {
        {
            let __self_vi =
                unsafe { ::std::intrinsics::discriminant_value(&*self) } as
                    isize;
            let __arg_1_vi =
                unsafe { ::std::intrinsics::discriminant_value(&*__arg_0) } as
                    isize;
            if true && __self_vi == __arg_1_vi {
                match (&*self, &*__arg_0) {
                    (&Option::Some(ref __self_0),
                     &Option::Some(ref __arg_1_0)) =>
                    (*__self_0) < (*__arg_1_0) ||
                        !((*__arg_1_0) < (*__self_0)) && true,
                    _ => true,
                }
            } else { __self_vi.le(&__arg_1_vi) }
        }
    }
    #[inline]
    fn gt(&self, __arg_0: &Option<T>) -> bool {
        {
            let __self_vi =
                unsafe { ::std::intrinsics::discriminant_value(&*self) } as
                    isize;
            let __arg_1_vi =
                unsafe { ::std::intrinsics::discriminant_value(&*__arg_0) } as
                    isize;
            if true && __self_vi == __arg_1_vi {
                match (&*self, &*__arg_0) {
                    (&Option::Some(ref __self_0),
                     &Option::Some(ref __arg_1_0)) =>
                    (*__self_0) > (*__arg_1_0) ||
                        !((*__arg_1_0) > (*__self_0)) && false,
                    _ => false,
                }
            } else { __self_vi.gt(&__arg_1_vi) }
        }
    }
    #[inline]
    fn ge(&self, __arg_0: &Option<T>) -> bool {
        {
            let __self_vi =
                unsafe { ::std::intrinsics::discriminant_value(&*self) } as
                    isize;
            let __arg_1_vi =
                unsafe { ::std::intrinsics::discriminant_value(&*__arg_0) } as
                    isize;
            if true && __self_vi == __arg_1_vi {
                match (&*self, &*__arg_0) {
                    (&Option::Some(ref __self_0),
                     &Option::Some(ref __arg_1_0)) =>
                    (*__self_0) > (*__arg_1_0) ||
                        !((*__arg_1_0) > (*__self_0)) && true,
                    _ => true,
                }
            } else { __self_vi.ge(&__arg_1_vi) }
        }
    }
}

Instead of doing stuff such as (a > b) || !(b > a) && true in ge, rustc should probably just reuse the operator syntax by doing a >= b.
@nox
Copy link
Contributor Author

nox commented Mar 30, 2018

@rust-lang/wg-compiler-performance

@nox
Copy link
Contributor Author

nox commented Mar 31, 2018

See also #15618, and I guess I should ping @rust-lang/wg-codegen too.

@pietroalbini pietroalbini added WG-compiler-performance Working group: Compiler Performance WG-llvm Working group: LLVM backend code generation I-slow Issue: Problems and improvements with respect to performance of generated code. C-enhancement Category: An issue proposing an enhancement or a PR with one. labels Apr 6, 2018
@ExpHP
Copy link
Contributor

ExpHP commented Apr 9, 2018 •
edited
Loading

Not only is it slow, but also wrong; see #49650

@varkor varkor self-assigned this Apr 11, 2018
@varkor varkor mentioned this issue Apr 11, 2018
Merged
bors added a commit that referenced this issue Apr 15, 2018
@bors
Auto merge of #49881 - varkor:partialord-opt, r=Manishearth
bc001fa 
Fix derive(PartialOrd) and optimise final field operation

```rust
// Before (`lt` on 2-field struct)
self.f1 < other.f1 || (!(other.f1 < self.f1) &&
(self.f2 < other.f2 || (!(other.f2 < self.f2) &&
(false)
))
)

// After
self.f1 < other.f1 || (!(other.f1 < self.f1) &&
self.f2 < other.f2
)

// Before (`le` on 2-field struct)
self.f1 < other.f1 || (!(other.f1 < self.f1) &&
(self.f2 < other.f2 || (!(other.f2 < self.f2) &&
(true)
))
)

// After
self.f1 < other.f1 || (self.f1 == other.f1 &&
self.f2 <= other.f2
)
```

(The big diff is mainly because of a past faulty rustfmt application that I corrected 😒)

Fixes #49650 and fixes #49505.
@varkor
Copy link
Member

varkor commented Apr 15, 2018

Although this was improved somewhat by #49881, let's keep this open until #49650 (comment) has been addressed (one function call per field comparison).

@varkor varkor reopened this Apr 15, 2018
@varkor varkor mentioned this issue Apr 16, 2018
Merged
bors added a commit that referenced this issue May 15, 2018
@bors
Auto merge of #50011 - varkor:partialord-opt-ii, r=Manishearth
d711dc9 
Ensure derive(PartialOrd) is no longer accidentally exponential

Previously, two comparison operations would be generated for each field, each of which could delegate to another derived PartialOrd. Now we use ordering and optional chaining to ensure each pair of fields is only compared once, addressing #49650 (comment).

Closes #49505.

r? @Manishearth (sorry for changing it again so soon!)

Close #50755
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@varkor varkor

Labels
C-enhancement Category: An issue proposing an enhancement or a PR with one. I-slow Issue: Problems and improvements with respect to performance of generated code. WG-compiler-performance Working group: Compiler Performance WG-llvm Working group: LLVM backend code generation
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Fix derive(PartialOrd) and optimise final field operation varkor/rust
4 participants
@nox @ExpHP @pietroalbini @varkor