Bounds checking should be eliminated in obvious case

[Geal]

Hi,

Following the benchmarks comparing the nom and chomp parser combinator libraries, I investigated the performance difference and found something interesting: in code that is nearly equivalent, rustc generates a lot more stuff with nom than chomp, and keeps bounds check where the parsers make sure no error should happen.

For the comparison, here are some code examples, in nom:

named!(message_header_value, chain!(
        take_while1!(is_horizontal_space) ~
  data: take_while1!(not_line_ending)     ~
  line_ending,
  || data));

in chomp:

fn message_header_line(i: Input<u8>) -> U8Result<&[u8]> {
    parse!{i;
                   take_while1(is_horizontal_space);
        let line = take_till(is_end_of_line);
                   end_of_line();

        ret line
    }   
}

(we could change take_while1!(not_line_ending) to a take_till!(is_end_of_line) and it would achieve the same code).

Once the macros are processed, it gives the following code in nom: https://gist.github.com/Geal/fa3740cf45530d123023

chomp uses the same approach, with iterators, in its version of take_while1 and take_till`: https://github.com/m4rw3r/chomp/blob/master/src/parsers.rs#L208-L253

Now, the interesting thing is the assembly generated by rustc ( 1.5.0-dev (ea2dabf 2015-10-21), but the version from yesterday has the same issues). Here is the nom version: http://dev.unhandledexpression.com/nom_http.pdf
And the chomp version: http://dev.unhandledexpression.com/chomp_http.pdf

We can see that nom's code is a lot more complex:

• large blocks of code calling nom's Err destructor (it is expected, but I'd like to improve that as well)
• 4 bounds checks are still present, while they do not appear in chomp

I would like to know if there is a way to improve code generation. If the issue is in rustc, I can provide as many test cases as you need. If it is in nom, I'm open to any ideas ;)

[Geal]

@bluss provided a reduced test case: http://is.gd/0vOZs0

[Gankra]

I'm pretty sure this is an LLVM/backend issue. LLVM's bounds-check removal analysis is really brittle. It's possible there's better flags we could be passing it to try to eliminate bounds checks. I seem to recall @huonw mentioning one once?

[bluss]

This kind of thing (playground) elides the bounds check for input[i] but not for input[..i], which is mysterious.

pub fn split_at(input: &[u8]) -> &[u8] {
    for i in 0..input.len() {
        if input[i] == b' ' {
            return &input[..i]
        }
    }
    &[]
}

[dotdash]

LLVM removes the first bounds check, because that is the same as the loop condition, i.e. i < input.len(). But for the second bounds is i <= input.len(), and LLVM only handles propagation in such cases if the value is compared to a constant, which is not the case here.

[bluss]

@dotdash That's unfortunate. Do you know if that is a reason for the original example too?

[Keruspe]

What could be the reason for llvm to keep bound checks when using nom but not when using chomp?

[dotdash]

@Geal could you provide the IR and the asm code for that function? I know the asm is in those pdfs, but I have a hard time reading that. You can get them with --emit llvm-ir,asm which should produce a .ll and a .s file. Thanks!

[Geal]

@dotdash here: https://gist.github.com/Geal/e7ebe638862828420863

It might be slightly different, since I built with a more recent rustc (1.6.0-dev (4867df4 2015-11-29) ), but the performance is the same.

[huonw]

I'm pretty sure this is an LLVM/backend issue. LLVM's bounds-check removal analysis is really brittle. It's possible there's better flags we could be passing it to try to eliminate bounds checks. I seem to recall @huonw mentioning one once?

IRCE: #22987

http://llvm.org/docs/Frontend/PerformanceTips.html also says:

For languages with numerous rarely executed guard conditions (e.g. null checks, type checks, range checks) consider adding an extra execution or two of LoopUnswith and LICM to your pass order. The standard pass order, which is tuned for C and C++ applications, may not be sufficient to remove all dischargeable checks from loops.

[dotdash]

@Geal the remaining checks are the ones that check that start is less than or equal to end for the range. Due to the the ranges including the end, that makes the actual bounds check go away. What I wonder is why there is a check that compares against 2 here: https://gist.github.com/Geal/e7ebe638862828420863#file-nom_http-ll-L216

I can't seem to figure out to which part of the code that belongs. Any idea?

[bluss]

Triage: rustc 1.13.0-nightly (4f9812a 2016-09-21)

• All three test cases in Bounds checking should be eliminated in obvious case #30112 (comment) still have bounds checks

#![crate_type="lib"]

pub fn split_to(input: &[u8]) -> &[u8] {
    match input.iter().position(|x| *x == b' ') {
        Some(i) => &input[..i],
        None => &[],
    }
}

pub fn split_from(input: &[u8]) -> &[u8] {
    match input.iter().position(|x| *x == b' ') {
        Some(i) => &input[i..],
        None => &[],
    }
}

pub fn find(input: &[u8]) -> Option<&u8> {
    match input.iter().position(|x| *x == b' ') {
        Some(i) => Some(&input[i]),
        None => None,
    }
}

• The test case in Bounds checking should be eliminated in obvious case #30112 (comment) elides the bounds check. Not in stable, but current beta and nightly.

[bluss]

The optimizer likes the indices best at this point. No bounds checks here (beta & nightly)

pub fn split_to(input: &[u8]) -> &[u8] {
    match (0..input.len()).find(|&i| input[i] == b' ') {
        Some(i) => &input[..i],
        None => &[],
    }
}

Optimization is simple: The range ensures i < input.len().

[steveklabnik]

Triage: I'm not great with asm, but https://godbolt.org/z/wj6kYl

It appears that split_to is partially unrolled in today's nightly, but still checks the bounds. split_to2, like was said above, compiles to very straightforward code with no checks.

[EgorBo]

https://godbolt.org/z/Wb46fYsPK

If I understand it correctly - after I altered the default order of LLVM passes and inserted IRCE there (I also added additional LICM and unswitch if I remember correctly - I just followed Pass Ordering tips.) it managed to "clone" the loop and have a fast loop where it doesn't poll for bounds checks 😏

[saethlin]

Looks to me like all the bounds checks in the original examples are gone now: https://godbolt.org/z/fcexGna7s

[workingjubilee]

Thanks for checking! I think this can be closed then?