3 ms·
Interestingly, Rust does not have the pointer aliasing hazard in the third example: the compiler ensures that all mutable array slices cannot overlap, unlike C,
by pcwalton 13y ago
Interestingly, Rust does not have the pointer aliasing hazard in the third example: the compiler ensures that all mutable array slices cannot overlap, unlike C, and so the introduction of the temporary should not be necessary. (Unfortunately we don't communicate that information to LLVM today, and we'd also have to optimize out the bounds checks, so more work is required...but from a language design perspective I think we're good.)
- joosters 13y agoThat is interesting... Can you point me to any information about Rust and how it avoids array aliasing? Is it because Rust disallows pointer manipulation with arrays? It's a shame that C prevents these optimisations by default. I suppose that a quick runtime check could see if the arrays overlapped and could then switch to the faster loop style, but the compiler would have to decide whether the loop was important enought to be worth generating the two code paths for.
- pcwalton 13y agoNo, Rust has pointer arithmetic, though it's bounds checked with slices. The restriction is that two mutable references cannot point to the same location. This is enforced by the borrow check: http://pcwalton.github.io/blog/2013/01/21/the-new-borrow-check-in-a-nutshell/ http://pcwalton.github.io/blog/2013/01/21/the-new-borrow-che...
- joosters 13y agoThanks!
- mcguire 13y agoAt compile time or run time?
- pcwalton 13y agoBounds checked at runtime (unless you use the unsafe sublanguage). Without dependent types (which I feel would exceed our complexity budget) we can't do much better. However, for simple iteration, if you use iterators idiomatically instead of C-style for loops then you won't incur any bounds checks.
- mcguire 13y agoI was just about to accuse you of dependent typing.
- dbaupp 13y agoHas anyone thought through how mut and &mut interact with each other in terms of aliasing (since they could definitely alias f(&mut x as mut u8, &mut x)), and also how this interacts with things like TLS and global variables?
- pcwalton 13y agoI'm not sure about your first example—the formatting seems messed up—but the second example is solved with dynamic borrow checking.
- dbaupp 13y agoOh, yes, HN replaced * with italics. I was talking about raw pointers, i.e. the second example is: f(&mut x as *mut u8, &mut x) and there is no dynamic borrowing checking for that. Would it become some form of undefined behaviour to have an *mut aliasing with an &mut?
- pcwalton 13y agoNah, I think we can handle it without undefined behavior by telling LLVM that `﹡mut` can alias anything. In effect, we would only tell LLVM that `&mut T` cannot alias `&mut T` if there is no `﹡mut T` in scope. Of course, if you transmute stuff into `&mut T`, then you'd better make sure that those two `&mut T`s don't overlap. But `﹡mut T` should be fine.
- sharpneli 13y agoC99 and later provide the restrict keyword which tells the compiler that the arrays do not overlap. It pretty much solves the whole issue.
- pcwalton 13y agoThat's true, although Rust provides for sound enforcement (so if you try to alias the equivalent of two restrict pointers the compiler will catch it at compile time). (It's also not technically in C++, although in practice it can be achieved through extensions.)
- pbsd 13y agoC++'s standard library has valarray, which is supposed to avoid aliasing effects, and is allowed to use expression templates and other tricks. Something like: float dot(std::valarray<float> const& x) { return (x*x).sum(); // Alternative: inner_product(begin(x), end(x), begin(x), 0.0f); } should, in theory, achieve the same kind of performance as the C version (but none of this is guaranteed, sadly). A smart implementation would actually end up calling BLAS routines, which is what libraries like Eigen do. Which reminds me: does Rust have infrastructure that would allow something like expression templates to exist?
- pcwalton 13y agoI believe you can use Rust traits to the same effect, although I haven't tried so you might hit stuff.
- noselasd 13y agoAnd before that, the alias issue in C compilers was one of the reasons why number crunching in Fortran could outperform C.