Use the enum_discriminant intrinsic when available in #[derive(PartialEq)]

[pcwalton]

It doesn't seem like we're using it as aggressively as we could. For example, if some variants are C-style, then we don't have to generate cases to handle those variants explicitly. This causes very large code bloat in Servo DOM code, for example.

[aturon]

triage: I-nominated

The compiler team may want to look at prioritizing improvements here.

[dotdash]

Checking for discriminant equality before the match statement allows LLVM to optimize the code quite a bit better, but doesn't always give optimal results (still better than what we currently get though).

For cases where we have e.g. a large number of equal match arms, it would be great if we could translate/expand them as

match x {
    A(v) | B(v) | C(v) => thing1(v),
    X | Y | Z => thing2(),
}

instead of the current

match x {
    A(v) => thing1(v),
    B(v) => thing1(v),
    C(v) => thing1(v),
    X => thing2(),
    Y => thing2(),
    Z => thing2(),
}

because that makes it a lot easier for llvm properly optimize the code. I never got around to understand the generic deriving and/or match codegen enough to see if we can do that though.

[Marwes]

I have done some work on this and assuming I did not mess up my tiny benchmark I currently have managed to get C-like enums an 8x(!) speedup for PartialEq. Looking at the llvm IR it seems that it does handle the current generated code well at all so even if it should still be a hefty improvement.

Non C-like enums currently get a 1.67x speedup as well but I think it might be possible to increase it further by generating some nastier deriving code to help llvm optimize it. Note that benchmarking non-C-like enums is really difficult to do fairly since the time depends massively on the data that is benchmarked.

The idea behind the improvements is to generate code like below.

let __self0_vi = unsafe {
    std::intrinsics::discriminant_value(&self) } as i32;
let __self1_vi = unsafe {
    std::intrinsics::discriminant_value(&__arg1) } as i32;
let __self2_vi = unsafe {
    std::intrinsics::discriminant_value(&__arg2) } as i32;
...

if __self0_vi == __self1_vi && __self0_vi == __self2_vi && ... {
    match (...) {
        (Variant1, Variant1, ...) => Body1
        (Variant2, Variant2, ...) => Body2,
        ...
        _ => ::core::intrinsics::unreachable()
    }
}
else {
    <delegated expression referring to __self0_vi, et al.>
}

I will try to get some better numbers up later but I wanted to give a heads up if anyone else is working on it/thinking of working on it.

New deriving

running 2 tests
test test1 ... bench:    286720 ns/iter (+/- 48894)
test test2 ... bench:   2189368 ns/iter (+/- 730107)

IR for Test::eq

; Function Attrs: inlinehint nounwind readonly uwtable
define zeroext i1 @_ZN26Test...std..cmp..PartialEq2eq20hcca4a1839d4d2498maaE(i8* noalias nocapture readonly dereferenceable(1), i8* noalias nocapture readonly dereferenceable(1)) unnamed_addr #0 {
entry-block:
  %2 = load i8* %0, align 1, !range !0
  %3 = load i8* %1, align 1, !range !0
  %4 = icmp eq i8 %2, %3
  ret i1 %4
}

Old deriving

running 2 tests
test test1 ... bench:   2,387,520 ns/iter (+/- 110,106)
test test2 ... bench:   3,666,369 ns/iter (+/- 35,928)

IR for Test::eq

; Function Attrs: inlinehint nounwind readonly uwtable
define zeroext i1 @_ZN26Test...std..cmp..PartialEq2eq20h54f0ffdc782fbe51maaE(i8* noalias nocapture readonly dereferenceable(1), i8* noalias nocapture readonly dereferenceable(1)) unnamed_addr #0 {
entry-block:
  %2 = load i8* %1, align 1, !range !0
  switch i8 %2, label %join [
    i8 0, label %match_case
    i8 1, label %match_case8
    i8 2, label %match_case11
    i8 3, label %match_case14
    i8 4, label %match_case17
  ]

match_case:                                       ; preds = %entry-block
  %3 = load i8* %0, align 1, !range !0
  %cond23 = icmp eq i8 %3, 0
  br label %join

match_case8:                                      ; preds = %entry-block
  %4 = load i8* %0, align 1, !range !0
  %cond22 = icmp eq i8 %4, 1
  br label %join

match_case11:                                     ; preds = %entry-block
  %5 = load i8* %0, align 1, !range !0
  %cond21 = icmp eq i8 %5, 2
  br label %join

match_case14:                                     ; preds = %entry-block
  %6 = load i8* %0, align 1, !range !0
  %cond20 = icmp eq i8 %6, 3
  br label %join

match_case17:                                     ; preds = %entry-block
  %7 = load i8* %0, align 1, !range !0
  %cond = icmp eq i8 %7, 4
  ret i1 %cond

join:                                             ; preds = %match_case14, %match_case11, %match_case8, %match_case, %entry-block
  %sret_slot.0 = phi i1 [ false, %entry-block ], [ %cond23, %match_case ], [ %cond22, %match_case8 ], [ %cond21, %match_case11 ], [ %cond20, %match_case14 ]
  ret i1 %sret_slot.0
}

#![feature(test, rand)]
extern crate rand;
extern crate test;
use rand::{Rand, Rng, SeedableRng, XorShiftRng};

#[derive(PartialEq)]
enum Test {
    Variant1,
    Variant2,
    Variant3,
    Variant4,
    Variant5,
}
#[derive(PartialEq)]
enum Test2 {
    Variant1(i32, i32),
    Variant2(f64),
    Variant3,
    Variant4(Vec<Test2>),
    Variant5,
}

impl Rand for Test {
    fn rand<R: Rng> (r: &mut R) -> Test {
        match r.gen_range(0, 5) {
            0 => Test::Variant1,
            1 => Test::Variant2,
            2 => Test::Variant3,
            3 => Test::Variant4,
            4 => Test::Variant5,
            _ => panic!()
        }
    }
}

impl Rand for Test2 {
    fn rand<R: Rng> (r: &mut R) -> Test2 {
        match r.gen_range(0, 5) {
            0 => Test2::Variant1(i32::rand(r), i32::rand(r)),
            1 => Test2::Variant2(f64::rand(r)),
            2 => Test2::Variant3,
            3 => {
                let i = r.gen_range(0, 10);
                Test2::Variant4(r.gen_iter().take(i).collect())
            }
            4 => Test2::Variant5,
            _ => panic!()
        }
    }
}

#[bench]
fn test1(b: &mut ::test::Bencher) {
    let mut rng: XorShiftRng = SeedableRng::from_seed([1,2,3,4]);
    let values: Vec<Test> = rng.gen_iter().take(500).collect();
    b.iter(|| {
        for x in &values {
            for y in &values {
                ::test::black_box(x == y);
            }
        }
    })
}

#[bench]
fn test2(b: &mut ::test::Bencher) {
    let mut rng: XorShiftRng = SeedableRng::from_seed([1,2,3,4]);
    let values: Vec<Test2> = rng.gen_iter().take(500).collect();
    b.iter(|| {
        for x in &values {
            for y in &values {
                ::test::black_box(x == y);
            }
        }
    })
}

[bluss]

That is very cool. Is it possible to improve the match code instead so that libraries don't have to write in these optimizations manually?

[Marwes]

The optimization is rather specific in that it only applies when you have 2 or more enums where you wan't to branch on all of them being the same. I'm not sure how often this would apply and wether the matching could detect it.

The best way of solving it though would be if llvm could optimize any generated match code to this form though :). I am honestly a bit surprised that it doesn't do it already.

[nikomatsakis]

I believe this was fixed by #26280, closing. (@Marwes, is this correct?)

[Marwes]

Yes, this is fixed.