Rust as a language is now realizing the benefits of borrow checking. As the article points out, the syntax doesn't have to distinguish between move and assign. The borrow checker will catch a reuse of something already moved away. This turns out to be effective enough in practice that the syntax distinction isn't necessary. That wasn't obvious up front.
Not having exceptions tends to generate workarounds which are uglier than having exceptions. Rust seems to be digging itself out of that hole successfully. Early error handling required extremely verbose code. The "try!()" thing was a hack, because a expression-valued macro that sometimes does an invisible external return is kind of strange. Any macro can potentially return, which is troublesome. The "?" operator looks cleaner; it's known to affect control flow, and it's part of the language, so you know it does that. Once "?" is in, it's probably bad form for an expression-valued macro to do a return.
There's still too much that has to be done with unsafe code. But the unsafe situations are starting to form patterns. Two known unsafe patterns are backpointers and partially initialized arrays. (The latter comes up with collections that can grow.) Those are situations where there's an invariant, and the invariant is momentarily broken, then restored. There's no way to talk about that in the language. Maybe there should be. More study of what really needs to be unsafe is needed.
> There's still too much that has to be done with unsafe code. But the unsafe situations are starting to form patterns.
I think as long as those patterns can be abstracted out and moved into thoroughly-vetted libraries with a safe interface, unsafe code isn't really a problem. I expect that getting Rust's standard libraries to a place where regular applications very rarely need to create their own unsafe code blocks is going to be a major long-term effort.
(Of course, if there were some simple language feature that would make some common use case of unsafe code blocks unnecessary, by all means we should do that as well.)
Is there something today that you're seeing that causes applications to use a lot of unsafe? In general, it should mostly be in library code, not application code.
No, but I'm pretty new to rust and haven't written enough code to know how often situations that call for unsafe code blocks come up.
(My current project I'm using to learn Rust is to port a ray-tracer I wrote in Haskell. I wouldn't expect functional-style code to require a lot of unsafe blocks and I haven't needed any yet, but who knows?)
I listed two things Rust doesn't handle well without unsafe code, doubly linked lists and multidimensional arrays. Here are examples of both from popular repositories with high download numbers:
Matrix math. "Unsafe" all over the place, and unsafeness is exported, allowing the caller to do unsafe things. This is an example of why I occasionally stress the need for multidimensional array support at the language level. If the compiler knew about multidimensional arrays, it could optimize the subscript checks for them, avoiding code such as this.
The unsafe version. The caller can store anywhere in memory.
fn unsafe_set_idx(&self, $mat: &T, v: f64)
{
let $self_ = self;
let (r, c) = $rc_expr;
unsafe
{ $mat.raw_set(r, c, v) }
}
Safe, but inefficient version. The compiler can't hoist those checks out of loops.
fn set_idx(&self, $mat: &T, v: f64)
{ let $self_ = self;
let (r, c) = $rc_expr;
assert!(r < $mat.nrow());
assert!(c < $mat.ncol());
unsafe
{ $mat.raw_set(r, c, v) }
}
This is the sort of thing that leads to exploits in code that reads things like JPEG files. Yet you can't do much better in Rust. That's why doing multidimensional arrays in macros and templates isn't good enough.
The multidimensional array thing has nothing to do with "Rust not handling multidimensional arrays without unsafe code".
It's a mistake in the library to export that as safe, yes (filed an issue). But that unsafe code being unsafe has nothing to do with multidimensional arrays. It has to do with arrays in general.
Implementing multidimensional arrays in the language would not change the fact that they would have `get_unchecked()` and `set_unchecked()` methods. The only thing that would change would be that you might have slightly nicer syntax for them, and "one way to do it". It doesn't change the scope for optimizations, either. Subscript checks do get optimized out in 1D arrays and they should get optimized out in this case too. The way indexing works for 1D arrays is basically exactly the same; there's a pair of methods for checked and unchecked; the subscript operator is specified to do checked indexing via an Index impl, and the optimizer usually gets rid of the checks. This would not change if indexing for the 1D array type was not implemented by the language itself.
Sometimes when the invariants aren't easily seen by the optimizer it won't get optimized out, and that's when folks use unchecked indexing.
Now, there is a problem here, and that is that unchecked indexing is an unsafe operation in Rust, whether with 1-D or 2-D arrays. Could be fixed with dependent types, but that's a lot of complexity and 99% of the cases where dependent types would work would have been optimized anyway.
But this has nothing whatsoever to do with multidimensional arrays, and would not be helped at all by multidimensional arrays being in the language.
The compiler already knows enough about multidimensional arrays to be able to optimize things. Rust supports multidimensional arrays in the language. It just doesn't have syntax sugar for it; and syntax sugar can't really affect optimization.
> it might be possible to break it by instantiating it on a type with unusual semantics.
Can you give an example? A lot of the semantics are well-encoded in the marker traits, so as long as you correctly specify the right Sized/Copy/Send/Sync bounds these problems should go away.
(Panic safety could be an issue if you were calling methods on T, but you're not)
Why do you still think the compiler can't host those out of loops? LLVM is perfectly capable of doing so in many cases and you've been told as much previously, could you make your claim more specific?
Where does LLVM do that? LLVM does hoist of invariant code out of loops in the Loop Invariant Code Motion and Loop Strength Reduction phases.[1] But that's not enough. This isn't an invariant situation. Consider a matrix multiply, the most common operation in number-crunching. You're indexing through three 2D matrices along both axes. The indices are usually controlled by FOR statements, so the compiler knows the range the indices can take. If the compiler knows about multidimensional arrays, it's easy to make those checks once at FOR loop entry.
But if those checks are in asserts, it's tougher. Is LLVM allowed to fail an assert early? If the array is 0..999, and the index is 0..1000, a subscript out of range condition will occur on iteration 1001. For best performance, you want to detect the subscript out of range condition at the point it becomes inevitable, rather than checking on every iteration and failing on iteration 1001. (Although technically you could generate a special case.)
But that requires special treatment of "assert". In Rust, "assert!" is just a macro. The compiler can't optimize it that aggressively and fail early. Especially since you can now catch assertion failures during unwinding.
MatrixMul<LHS, RHS>
{ unsafe fn raw_get(&self, r: usize, c: usize) -> f64
{ let mut ret = 0.0;
for z in 0..self.lhs.ncol()
{ ret += self.lhs.raw_get(r, z) * self.rhs.raw_get(z, c); }
ret
}
}
If what you say is true, all that unsafe stuff is unnecessary.
In this example, the loop bound is from the lhs, so llvm can prove that it will never get out of bounds and elide the bound checks. But llvm can't be sure that the rhs has the same size, so it can't elide the bound checks for the rhs.
However, there's a trick. Take a look at https://github.com/rust-lang/rust/commit/6a7bc47a8f1bf4441ca... where the Rust developers had the same issue, and managed to avoid the bound checks without having to use unsafe code. You have to somehow make the optimizer see that both sides have the same length, so it'll elide both bounds checks. A slice is actually a pair of a pointer to the first element, and the length. Their trick copies the length from one slice to the other (after a bound check, obviously), so the compiler is sure that the lengths are the same.
> If the compiler knows about multidimensional arrays, it's easy to make those checks once at FOR loop entry.
Or you could just use a little unsafe code to implement iterators and matrix multiplication on top of the array, and then never use unsafe with the matrices anyway. This is what gets done with regular arrays and vectors. Directly indexing these types is pretty rare. You would do the same with matrices. "Put it in the language" is not a solution for everything, especially when the tools are there to build it with almost the same level of ergonomics.
Requiring unsafe for designing some kinds of abstractions is not a bad thing. There's no need to shove everything into the language if it can be implemented as a library with a smattering of unsafe code.
It's almost equivalent, really. Making a mistake when writing this unsafe code and making a mistake in the builtin optimization are mostly equivalent risks. There's nothing inherently worse about doing it as a library, aside from the minor issue that the indexing syntax isn't so great.
LICM is very relevant: it allows hoisting various dimensions of the check up to the loop with the relevant induction variable, meaning LLVM only has to handle things of the pattern:
for i in 0..X {
if !(i < X) { panic!() }
...
}
It is capable of doing this with the various induction variable passes it has, showing that i < X is always true.
There's also the IRCE (inductive range check elimination) [0] pass—which isn't listed in that document—that should help even more, if/when it is enabled.
Hopefully you agree at this point that LLVM is perfectly capable of handling multidimensional arrays and matrices even if it doesn't have optimisation passes with names that obviously apply to them specifically. Most of the optimisations you keep talking about are basic consequences of other standard passes, a fact that has been pointed out many times to you before.
> Consider a matrix multiply, the most common operation in number-crunching
Also an operation you won't be implementing manually if you actually care about performance (better implementation: call a BLAS library). And, any high performance implementation will be doing more than the naive triple-nested loop (blocking, SIMD, etc.). Focusing on this operation is somewhat missing the forest for the trees.
> You're indexing through three 2D matrices along both axes. The indices are usually controlled by FOR statements, so the compiler knows the range the indices can take.
Yes exactly, the compiler knows the range of the indices.
> If the compiler knows about multidimensional arrays, it's easy to make those checks once at FOR loop entry.
This is a non-sequitur: the compiler can still make/move the checks based on what the code looks like, without having to have a hardcoded concept of arrays. Ensuring optimisation passes are powerful enough to handle these sort of relatively straight-forward cases is more general than relying on a language-level concept of multidimensional arrays, as it allows them to apply to cases which can't quite be implemented with an array directly.
> Although technically you could generate a special case
This is exactly what compilers do, see the IRCE documentation.
> The compiler can't optimize it that aggressively and fail early
It certainly can: these sort of assertions shouldn't ever trigger, and with appropriate top level assertions (e.g. asserting that the dimensions of the incoming matrices work for multiplication) the compiler can easily see this. Also, the compiler can hoist assertions early if this cannot be observed externally, e.g. the loop kernel only mutates locals.
That code is almost 2 years old, and so the compiler will have improved since then. Of course, the compiler may not have improved enough (e.g. IRCE still may not be enabled). Additionally, there's a lot of uncertainity/lack of clarity (as demonstrated by your own comments) about exactly what the compiler can do, and so people may use `unsafe` unnecessarily. I've certainly been guilty of this myself, and been glad when people have pushed back in code-review, making me work a bit harder to get equal (or better) performance in safe code.
Here's what the current Rust compiler actually does. Optimization level 3, checking enabled. The question is whether the Rust compiler can optimize out all the checks for a simple matrix multiply without loss of safety.
Rust doesn't know about multidimensional arrays, so they have to be supported in a library. This matrix representation was extracted from the "algebloat" crate:
#[inline]
pub fn mult(&self, other: &Matrix, result: &mut Matrix)
{ assert!(self.ncol == result.ncol); // out of the loop checks
assert!(self.nrow == result.nrow);
assert!(self.ncol == other.nrow);
assert!(self.nrow == other.ncol);
for r in 0..self.nrow
{ for c in 0..self.ncol
{ let mut tot = 0.0;
for rr in 0..self.nrow
{ tot += self.get(rr,c) * other.get(r,rr); }
result.set(r, c, tot);
}
}
}
Generated code for the inner loop:
///
/// mult - matrix multiply, straightforward approach
///
#[inline]
pub fn mult(&self, other: &Matrix, result: &mut Matrix)
{ assert!(self.ncol == result.ncol); // out of the loop checks
assert!(self.nrow == result.nrow);
assert!(self.ncol == other.nrow);
assert!(self.nrow == other.ncol);
for r in 0..self.nrow
{ for c in 0..self.ncol
{ let mut tot = 0.0;
for rr in 0..self.nrow
{ tot += self.get(rr,c) * other.get(r,rr); }
result.set(r, c, tot);
}
}
}
Generated code for the inner loop. "rustc 1.14.0", optimization level "opt-level = 3", AMD64 instruction set. Debug mode, so asserts should be checked. (Not sure about this; it is
possible that opt-level=3, "Aggressive" disables some checking. Documentation is unclear on this.)
.LBB8_50:
.Ltmp254: ; in Matrix::get()
.loc 1 122 0 ; self.data[c + r * self.ncol]
movq %rdi, %rax
mulq %r11 ; doing the multiply for the subscript every time
jo .LBB8_74 ; and checking it for overflow
addq %rsi, %rax ; doing the add. No strength reduction
jb .LBB8_76 ; another check
.Ltmp255:
.loc 17 1362 0
cmpq %rax, %r9
jbe .LBB8_72 ; and another check
.Ltmp256:
.loc 17 1362 0 is_stmt 0
cmpq %rcx, %r15
jbe .LBB8_78 ; array overflow check
.Ltmp257:
.loc 1 188 0 is_stmt 1
incq %rdi
.Ltmp258:
.loc 1 122 0
movsd (%r12,%rax,8), %xmm1
.Ltmp259:
.loc 1 147 0
mulsd (%rbx,%rcx,8), %xmm1 ; The real work: floating multiply
addsd %xmm1, %xmm0 ; and the add
.Ltmp260:
.loc 18 746 0
incq %rcx
cmpq %r14, %rdi
jb .LBB8_50 ; loop counter check - required
This is relatively decent code. the compiler got rid of multiple checks on the same values. There was some strength reduction of indices, too; only the subscript that's traversing the "wrong way" generated a multiply. The ones that are advancing one element at a time along the underlying vector are just adds. About five instructions could come out, but it's not bad code.
I've seen FORTRAN compilers do this kind of matrix multiply with a five instruction inner loop on a mainframe, incrementing pointers in registers for both dimensions. That's the advantage of multidimensional array support.
The point I made about multidimensional arrays stands - the compiler didn't strength reduce the multiply and eliminate the rest of the checks. That requires inferring too much from the user's code.
On the other hand, the code is good enough that using "unsafe" for performance reasons is very seldom justified.
I started writing a test case, and discovered that crate "algebloat" won't even compile on stable rust 1.14.0. (It uses features "rustc_private" and "test".) It looks like this crate was never finished.
This is the other problem with not having built-in multidimensional arrays. There are so many implementations to choose from. Here's the list of all 34 Rust matrix math packages.[1]
Looking at crate "matrixmultiply", it's all unsafe code.[2] That's because it's C written in Rust:
Arrays? What arrays? Raw pointers are good enough, right? What could possibly go wrong?
Still trying to find a package with a matrix multiply in safe Rust code with the subscript checks optimized out.
Update: checked crate "ndarray". Indexing is unsafe.[3]
Update: checked crate "matrices". Empty project.
Update: Checked "scirust" - more raw pointer manipulation.[4]
Not finding real-world matrix libraries in which all those fantastic checking optimizations are used and working. I'd like to see that stuff in action.
Cool, just wondering. In general, unsafe code should be encapsulated, to isolate its possible effects, and once you've got it isolated, it's easy to break that bit out in a library.
From poking around in Rust for ~1 year my common ones are uninitialized arrays for scratch buffers(> 1Kb) and FFI(obviously).
Like you said all the other cases are nicely wrapped into a library but I'm not quite sure how you'd abstract the first one above. It's small enough to do the unsafe block inline that it's not annoying but definitely shows up(esp when you hit APIs that are copy of C interfaces).
Depends on what you're doing; see https://crates.io/crates/init_with as one example. It's not the exact same thing, and yeah, I would argue that's one area where it's okay to not totally abstract it. Rules are meant to be broken. (I was thinking about removing bounds checks with get_unchecked as well).
What I worry about is those "thoroughly-vetted libraries" is that the use of those will likely follow a power law distribution in terms of code dependent upon them. When that happens, a disproportionately-high amount of code will depend upon those libraries. So when a defect (or vulnerability) shows up in one of them, a disproportionately-high amount of code will become vulnerable.
Reducing this unsafe surface area should result in outsized gains overall. I'm not familiar with the unsafe patterns, and to what extent they could be addressed/reduced through Rust language/compiler design, but that'd be one area where research focus might produce even more benefit.
The other weak point may be the LLVM itself, which I guess would be sort of a background hum of risk to Rust.
Outsider view: not sure of the relative levels of risk in each layer, and to what extent they can be addressed.
Can (or will) these unsafe patterns be capable of being addressed by future changes in Rust?
> Rust as a language is now realizing the benefits of borrow checking. As the article points out, the syntax doesn't have to distinguish between move and assign. The borrow checker will catch a reuse of something already moved away. This turns out to be effective enough in practice that the syntax distinction isn't necessary. That wasn't obvious up front.
Could you say a bit more about what you mean by "now"? You write like it's a recent realisation but (as linked in the parent article) it was "discovered"/described/promoted more than 4 years ago: http://smallcultfollowing.com/babysteps/blog/2012/10/01/move... .
---
Are your other two paragraphs related to the article, or are they just your general observations about Rust?
The "implicitly copyable" problem is amusing. That was dealt with by Wirth in Modula 1 with the rule "if the programmer can't tell, it's up to the compiler". Thus, non-writable objects could be passed either by reference or by copy, depending on object size. This was up to the compiler. The usual rule was that anything up to 2 words in size was copied. Since the called function couldn't change the value, it didn't matter.
This avoids philosophical gyrations. You want a rule that says you can copy ints and floats, for performance reasons. Trying to reach that via type theory makes it harder. It's an optimization.
We tried making copy/move an optimization. The number of useless copies that ended up in the resulting code was absurd. You think compile times are bad now…
The other way round. Sometimes you want to convert non-mutable references to non-mutable copies. This is almost always a win for int, float, etc., and usually a win for anything up to 8 bits on a modern processor.
Fortunately there's no need to have read all of the (very interesting) archives of Niko's blog in this case, as the parent article linked to that post in the relevant section too.
Not having exceptions tends to generate workarounds which are uglier than having exceptions. Rust seems to be digging itself out of that hole successfully. Early error handling required extremely verbose code. The "try!()" thing was a hack, because a expression-valued macro that sometimes does an invisible external return is kind of strange. Any macro can potentially return, which is troublesome. The "?" operator looks cleaner; it's known to affect control flow, and it's part of the language, so you know it does that. Once "?" is in, it's probably bad form for an expression-valued macro to do a return.
There's still too much that has to be done with unsafe code. But the unsafe situations are starting to form patterns. Two known unsafe patterns are backpointers and partially initialized arrays. (The latter comes up with collections that can grow.) Those are situations where there's an invariant, and the invariant is momentarily broken, then restored. There's no way to talk about that in the language. Maybe there should be. More study of what really needs to be unsafe is needed.