4 ms·
Are there any more efficient ways to represent a dense multi-dimensional array than a one-dimensional array + index multiplication? Is there any difference betw
by nine_k 9y ago
Are there any more efficient ways to represent a dense multi-dimensional array than a one-dimensional array + index multiplication? Is there any difference between said multiplication done by some internal function inside the compiler, or by a regular (and trivial) function generated by a macro / template system?
- Animats 9y agoYes. And yes. One dimensional array + index multiplication doesn't make it clear to the compiler that the rows are disjoint. So the compiler can't assume there's no aliasing. It also probably can't strength-reduce the multiply to an add when advancing through an array in the "wrong" direction. FORTRAN compilers have been doing subscripting optimizations like that since 1956. After those optimizations, it may be possible to use some of the SSE instructions on x86.
- mamcx 9y agoI wonder how are FORTRAN arrays implemented. I was also assuming was a bing single arrays + indexes... If I wanna add this to a language, what I need to consider to be as FORTRAN?
- Animats 9y agoLook at the generated code for a matrix multiply in different languages. How tight is the inner loop?
- nine_k 9y agoThe whole idea of aliasing comes with C and arbitrary pointer arithmetics. It's not a necessity. In languages without it (beyond Fortran, Rust comes to mind), the compiler may assume the lack of aliasing and optimize accordingly. I wonder what JVM's JIT would come up with (likely not with SSE, though). I can agree that however you choose to represent a multi-dimensional array in RAM, giving the compiler some idea about them, or 2D matrices at least, could lead to some special optimizations.