News for hackers. Stuff that matters.
Re:Rust, Lifetimes, and Collections by Animats on Wednesday November 19, 2014 @01:20PM (#8631632)
But, with a little sprinkle of unsafe inside this method, we can make it happen.

Uh oh. If you have to turn off subscript checking in Rust for "performance" for simple loop iteration, something is very wrong.

The way this ought to work is by the compiler hoisting checks out of the loop. Consider

let mut v = vec![1i32, 2, 3, 4, 5];

let vlen = v.len()

for i in range(0, vlen) {

    let x = &mut v[i];

    // do some work with x
}

(Have to double space due to lack of formatting capabilities here.)

Subscript checking requires something comparable to

"assert(i >= 0 && i < v.len())" at the subscript check v[i]

The compiler, knowing how "for" works, can hoist that check out of the loop, so it becomes

"assert(0 >= 0 && vlen-1 < v.len())"

at the the top of the loop, before the FOR statement is entered. Now the check only has to be executed once. This optimization is valid for all iterative FOR loops where the iteration variable and the array are not modified within the loop, and the compiler has to check that.

Then, after hoisting, some algebraic simplification can be applied to the expression in the assert. This requires a small theorem prover, or more cheaply, some rewrite rules for the common cases.

"assert(true && vlen <= v.len())" "assert(vlen <= v.len())"

Now, flow analysis shows that, at the point of the assert, vlen = v.len(). So we get

"assert(v.len() <= v.len())"

and finally

"assert(true)"

which is eliminated as dead code. Zero overhead for subscript checking, yet proved correct.

Now that's how it ought to work. One of the Go compilers does this for simple loops like this. Sprinkling "unsafe" around, and making people use funny library constructs for simple loops, is doing it wrong.

This seems to be a forgotten technology. There were Pascal compilers in the 1980s which did this. In practice, about 95% of subscript checks could be optimized out for Pascal. You can almost always get checks out of iterative inner loops, which is where they really matter.

Re:Rust, Lifetimes, and Collections by veddan on Wednesday November 19, 2014 @01:34PM (#8631721)
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

Re:Rust, Lifetimes, and Collections by kibwen on Wednesday November 19, 2014 @01:53PM (#8631831)
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.
Re:Rust, Lifetimes, and Collections by veddan on Wednesday November 19, 2014 @02:15PM (#8632001)
> 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.

And there are cases where it is desirable to use unsafe indexing (beyond implementing the standard library iterators). While LLVM is able to get rid of nounds-checking for a simple indexing loop, it's less likely to do in other circumstances. For example, a high-performance sorting function might want to use (some) unsafe indexing. The access patterns and loop exit conditions can be very complex, and LLVM will not be clever enough to reliable optimize out bounds checks.

Re:Rust, Lifetimes, and Collections by Animats on Wednesday November 19, 2014 @02:06PM (#8631940)
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.

Re:Rust, Lifetimes, and Collections by dbaupp on Wednesday November 19, 2014 @04:26PM (#8632717)
> "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.

How does Rust get an efficient vector type? How does it spawn a thread? How does it print something, or write something to file?

All of these need really low-level code e.g. for interacting with the operating system APIs, or handling possibly-uninitialised data.

Rust explicitly segregates `unsafe`, and we try to instil a strong aversion to using it exactly because it is dangerous and very easy to get wrong, but it's just not reasonable to remove that ability.

Re:Rust, Lifetimes, and Collections by veddan on Wednesday November 19, 2014 @02:21PM (#8632031)
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.
Re:Rust, Lifetimes, and Collections by Dewie on Wednesday November 19, 2014 @04:08PM (#8632630)
> That's kind of what compilers are for.

To be black boxes? Yes, they seem to have a long history of being that.

If I want to implement a stack data type being backed by an array, and I can not be sure that bounds checking is optimized away, I want to be able to turn off bounds checking if I'm 100% sure that my implementation indexes into the array in a correct way. I have all the information that I need about indexing into the array, since I don't expose indexing to whoever is using my stack. The compiler doesn't know more than me, in that sense. So why would I need compiler support - as in some graph which is a result of static analysis - in order to eliminate bounds checking?

Re:Rust, Lifetimes, and Collections by Animats on Wednesday November 19, 2014 @07:27PM (#8633685)
I want to be able to turn off bounds checking if I'm 100% sure

But is everyone else 100% sure? Look at that CERT advisory I posted from Microsoft. "SafeBufferResize" - wasn't. Somebody at Microsoft was probably "100% sure".

If a buffer overflow in your code meant being fired, would you turn off subscript checking?

Re:Rust, Lifetimes, and Collections by Dewie on Wednesday November 19, 2014 @07:32PM (#8633709)
> If a buffer overflow in your code meant being fired, would you turn off subscript checking?

If I could get fired for my implementation not being efficient enough (and the performance hit from the bounds checking mattered as shown through benchmarking, yadda yadda), then yes. :)

Re:Rust, Lifetimes, and Collections by Animats on Wednesday November 19, 2014 @01:48PM (#8631805)
Thanks. Can you do that again for a case where the compiler can't see the number of iterations at compile time?
Re:Rust, Lifetimes, and Collections by pbsd on Wednesday November 19, 2014 @01:56PM (#8631852)
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
Re:Rust, Lifetimes, and Collections by Animats on Wednesday November 19, 2014 @02:25PM (#8632056)
(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?

Re:Rust, Lifetimes, and Collections by kibwen on Wednesday November 19, 2014 @03:29PM (#8632412)
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.

Re:Rust, Lifetimes, and Collections by Animats on Wednesday November 19, 2014 @02:12PM (#8631982)
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.

Re:Rust, Lifetimes, and Collections by pbsd on Wednesday November 19, 2014 @02:15PM (#8632000)
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`.
Re:Rust, Lifetimes, and Collections by masklinn on Wednesday November 19, 2014 @04:01PM (#8632594)
> 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.

Re:Rust, Lifetimes, and Collections by gliptic on Wednesday November 19, 2014 @01:37PM (#8631740)
You don't have to turn off subscript checking for simple loop iteration. As the article says, you're supposed to use .iter_mut() for this purpose where the unsafe code is isolated to library code.

The passage you quoted is about splitting a slice in two, not loop iteration. Bounds-check elimination can't solve this problem, and once again it's about unsafe code encapsulated in libraries. The function split_at_mut is perfectly safe to use in safe code.

Re:Rust, Lifetimes, and Collections by dbaupp on Wednesday November 19, 2014 @04:21PM (#8632689)
Rust uses an industrial strength optimiser (LLVM) and the analysis you list is all rather standard. As others have said, one usually doesn't need manual indexing in loops, and even if it is required, an obvious loop like that is quite transparent to the compiler.

In any case, it's an implementation detail of the compiler, not a language thing.

Re:Rust, Lifetimes, and Collections by haberman on Wednesday November 19, 2014 @01:33PM (#8631714)
> (Have to double space due to lack of formatting capabilities here.)

Indent by four spaces to get a <pre> tag:

    let mut v = vec![1i32, 2, 3, 4, 5];
    let vlen = v.len()
    for i in range(0, vlen) {
        let x = &mut v[i];

        // do some work with x
    }
> This seems to be a forgotten technology.

Given what I know about Rust, I strongly suspect that there is a way in Rust to iterate over a vector with only a single hoisted bounds-check. Hopefully other Rust people can chime in on what this is.

Re:Rust, Lifetimes, and Collections by veddan on Wednesday November 19, 2014 @01:47PM (#8631794)
In most cases, you use iterators rather than indexing

    for x in v.iter_mut() {
        // do some work with x
    }
or if you need the index

    for (i, x) in v.iter_mut().enumerate() {
        // do some work with x and i
    }
similar to Python's enumerate(). These loops never need to do any bounds-checking, even when compiling without optimization.

In this example the iteration count is a small compile-time constant (5), and the loop body is small, so when compiling with optimizations the loop will be unrolled.

Re:Rust, Lifetimes, and Collections by masklinn on Wednesday November 19, 2014 @04:02PM (#8632601)
> I strongly suspect that there is a way in Rust to iterate over a vector with only a single hoisted bounds-check. Hopefully other Rust people can chime in on what this is.

Iterators.