6 ms·

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 t

by 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...

Animats 10y ago
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: pub unsafe fn sgemm( m: usize, k: usize, n: usize, alpha: f32, a: *const f32, rsa: isize, csa: isize, b: *const f32, rsb: isize, csb: isize, beta: f32, c: *mut f32, rsc: isize, csc: isize) 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. [1] https://libraries.io/search?keywords=matrix&languages=Rust https://libraries.io/search?keywords=matrix&languages=Rust [2] https://docs.rs/crate/matrixmultiply/0.1.13/source/src/gemm.rs https://docs.rs/crate/matrixmultiply/0.1.13/source/src/gemm.... [3] https://github.com/bluss/rust-ndarray/blob/master/src/dimension/ndindex.rs https://github.com/bluss/rust-ndarray/blob/master/src/dimens... [4] https://github.com/indigits/scirust/blob/master/src/matrix/matrix.rs https://github.com/indigits/scirust/blob/master/src/matrix/m...
Animats 10y ago
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: pub struct Matrix { data: Vec<f64>, nrow: usize, ncol: usize } Access functions, get and set written in the obvious way: #[inline] pub fn get(&self, r: usize, c: usize) -> f64 { assert!(r < self.nrow); assert!(c < self.ncol); self.data[c + r * self.ncol] // index } #[inline] pub fn set(&mut self, r: usize, c: usize, v: f64) { assert!(r < self.nrow); assert!(c < self.ncol); self.data[c + r & self.ncol] = v; // set value } Matrix multiply, written in the obvious way: #[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.

by dbaupp 10y ago

Animats 10y ago

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: pub unsafe fn sgemm( m: usize, k: usize, n: usize, alpha: f32, a: *const f32, rsa: isize, csa: isize, b: *const f32, rsb: isize, csb: isize, beta: f32, c: *mut f32, rsc: isize, csc: isize) 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. [1] https://libraries.io/search?keywords=matrix&languages=Rust https://libraries.io/search?keywords=matrix&languages=Rust [2] https://docs.rs/crate/matrixmultiply/0.1.13/source/src/gemm.rs https://docs.rs/crate/matrixmultiply/0.1.13/source/src/gemm.... [3] https://github.com/bluss/rust-ndarray/blob/master/src/dimension/ndindex.rs https://github.com/bluss/rust-ndarray/blob/master/src/dimens... [4] https://github.com/indigits/scirust/blob/master/src/matrix/matrix.rs https://github.com/indigits/scirust/blob/master/src/matrix/m...

Animats 10y ago

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: pub struct Matrix { data: Vec<f64>, nrow: usize, ncol: usize } Access functions, get and set written in the obvious way: #[inline] pub fn get(&self, r: usize, c: usize) -> f64 { assert!(r < self.nrow); assert!(c < self.ncol); self.data[c + r * self.ncol] // index } #[inline] pub fn set(&mut self, r: usize, c: usize, v: f64) { assert!(r < self.nrow); assert!(c < self.ncol); self.data[c + r & self.ncol] = v; // set value } Matrix multiply, written in the obvious way: #[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.