5 ms·

If we take your code and modify it so that the compiler can't just get rid of the array acces, we get: extern crate test; fn main() { let mut

by veddan 12y ago

If we take your code and modify it so that the compiler can't just get rid of the array acces, we get: extern crate test; fn main() { let mut v = vec![1i32, 2, 3, 4, 5]; let vlen = v.len(); for i in range(0, vlen) { let x = &mut v[i]; test::black_box(x); // do some work with x } } Compiling this file with rustc -O, the compiler not only gets rid of the bounds checking, it gets rid of the loop altogether by unrolling it completely. LLVM IR: https://gist.github.com/veddan/1535a8718cf2c85006ea https://gist.github.com/veddan/1535a8718cf2c85006ea

Animats 12y ago
Thanks. Can you do that again for a case where the compiler can't see the number of iterations at compile time?
- pbsd 12y ago
  Let's change the example to pub fn f(v: &mut [u8]) { let vlen = v.len(); for i in range(0, vlen) { let x = &mut v[i]; test::black_box(x); // do some work with x } } The output assembly of latest nightly of rustc is: f::h1371efe4e4343230faa: cmp rsp, qword ptr fs:[112] ja .LBB0_2 movabs r10, 16 movabs r11, 0 call __morestack ret .LBB0_2: push rbp mov rbp, rsp push rax mov rax, qword ptr [rdi + 8] test rax, rax je .LBB0_5 mov rcx, qword ptr [rdi] xor edx, edx lea rsi, qword ptr [rbp - 8] .LBB0_4: lea rdi, qword ptr [rcx + rdx] inc rdx mov qword ptr [rbp - 8], rdi cmp rdx, rax jb .LBB0_4 .LBB0_5: add rsp, 8 pop rbp ret
  - Animats 12y ago
    Thanks. I don't see a call to test::black_box(x), so I assume that was an empty function optimized out. Would you change "let vlen = v.len()" to "let vlen = v.len() + 1" and try again, please? That introduces an off-by-one error and a buffer overflow. Let's see what the compiler does with it. Thanks.
    - pbsd 12y ago
      Your modification results in the inclusion of a bounds check in the inner loop: .LBB0_4: cmp rdx, rsi jae .LBB0_7 At `LBB0_7` is a call to `panic_bounds_check`.
    - masklinn 12y ago
      > Thanks. I don't see a call to test::black_box(x), so I assume that was an empty function optimized out. black_box is and does nothing, its purpose is to be opaque to the optimiser and make values it is passed "used" for optimiser purposes, otherwise the optimiser would remove the whole thing since it's a noop.
  - Animats 12y ago
    (Replying to message below, indent limit reached). The panic check is inside the loop, not hoisted out of the loop? OK, that means it's only optimizing bounds tests out when it can, not hoisting them out of loops. That's not bad for a compiler in the early stages. Is a matrix multiply free of checks in the inner loops? That's a good test, because most numerical code has a lot of matrix multiplies underneath. A useful goal is to have most of the inner loops from algorithms in Numerical Recipes free of unnecessary subscript checks. If that can be done, is the "unsafe" stuff necessary at all?
    - kibwen 12y ago
      At the limit, `unsafe` blocks would still be necessary for any FFI used to call into C code, which is trivially proven unsafe. It's mistaken to think of `unsafe` as a novel language feature. All other languages merely defer their unsafe shenanigans to native C calls. I can just as easily write a memory-unsafe program in Python. In Rust, we use `unsafe` to hoist logic out of C wherever possible, to make our code even more safe; even the unsafe dialect of Rust is safer than C.
- deleted 12y ago
  [deleted]
kibwen 12y ago
To elaborate, when Rust says that array access is bounds-checked while iterators aren't, what it means is that iterators are guaranteed not to bounds check, while typical array accesses may or may not be optimized away. With the GP's approach, not only do you need to hardcode the hoisting optimization into the frontend, you need the body of the loop to follow a specific patterns and you need to trust that the compiler will recognize the cases where the optimization can be applied. By avoiding privileged optimizations in the frontend and by giving programmers low-level tools where they need them, Rust empowers library authors to get things done without having to bug the Rust developers themselves to implement them.
- Animats 12y ago
  That's kind of what compilers are for. One of their jobs is static analysis. They have the graphs needed for hoisting. Libraries don't. This may be a problem with the existing compiler, if the Rust implementation is mostly a front-end to LLVM. I'd hate to see "unsafe" code baked into the language standard, though. C++ tried to fix the mess underneath with template libraries. That didn't end well. "Giving programmers low-level tools when they need them" as an excuse for abandoning language safety is a recipe for bad code. There's a long, long history of that not working. "Unsafe" code should be very, very rare, used for dealing with device registers and such. This sounds like designing buffer overflows into Rust.
  - deleted 12y ago
    [deleted]
  - veddan 12y ago
    Checked array access is implemented with unsafe code. Actual code implementing the `[]` operator for arrays ("slices"): fn index(&self, &index: &uint) -> &T { assert!(index < self.len()); unsafe { mem::transmute(self.repr().data.offset(index as int)) } } By having `unsafe {}` it's possible to build low-level functionality as libraries rather than in the compiler. There no reason to think that code such as this would be less prone to bugs if it were hard-coded into the compiler. I'd be more inclined to believe the opposite.
  - 12y ago

by veddan 12y ago

Animats 12y ago

Thanks. Can you do that again for a case where the compiler can't see the number of iterations at compile time?

pbsd 12y ago
Let's change the example to pub fn f(v: &mut [u8]) { let vlen = v.len(); for i in range(0, vlen) { let x = &mut v[i]; test::black_box(x); // do some work with x } } The output assembly of latest nightly of rustc is: f::h1371efe4e4343230faa: cmp rsp, qword ptr fs:[112] ja .LBB0_2 movabs r10, 16 movabs r11, 0 call __morestack ret .LBB0_2: push rbp mov rbp, rsp push rax mov rax, qword ptr [rdi + 8] test rax, rax je .LBB0_5 mov rcx, qword ptr [rdi] xor edx, edx lea rsi, qword ptr [rbp - 8] .LBB0_4: lea rdi, qword ptr [rcx + rdx] inc rdx mov qword ptr [rbp - 8], rdi cmp rdx, rax jb .LBB0_4 .LBB0_5: add rsp, 8 pop rbp ret
- Animats 12y ago
  Thanks. I don't see a call to test::black_box(x), so I assume that was an empty function optimized out. Would you change "let vlen = v.len()" to "let vlen = v.len() + 1" and try again, please? That introduces an off-by-one error and a buffer overflow. Let's see what the compiler does with it. Thanks.
  - pbsd 12y ago
    Your modification results in the inclusion of a bounds check in the inner loop: .LBB0_4: cmp rdx, rsi jae .LBB0_7 At `LBB0_7` is a call to `panic_bounds_check`.
  - masklinn 12y ago
    > Thanks. I don't see a call to test::black_box(x), so I assume that was an empty function optimized out. black_box is and does nothing, its purpose is to be opaque to the optimiser and make values it is passed "used" for optimiser purposes, otherwise the optimiser would remove the whole thing since it's a noop.
- Animats 12y ago
  (Replying to message below, indent limit reached). The panic check is inside the loop, not hoisted out of the loop? OK, that means it's only optimizing bounds tests out when it can, not hoisting them out of loops. That's not bad for a compiler in the early stages. Is a matrix multiply free of checks in the inner loops? That's a good test, because most numerical code has a lot of matrix multiplies underneath. A useful goal is to have most of the inner loops from algorithms in Numerical Recipes free of unnecessary subscript checks. If that can be done, is the "unsafe" stuff necessary at all?
  - kibwen 12y ago
    At the limit, `unsafe` blocks would still be necessary for any FFI used to call into C code, which is trivially proven unsafe. It's mistaken to think of `unsafe` as a novel language feature. All other languages merely defer their unsafe shenanigans to native C calls. I can just as easily write a memory-unsafe program in Python. In Rust, we use `unsafe` to hoist logic out of C wherever possible, to make our code even more safe; even the unsafe dialect of Rust is safer than C.
deleted 12y ago
[deleted]

kibwen 12y ago

To elaborate, when Rust says that array access is bounds-checked while iterators aren't, what it means is that iterators are guaranteed not to bounds check, while typical array accesses may or may not be optimized away. With the GP's approach, not only do you need to hardcode the hoisting optimization into the frontend, you need the body of the loop to follow a specific patterns and you need to trust that the compiler will recognize the cases where the optimization can be applied. By avoiding privileged optimizations in the frontend and by giving programmers low-level tools where they need them, Rust empowers library authors to get things done without having to bug the Rust developers themselves to implement them.

Animats 12y ago
That's kind of what compilers are for. One of their jobs is static analysis. They have the graphs needed for hoisting. Libraries don't. This may be a problem with the existing compiler, if the Rust implementation is mostly a front-end to LLVM. I'd hate to see "unsafe" code baked into the language standard, though. C++ tried to fix the mess underneath with template libraries. That didn't end well. "Giving programmers low-level tools when they need them" as an excuse for abandoning language safety is a recipe for bad code. There's a long, long history of that not working. "Unsafe" code should be very, very rare, used for dealing with device registers and such. This sounds like designing buffer overflows into Rust.
- deleted 12y ago
  [deleted]
- veddan 12y ago
  Checked array access is implemented with unsafe code. Actual code implementing the `[]` operator for arrays ("slices"): fn index(&self, &index: &uint) -> &T { assert!(index < self.len()); unsafe { mem::transmute(self.repr().data.offset(index as int)) } } By having `unsafe {}` it's possible to build low-level functionality as libraries rather than in the compiler. There no reason to think that code such as this would be less prone to bugs if it were hard-coded into the compiler. I'd be more inclined to believe the opposite.
- 12y ago