How to make compiler automatically elide bound checks

Hi,

I have a library which has a mutable Jaro-Winkler implementation (mutable so as to be memory efficient).
I checked the generated assembly and I found the most bounds checks are not automatically elided. All the index access are valid and theoretically proven. So, I used unsafe get_unchecked methods to fix this.

My question is that is there way to write the code to convey to compiler that the bounds are elide-able without unsafe.

Without unsafe: https://godbolt.org/z/n_XEQ4
With unsafe: https://godbolt.org/z/JT5fN6

1 Like

See indexing, my unpublished fork/reimplementation windex, and compact_arena for different approaches that use the type system to ensure indexes are valid.

Though these crates so use unsafe under the hood, of course.

1 Like
  1. Bounds checks are elided only locally within a function, so don't expect self.indices[i] to be elided, because the compiler doesn't know what else could have happened to self.

  2. [] has a side effect of stopping the program, and LLVM cares about stopping the program at the exact moment, so it won't group or reorder bounds checks.

You can usually fix it by forcing a bound check outside of a loop, e.g.:

let indices = &self.indices[0..len]; // proves that there's `len` elements
for i in 0..len {
   indices[i] // no bounds check
}
4 Likes

I see that whole thing is inlined in the optimized build. Doesn't that help in this kind of analysis?

Also, it couldn't infer that in local context in match function:

    fn matches(&mut self) -> u32 {
        let range = (self.max.len() / 2 - 1).max(0);
        let mut matches = 0;
        let mut index = 0;
        for (i, c1) in self.min.iter().enumerate() {
            let start = if i > range { i - range } else { 0 };
            let end = (i + range + 1).min(self.max.len());

            for (j, c2) in self.max.iter().enumerate().take(end).skip(start) {
                if self.max_flags[j] != 0 && c1 == c2 {
                    self.min_indices[index] = i as isize;// <-- This access is bound checked.
                    self.max_flags[j] = 0;
                    index += 1;
                    matches += 1;
                    break;
                }
            }
        }
        matches
    }

here we know that min_indices.len() == min.len() and if body can be executed at most as many times as outer loop which is 0..min.len()

Oh I realize that min_indices.len() == min.len() is not known in this function

I put several asserts in the code and found that only the local part is not inferred i.e.index <= i:

Other asserts that are inferred correctly don't generate any code

Here is a minimized version: https://godbolt.org/z/qv44iu

pub fn foo() -> usize {
    let mut index = 0;
    for i in 0..100 {
        assert!(index <= i); // <-- this generates panic jmp
        for j in 0..100 {
            if i == j {
                index += 1;
                break;
            }
        }
    }
    index
}
1 Like

Maybe I am misunderstanding something, but it seems that if you remove the assert in the minimized example, we are left without any panic jumps? https://godbolt.org/z/L4SGIE

The presence of assert generating the panic jmp means that the compiler doesn't know that this condition is always true, while you can see that it is.

2 Likes

There will always be cases that the optimizer cannot prove that you can with a higher-level view, and that's why the unsafe hatch exists: to promise something to the optimizer.

Given the minimized example of the missed optimization, I feel it's somewhat reasonable that the optimizer misses this one: both index and i are changing value, and index behind a condition.

Without looking at the actual algorithm, there's potentially a way to rewrite it using iterators such that no potentially-out-of-bounds-from-the-optimizer's-pov accesses happen. But doing so would obscure the connection to the formally proven algorithm enough that I'd link to the formal proof and just use the unsafe indexing. Even the most unsafe-wary environment should allow it with a formal proof of correctness (otherwise no software would ever be good enough).

7 Likes

You can use the following unsafe macro to assert things to the compiler so that it does not need to check them, with the advantage that in debug mode they are checked:

macro_rules! assert_unchecked {(
    $cond:expr
) => (
    if <bool as ::core::ops::Not>::not($cond) {
        if cfg!(debug_assertions) {
            panic!(
                "Fatal error: assertion `{}` failed: this is a bug and a safety issue!",
                 stringify!($cond),
            );
        } else {
             ::std::hint::unreachable_unchecked();
        }
    }
)}
9 Likes

Woah! I never knew we can do this! Rust amazes me once again. Thank you!!!

1 Like

Small question: why <bool as ::core::ops::Not>::not($cond) and not !$cond?

I think this is the sanity check, so that you can't pass there anything but bool without a type error.

2 Likes

:ok_hand:

Rust Not trait uses an associated Output type, meaning that you can do

struct Foo;

impl ::core::ops::Not for Foo {
    type Output = bool;

    fn not (self: Foo) -> bool { true }
}

assert!( !Foo );
2 Likes