3 ms·

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,

• Animats 10y ago
  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. If all those optimizations really exist, why is there code like this (at https://github.com/SiegeLord/RustAlgebloat/blob/master/algebloat/src/matrix_mul.rs https://github.com/SiegeLord/RustAlgebloat/blob/master/algeb...)? 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. [1] http://llvm.org/docs/Passes.html http://llvm.org/docs/Passes.html
  • Manishearth 10y ago
    > 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.
  • dbaupp 10y ago
    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. > If all those optimizations really exist, why is there code like this (at https://github.com/SiegeLord/RustAlgebloat/blob/master/algeb... https://github.com/SiegeLord/RustAlgebloat/blob/master/algeb...)? 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. [0]: http://llvm.org/docs/doxygen/html/InductiveRangeCheckElimination_8cpp_source.html http://llvm.org/docs/doxygen/html/InductiveRangeCheckElimina...
  • cesarb 10y ago
    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/6a7bc47a8f1bf4441ca55e42aa50db6dda28181f 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.