Is there a place to report missed optimisation?

1

Is there a way to report a miss-optimization? I tried to search for some kind of label on the rustc github but couldn’t find it (nor the corresponding category when creating an issue). I would expect such category to have very low priority (if at all). But if a miss-optimization is optimized at one point it would make it easy to record it, and prevent later (unwanted) regressions.

Both code should be optimized to the same assembly, and while I’m not expecting the first one to be written in practice, I think it can come up after constant propagation and inlining in real code.

pub fn square42_fp(v: Vec<u32>) -> Vec<u32> {
    v.into_iter().enumerate().map(|(idx, elem)| { if idx == 42 { elem * 2 } else { elem } }).collect()
}

pub fn square42_assign(mut v: Vec<u32>) -> Vec<u32> {
    if v.len() > 42 {
        v[42] *= 2;
    }
    v
}

godbolt

If the tool I had in mind existed, then square42_fp would have an annotation that says that its assembly should be (but isn’t yet) the same than square42_assign. In CI, both function would be compiled, and their assembly compared.

At one point square42_fp and square42_assign’s assemblies will match and thus the test will fail, reporting that the assembly of both function matches now. This would allow for a manual review (in case square42_assign was pessimized instead of optimized). At that point the author of the commit would be able to change the annotation to say that both function assembly should match.

If at one point the assembly diverge again the test will fail, making it possible for a reviewer to analyze it, and possibly catch a regression.

I think that comparing the assembly of two function is better than comparing the assembly of one function to a reference, because I expect less false positive to come up.

Since Rust makes the strong promise that high-level construction should be as efficient as a lower-level equivalent one, I hope that such tool exists.

4 Likes
2

The compiler has optimization tests as part of its CI. Here's an example:

I don't know that there's an external tool for this kind of thing, though.

(And the level of difference between those two examples is such that I would be very surprised if the former would optimize down the same as the latter.)

2 Likes
3

The two square functions do not look identical to me, so I am not sure if that counts as an allowable optimization.

square42_fp creates a new Vec as return value. This creates an additional allocation and deallocation. I am unsure if that alone counts as an observable side effect, but the capacity of the Vec can also be read and this might be different between the two functions.

4

It's worth noting that this is a very tricky high level optimization to apply automatically.

The reason that vec.into_iter().collect::<Vec<_>>() doesn't allocate is a specialization of (I believe) for<T> Vec::<T> as FromIterator::<T>::from_iter::<vec::IntoIterator<T>>. Without this specialization, it's very difficult to actually justify the allocation slot reuse. (E.g. capacity could likely be an observable difference the optimizer has to not change.)

A specialization to cover this would need to specialize from_iter for something along the vague lines of all iterator combinators which (type recursively) do not change the length of the iteration and which terminates in a vec::IntoIter. The specialization could then theoretically run the iterator and collect into the moved-from head, and also fix up drop (on panic) to drop the whole Vec exactly once (except the element which panicked and is moved from).

I believe even the simple vec.into_iter().map(identity).collect() will not reuse the Vec allocation.

2 Likes
5

I would argue that the capacity is not something that can be observed from outside of the function, since there is no guaranty that the output Vec is related in any way to the input one.

For the allocation, I’m not sure that it counts as observable effect. I think, but I can be wrong, that in C++, it’s not considered as observable behavior, and I would have expected the same in Rust. In zig, since the allocator is passed explicitly, I think that it would have counted as observable.

But I totally agree that it’s not at all an easy optimization. I’m not really surprised that it was not optimized (yet). I mostly wanted to know if there was some place to create high-level optimization regression tests.

1 Like
6

It’s correctly optimized out :slight_smile: godbolt. I don’t understand what is different in the assembly however (I’m not familiar enough with asm), I think it’s strictly instruction ordering.

7

There's no guarantee at the Rust library level, so it's something that could possibly be specialized, but at LLVM's level the capacity is definitely an observable effect.

2 Likes
8

I played a bit with the assembly:

If the signature of the function is pub fn foo(v: Vec<u32>) -> Vec<u32>, then all 3 are equivalent (godbolt) except for some instruction re-ordering:

  • v
  • v.into_iter().map(std::convert::identity).collect()
  • v.into_iter().enumerate().map(|(_idx, elem)| elem).collect()

So it’s seems that the only thing that prevent the optimization in the original example is the map when it’s not an identity.

For fun I also tested v.clone(), and it’s not optimized away, even if v is not re-used (godbolt).

1 Like
9

This seems like it could run into a problem of "what if the codegen changes to something ruled out, because it's faster on the particular CPU (with -C target-cpu=native or -Z tune-cpu=native)"

10

Right. Optimizations are usually couched in "as-if" language. The collect induces a reallocation which does not have a forced link to the old capacity, so that is "observable behavior" as far as the optimizer is concerned.

AFAIU, Clone can only be optimized away if it is also Copy (though I'm not sure if this is actually happening). See these threads:

There was a more recent one mentioning it too, but I'm not seeing it right now.

2 Likes
11

Clone can be optimized away iff the compiler can prove it's trivial, other otherwise that it is pure. Copy is irrelevant to it, it's only a logical requirement that T::clone() be trivial if T: Copy.

12

I think most such issues are marked as I-slow + A-LLVM. Unfortunately, such issues indeed have a very low priority and we often simply wait for LLVM to improve. For example, I had several such issues reported and I closed them myself long time after they apparently got resolved on the LLVM side.

In my opinion, one problem is that such issues often do not get mirrored into the LLVM bug tracker (lack of open registration makes reporting them only harder), so LLVM developers may not know about those issues in the first place.

1 Like
13

Well, that test doesn't pass those flags, so they're not really a concern.

But also, LLVM will always canonicalize things at the IR level -- so it'll always simplify multiplication to shifts as part of doing the optimizations. Then if it's actually faster on a particular target to use multiplication for shifts, then the codegen part will do that, but the test isn't looking at the assembly output to see that.

At the same time, yes, the codegen tests are absolutely more tempermental than most of the other kinds of tests in the compiler. You'll notice all the comments at the top of that one, restricting it to only 64-bit, disabling debug assertions, ...

1 Like
14

For the record, this specialization infrastructure exists. It's for standard library iterator adapters that do not increase the length of the iterator, so e. g. filter works as well. It's become far less discoverable since the documentation of the involved unstable traits has been hidden in 1.54, e.g. InPlaceIterable in std::iter - Rust. Apparently it supports vec and binary_heap.

3 Likes
15

To show something that does work: At least for a small statically-known-size Vec, the two functions produce very similar assembly:

Compiler Explorer

5 Likes
16

And even with the original code, that specialization does kick in, meaning that there is no allocation or deallocation. It seems to be just that the loop can't be optimised away.

Example:

pub fn iter_thru(v: usize, slice: &mut [u32]) {
    assert!(slice.len() > 42);
    assert!(slice.len() < v);
    for item in 0..v {
        if item == 42 {
            slice[42] = 17;
            // With a `return;` added here, the function suddenly is
            // just as optimised as the one below.
        }
    }
}

pub fn iter_thru_2(v: usize, slice: &mut [u32]) {
    assert!(slice.len() > 42);
    assert!(slice.len() < v);
    slice[42] = 17;
}

(Godbolt)

4 Likes
17

Continuing the discussion from Is there a place to report missed optimisation?:

Another reduced test case :

pub fn iter_to_2(v: usize, slice: &mut [u32; 8]) {
    if v <= slice.len() { return; } // remove panic noise

    for item in 0..v {
        if item > 0 {
            slice[5] = 17;
        }
    }
}

example::iter_to_2:
        cmp     rdi, 9
        jb      .LBB3_6
        mov     dword ptr [rsi + 20], 17
        lea     rcx, [rdi - 1]
        add     rdi, -2
        mov     eax, ecx
        and     eax, 7
        cmp     rdi, 7
        jb      .LBB3_4
        and     rcx, -8
        neg     rcx
.LBB3_3:
        add     rcx, 8
        jne     .LBB3_3
.LBB3_4:
        test    rax, rax
        je      .LBB3_6
.LBB3_5:
        add     rax, -1
        jne     .LBB3_5
.LBB3_6:
        ret

godbolt link (contains one more example)

The compiler is smart enough to know that the slice will be affected and thus perform the operation right away (after checking that v > slice.len(), of course, or else v could be lower or equal to 8, which would trigger an early return, or equal to 0 in which case the slice wouldn't be affected even without the first if). But then, there is still some assembly that doesn't make much sense to me.

1 Like
18

Where can I read about why they were hidden from documentation?

19

I don't know. Possibly because they're considered implementation details? I could try to locate the PR that made them hidden.

The only good way I’m aware of for reading what they currently look like is to clone the rust repository and build the hidden docs locally e.g. with RUSTDOCFLAGS='--document-private-items --document-hidden-items' ./x.py doc library/std --open. I only know about these due to the fact that they used to be visible in the online standard library docs.

2 Likes
20

Here:

2 Likes