`&usize::<=` is much slower than `usize::<=`

[hashworks]

While solving AoC Day 4 I ran into the following performance difference:

fn main() {
    let input = vec![
        (2, 4, 6, 8),
        (2, 3, 4, 5),
        (5, 7, 7, 9),
        (2, 8, 3, 7),
        (6, 6, 4, 6),
        (2, 6, 4, 8), // .. 500000000 lines of random data, read from disk with real code (~12GB)
    ];

    // 1761ms on my machine
    let _variant_a_result = variant_a(&input);

    //  656ms on my machine
    let _variant_b_result = variant_b(&input);
}

pub fn variant_a(input: &[(usize, usize, usize, usize)]) -> usize {
    input
        .iter()
        .filter(|(a, b, c, d)| a <= c && d <= b || c <= a && b <= d)
        .count()
}

pub fn variant_b(input: &[(usize, usize, usize, usize)]) -> usize {
    input
        .iter()
        .filter(|&&(a, b, c, d)| a <= c && d <= b || c <= a && b <= d)
        .count()
}

As you can see, using |&&(a, b, c, d)| on the same closure is 2.6 times faster than |(a, b, c, d)|.
Viewing the compiled code makes this clear: https://rust.godbolt.org/z/oaeaGGPK7

Is this a compiler behavior a developer should know / expect?

Meta

Thanks to @Arnavion for pointing this out.

rustc --version --verbose:

rustc 1.67.0-nightly (c090c6880 2022-12-01)

[leonardo-m]

Unrelated: adding some parentesys could improve the clarity of this code:

.filter(|(a, b, c, d)| (a <= c && d <= b) || (c <= a && b <= d))

[jruderman]

@rustbot label +I-slow

[workingjubilee]

Is this a compiler behavior a developer should know / expect?

Strictly answering this question: You are working with &T and then calling .iter(), which creates nested indirections. Yes, the cost of an indirection, especailly nested indirections, is indeed probably something you should be aware of when you are working with plain, "by-value" data, and thus you should probably try to avoid it.

Also your signature should probably be

fn(input: &[(u64, u64, u64, u64)]) -> usize

But that doesn't make a difference to codegen.

This issue is one of the ones that motivated:

• Tracking issue: Allow autoderef and autoref in operators (experiment) #44762

[jruderman]

Why is variant_a valid, and why does it create a nested indirection? I sorta understand the non-tuple case described in an old reddit thread, but I don't understand how you can destructure a tuple and still have the wrong level of indirection.

[leonardo-m]

Both versions are idiomatic. And I think Clippy doesn't fire on them.

[hashworks]

And I think Clippy doesn't fire on them

I'm using clippy, and yes, it doesn't.

[workingjubilee]

Yes, this code is not unusual and ideally we'd compile it optimally in all cases, but creating indirections is Known to sometimes affect performance. It can sometimes be preferable to e.g. call .into_iter() instead of .iter() for this reason (or do the opposite, for other reasons).

but I don't understand how you can destructure a tuple and still have the wrong level of indirection.

If you destructure some &tuple into (A, B), you will get (&A, &B). This happens due to... you know, I forget exactly which, at this point.

[jruderman]

I see. So variant_a binds a etc as references, and the comparisons either doing impl-for-ref or auto-derefs like:

pub fn variant_a_2(input: &[(usize, usize, usize, usize)]) -> usize {
    input
        .iter()
        .filter(|(a, b, c, d)| *a <= *c && *d <= *b || *c <= *a && *b <= *d)
        .count()
}

It only seems to keep one level of references, though.

[workingjubilee]

Indeed. The nesting is only somewhat relevant because it requires more work to remove both levels. And I believe it is hitting this implementation:

impl<A, B> PartialOrd<&B> for &A where
    A: PartialOrd<B> + ?Sized,
    B: ?Sized,

[Arnavion]

This happens due to... you know, I forget exactly which, at this point.

Match ergonomics. Without it the equivalent code would've been &&(ref a, ref b, ref c, ref d). Of course if one was writing that they would notice that usize is Copy so they can skip the refs, which would happen to solve the slowness issue. (This same logic is how I came up with the fix for OP.) But since we do have match ergonomics, code like OP's is very common, so it would be nice if it didn't have a penalty.